News for hackers. Stuff that matters.
Re:The One Billion Row Challenge by weinzierl on Thursday January 04, 2024 @06:09AM (#38865623)
Unfortunately I have no time to code this up but things that I would try to make it fast:

- Read with O_DIRECT (but compare it with the mmap approach). I know O_DIRECT gets much hate, but this could be one of the rare cases where it helps.

- Use a simple array with sentinel and linear search for the station names. This is dumb, but if the number of stations is small enough this could beat the hash. (In the back of my head I have a rule of thumb that linear search is faster for up to 1000 elements, but I'm not sure anymore where I got this from).

Re:The One Billion Row Challenge by londons_explore on Thursday January 04, 2024 @06:16AM (#38865654)
linear search is never faster assuming your hash algorithm is cheap enough. However, if your list only contains 2 items, then your hash algorithm better be "Is first character > 'm'".

When you want real speed like this and are happy with insane complexity, code that writes and self-compiles a hash function based on the data can make sense.

Re:The One Billion Row Challenge by gpderetta on Thursday January 04, 2024 @08:57AM (#38866999)
> Read with O_DIRECT

apparently the challenge explicitly allow for warming up the os cache on a prior run, so O_DIRECT would be disadvantaged here as the working set fits in memory.

edit: also in my very simple tests a good hashmap can beat linear search already at <10 items. It depends a lot on the hash function cost.

Re:The One Billion Row Challenge by weinzierl on Thursday January 04, 2024 @10:06AM (#38867853)
> beat linear search already at <10 items

The sources I found corroborate this. My 1000 elements rule of thumb is apparently way off.

Re:The One Billion Row Challenge by dvko on Thursday January 04, 2024 @01:22PM (#38870426)
I tried the linear search by station name in my first naive approach. Using a hashmap was at least 2-3x as fast with the ~415 distinct keys in the 1BRC dataset.