4 ms·

> GPU Hash Table? How bad would performance have suffered if you sha256'd the lines to build the map? I'm going to guess "badly"? Maybe something like this in

• tspeterkim 3y 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 3y ago
    You could hash the city names using something like a djb2a algorithm?
  • mandarax8 3y 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 3y ago
      I 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__ 3y ago
    If 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.)