3 ms·

As the algorithm used in the example is straight-forward I figured that using UNIX command line tools might be an even simpler way to implement it. Here is what

As the algorithm used in the example is straight-forward I figured that using UNIX command line tools might be an even simpler way to implement it. Here is what I came up with: time cat kjvbible_x100.txt | tr "[:upper:] " "[:lower:]\n" | sort --buffer-size=50M | uniq -c | sort -hr > /dev/null On my machine this turned out to be ~5 times slower than the provided Python implementation. Nearly all of the time is spent in the first invocation of `sort`. Further increasing the buffer size doesn't make a significant difference. I also played around with the number of threads `sort` uses, but didn't see any improvement there either. I'm quite puzzled why `sort is so much slower, especially as it does sorting in parallel utilizing multiple CPU cores, while the Python implementation is single-threaded. Does somebody have an explanation for that?

benhoyt 4y ago
It's because that first invocation of sort is sorting the entire input (413MB), not just the unique words (less than a MB). The sort is probably O(NlogN), but that's a big N. Counting by inserting into a hash table is much faster, at O(N).
aljarry 4y ago
It looks like you're sorting the whole file, while python implementation sorts only unique values.
mastax 4y ago
`sort | uniq` is really slow for this, as it has to sort the entire input first. I use `huniq` which is way faster for this. I'm sure there are many similar options. https://github.com/koraa/huniq https://github.com/koraa/huniq
zackmorris 4y ago
Dangit, I'm supposed to be doing yardwork today so you hijacked my procrastination motivation haha! Edit: I had no idea that awk was so fast, and I suspect that only parallelization would beat it. but I agree with the others that the main bottleneck is the `sort | uniq` for results1.txt # https://stackoverflow.com/a/27986512 # count word occurrences # https://unix.stackexchange.com/a/205854 # trim surrounding whitespace # https://linuxhint.com/awk_trim_whitespace/ # trim leading or trailing whitespace time cat kjvbible_x100.txt | tr "[:upper:] " "[:lower:]\n" | sort --buffer-size=50M | uniq -c | sort -hr > results1.txt real 0m13.852s user 0m13.836s sys 0m0.229s time cat kjvbible_x100.txt | tr "[:upper:] " "[:lower:]\n" | awk '{count[$1]++} END {for (word in count) print count[word], word}' | sort -hr > results2.txt real 0m1.425s user 0m2.243s sys 0m0.061s diff results1.txt results2.txt 109,39133c109,39133 # many whitespace differences due to how `uniq -c` left-pads first column with space diff <(cat results1.txt | awk '{$1=$1};1') <(cat results2.txt | awk '{$1=$1};1') # bash-only due to <() inline file, no differences after trimming surrounding whitespace cat results1.txt | awk '{ sub(/^[ \t]+/, ""); print }' | diff - results2.txt # sh-compatible, no differences after trimming leading whitespace of results1.txt # 13.836 / 2.243 = ~6x speedup with awk
- TristanBall 4y ago
  I don't understand how you're getting <2s for that awk result. I'm testing on slightly older hardware, for example I get 4.6s and 11.9s for the optimized and simple go versions taken from the git repo. But when I also get: # time cat kjvbible_x100.txt | tr "[:upper:] " "[:lower:]\n" | awk '{count[$1]++} END {for (word in count) print count[word], word}' | sort -hr > results2.txt real 0m23.174s user 0m23.309s sys 0m1.234s So my result is 10x slower than yours. What are you running this on and where do I get one?
  - zackmorris 4y ago
    Oh gosh, sorry to burst your bubble but it's a 2011 Mac Mini :-P 2.3 GHz Intel Core i5 8 GB 1333 MHz DDR3 Intel HD Graphics 3000 512 MB macOS High Sierra 10.13.6 (17G14042) 512 GB PLEXTOR PX-512M5Pro SSD (Get Info says I installed it July 2, 2011 but it might be a clone of another drive) <rant> I really like it, but will probably have to sell it because it has various software failures, like sometimes one of my displays won't turn on or goes black and I have to restart. That bug seems to be fixed on newer macOSs like the one on an Intel MacBook Pro I use for work, but Apple artificially sunsets their hardware by preventing newer versions of macOS from being installed and not back-porting bug fixes to previous macOSs. Since pretty much all computers today are Turing-complete, that feels.. disingenuous. Computers haven't gotten appreciably faster for roughly 15 years since R&D funding shifted to mobile in 2007 and Moore's Law ended. All that matters today is whether we are using an SSD and how wide the memory bus is, since speed there hasn't changed much either, just latency. And Apple's not the only one treading water. PCs often suffer from mismatched hardware, so maybe an Intel i9 gets installed on a logic board with a memory bus too slow to recruit it. I built a gaming PC a few years back and I may have inadvertently underpowered it by putting most of the budget into the RTX 2070. Since video cards can't do the everyday workloads we're discussing, I mostly consider them a waste of time and mourn what might have been had CPUs kept improving instead. Apple's Arm M1 is a logical progression off of Intel, but I can't really endorse it, since they chose a relatively complex architecture where a big dumb array of cores would have been more scalable. If some indie brand comes along and builds one of the 1000+ core CPUs I've blabbered on about, I can't say that I'll have much sympathy for the current big players. Due to all of that, I perceived computers in 2010 as being roughly 1000 times slower than they could/should be had they kept up with Moore's Law, and computers in 2020 as being roughly 1000000 times slower (the ratio of GPU to CPU FLOPs for example). It doesn't help that stuff like Spotlight and Safari eagerly take 100+% CPU or that basically all PCs are bogged down with either spyware or the daemons that supposedly find and remove spyware (thank you M$). Or that we don't have the network computing that Sparc had in the 1990s, where all of the computers on the LAN were available for additional cores seamlessly. Just slow on top of slow on top of slow under surveillance capitalism yay! </rant>

