The Billion Row Challenge (1BRC) – Step-by-Step from 71s to 1.7s

Re:The Billion Row Challenge (1BRC) – Step-by-Step from 71s ... by haxen on Thursday February 22, 2024 @03:38PM (#39472855)

The 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.

[ Parent | on HN ]

Re:The Billion Row Challenge (1BRC) – Step-by-Step from 71s ... by scottlamb on Thursday February 22, 2024 @04:55PM (#39473845)

> 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?

[ Parent | on HN ]

Re:The Billion Row Challenge (1BRC) – Step-by-Step from 71s ... by haxen on Thursday February 22, 2024 @05:29PM (#39474220)

I 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.

[ Parent | on HN ]