5 ms·

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 mat

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 https://github.com/benhoyt/countwords/pull/115

codeflo 4y ago
Very nice. That’s in fact really clean, and (at least to me) indeed surprising. 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.
- mustache_kimono 4y ago
  Can't win them all. I think I came along when they were just really sick of maintaining it. Ben and Andrew have all my respect.
- deleted 4y ago
  [deleted]
grumpyprole 4y ago
Iterators are potentially a much better design too as they allow for more modular code.
deleted 4y ago
[deleted]
mustache_kimono 4y ago
In case anyone is interested, I did an optimized, but much more simple, Rust implementation just today[0], which is faster than the optimized implementation on my machine. No indexing into arrays of bytes, no unsafe, etc., no "code golf" measures. Of course, credit where it's due -- these are simply tweaks to Andrew Gallant's code. 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/fast-simple/main.rs https://github.com/kimono-koans/countwords/blob/master/rust/...
- deleted 4y ago
  [deleted]
- arijun 4y ago
  Out of curiosity, what's the difference in runtime when compared to Andrew's optimized version on your machine? 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.
  - mustache_kimono 4y ago
    > Out of curiosity, what's the difference in runtime when compared to Andrew's optimized version on your machine? 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.
    - burntsushi 4y ago
      Can you share precisely how you're running the code and measuring timings? I've seen folks flub the measuring for this benchmark by testing much smaller inputs, for example.
      - mustache_kimono 4y ago
        I'm using the kjvbible_x10.txt corpus and using hyperfine on the Mac. 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!
tobz1000 4y ago
These changes would prompt some additional remarks about the Rust implementation: most optimisations make code more verbose and less idiomatic, but in Rust it can sometimes be the opposite.
nyxtom 4y ago
BufWriter provides a default capacity of 8 KB. Rather than perform repeated syscalls to write to the stdout fd, this will syscall on flush https://doc.rust-lang.org/std/io/struct.BufWriter.html https://doc.rust-lang.org/std/io/struct.BufWriter.html 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 https://doc.rust-lang.org/book/ch13-04-performance.html
burntsushi 4y ago
From my measurements, your optimized version runs at about the same speed as mine: $ 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' You mentioned in another comment that you were benchmarking on an M1. Maybe there's some interesting differences there in the codegen, how the CPU executes or both. 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.)
- 4y ago

codeflo 4y ago

Very nice. That’s in fact really clean, and (at least to me) indeed surprising. 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.

mustache_kimono 4y ago
Can't win them all. I think I came along when they were just really sick of maintaining it. Ben and Andrew have all my respect.
deleted 4y ago
[deleted]

grumpyprole 4y ago

Iterators are potentially a much better design too as they allow for more modular code.

deleted 4y ago

[deleted]

mustache_kimono 4y ago

In case anyone is interested, I did an optimized, but much more simple, Rust implementation just today[0], which is faster than the optimized implementation on my machine. No indexing into arrays of bytes, no unsafe, etc., no "code golf" measures. Of course, credit where it's due -- these are simply tweaks to Andrew Gallant's code. 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/fast-simple/main.rs https://github.com/kimono-koans/countwords/blob/master/rust/...

deleted 4y ago
[deleted]
arijun 4y ago
Out of curiosity, what's the difference in runtime when compared to Andrew's optimized version on your machine? 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.
- mustache_kimono 4y ago
  > Out of curiosity, what's the difference in runtime when compared to Andrew's optimized version on your machine? 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.
  - burntsushi 4y ago
    Can you share precisely how you're running the code and measuring timings? I've seen folks flub the measuring for this benchmark by testing much smaller inputs, for example.
    - mustache_kimono 4y ago
      I'm using the kjvbible_x10.txt corpus and using hyperfine on the Mac. 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!

tobz1000 4y ago

These changes would prompt some additional remarks about the Rust implementation: most optimisations make code more verbose and less idiomatic, but in Rust it can sometimes be the opposite.

nyxtom 4y ago

BufWriter provides a default capacity of 8 KB. Rather than perform repeated syscalls to write to the stdout fd, this will syscall on flush https://doc.rust-lang.org/std/io/struct.BufWriter.html https://doc.rust-lang.org/std/io/struct.BufWriter.html 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 https://doc.rust-lang.org/book/ch13-04-performance.html

burntsushi 4y ago

From my measurements, your optimized version runs at about the same speed as mine: $ 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' You mentioned in another comment that you were benchmarking on an M1. Maybe there's some interesting differences there in the codegen, how the CPU executes or both. 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.)

4y ago