4 ms·
This has been super fun. My current PR[1] is another 15% faster than my entry in the README. Sadly I haven't been able to make any progress on using SIMD to acc
by spullara 3y ago
This has been super fun. My current PR[1] is another 15% faster than my entry in the README. Sadly I haven't been able to make any progress on using SIMD to accelerate any part of it.
I think the issues with hashing could be easily covered by having the 500 city names in the test data also be randomly generated at test time. There is no way to ensure there aren't hash collisions without doing a complete comparison between the names.
[1] https://github.com/gunnarmorling/1brc/pull/56 https://github.com/gunnarmorling/1brc/pull/56
- londons_explore 3y ago1 billion rows, 500 unique values... It becomes very possible to find an instance of each unique value, then runtime-design a hash algorithm where those 500 values don't collide. Java allows self modifying code after all (and this challenge also allows native code, which can also be compiled-at-runtime)
- spullara 3y agoYou have to compare the keys in order to figure out if you have a hash collision or a new key. Without first scanning the entire file to know what the list of keys are there isn't a way around it. Even determining that list of keys involves doing key comparisons for every row.