How to implement hash map with a KeyValue type whose key is a idx and value maybe a coordinate

[erwangccc]

@nosferalatu Hi!

As the title says, i want to implement a hash table on GPU whose key is a idx and value maybe a coordinate( it has 4 value, maybe a ptr). I'll not insert a same coordinate when I find a there is a same coordinate at hash map.
And where should i modify to implement it. Maybe it's necessary to override the "==" operator?

Thanks!

[nosferalatu]

whose key is a idx and value maybe a coordinate( it has 4 value, maybe a ptr)

The hash table needs to be modified atomically. GPUs
have 64 bit atomics, so you can use that for value types up to 64 bits. For value type larger than 64 bits (like a 3D coordinate of floats), the value will need to be an array index or a pointer into another table that stores the actual value.

I'll not insert a same coordinate when I find a there is a same coordinate at hash map.

The simple GPU hash table implementation already has unique keys. If you do two inserts with the same key but different values, then the result will be one of the key/values in the hash table. But which key/value pair is unknown: they are happening in parallel, so it depends on which one is executed first by the GPU, which is entirely GPU dependent.

You could modify https://github.com/nosferalatu/SimpleGPUHashTable/blob/master/src/linearprobing.cu line 44 so that it only changes the value when the key is empty, like this:

if (prev == kEmpty)
{
    hashtable[slot].value = value;
    return;
}

if (prev == key)
{
    return;
}

That code will write a value to the slot only once. But again, that's not necessarily the first key/value. Depending on how the GPU executes the warps, the first value written to the slot might not be the first key/value pair in array of items to insert.

[zheng95z]

Hi @nosferalatu. First, thank you for this great tutorial!

I'm new to hash table & atomic stuffs, so I have a potentially stupid question here: why can't we save more than one values (like three values for coordiates) here?

Here is my understanding:

Let say we have this struct:

struct hash_cell{
    uint32_t key;
    uint32_t value_0;
    uint32_t value_1;
    uint32_t value_2;
}

And inside the intersection algorithm:

uint32_t prev = atomicCAS(&hashtable[slot].key, kEmpty, key);
if (prev == kEmpty || prev == key)
{
    hashtable[slot].value_0 = value_0;
    hashtable[slot].value_1 = value_1;
    hashtable[slot].value_2 = value_2;
    break;
}

Even if the values are required to be filled atomically (we could use InterlockedExchange here), I guess it's safe to have more than one value here?

I don't know what's wrong here, please do enlighten me.