3 ms·
> HashMap was quite a bottleneck in Rust as well, for many reasons, not just the key allocation problem. I'd be curious to hear more. Other than the default ha
by scottlamb 3y ago
> HashMap was quite a bottleneck in Rust as well, for many reasons, not just the key allocation problem.
I'd be curious to hear more. Other than the default hash function being quite expensive, and occasionally wanting to use the more expressive hashbrown API, I've been happy with Rust's std::collections::HashMap.
- haxen 3y agoThe reason the custom hashtable wins out isn't something generally applicable. For the very specific dataset used in the challenge, the hash function could be radically simplified, to just a single multiply and rotate left. To be fair, I didn't try out the hashbrown API. Maybe that, together with FxHash, would have been enough for the official dataset with 97% of keys < 16 bytes. But, I was optimizing for the "10k" dataset as well, with a lot of longer keys, and hashing just the first 8 bytes was the winning idea.
- scottlamb 3y ago> For the very specific dataset used in the challenge, the hash function could be radically simplified, to just a single multiply and rotate left. That's just a custom hash function, though; couldn't you do that with the standard std::collections::HashMap?
- haxen 3y agoI didn't bother to try, so not sure. There would probably be some challenges and I don't see how I'd accomplish it without some branch instruction in the custom hasher.