5 ms·

> I haven’t shown an optimized Python version because it’s hard to optimize Python much further! (I got the time down from 8.4 to 7.5 seconds). It’s as fast as

> I haven’t shown an optimized Python version because it’s hard to optimize Python much further! (I got the time down from 8.4 to 7.5 seconds). It’s as fast as it is because the core operations are happening in C code – that’s why it so often doesn’t matter that “Python is slow”. An obvious optimization would be to utilize all available CPU cores by using the MapReduce pattern with multiple threads. I believe that'd be necessary for a fair conclusion anyway, as you can't claim that I/O isn't the bottleneck, without utilizing all of the available CPU and memory resources.

deleted 4y ago
[deleted]
plonk 4y ago
> An obvious optimization would be to utilize all available CPU cores by using the MapReduce pattern with multiple threads. Nope, the GIL will make that useless. You need to actually implement the tight loops in C/C++ and call that with batches of data to get benefits from threading. An obvious, but more expensive optimization would be to use a process pool. Make sure that all the objects you pass around are serializable. Python makes optimization much harder than it should be. I hope the GIL gets the hammer at some point, but that seems to be a huge task.
- Waterluvian 4y ago
  You can use Processpool but at that point you’re way into re-architecting.
  - plonk 4y ago
    Not much more than the switch to MapReduce and threads. Actually the interface is exactly the same if you use executors from concurrent.futures.
  - znpy 4y ago
    inter-process communication has its own overhead though.
    - plonk 4y ago
      You can usually counteract that by sending large enough batches to the processes.
- Dunedan 4y ago
  > Nope, the GIL will make that useless. In Python yes. I missed that. The Go implementation would still benefit from multiple threads, wouldn't it?
  - plonk 4y ago
    Yes I think so.
