3 ms·

Even the "optimized" C version is far from what an experienced C programmer would write if performance was paramount. General-purpose memory allocation, using h

Even the "optimized" C version is far from what an experienced C programmer would write if performance was paramount. General-purpose memory allocation, using hash tables with inherently bad spatial and temporal locality, using buffered I/O instead of mapping the file to memory.

burntsushi 6y ago
You can't map an arbitrary stream into memory. That's one of the constraints of the challenge: it has to be able to work on a stream. And even then, you can't memory map all kinds of files. This is what happens when you assume that you can: $ ag MHz /proc/cpuinfo $ grep MHz /proc/cpuinfo cpu MHz : 2300.000 cpu MHz : 988.934 cpu MHz : 2300.000 cpu MHz : 800.044 cpu MHz : 2300.000 cpu MHz : 2300.000 cpu MHz : 2300.000 cpu MHz : 1100.949 In the optimized C program, allocation is not a bottleneck. Pretty much all allocation is done upfront and that's all you need. There is an allocation for writing a new word to the table, but that's also amortized and isn't a big factor in the performance of the program in this particular benchmark. As for "bad spatial and temporal locality," can you be more specific? I guess the only thing I can see is perhaps inlining words smaller than some size into the same allocation as the hash table. But the hash table is otherwise one contiguous allocation.
- cb321 6y ago
  > That's one of the constraints of the challenge: it has to be able to work on a stream. I cannot find any stream constraint in either the article or the countwords repo. He just says "standard input" and his "test.sh" uses "<kjvbible_x10.txt". You can mmap stdin/fd 0 after an `fstat(0,..)` no problemo. Can it fail and should you check errors? Sure (as can accessing stdin in any way, actually). He even mentions memory-mapped IO as a further way to go in the article in the C part.
  - burntsushi 6y ago
    From the OP: > Memory: don’t read whole file into memory. Buffering it line-by-line is okay, or in chunks with a maximum buffer size of 64KB. That said, it’s okay to keep the whole word-count map in memory (we’re assuming the input is text in a real language, not full of randomized unique words). A shorter but less precise way of saying that is, "make the program work on streams." > You can mmap stdin/fd 0 after an `fstat(0,..)` no problemo. Can it fail and should you check errors? Sure (as can accessing stdin in any way, actually). Of course. And when it fails, what do you do? You defer to something that can handle a stream! Which is exactly the problem in the OP.
    - cb321 6y ago
      I disagree. mmap will demand page into memory - typically reading 4K at a time off storage (though really the buffer cache in all these timings). Much less than 64K. Were the file bigger than RAM/were there competition, it would also evict earlier pages. It's really just another way to "buffer" without worrying about all the fuss in user space, and I don't think you're going to convince me otherwise. I mean, MAP_POPULATE might violate the idea, but that is a very special case of mmap. Honestly, I think the author himself saying memory-mapped IO is a forward direction but "enough for now!" is pretty conclusive that he didn't think it was a forbidden optimization direction. I think you are over interpreting his early step-by-step style language explaining finite memory as a strict spec, or perhaps he shared an earlier draft of the article with you before he wrote that. It's fine to fail over to a stream, but often mmap is faster, as I know you know.
      - burntsushi 6y ago
        If you mmap'd a file, how do you keep its maximum memory usage to 64KB? I actually don't know the answer to that question. It's definitely not the default. You don't get to control it. The OS does. > It's fine to fail over to a stream, but often mmap is faster, as I know you know. But that's exactly the point. You literally cannot use mmap in all cases, either because you just can't or because it's actually slower. And in those cases, you need to fail over to a streaming implementation. And that streaming implementation needs to be fast too. And that's what this benchmark is. If you submitted a program that only used mmaps, and I sent a stream into that program, it would fail. So then you would need to modify the program to handle streams. And your strategy for dealing with mmaps couldn't be used. So then you'd need to optimize your handling of streams. Which is exactly what the programs in the OP are doing. So in the end, mmaps are a distraction for a benchmark like this, and I suspect that's why the OP didn't bother with them.
- bluetomcat 6y ago
  > As for "bad spatial and temporal locality," can you be more specific? One could use a lexicographic Btree-like structure with multiple characters per node, sharing consecutive cache-lines. For looking up the word "bar", you would traverse the "b" key from the root node, then its child "a" node, then the "r" child of the "a" node. Most of the nodes near the top would remain hot in the cache, and deeper less-visited nodes could be joined or compacted based on some criteria. Of course there are many subtleties, special cases and complications and the solution would be far more complex in terms of source code length. With a hash table, you effectively compute a hash for every word, and then jump at arbitrary locations throughout the whole table.
  - burntsushi 6y ago
    You've traded hashing for a memory access per byte. I did something similar in the 'optimized-trie' program for Rust: https://github.com/benhoyt/countwords/blob/master/rust/optimized-trie/main.rs https://github.com/benhoyt/countwords/blob/master/rust/optim... --- It ended up being slower. But, it is very much impacted by cache effects. So the next step here would indeed be to figure out how to reduce cache misses. But it's non-trivial. Like, maybe your idea works. Maybe. I don't know. You'd have to try it. But it's not clear to me that it will. And it doesn't support "is far from what an experienced C programmer would write if performance was paramount" IMO.

