haxen

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.

I think it would work if that was the only code in the loop. But the loop spans several more nontrivial operations, including hashtable insertion.

> maybe 4 cycles worth in this optimized version?

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!