The insert operation in cuco::dynamic_map fails when attempting to insert a duplicate key.

[iamlazy123]

When calling the insert method of cuco::dynamic_map, I found that it fails if the key already exists. Here is my test code:

using KeyType = int;
using ValueType = int;

int main() {
    // cout << "Hello, World!" << endl;
    int empty_key_sentinel = -1;
    int empty_value_sentinel = -1;

    auto map = cuco::dynamic_map<KeyType, ValueType>{100000,
                                          cuco::empty_key<KeyType>{empty_key_sentinel},
                                          cuco::empty_value<ValueType>{empty_value_sentinel}};


    // Insert
    std::size_t num_keys = 5;
    thrust::device_vector<KeyType> keys = {1, 2, 3, 4, 5};
    thrust::device_vector<ValueType> values = {10, 20, 30, 40, 50};
    auto pairs_begin = thrust::make_zip_iterator(cuda::std::tuple{keys.begin(), values.begin()});
    map.insert(pairs_begin, pairs_begin + num_keys);

    // Find
    std::size_t num_keys2 = 7;
    thrust::device_vector<KeyType> keys2 = {1, 2, 3, 6, 7, 4, 5};
    thrust::device_vector<ValueType> values2(num_keys2);
    map.find(keys2.begin(), keys2.end(), values2.begin());
    for (size_t i = 0; i < num_keys2; i++) {
      std::cout << "Before update[key:" << keys2[i] << "][val:" << values2[i] << "]" << std::endl;
    }

    // Update
    std::size_t num_keys3 = 4;
    thrust::device_vector<KeyType> keys3 = {1, 2, 10, 11};
    thrust::device_vector<ValueType> values3 = {101, 102, 103, 104};
    auto pairs_begin3 = thrust::make_zip_iterator(cuda::std::tuple{keys3.begin(), values3.begin()});
    map.insert(pairs_begin3, pairs_begin3 + num_keys3);
    for (size_t i = 0; i < num_keys3; i++) {
      std::cout << "Set kv-pairs[key:" << keys3[i] << "][val:" << values3[i] << "]" << std::endl;
    }

    // Find
    std::size_t num_keys4 = 7;
    thrust::device_vector<KeyType> keys4 = {1, 2, 3, 4, 11, 10, 5};
    thrust::device_vector<ValueType> values4(num_keys4);
    map.find(keys4.begin(), keys4.end(), values4.begin());
    for (size_t i = 0; i < num_keys4; i++) {
      std::cout << "After update[key:" << keys4[i] << "][val:" << values4[i] << "]" << std::endl;
    }

    return 0;
}

The output is:

Before update[key:1][val:10]
Before update[key:2][val:20]
Before update[key:3][val:30]
Before update[key:6][val:-1]
Before update[key:7][val:-1]
Before update[key:4][val:40]
Before update[key:5][val:50]
Set kv-pairs[key:1][val:101]
Set kv-pairs[key:2][val:102]
Set kv-pairs[key:10][val:103]
Set kv-pairs[key:11][val:104]
After update[key:1][val:10]
After update[key:2][val:20]
After update[key:3][val:30]
After update[key:4][val:40]
After update[key:11][val:104]
After update[key:10][val:103]
After update[key:5][val:50]

In the previous example, the insert operation did not overwrite the existing entries {1:10, 2:20} as expected when attempting to insert {1:101, 2:102}.

So what would be the proper way to implement this feature?

[PointKernel]

The behavior you observed is expected. If a key already exists in the hash table, reinserting it with a different value has no effect. To update the value associated with a key in dynamic_map, you’d need functionality similar to static_map::insert_or_assign:
https://github.com/NVIDIA/cuCollections/blob/dev/include/cuco/static_map.cuh#L430-L449.
@iamlazy123 could you please open a GitHub issue so we can track this properly?

[iamlazy123]

Thank you for the reply.

Here is the new issue: #732

[PointKernel]

Thank you for the reply.

Here is the new issue: #732

Thanks!

[sleeepyjack]

cuco::dynamic_map is far from as feature-rich as our static containers and needs a complete overhaul.

@iamlazy123 is it possible to switch your workflow to use cuco::static_map instead? You could estimate the size of the map using cuco::hyperloglog which gives you a close estimate of the number of distinct keys in your input data aka the number of slots to reserve for the hash table.

[iamlazy123]

Since the map size cannot be predetermined in my scenario, static_map is not an optimal solution.