8 ms·

The title I/O is _no longer_ the bottleneck seems to suggest disk speed has caught up, while in reality the slowness is due to poor implementation (slow Python

The title I/O is _no longer_ the bottleneck seems to suggest disk speed has caught up, while in reality the slowness is due to poor implementation (slow Python or Go with lots of allocations). The real problem to me is that languages are too high-level and hiding temporary allocations too much. If you had to write this in C, you would naturally avoid unnecessary allocations, cause alloc / free in the hot loop looks bad. Presumably soon enough it's very unlikely you find any new word (actually it's 10 passes over the same text) and most keys exist in the hashmap, so it would be doing a lookup and incrementing a counter, which should not require allocations. Edit: OK, I've ran OP's optimize C-version [1] and indeed, it only hits 270MB/s. So, OP's point remains valid. Perf tells me that 23% of all cache refs are misses, so I wonder if it can be optimized to group counters of common words together. [1] https://benhoyt.com/writings/count-words/ https://benhoyt.com/writings/count-words/

davedx 4y ago
Yeah I’ve worked on non trivial javascript codebases where allocations and gc mattered.
- christophilus 4y ago
  I’d like to hear more about this.
  - mceachen 4y ago
    Not your OP, but I've got stories! PhotoStructure is a non-trivial app written in TypeScript for both frontend and backend tasks. Coming from Scala, I initially used a lot of Array.map, Array.foreach, and, to handle things like Some/None/Either: function map<T,U>( maybe: <T|undefined>, f: (t:T) => U ) According to the V8 memory inspector, all those tiny fat-arrow functions can hammer the GC (presumably due to stack allocations and pulling in local context). Replacing large array iteration with for loops was a big win. Also, handling large files with a streaming parser when possible, instead of reading them entirely into memory, another win. Buffer concatenation may be faster by pushing read chunks onto an array, and joining the lot at the end, rather than incrementally appending with .concat. When memoizing functions, if they themselves return functions, watch out for fat-arrows if you didn't need the caller's context (which may prevent gc from unexpectedly retained variables). But the first step should always be to profile your app. You can't assert improvement without a baseline.
xyzzy_plugh 4y ago
I don't know if I can agree. Python is certainly problematic for the reasons you outlined, but Go is much closer to C in terms of performance. Go is also compiled, and as such you have similar opportunity to optimize and measure allocs. In my experience it's much harder to tune Python, and Go is often easier to tune than C due to the great ergonomics of the compiler. You can also drop down to assembly! But really, I disagree because I've frequently saturated massive IOPS. I/O is still the bottleneck. The article pretty much immediately excludes network I/O, which is in many cases more common than disk I/O. Even so, tiny single-threaded programs reading words one-at-a-time are obviously not going to be I/O constrained with modern disks. For these types of programs, I/O hasn't been a bottleneck in a long, long time, and I'd actually be surprised to hear candidates suggest otherwise.
- dahfizz 4y ago
  I mean, Go is closer to C than Python is. But Go is still a garbage collected language with a runtime. It's not going to come close to the limits of performance that C offers
  - morelisp 4y ago
    Having played with this a previous time it was posted and looking at the profiler results, the main difference between the Go and C isn't due to any memory allocations but rather the lack of in-place update and slightly higher cost from being general-purpose in Go's hash table. (This is also probably why Rust, without the GC overhead, clusters with Go rather than C.)
    - sidlls 4y ago
      I'm fairly certain that if one wrote C (or C++) programs with the same safety targets that Rust has out-of-the-box the performance is close, if not (for practical purposes) identical. Of course, to do much useful (and performant) in Rust one often has to break out `unsafe`, which eliminates some of the out-of-the-box guarantees for safety--and in some cases makes one wonder if it's worth all the overhead instead of just using C or C++.
morelisp 4y ago
The Go code is reasonably efficient at avoiding allocations, though it's hard to avoid some. Without thinking too hard, it's also going to be hard to avoid those same ones in C, and some possible improvements would apply to both (e.g. defining a maximum word length). "Lowercase word count" is a surprisingly difficult case in this regard, because you need to check and potentially transform each character individually, and also store a normalized form of each word. Probably some smart SIMD lowercase function could help here but I don't think any language is going to offer that out of the box. It's also defined in a way I think detaches a bit much from real-world issues - it's handling arbitrary bytes but also only ASCII. If it had to handle UTF-8 it would be very different; but also if it could make assumptions that only a few control characters were relevant.
- dahfizz 4y ago
  > Probably some smart SIMD lowercase function could help here but I don't think any language is going to offer that out of the box. No, but at least you have direct access to the intrinsics in C. To get vectorization in Go, you have to implement it in C and link that into your Go program.
  - morelisp 4y ago
    > To get vectorization in Go, you have to implement it in C and link that into your Go program. Go has an assembler which does not require implementing anything in C (though the assembler uses a more C-style syntax), nor critically does it require using CGo linkage. It's used to implement many hot paths in the stdlib.
  - throwaway894345 4y ago
    Typically you would just implement vectorization in assembly in the Go case.
