Can you provide more details on how that would work? Given that the input is CSV rows and not an array of integers alone, and the fact that getting to the next row is dependent on finding the delimiter in the current row.
It's quite a bit more than that, just the code discussed in the post is around 20 instructions, and there's a bunch more concerns like finding the delimiter between the name and the temperature, and hashtable operations. All put together, it comes to around 80 cycles per row.
When explaining the timing of 1.5 seconds, one must take into account that it's parallelized across 8 CPU cores.
I wonder what you mean here. What code exactly would get auto-vectorized? Parsing the temperature surely not, since it's not in an array of fixed-size fields.
There are many variations of the original code used in different solutions. Many of them return the temperature like the variant used in the post, but they split out the part that finds the decimal dot into a separate function. Then you can reuse that twice: to finish parsing the temperature, and to advance the cursor to the next row.
The temperature fields are interleaved with name fields, so I don't think you'd get any extra benefit from SSE. Also, since the temperature field is variable-sized, it would probably not pay off even if it was stored by column.
SSE was successfully applied to finding the delimiter between the name and the temperature, though.
This post explains a piece of code that appeared on the recent One Billion Row Challenge, it parses a variable-layout string whose bytes are packed into a single 64-bit variable, and doesn't use any if statements to achieve it. The string represents a decimal number from the range [-99.9, 99.9].
The general class of techniques used is called SWAR -- SIMD Within A Register, because it uses the regular ALU instruction set to achieve the effect of SIMD (Single Instruction, Multiple Data).
The code in question was submitted by Quan Anh Mai (@merykitty on GitHub).
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).
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.
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.
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.
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!
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.
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.
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.
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.
Here are some examples where user consent is undisputed: ride hailing, bicycle rental, street navigation, running/biking/sailing contests, location-sensitive searches. These are the kinds of applications for which Hazelcast Jet offers easy scaling into millions of users.
The point is that Jet can track several million distinct keys, even on a single machine, and finding velocity vectors boils down to linear regression sliding window against two FP variables.
If your concern is why you would specifically want to track locations, the answer is that there are plenty location-based apps that track locations with user's consent.
Beam is just an API layer with different backing implementations. But you don't typically use Beam to work with Jet, instead you use its own Pipeline API which is mostly like Java Streams. Jet will also soon get an SQL API.