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.
> 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.
> beat linear search already at <10 items
The sources I found corroborate this. My 1000 elements rule of thumb is apparently way off.
- 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).