3 ms·
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
by weinzierl 3y ago
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).
- londons_explore 3y agolinear 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.
- gpderetta 3y ago> 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.
- weinzierl 3y ago> beat linear search already at <10 items The sources I found corroborate this. My 1000 elements rule of thumb is apparently way off.
- dvko 3y agoI 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.