3 ms·
So performance would increase since hashing is faster than binary-searching. However, the problem of collisions across threads and dealing with concurrent map
by tspeterkim 2y ago
So performance would increase since hashing is faster than binary-searching.
However, the problem of collisions across threads and dealing with concurrent map key insertions still remains. e.g. when two different cities produce the same hash (one at each thread), how can we atomically compare 100 byte city strings and correctly do collision-solving (using linear probe, for example - https://nosferalatu.com/SimpleGPUHashTable.html https://nosferalatu.com/SimpleGPUHashTable.html)
Atomic operations are limited to 32-bits.
- convivialdingo 2y agoYou could hash the city names using something like a djb2a algorithm?
- mandarax8 2y ago> Atomic operations are limited to 32-bits. I'm using 64bit atomics at work, are you on an old version of cuda or are some operations only supported on 32bit?
- tspeterkim 2y agoI misspoke. (got confused with the key limit in my link above) Atomics work up to 128-bits (https://docs.nvidia.com/cuda/cuda-c-programming-guide/#atomic-functions https://docs.nvidia.com/cuda/cuda-c-programming-guide/#atomi...). Regardless, it's still less than 100 bytes, which is the max length of city strings.
- Sesse__ 2y agoIf the set of cities is known (as your binary search algorithm assumes), you can insert all of them first, on the CPU. That will resolve all collisions ahead of time, making the structure of the hash table essentially read-only. (Of course, you would still need atomics for the values.)