4 ms·

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

274 points by mfiguiere 3y ago

haxen 3y ago
Cool, I see mfiguiere linked to my recent blog post! Let me share a few words about it... 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.
- e12e 3y ago
  Thank you for taking the time to write it up. Really nice to see some modern Java, as well as the ideas with comments - many of which seem to generalize quite well - beyond Java and the jvm.
- fearthetelomere 3y ago
  If you do find the time, I'm sure that writeup would be very valuable!
  - tristor 3y ago
    The linked article is that write-up, this is the author replying to someone else posting their blog article.
compsciphd 3y ago
I wonder if using a trie instead of a hash would have provided a performance win. 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.
- haxen 3y ago
  Interestingly enough, that was my first idea. But when you consider the tiny keyset size, it would be hard to beat two machine instructions to calculate the hash + a single array lookup.
- gunnarmorling 3y ago
  There is one entry which uses a trie, but it's not at the top, IIRC (which may or may not be related to using a trie, there's many other relevant design decisions).
- o11c 3y ago
  There's a reason everybody uses hashing - if your data is trusted, it does very few operations. Tries have to allocate, walk, and interpret multiple nodes. Perhaps not as bad as trees (though that depends on how many possible trie node representations there are, vs what the data density is at each level), but still worse than the non-colliding hash. That said, with a finite dataset a perfect hash would probably beat a general hash though.
  - koliber 3y ago
    Was the list of city names known? Could you statically pre-build the Trie structure?
    - haxen 3y ago
      It was known, but the requirement was that the program keep working for an arbitrary keyset that conforms to the specified rules (up to 10,000 unique keys, each up to 100 bytes in length).
- paulddraper 3y ago
  Tries are rarely the most efficient option. Kind of like linked lists...conceptually pleasant but rarely if ever the best option for real-world perf.
- anonymoushn 3y ago
scottlamb 3y ago
Fun read. I haven't used Java in a long time, so even the "idiomatic Java code that would pass muster with any seasoned Java developer" was a bit shocking. 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.)
- haxen 3y ago
  I actually wrote a Rust version as well, and yes, it was far easier to write, far less code (although not incorporating all the tricks), completely safe, and pretty fast -- but still 2x slower than my end result in Java. HashMap was quite a bottleneck in Rust as well, for many reasons, not just the key allocation problem. But it was very easy to implement the same kind of custom hashtable, which almost by default ends up having a better memory layout than in Java. https://github.com/mtopolnik/rust-1brc/blob/main/src/main.rs https://github.com/mtopolnik/rust-1brc/blob/main/src/main.rs I bet I could improve on it just a bit and match the Java time. Not sure about topping it, though.
  - jasonjmcghee 3y ago
    I thought everyone used hashbrown now https://github.com/rust-lang/hashbrown https://github.com/rust-lang/hashbrown
    - IshKebab 3y ago
      They do because the standard library implementation was changed to use Hashbrown. However the standard library API has a slight limitation in that you can't get say "I have a reference to a string. If there's an entry for it, give me that. Otherwise clone the string and insert a new entry. Also only do one key lookup." You end up either having to do two lookups or always cloning the string even if you ended up not needing it.
gunnarmorling 3y ago
What an excellent post, one of the best on 1BRC I've come across so far. Big shout-out to Marko for participating in the challenge, making a strong push for clarifying corner cases of the rules, and sharing his experiences in this amazing write-up!
- haxen 3y ago
  Thanks for the praise Gunnar, but we all owe it to you for organizing it, and especially sticking through thick and thin when it took off, and needed lots of attention to evaluate everyone and maintain a level playing field!
  - tpmoney 3y ago
    The last part of the article raises an interesting question for me. What is the fastest, mostly fault tolerant implementation that could be created? So something that runs on say 10 different versions of the input, each of which has had up to 20 characters from the standard ASCII set inserted, replaced or removed randomly in the input file. So we'd be mostly looking for "data corruption" fault tolerance vs hardened against malicious input. How much can you still "out optimize" the compiler and JVM if you can't throw away all the safety?
