4 ms·

> Kudos! 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 knuckl

> Kudos! 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.

burntsushi 4y ago
The "why" behind the trie is explained in the comments in the code. :-) The core of my hypothesis was to avoid hashing and hash table lookups at all. 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.