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

I know it's a cliche that someone brings up Rust in any programming thread, but I can't help myself. ;-) Several of the techniques here are easy enough in Rust that I just do them routinely.

* Rayon makes it easy to process line-wise in reasonable-sized chunks without allocating a string per line.

* The standard integer parsing stuff takes a slice, not an owned string.

* The standard hash map doesn't have the same expectation "that we pass in an instance of the key class that is equal to an existing instance"; you can call HashMap<String>::get with a &str. (One limitation is that std::collections::HashMap::entry does expect a K, so there's some redundancy if you need to insert afterward, but you could drop to hashbrown::HashMap::raw_entry_mut to avoid that.)

I took part in the One Billion Row challenge (1BRC). It was a lot of fun, but also a great learning experience. People came up with some pretty incredible optimization tricks. When you put them all together, it's a huge number, and they are all mingled up in individual solutions. They also happen on many levels -- from quite high, to incredibly low and detailed.

In retrospect, I could see there was a good number of tricks that are relatively easy to grasp, and reusable in other projects. I felt the urge to do a writeup that captures this knowledge in one place, isolating and explaining each of the tricks.

if you're parsing the file row by row, iterating over the trie as you process each character (as they argue to calculate the int value) (so what you have to do to hash it anyways), should be similar. What you'd end up in is micro-architectual issues on cache performance.

up to 6.6 seconds variant, i see the point of pushing the envelope of the programming environment and hacks that might help optimize future builds of the language. but beyond that the optimizations seems to be more about overcoming the inherent limitations of the environment, which are due to conciously made tradeoffs.

i feel that once you hit that limit, we have reached the upper limit of the competition.

https://github.com/noahfalk/1brc

a bit faster than fatest java still

In reality, though, data always have errors, and you get many validity checks in there, and data is never only ascii, but full of Unicode.

I so wish python would come with the equivalent of jvisualvm in its “batteries included” (not even talking about better profilers even).