Keyframe 3y ago
I must admit I only glanced at the article and in the past when topic appeared. How does this work, the speed of 1.7s I mean? Taking a look at input, let's say average entry is 16 bytes, there's billion of it; That's ~16GB. Average read speed of SSDs is what, ~500MB/s? Scanning alone at max throughput will take half a minute. This must be relying on DDR4+ read speeds which would probably come in under a second in certain cases. Is that's what's going on, RAM disk?
- haxen 3y ago
  I used to benchmark a lot on an enterprise-grade SSD 10 years ago, and that was already at 2 GB/s. Today, even my laptop's SSD supports multiple GB/s. But you're right about the contest -- each program was measured five times in a row, and there was enough RAM to fit the entire file into the page cache. The best time using all 32 cores (64 hyperthreads) on the evaluation machine was 323 milliseconds.
  - Keyframe 3y ago
    I went to the original repo, it's indeed a RAM disk. That makes it clear then. I was already almost excited about some IO wizardry going on. Results are determined by running the program on a Hetzner AX161 dedicated server (32 core AMD EPYC™ 7502P (Zen2), 128 GB RAM). Programs are run from a RAM disk (i.o. the IO overhead for loading the file from disk is not relevant), using 8 cores of the machine.
    - haxen 3y ago
      Running without RAM cache would be a great followup to this challenge. I think a time around 2-3 seconds should be achievable. But, it would be highly sensitive to the hardware setup and how well the disk-reading code is placed on cores relative to the connection to the disk. Not sure what it would take to allow hundreds of contestants to benefit from the best arrangement.
- pulse7 3y ago
  PCIe 3.0 x4 SSD runs at ~3500MB/s, PCIe 4.0 x4 SSD runs at ~7000MB/s and PCIe 5.0 x4 SSD runs at ~14000MB/s (yes - megabytes, not megabits)!
jiehong 3y ago
Very nice! Always use profilers! 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).
teo_zero 3y ago
The bottom line is: of you want performance in Java, code if it was C!
yread 3y ago
Here is the .net version https://github.com/noahfalk/1brc https://github.com/noahfalk/1brc a bit faster than fatest java still
- pjmlp 3y ago
  For the ultimate performance, so to speak, Valhala still needs to arrive into the JVM. So .NET has quite a few tricks that on Java side still require FFI, or clever use of Panama, maybe.
  - anonymoushn 3y ago
    These tools won't really close the gap unless Panama's vector APIs get a big makeover.
    - pjmlp 3y ago
      Panama vector API is still in preview for a reason. And it depends on Valhala being done.
rldjbpin 3y ago
this was the most approachable commentary on a 1BRC submission i've read thus far. 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.

274 points by mfiguiere 3y ago

Cool, I see mfiguiere linked to my recent blog post! Let me share a few words about it... 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.

e12e 3y ago
Thank you for taking the time to write it up. Really nice to see some modern Java, as well as the ideas with comments - many of which seem to generalize quite well - beyond Java and the jvm.
fearthetelomere 3y ago
If you do find the time, I'm sure that writeup would be very valuable!
- tristor 3y ago
  The linked article is that write-up, this is the author replying to someone else posting their blog article.

compsciphd 3y ago

I wonder if using a trie instead of a hash would have provided a performance win. 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.

haxen 3y ago
Interestingly enough, that was my first idea. But when you consider the tiny keyset size, it would be hard to beat two machine instructions to calculate the hash + a single array lookup.
gunnarmorling 3y ago
There is one entry which uses a trie, but it's not at the top, IIRC (which may or may not be related to using a trie, there's many other relevant design decisions).
o11c 3y ago
There's a reason everybody uses hashing - if your data is trusted, it does very few operations. Tries have to allocate, walk, and interpret multiple nodes. Perhaps not as bad as trees (though that depends on how many possible trie node representations there are, vs what the data density is at each level), but still worse than the non-colliding hash. That said, with a finite dataset a perfect hash would probably beat a general hash though.
- koliber 3y ago
  Was the list of city names known? Could you statically pre-build the Trie structure?
  - haxen 3y ago
    It was known, but the requirement was that the program keep working for an arbitrary keyset that conforms to the specified rules (up to 10,000 unique keys, each up to 100 bytes in length).
paulddraper 3y ago
Tries are rarely the most efficient option. Kind of like linked lists...conceptually pleasant but rarely if ever the best option for real-world perf.
anonymoushn 3y ago

scottlamb 3y ago

Fun read. I haven't used Java in a long time, so even the "idiomatic Java code that would pass muster with any seasoned Java developer" was a bit shocking. 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.)