benhoyt 4y ago

It's because that first invocation of sort is sorting the entire input (413MB), not just the unique words (less than a MB). The sort is probably O(NlogN), but that's a big N. Counting by inserting into a hash table is much faster, at O(N).

aljarry 4y ago

It looks like you're sorting the whole file, while python implementation sorts only unique values.

mastax 4y ago

`sort | uniq` is really slow for this, as it has to sort the entire input first. I use `huniq` which is way faster for this. I'm sure there are many similar options. https://github.com/koraa/huniq https://github.com/koraa/huniq

zackmorris 4y ago

Dangit, I'm supposed to be doing yardwork today so you hijacked my procrastination motivation haha! Edit: I had no idea that awk was so fast, and I suspect that only parallelization would beat it. but I agree with the others that the main bottleneck is the `sort | uniq` for results1.txt # https://stackoverflow.com/a/27986512 # count word occurrences # https://unix.stackexchange.com/a/205854 # trim surrounding whitespace # https://linuxhint.com/awk_trim_whitespace/ # trim leading or trailing whitespace time cat kjvbible_x100.txt | tr "[:upper:] " "[:lower:]\n" | sort --buffer-size=50M | uniq -c | sort -hr > results1.txt real 0m13.852s user 0m13.836s sys 0m0.229s time cat kjvbible_x100.txt | tr "[:upper:] " "[:lower:]\n" | awk '{count[$1]++} END {for (word in count) print count[word], word}' | sort -hr > results2.txt real 0m1.425s user 0m2.243s sys 0m0.061s diff results1.txt results2.txt 109,39133c109,39133 # many whitespace differences due to how `uniq -c` left-pads first column with space diff <(cat results1.txt | awk '{$1=$1};1') <(cat results2.txt | awk '{$1=$1};1') # bash-only due to <() inline file, no differences after trimming surrounding whitespace cat results1.txt | awk '{ sub(/^[ \t]+/, ""); print }' | diff - results2.txt # sh-compatible, no differences after trimming leading whitespace of results1.txt # 13.836 / 2.243 = ~6x speedup with awk

TristanBall 4y ago
I don't understand how you're getting <2s for that awk result. I'm testing on slightly older hardware, for example I get 4.6s and 11.9s for the optimized and simple go versions taken from the git repo. But when I also get: # time cat kjvbible_x100.txt | tr "[:upper:] " "[:lower:]\n" | awk '{count[$1]++} END {for (word in count) print count[word], word}' | sort -hr > results2.txt real 0m23.174s user 0m23.309s sys 0m1.234s So my result is 10x slower than yours. What are you running this on and where do I get one?
- zackmorris 4y ago
  Oh gosh, sorry to burst your bubble but it's a 2011 Mac Mini :-P 2.3 GHz Intel Core i5 8 GB 1333 MHz DDR3 Intel HD Graphics 3000 512 MB macOS High Sierra 10.13.6 (17G14042) 512 GB PLEXTOR PX-512M5Pro SSD (Get Info says I installed it July 2, 2011 but it might be a clone of another drive) <rant> I really like it, but will probably have to sell it because it has various software failures, like sometimes one of my displays won't turn on or goes black and I have to restart. That bug seems to be fixed on newer macOSs like the one on an Intel MacBook Pro I use for work, but Apple artificially sunsets their hardware by preventing newer versions of macOS from being installed and not back-porting bug fixes to previous macOSs. Since pretty much all computers today are Turing-complete, that feels.. disingenuous. Computers haven't gotten appreciably faster for roughly 15 years since R&D funding shifted to mobile in 2007 and Moore's Law ended. All that matters today is whether we are using an SSD and how wide the memory bus is, since speed there hasn't changed much either, just latency. And Apple's not the only one treading water. PCs often suffer from mismatched hardware, so maybe an Intel i9 gets installed on a logic board with a memory bus too slow to recruit it. I built a gaming PC a few years back and I may have inadvertently underpowered it by putting most of the budget into the RTX 2070. Since video cards can't do the everyday workloads we're discussing, I mostly consider them a waste of time and mourn what might have been had CPUs kept improving instead. Apple's Arm M1 is a logical progression off of Intel, but I can't really endorse it, since they chose a relatively complex architecture where a big dumb array of cores would have been more scalable. If some indie brand comes along and builds one of the 1000+ core CPUs I've blabbered on about, I can't say that I'll have much sympathy for the current big players. Due to all of that, I perceived computers in 2010 as being roughly 1000 times slower than they could/should be had they kept up with Moore's Law, and computers in 2020 as being roughly 1000000 times slower (the ratio of GPU to CPU FLOPs for example). It doesn't help that stuff like Spotlight and Safari eagerly take 100+% CPU or that basically all PCs are bogged down with either spyware or the daemons that supposedly find and remove spyware (thank you M$). Or that we don't have the network computing that Sparc had in the 1990s, where all of the computers on the LAN were available for additional cores seamlessly. Just slow on top of slow on top of slow under surveillance capitalism yay! </rant>