- stabbles 4y ago
  > but I don't think any language is going to offer that out of the box. That's what compilers are for. I tried to improve the C version to make it friendlier to the compiler. Clang does a decent job: https://godbolt.org/z/o35edavPn https://godbolt.org/z/o35edavPn I'm getting 1.325s (321MB/s) instead of 1.506s (282MB/s) on a 100 concatenated bibles. That's still not a 10x improvement though; the problem is cache locality in the hash map.
imtringued 4y ago
The file is only being read once according to the blog and then it is in memory. This isn't an I/O intensive application at all. I have written a small script in python that does something similar. I have a word list with 1000 words and I check the presence of the words. Here is the thing. For every word I go through the entire file. So lets say I scan the file one thousand times. In fact I did something more complicated and ended up going 6000 times over the original file and yet it still took only three seconds. If all these scans had to reread the file it would take forever.
- kragen 4y ago
  he has figures for both cached and uncached performance if all your scans had to reread the file from nvme it would take five times as long if we extrapolate from those figures not forever
- Severian 4y ago
  This sounds like a very inefficient method. The Python stdlib module 'collections' includes a Counter class which can do this for you. Then all you need to do is copy the dict key/item pair to a new one that match your word list.
- nunez 4y ago
  the optimized version does it byte by byte
adverbly 4y ago
Of course disk speed has caught up. Single core clock speed hasn't changed in over 10 years now? Disk now uses SSD and has been chugging along with improvements. I'm curious what a multi thread(multi process for python due to GIL?) comparison would be. Obviously people aren't doing this by default though, so the author's point still stands.
- PartiallyTyped 4y ago
  > Single core clock speed hasn't changed in over 10 years now? Technically we have gone from 3.3gz- 3.9gz base frequency, 4.1-4.2 single core boosts, 4.7ghz heavy OC in Haswell to 4.3 and 3.0 base clock for efficiency/perf cores, with boosts to 5.4 ish, stable 5.8ghz all core frequency with heavy OC, and even pushing 6.something GHz single core with a good setup. But then again, this is on the more extreme ends. Mainstream laptops have remained relatively stable. re Python MP: On my 12700k, I saw almost linear scaling (per core, not thread) with multiprocessing when loading stuff from the disk for ML applications and processing. This was with the datasets library.
- chronial 4y ago
  > Single core clock speed hasn't changed in over 10 years now? This is not true. I thought the same thing and you are right in regards to base line clock speed. But the performance is still increasing. I just got a new PC at work with a 2021 high-end CPU and it has 200% single core performance of the 2015 mid-range CPU in my private PC: https://www.cpubenchmark.net/compare/4597vs2599/Intel-i9-12900K-vs-Intel-i5-6500 https://www.cpubenchmark.net/compare/4597vs2599/Intel-i9-129...
  - antisthenes 4y ago
    Are you simply glossing over the fact that CPU 1 has a turbo of 5.2 Ghz and the other 3.6 Ghz ?
    - chronial 4y ago
      Yes, I did not go into details where the differences are coming from. The base clockspeeds are the same, which is obviously the number that GP noticed not changing over the last 10 years. Other things changed. The turbo clockspeed is one of them.