haxen 3y ago
I actually wrote a Rust version as well, and yes, it was far easier to write, far less code (although not incorporating all the tricks), completely safe, and pretty fast -- but still 2x slower than my end result in Java. HashMap was quite a bottleneck in Rust as well, for many reasons, not just the key allocation problem. But it was very easy to implement the same kind of custom hashtable, which almost by default ends up having a better memory layout than in Java. https://github.com/mtopolnik/rust-1brc/blob/main/src/main.rs https://github.com/mtopolnik/rust-1brc/blob/main/src/main.rs I bet I could improve on it just a bit and match the Java time. Not sure about topping it, though.
- jasonjmcghee 3y ago
  I thought everyone used hashbrown now https://github.com/rust-lang/hashbrown https://github.com/rust-lang/hashbrown
  - IshKebab 3y ago
    They do because the standard library implementation was changed to use Hashbrown. However the standard library API has a slight limitation in that you can't get say "I have a reference to a string. If there's an entry for it, give me that. Otherwise clone the string and insert a new entry. Also only do one key lookup." You end up either having to do two lookups or always cloning the string even if you ended up not needing it.

gunnarmorling 3y ago

What an excellent post, one of the best on 1BRC I've come across so far. Big shout-out to Marko for participating in the challenge, making a strong push for clarifying corner cases of the rules, and sharing his experiences in this amazing write-up!

haxen 3y ago
Thanks for the praise Gunnar, but we all owe it to you for organizing it, and especially sticking through thick and thin when it took off, and needed lots of attention to evaluate everyone and maintain a level playing field!
- tpmoney 3y ago
  The last part of the article raises an interesting question for me. What is the fastest, mostly fault tolerant implementation that could be created? So something that runs on say 10 different versions of the input, each of which has had up to 20 characters from the standard ASCII set inserted, replaced or removed randomly in the input file. So we'd be mostly looking for "data corruption" fault tolerance vs hardened against malicious input. How much can you still "out optimize" the compiler and JVM if you can't throw away all the safety?

Keyframe 3y ago

I must admit I only glanced at the article and in the past when topic appeared. How does this work, the speed of 1.7s I mean? Taking a look at input, let's say average entry is 16 bytes, there's billion of it; That's ~16GB. Average read speed of SSDs is what, ~500MB/s? Scanning alone at max throughput will take half a minute. This must be relying on DDR4+ read speeds which would probably come in under a second in certain cases. Is that's what's going on, RAM disk?

haxen 3y ago
I used to benchmark a lot on an enterprise-grade SSD 10 years ago, and that was already at 2 GB/s. Today, even my laptop's SSD supports multiple GB/s. But you're right about the contest -- each program was measured five times in a row, and there was enough RAM to fit the entire file into the page cache. The best time using all 32 cores (64 hyperthreads) on the evaluation machine was 323 milliseconds.
- Keyframe 3y ago
  I went to the original repo, it's indeed a RAM disk. That makes it clear then. I was already almost excited about some IO wizardry going on. Results are determined by running the program on a Hetzner AX161 dedicated server (32 core AMD EPYC™ 7502P (Zen2), 128 GB RAM). Programs are run from a RAM disk (i.o. the IO overhead for loading the file from disk is not relevant), using 8 cores of the machine.
  - haxen 3y ago
    Running without RAM cache would be a great followup to this challenge. I think a time around 2-3 seconds should be achievable. But, it would be highly sensitive to the hardware setup and how well the disk-reading code is placed on cores relative to the connection to the disk. Not sure what it would take to allow hundreds of contestants to benefit from the best arrangement.
pulse7 3y ago
PCIe 3.0 x4 SSD runs at ~3500MB/s, PCIe 4.0 x4 SSD runs at ~7000MB/s and PCIe 5.0 x4 SSD runs at ~14000MB/s (yes - megabytes, not megabits)!

jiehong 3y ago

Very nice! Always use profilers! 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).

teo_zero 3y ago

The bottom line is: of you want performance in Java, code if it was C!

yread 3y ago

Here is the .net version https://github.com/noahfalk/1brc https://github.com/noahfalk/1brc a bit faster than fatest java still

pjmlp 3y ago
For the ultimate performance, so to speak, Valhala still needs to arrive into the JVM. So .NET has quite a few tricks that on Java side still require FFI, or clever use of Panama, maybe.
- anonymoushn 3y ago
  These tools won't really close the gap unless Panama's vector APIs get a big makeover.
  - pjmlp 3y ago
    Panama vector API is still in preview for a reason. And it depends on Valhala being done.

rldjbpin 3y ago

this was the most approachable commentary on a 1BRC submission i've read thus far. 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.