[QST] Is there any plan to support insert empty_key_sentinel in static_map?

[OliverLPH]

The origin question is situated within cudf issue #14896. As the maintenance of GPU hash tables will be transferred to the cuCollections repo, so I migrate the question here.

Based upon the response to issue.
@PointKernel Hi, I just realize that if solely remapping the sentinel value may give rise to additional issues, as illustrated in the figure below.

If the remapped value of the empty_key_sentinel is equal to a key(key2) value already existed in insert_pair, key2 and empty_key_sentinel will occupy the same slot in slot_contents, which is not acceptable.

In the case, I think if extend slot_contents with an additional slot and storing empty_key_sentinel pair at the end might be a better solution?

[PointKernel]

key2 and empty_key_sentinel will occupy the same slot in slot_contents

They will not.

The "get current_slot" process only indicates the starting point for a given key and doesn't determine the actual insertion place. If that initial slot is empty (a.k.a equal to the sentinel value), the key will be inserted. Otherwise, we will follow a certain pattern (probing scheme) to find the next empty slot and insert the key/value there.

Can you provide more details on your use case so we can understand the problem better? e.g. What's the key type and payload type? Are you using the device singular API or host bulk API?

[OliverLPH]

Many Thanks for your reply.

What's the key type and payload type?

key type: uint64_t
payload type: int32_t
Actually, I am not using the latest cuco implementation. Instead, I am using an older version within cudf. But I noticed the implement logic is almost the same, so this problem should still exist.

Are you using the device singular API or host bulk API?

I'm not very sure, what are the differences between device singular API and host bulk API?

The "get current_slot" process only indicates the starting point for a given key and doesn't determine the actual insertion place. If that initial slot is empty (a.k.a equal to the sentinel value), the key will be inserted. Otherwise, we will follow a certain pattern (probing scheme) to find the next empty slot and insert the key/value there.

Yes, I understand your point. But my problem is not followed this procedure.
To make the problem elaborate more easier, let's assume that the hash output is very simple.

insert_k	hash(k)	capacity_	hash(k) % capacity_
1	1	10	1
2	2	10	2
11	11	10	1
-1(sentinel value)	21	10	1

In this scenario, 1, 11 and -1 will be located in the same slot.
If 1 is inserted first, 11 would need to find the next empty slot for insertion, and the same would apply to -1(sentinel value).
However, if -1(sentinel value) is inserted first, then when 1 or 11 are inserted, they would consider this position as unoccupied, potentially overwriting the value inserted by -1(sentinel value).

If this situation occurs, when attempting to find -1(sentinel value), it would return a default value of slot instead of the inserted value of -1(sentinel value).

To sum up, this is the origin problem I met. Additionally, remapping -1(sentinel value) might lead to another issue like this

insert_k	remap	hash(k)	capacity_	hash(k) % capacity_
1		1	10	1
2		2	10	2
11		11	10	1
-1(sentinel value)	11	11	10	1

After the remap, if -1(sentinel value) equals another inserted key(11), it will disrupt the lookup results.

[PointKernel]

Please do not insert sentinels.

Sentinel values are reserved values and they must be never present in your input data. Attempting to insert them is an undefined behavior.

Whenever one needs to insert sentinels, it's time to take a step back and revise the algorithm. A common workaround is to use the hash map as an indirection mapping table to the original input, e.g. https://godbolt.org/z/s96e5z7bn:

• the actual keys inserted in the map are indices of your original key array
• -1 is a valid sentinel value since you will never access to keys[-1] in your problem
• any original keys can be inserted/queried without worrying about conflicts against sentinels
• custom hasher and key_equal are needed to hash and compare original keys based on the index (or actual key)

As you may notice, the whole logic can be further simplified by just inserting indices in a hash set since the payload can be retrieved via indices as well: https://godbolt.org/z/zhTzKqo5h

[OliverLPH]

Thank you so much. I believe this workaround should solve my problem. I will give it a try.