burntsushi 6y ago

You can't map an arbitrary stream into memory. That's one of the constraints of the challenge: it has to be able to work on a stream. And even then, you can't memory map all kinds of files. This is what happens when you assume that you can: $ ag MHz /proc/cpuinfo $ grep MHz /proc/cpuinfo cpu MHz : 2300.000 cpu MHz : 988.934 cpu MHz : 2300.000 cpu MHz : 800.044 cpu MHz : 2300.000 cpu MHz : 2300.000 cpu MHz : 2300.000 cpu MHz : 1100.949 In the optimized C program, allocation is not a bottleneck. Pretty much all allocation is done upfront and that's all you need. There is an allocation for writing a new word to the table, but that's also amortized and isn't a big factor in the performance of the program in this particular benchmark. As for "bad spatial and temporal locality," can you be more specific? I guess the only thing I can see is perhaps inlining words smaller than some size into the same allocation as the hash table. But the hash table is otherwise one contiguous allocation.

cb321 6y ago
> That's one of the constraints of the challenge: it has to be able to work on a stream. I cannot find any stream constraint in either the article or the countwords repo. He just says "standard input" and his "test.sh" uses "<kjvbible_x10.txt". You can mmap stdin/fd 0 after an `fstat(0,..)` no problemo. Can it fail and should you check errors? Sure (as can accessing stdin in any way, actually). He even mentions memory-mapped IO as a further way to go in the article in the C part.
- burntsushi 6y ago
  From the OP: > Memory: don’t read whole file into memory. Buffering it line-by-line is okay, or in chunks with a maximum buffer size of 64KB. That said, it’s okay to keep the whole word-count map in memory (we’re assuming the input is text in a real language, not full of randomized unique words). A shorter but less precise way of saying that is, "make the program work on streams." > You can mmap stdin/fd 0 after an `fstat(0,..)` no problemo. Can it fail and should you check errors? Sure (as can accessing stdin in any way, actually). Of course. And when it fails, what do you do? You defer to something that can handle a stream! Which is exactly the problem in the OP.
  - cb321 6y ago
    I disagree. mmap will demand page into memory - typically reading 4K at a time off storage (though really the buffer cache in all these timings). Much less than 64K. Were the file bigger than RAM/were there competition, it would also evict earlier pages. It's really just another way to "buffer" without worrying about all the fuss in user space, and I don't think you're going to convince me otherwise. I mean, MAP_POPULATE might violate the idea, but that is a very special case of mmap. Honestly, I think the author himself saying memory-mapped IO is a forward direction but "enough for now!" is pretty conclusive that he didn't think it was a forbidden optimization direction. I think you are over interpreting his early step-by-step style language explaining finite memory as a strict spec, or perhaps he shared an earlier draft of the article with you before he wrote that. It's fine to fail over to a stream, but often mmap is faster, as I know you know.
    - burntsushi 6y ago
      If you mmap'd a file, how do you keep its maximum memory usage to 64KB? I actually don't know the answer to that question. It's definitely not the default. You don't get to control it. The OS does. > It's fine to fail over to a stream, but often mmap is faster, as I know you know. But that's exactly the point. You literally cannot use mmap in all cases, either because you just can't or because it's actually slower. And in those cases, you need to fail over to a streaming implementation. And that streaming implementation needs to be fast too. And that's what this benchmark is. If you submitted a program that only used mmaps, and I sent a stream into that program, it would fail. So then you would need to modify the program to handle streams. And your strategy for dealing with mmaps couldn't be used. So then you'd need to optimize your handling of streams. Which is exactly what the programs in the OP are doing. So in the end, mmaps are a distraction for a benchmark like this, and I suspect that's why the OP didn't bother with them.
bluetomcat 6y ago
> As for "bad spatial and temporal locality," can you be more specific? One could use a lexicographic Btree-like structure with multiple characters per node, sharing consecutive cache-lines. For looking up the word "bar", you would traverse the "b" key from the root node, then its child "a" node, then the "r" child of the "a" node. Most of the nodes near the top would remain hot in the cache, and deeper less-visited nodes could be joined or compacted based on some criteria. Of course there are many subtleties, special cases and complications and the solution would be far more complex in terms of source code length. With a hash table, you effectively compute a hash for every word, and then jump at arbitrary locations throughout the whole table.
- burntsushi 6y ago
  You've traded hashing for a memory access per byte. I did something similar in the 'optimized-trie' program for Rust: https://github.com/benhoyt/countwords/blob/master/rust/optimized-trie/main.rs https://github.com/benhoyt/countwords/blob/master/rust/optim... --- It ended up being slower. But, it is very much impacted by cache effects. So the next step here would indeed be to figure out how to reduce cache misses. But it's non-trivial. Like, maybe your idea works. Maybe. I don't know. You'd have to try it. But it's not clear to me that it will. And it doesn't support "is far from what an experienced C programmer would write if performance was paramount" IMO.