I even submitted a PR[0], but Ben decided he was tired of maintaining and decided to archive the project (which fair enough!).
Looks like idiomatic Rust, which I think is interesting. Shows there is more than one way to skin a cat.
[0]: https://github.com/kimono-koans/countwords/blob/master/rust/...
For your other solution, if the time save is consistent from your machine to OP's (a big if), the Rust solution bumps up to 4th place.
Results on an M1: my "idiomatic" version is 1.32 times faster than Andrew's original optimized version, whereas the optimized C version is 1.13 times faster than my "idiomatic" version. So, all things being equal, that'd make Rust 3rd, just ahead of C++, and behind Zig and C, if I'm reading the results correctly.
More important, to me, would be the other thing -- it's readable, idiomatic Rust. That is, if it had been 5% slower, I think we'd probably all prefer to maintain this code.
I've seen folks flub the measuring for this benchmark by testing much smaller inputs, for example.
I just took a look on Linux and my code that is now running 1.43x faster on the Mac is only 1.02x faster on Ubuntu 22.04. But, again, it's really that it's a Rust commercial -- by leaning on the stdlib, it's possible to get straightforward, but still really fast code.
I have no doubt you could make it faster than me and have!
As rejection reasons go, “I wanted to name-drop person X” is interesting. But as you said, that’s the maintainer’s decision to make.
Also, for loops desugar to into_iter, but the extra closure does provide an additional bump https://doc.rust-lang.org/book/ch13-04-performance.html
$ cd /tmp/
$ git clone -b ag/test-kimono https://github.com/BurntSushi/countwords
$ cd countwords/rust/
$ ./bench
<snip>
Summary
'./optimized-trie/target/release/countwords < kjvbible_x10.txt' ran
1.22 ± 0.02 times faster than './kimono-simple/target/release/countwords < kjvbible_x10.txt'
1.26 ± 0.02 times faster than './optimized-customhashmap/target/release/countwords < kjvbible_x10.txt'
1.56 ± 0.03 times faster than './optimized-unsafe/target/release/countwords < kjvbible_x10.txt'
1.58 ± 0.03 times faster than './kimono-optimized/target/release/countwords < kjvbible_x10.txt'
1.60 ± 0.03 times faster than './optimized/target/release/countwords < kjvbible_x10.txt'
3.97 ± 0.06 times faster than './simple/target/release/countwords < kjvbible_x10.txt'
7.58 ± 0.21 times faster than './bonus/target/release/countwords < kjvbible_x10.txt'
Your 'fast-simple' version is a different story though. Personally, I would not put that in the "simple" classification as outlined by the OP. It is IMO very much not the first program someone would write for this. Bringing in 'hashbrown' and futzing with the hash table lookup/insert is definitely a perf tweak that you probably wouldn't want to do unless you had to, because it makes the code more complex. The 'Box<[u8]>' cements it as an 'optimized' variant.
Now it does look like a simpler variant of the "optimized" Rust program I wrote. I'm pretty impressed. I don't think I ever would have broken out of my local optima to discover that program. In particular, your approach appears to do 3 (and some change) passes over each buffer: 1) read up to '\n' (just the first line), 2) UTF-8 validation, 3) make lowercase and 4) split on whitespace. I realize chunking all of that up confers a lot of benefits, but still, 4 passes and it still being faster than 1 pass is very interesting.
I've glanced at the profiles of each program but haven't been able to solidly conclude anything more precisely about where exactly the benefit is. At this point, my next step would be to slowly translate my version into yours, and benchmark each step of the way until I could isolate the key change (assuming it is one change). But alas, I have run out of time this evening. :-)
Kudos!
(The other interesting thing to note here is that my 'trie' variant is now the fastest Rust submission. Previously, it was slower than the optimized variants on my older CPU. That's pretty neat.)
Thanks!
> I don't think I ever would have broken out of my local optima to discover that program.
It really is the answer to what is the most knuckle-headed thing one could try, but I was curious what Rust-with-the-guardrails could do.
> My 'trie' variant is now the fastest Rust submission
Cool. Very interested why this is the case.
The problem with the trie, though, is that it does a memory access per byte.
Whether and when this trade is beneficial is not totally clear to me, but clearly, it can vary.
Whether my hypothesis is actually correct is also not something I'm certain of. Verifying this would take some time with: 1) looking at the codegen and 2) some use of `perf` to extract CPU counters for things like branch and cache misses, and see if a correlation can be established.
I really should have waited until I had more time to respond, but it really only should be 2, 3, and 4.
I tried unsafe/unchecked for UTF8, and, yes, it is a modest bump, but I wanted to do it without unsafe. And 3 and 4 are really pretty fast for what they are. They both work on bytes and the str as_bytes transmute is virtually cost free from what I can tell.
True.
> Bringing in 'hashbrown' and futzing with the hash table lookup/insert is definitely a perf tweak that you probably wouldn't want to do unless you had to, because it makes the code more complex. The 'Box<[u8]>' cements it as an 'optimized' variant.
I would say, both these items, I added much later, and contribute substantially less to the bottom line performance than you might think. Bulk of the performance is elsewhere.