countwords

I believe this is because the code `counts[word]++` basically works by: 1. Hash word, retrieve the value from the counts map 2. Increment the value 3. Hash word, store the value into the counts map By change counts to a map of strings to pointers of ints, you only need to perform #3 once per unique word. Once you've read the int pointer, you need only write to the pointer and not re-hash the word and write that to the map, which can be expensive. https://github.com/benhoyt/countwords/blob/master/optimized....

Why not read the source code? :-) I wrote comments explaining things: https://github.com/benhoyt/countwords/blob/8553c8f600c40a462...

> It uses byte strings instead of UTF-8 strings. In my opinion, that’s not an optimization, that’s changing the problem. Depending on the question you’re asking, only one of the two can be correct. No, that's very wrong. ripgrep has rich Unicode support for example, but represents file contents as byte strings. UTF-8 strings vs byte strings is an implementation detail. I think you might benefit from reading the "bonus" Rust submission: https://github.com/benhoyt/countwords/blob/8553c8f600c40a462... IMO, Ben kind of glossed over the bonus submission. But I personally think it was the biggest point in favor of Rust for a real world version of this task.

https://github.com/benhoyt/countwords/blob/master/simple.lis... From Hoyt's repository itself.

Are you looking at the "simple" or the "optimized" versions? For the optimized, yes, the Go one is very similar to the C. For the simple, idiomatic version, the Go version [1] is much simpler than the C one [2]: 40 very straight-forward LoC vs 93 rather more complex ones including pointer arithmetic, tricky manual memory management, and so on. [1] https://github.com/benhoyt/countwords/blob/c66dd01d868aa83dc... [2] https://github.com/benhoyt/countwords/blob/c66dd01d868aa83dc...

Re: the Rust optimized implementation, I was able to get ~20-25% better performance by rewriting the for loops as iterators, using Rust's byte range pattern matching, and a buffered writer, which seems crazy, but it's true. I chalked it up to some crazy ILP/SIMD tricks the compiler is doing. I even submitted a PR[0], but Ben decided he was tired of maintaining and decided to archive the project (which fair enough!). [0]: https://github.com/benhoyt/countwords/pull/115

There is a gap between languages at the moment imo. Ruby is just ruthlessly productive. Compare https://github.com/benhoyt/countwords/blob/master/simple.rb with https://github.com/benhoyt/countwords/blob/master/simple.go Hoping new age compiled languages like Crystal & Nim fill the gap of performance, types & productivity. But compile speeds need to be factored in.

I don't know. But Ben Hoyt got a similar time as me too. I saw your GitHub PR. Moreover, looking at your program, I would expect it to be slower than the other optimized versions (Rust, C, Go). Because it doesn't actually implement the optimizations in those programs! So not only is your code slow on two different compilers, but it also matches my prior. You're the one who came out of the woodwork and said a bunch of nonsense. Maybe put in a little effort here to try to figure things out. Like, oh, I don't know, run the benchmarks on the other programs to compare relative timings. Like I did. Or show the commands you used to compile. Like I did. Or show the commands you used to run the program. Like I did. You want me to hold your beer? Fine. But put in the work. My bet is that you're being just as sloppy now as you were in your comments.

The source code of the trie program I wrote is here: https://github.com/benhoyt/countwords/blob/master/rust/optim... The comments explain why I think it's slower. The TL;DR is that using a trie requires more memory accesses than a hash table (per byte of input), and those memory accesses slow the whole enterprise down. But, not all memory accesses are created equal. So perhaps a more clever representation that exploits locality better would do better. "Obvious" techniques for shrinking memory usage made a big difference and brought the performance of the trie program closer to C: https://github.com/benhoyt/countwords/pull/2

Checkout Crystal lang one (Ruby but fast), https://github.com/benhoyt/countwords/pull/21/files seems to keep readability intact and committer is saying it outperforms Go which is interesting.

Yeah, I noticed that too: https://github.com/benhoyt/countwords/blob/9d81d13711e56c250... The constraints do say that it is okay to assume lines are reasonable length. But yes, if you were making GNU wordfreq, that might not be something you want to assume. But at that point, it just depends on what you want your failure mode to be I suppose. greps for example will happily just gobble up as much memory as they can to fit a line into memory. :-)

The "grep" and "wc" commands that are included in that table don't attempt to solve the problem. That wasn't clear to me on first reading. I suppose they are included as a baseline for reading a file and for tokenising strings into words. See https://github.com/benhoyt/countwords/blob/eb2a8adf21c895907...

The grep version searches the input for "foobar" [1]. Hence, it doesn't solve the problem. [1] https://github.com/benhoyt/countwords/blob/eb2a8adf21c895907...

That file repeated 10 times, even: https://github.com/benhoyt/countwords/blob/master/test.sh

On a 4.3MB file: https://github.com/benhoyt/countwords/blob/master/kjvbible.t...