bluedino 4y ago
Don't forget about naive implementations in languages like C++ where using cin/cout can cause your program to run slower than Python when doing file IO
StillBored 4y ago
Yah, that was my thought exactly. Its probably not just the language choice, but the chosen algorithm. I expect a word frequency counting algorithm to run at close to the speed of sequential main memory read speeds. So the bottleneck in real situations is likely how fast the I/O subsystem can get it into RAM. (a quick glance at the C version tells me all I need to know with the scanf, strdup, etc. This is sorta like those C vs Java benchmarks which boil down to the fact that the default (glibc/etc) C malloc() isn't really optimized for perf, and what your really bench marking is how terrible it is for frequent tiny allocations. I think there _IS_ a diffrence between the code written by someone who lives C in a system programming context, and people who dabble in it from a higher level language.). PS: Say using a hash to track a words frequency, likely works OKish but the need to keep it small, while still avoiding collisions would cause problems if the algorithm were parallelized in a long running system (rather than batching, where you would just run each thread against its own copy of the frequency tables, and then merge them at the end). But I'm still fairly certain that "your doing it wrong" if the overall algorithm can't run at a significant fraction of main memory bandwidth.

davedx 4y ago

Yeah I’ve worked on non trivial javascript codebases where allocations and gc mattered.

christophilus 4y ago
I’d like to hear more about this.
- mceachen 4y ago
  Not your OP, but I've got stories! PhotoStructure is a non-trivial app written in TypeScript for both frontend and backend tasks. Coming from Scala, I initially used a lot of Array.map, Array.foreach, and, to handle things like Some/None/Either: function map<T,U>( maybe: <T|undefined>, f: (t:T) => U ) According to the V8 memory inspector, all those tiny fat-arrow functions can hammer the GC (presumably due to stack allocations and pulling in local context). Replacing large array iteration with for loops was a big win. Also, handling large files with a streaming parser when possible, instead of reading them entirely into memory, another win. Buffer concatenation may be faster by pushing read chunks onto an array, and joining the lot at the end, rather than incrementally appending with .concat. When memoizing functions, if they themselves return functions, watch out for fat-arrows if you didn't need the caller's context (which may prevent gc from unexpectedly retained variables). But the first step should always be to profile your app. You can't assert improvement without a baseline.

xyzzy_plugh 4y ago

I don't know if I can agree. Python is certainly problematic for the reasons you outlined, but Go is much closer to C in terms of performance. Go is also compiled, and as such you have similar opportunity to optimize and measure allocs. In my experience it's much harder to tune Python, and Go is often easier to tune than C due to the great ergonomics of the compiler. You can also drop down to assembly! But really, I disagree because I've frequently saturated massive IOPS. I/O is still the bottleneck. The article pretty much immediately excludes network I/O, which is in many cases more common than disk I/O. Even so, tiny single-threaded programs reading words one-at-a-time are obviously not going to be I/O constrained with modern disks. For these types of programs, I/O hasn't been a bottleneck in a long, long time, and I'd actually be surprised to hear candidates suggest otherwise.

dahfizz 4y ago
I mean, Go is closer to C than Python is. But Go is still a garbage collected language with a runtime. It's not going to come close to the limits of performance that C offers
- morelisp 4y ago
  Having played with this a previous time it was posted and looking at the profiler results, the main difference between the Go and C isn't due to any memory allocations but rather the lack of in-place update and slightly higher cost from being general-purpose in Go's hash table. (This is also probably why Rust, without the GC overhead, clusters with Go rather than C.)
  - sidlls 4y ago
    I'm fairly certain that if one wrote C (or C++) programs with the same safety targets that Rust has out-of-the-box the performance is close, if not (for practical purposes) identical. Of course, to do much useful (and performant) in Rust one often has to break out `unsafe`, which eliminates some of the out-of-the-box guarantees for safety--and in some cases makes one wonder if it's worth all the overhead instead of just using C or C++.

morelisp 4y ago

The Go code is reasonably efficient at avoiding allocations, though it's hard to avoid some. Without thinking too hard, it's also going to be hard to avoid those same ones in C, and some possible improvements would apply to both (e.g. defining a maximum word length). "Lowercase word count" is a surprisingly difficult case in this regard, because you need to check and potentially transform each character individually, and also store a normalized form of each word. Probably some smart SIMD lowercase function could help here but I don't think any language is going to offer that out of the box. It's also defined in a way I think detaches a bit much from real-world issues - it's handling arbitrary bytes but also only ASCII. If it had to handle UTF-8 it would be very different; but also if it could make assumptions that only a few control characters were relevant.

dahfizz 4y ago
> Probably some smart SIMD lowercase function could help here but I don't think any language is going to offer that out of the box. No, but at least you have direct access to the intrinsics in C. To get vectorization in Go, you have to implement it in C and link that into your Go program.
- morelisp 4y ago
  > To get vectorization in Go, you have to implement it in C and link that into your Go program. Go has an assembler which does not require implementing anything in C (though the assembler uses a more C-style syntax), nor critically does it require using CGo linkage. It's used to implement many hot paths in the stdlib.
- throwaway894345 4y ago
  Typically you would just implement vectorization in assembly in the Go case.
stabbles 4y ago
> but I don't think any language is going to offer that out of the box. That's what compilers are for. I tried to improve the C version to make it friendlier to the compiler. Clang does a decent job: https://godbolt.org/z/o35edavPn https://godbolt.org/z/o35edavPn I'm getting 1.325s (321MB/s) instead of 1.506s (282MB/s) on a 100 concatenated bibles. That's still not a 10x improvement though; the problem is cache locality in the hash map.

imtringued 4y ago

The file is only being read once according to the blog and then it is in memory. This isn't an I/O intensive application at all. I have written a small script in python that does something similar. I have a word list with 1000 words and I check the presence of the words. Here is the thing. For every word I go through the entire file. So lets say I scan the file one thousand times. In fact I did something more complicated and ended up going 6000 times over the original file and yet it still took only three seconds. If all these scans had to reread the file it would take forever.

kragen 4y ago
he has figures for both cached and uncached performance if all your scans had to reread the file from nvme it would take five times as long if we extrapolate from those figures not forever
Severian 4y ago
This sounds like a very inefficient method. The Python stdlib module 'collections' includes a Counter class which can do this for you. Then all you need to do is copy the dict key/item pair to a new one that match your word list.
nunez 4y ago
the optimized version does it byte by byte

adverbly 4y ago

Of course disk speed has caught up. Single core clock speed hasn't changed in over 10 years now? Disk now uses SSD and has been chugging along with improvements. I'm curious what a multi thread(multi process for python due to GIL?) comparison would be. Obviously people aren't doing this by default though, so the author's point still stands.

PartiallyTyped 4y ago
> Single core clock speed hasn't changed in over 10 years now? Technically we have gone from 3.3gz- 3.9gz base frequency, 4.1-4.2 single core boosts, 4.7ghz heavy OC in Haswell to 4.3 and 3.0 base clock for efficiency/perf cores, with boosts to 5.4 ish, stable 5.8ghz all core frequency with heavy OC, and even pushing 6.something GHz single core with a good setup. But then again, this is on the more extreme ends. Mainstream laptops have remained relatively stable. re Python MP: On my 12700k, I saw almost linear scaling (per core, not thread) with multiprocessing when loading stuff from the disk for ML applications and processing. This was with the datasets library.
chronial 4y ago
> Single core clock speed hasn't changed in over 10 years now? This is not true. I thought the same thing and you are right in regards to base line clock speed. But the performance is still increasing. I just got a new PC at work with a 2021 high-end CPU and it has 200% single core performance of the 2015 mid-range CPU in my private PC: https://www.cpubenchmark.net/compare/4597vs2599/Intel-i9-12900K-vs-Intel-i5-6500 https://www.cpubenchmark.net/compare/4597vs2599/Intel-i9-129...
- antisthenes 4y ago
  Are you simply glossing over the fact that CPU 1 has a turbo of 5.2 Ghz and the other 3.6 Ghz ?
  - chronial 4y ago
    Yes, I did not go into details where the differences are coming from. The base clockspeeds are the same, which is obviously the number that GP noticed not changing over the last 10 years. Other things changed. The turbo clockspeed is one of them.

bluedino 4y ago

Don't forget about naive implementations in languages like C++ where using cin/cout can cause your program to run slower than Python when doing file IO

StillBored 4y ago

Yah, that was my thought exactly. Its probably not just the language choice, but the chosen algorithm. I expect a word frequency counting algorithm to run at close to the speed of sequential main memory read speeds. So the bottleneck in real situations is likely how fast the I/O subsystem can get it into RAM. (a quick glance at the C version tells me all I need to know with the scanf, strdup, etc. This is sorta like those C vs Java benchmarks which boil down to the fact that the default (glibc/etc) C malloc() isn't really optimized for perf, and what your really bench marking is how terrible it is for frequent tiny allocations. I think there _IS_ a diffrence between the code written by someone who lives C in a system programming context, and people who dabble in it from a higher level language.). PS: Say using a hash to track a words frequency, likely works OKish but the need to keep it small, while still avoiding collisions would cause problems if the algorithm were parallelized in a long running system (rather than batching, where you would just run each thread against its own copy of the frequency tables, and then merge them at the end). But I'm still fairly certain that "your doing it wrong" if the overall algorithm can't run at a significant fraction of main memory bandwidth.