- ShredKazoo 4y ago
  The GIL won't prevent you from parallelizing I/O will it?
  - plonk 4y ago
    If I/O was the bottleneck, parallelizing it won't help, your SSD/network link/database won't get magically faster. If I/O wasn't the bottleneck, I guess you can parallelize reading, but what are you gaining? If you're writing to files, most of the time the parallism will be hard to implement correctly. SQLite doesn't support parallel writes for example.
    - ShredKazoo 4y ago
      >If I/O was the bottleneck, parallelizing it won't help, your SSD/network link/database won't get magically faster. I think your SSD/network link/database might be able to work in parallel even when Python can't. Details: Suppose I am scraping a website using a breadth-first approach. I have a long queue of pages to scrape. A single-threaded scraper looks like: pop the next page in the queue, block until the web server returns that page, repeat. A multi-threaded scraper looks like: thread wakes up, pops the next page in the queue, sleeps until the web server returns that page, repeat. With the multi-threaded scraper I can initiate additional downloads while the thread sleeps. My assumption here is that the download over the network is at some level being performed by making a system call (how could it not be?) And once you have multiple system calls going, they can be as parallel as the OS permits them to be; the OS doesn't have to worry about the GIL. And also the server should be able to serve requests in parallel (assuming for the sake of argument that the server doesn't suffer from the GIL). Same essential argument applies to the database. Suppose I'm communicating with the database using IPC. The database isn't written in Python and doesn't suffer from the GIL. Multiple Python threads can be sleeping on the database while the database processes their requests, possibly in parallel if the db supports that. I think this argument could even work for the SSD if the kernel is able to batch your requests in a way that takes advantage of the hardware, according to this person: https://news.ycombinator.com/item?id=33752411 https://news.ycombinator.com/item?id=33752411 Very curious to hear your thoughts here. Essentially my argument is that the SSD/network link/database could be a "bottleneck" in terms of latency without being the bottleneck in terms of throughput (i.e. it has unused parallel capacity even though it's operating at maximum speed).
- xmcqdpt2 4y ago
  For this problem the multiple process version would be quite simple in python or any other languages. It's a classic same program multiple data (SPMD) task. You split the file into N chunks than run N versions of the original program on it (a Map). You then need to collate the results, which required a second program, but that step is similar to the sorting step in the original and so would be negligible wrt wall time (a quick Reduce). For large files you should get almost embarrassing parallelism.
  - jvanderbot 4y ago
    Oh I think a few simd instructions could reduce processing to near zero without going crazy with multi-threaded architectures. Remember that fizzbuzz on HN that hit GB/s? Mostly SIMD. Zero multi-threaded IIRC.
superjan 4y ago
That is of course an easy solution but I would argue that this is just throwing more resources at the problem. Not a very impressive optimization. Emery Berger has a great talk [1] where he argues that it is mostly pointless to optimize python code, if your program is slow, you should look for a properly optimized library to do that work for you. 1: https://www.youtube.com/watch?v=vVUnCXKuNOg https://www.youtube.com/watch?v=vVUnCXKuNOg
- Dunedan 4y ago
  > That is of course an easy solution but I would argue that this is just throwing more resources at the problem. Not a very impressive optimization. You could say the same about the existing implementation as that reads the whole file into memory instead of processing it in chunks.
masklinn 4y ago
A more obvious optimisation (to me) would be to leverage the native functions and avoid creating a list of ~80 million strings in memory. On my machine, the base script pretty reliably takes ~10s: Reading : 0.1935129165649414 Processing: 9.955206871032715 Sorting : 0.0067043304443359375 Outputting: 0.01335597038269043 TOTAL : 10.168780088424683 Switching content to a no-op (`content = sys.stdin`) and feeding `Counter` from a native iterators pipeline: counts = collections.Counter(chain.from_iterable(map(str.split, map(str.lower, content)))) is a pretty reliable 10% gain: Reading : 1.1920928955078125e-06 Processing: 8.863707780838013 Sorting : 0.004117012023925781 Outputting: 0.012418985366821289 TOTAL : 8.880244970321655 As far as I can tell, the bottleneck is about half the preprocessing (lowercasing and splitting) and half filling the Counter. You won't get a 10x gain out of that though.
ummonk 4y ago
Or better yet, write a compute shader since hashing is an embarrassingly parallel operation. That said, the OP's article is correct in that straightforward idiomatic implementations of this algorithm are very much compute bound. The corollary is that eng work put into optimizing compute usage often won't be waisted for programs processing disk data (or even network data with modern 10Gb fiber connections).

deleted 4y ago

[deleted]

plonk 4y ago

> An obvious optimization would be to utilize all available CPU cores by using the MapReduce pattern with multiple threads. Nope, the GIL will make that useless. You need to actually implement the tight loops in C/C++ and call that with batches of data to get benefits from threading. An obvious, but more expensive optimization would be to use a process pool. Make sure that all the objects you pass around are serializable. Python makes optimization much harder than it should be. I hope the GIL gets the hammer at some point, but that seems to be a huge task.

Waterluvian 4y ago
You can use Processpool but at that point you’re way into re-architecting.
- plonk 4y ago
  Not much more than the switch to MapReduce and threads. Actually the interface is exactly the same if you use executors from concurrent.futures.
- znpy 4y ago
  inter-process communication has its own overhead though.
  - plonk 4y ago
    You can usually counteract that by sending large enough batches to the processes.
Dunedan 4y ago
> Nope, the GIL will make that useless. In Python yes. I missed that. The Go implementation would still benefit from multiple threads, wouldn't it?
- plonk 4y ago
  Yes I think so.
ShredKazoo 4y ago
The GIL won't prevent you from parallelizing I/O will it?
- plonk 4y ago
  If I/O was the bottleneck, parallelizing it won't help, your SSD/network link/database won't get magically faster. If I/O wasn't the bottleneck, I guess you can parallelize reading, but what are you gaining? If you're writing to files, most of the time the parallism will be hard to implement correctly. SQLite doesn't support parallel writes for example.
  - ShredKazoo 4y ago
    >If I/O was the bottleneck, parallelizing it won't help, your SSD/network link/database won't get magically faster. I think your SSD/network link/database might be able to work in parallel even when Python can't. Details: Suppose I am scraping a website using a breadth-first approach. I have a long queue of pages to scrape. A single-threaded scraper looks like: pop the next page in the queue, block until the web server returns that page, repeat. A multi-threaded scraper looks like: thread wakes up, pops the next page in the queue, sleeps until the web server returns that page, repeat. With the multi-threaded scraper I can initiate additional downloads while the thread sleeps. My assumption here is that the download over the network is at some level being performed by making a system call (how could it not be?) And once you have multiple system calls going, they can be as parallel as the OS permits them to be; the OS doesn't have to worry about the GIL. And also the server should be able to serve requests in parallel (assuming for the sake of argument that the server doesn't suffer from the GIL). Same essential argument applies to the database. Suppose I'm communicating with the database using IPC. The database isn't written in Python and doesn't suffer from the GIL. Multiple Python threads can be sleeping on the database while the database processes their requests, possibly in parallel if the db supports that. I think this argument could even work for the SSD if the kernel is able to batch your requests in a way that takes advantage of the hardware, according to this person: https://news.ycombinator.com/item?id=33752411 https://news.ycombinator.com/item?id=33752411 Very curious to hear your thoughts here. Essentially my argument is that the SSD/network link/database could be a "bottleneck" in terms of latency without being the bottleneck in terms of throughput (i.e. it has unused parallel capacity even though it's operating at maximum speed).
xmcqdpt2 4y ago
For this problem the multiple process version would be quite simple in python or any other languages. It's a classic same program multiple data (SPMD) task. You split the file into N chunks than run N versions of the original program on it (a Map). You then need to collate the results, which required a second program, but that step is similar to the sorting step in the original and so would be negligible wrt wall time (a quick Reduce). For large files you should get almost embarrassing parallelism.
- jvanderbot 4y ago
  Oh I think a few simd instructions could reduce processing to near zero without going crazy with multi-threaded architectures. Remember that fizzbuzz on HN that hit GB/s? Mostly SIMD. Zero multi-threaded IIRC.

superjan 4y ago

That is of course an easy solution but I would argue that this is just throwing more resources at the problem. Not a very impressive optimization. Emery Berger has a great talk [1] where he argues that it is mostly pointless to optimize python code, if your program is slow, you should look for a properly optimized library to do that work for you. 1: https://www.youtube.com/watch?v=vVUnCXKuNOg https://www.youtube.com/watch?v=vVUnCXKuNOg

Dunedan 4y ago
> That is of course an easy solution but I would argue that this is just throwing more resources at the problem. Not a very impressive optimization. You could say the same about the existing implementation as that reads the whole file into memory instead of processing it in chunks.

masklinn 4y ago

A more obvious optimisation (to me) would be to leverage the native functions and avoid creating a list of ~80 million strings in memory. On my machine, the base script pretty reliably takes ~10s: Reading : 0.1935129165649414 Processing: 9.955206871032715 Sorting : 0.0067043304443359375 Outputting: 0.01335597038269043 TOTAL : 10.168780088424683 Switching content to a no-op (`content = sys.stdin`) and feeding `Counter` from a native iterators pipeline: counts = collections.Counter(chain.from_iterable(map(str.split, map(str.lower, content)))) is a pretty reliable 10% gain: Reading : 1.1920928955078125e-06 Processing: 8.863707780838013 Sorting : 0.004117012023925781 Outputting: 0.012418985366821289 TOTAL : 8.880244970321655 As far as I can tell, the bottleneck is about half the preprocessing (lowercasing and splitting) and half filling the Counter. You won't get a 10x gain out of that though.

ummonk 4y ago

Or better yet, write a compute shader since hashing is an embarrassingly parallel operation. That said, the OP's article is correct in that straightforward idiomatic implementations of this algorithm are very much compute bound. The corollary is that eng work put into optimizing compute usage often won't be waisted for programs processing disk data (or even network data with modern 10Gb fiber connections).