NVIDIA / NVIDIA/cuCollections

[FEA] Add option to report hash collisions

Open
#70 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

type: feature request
Dominant language
Cuda
Stars
667
Forks
120
Avg merge
7d 5h
Merged PRs (30d)
4

Description

Is your feature request related to a problem? Please describe.
Hash collisions impact performance of hash map insert and probe. It will be useful to find a way to report the number of collisions for static_map and dynamic_map to help assess performance of insert or probe when developers are evaluating perf on their dataset. It would also allow developers to tune the hash function or occupancy to reduce collisions and find the right balance for their scenario.

Describe the solution you'd like
The map can have an optional template argument that specifies if we need to count collisions (disabled by default), so it's opt-in and doesn't impact perf for the standard case. The number of collisions would be stored in a class variable that's accessible with something like get_num_collisions(). Implementation: allocate memory for device variable uint64_t *d_num_collisions, update all insert and find device code to do atomicAdd(d_num_collisions, 1) to that variable, then copy the contents to the host variable after the kernel. Here is where we can count the collisions for no-CG static_map::find:
https://github.com/NVIDIA/cuCollections/blob/2196040f0562a0280292eebef5295d914f615e63/include/cuco/detail/static_map.inl#L252
The atomic will be guarded by the template argument check, so should only impact perf if we're asked to count collisions. Similarly, would have to update all other insert and find functions.

Describe alternatives you've considered
None.

Additional context
None.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start in include/cuco/detail/static_map.inl around the no-CG static_map::find path at line 252, then trace the other insert and find device functions mentioned in the issue. Define the opt-in collision-counting behavior across static_map and dynamic_map, ensuring the count is accessible on the host and disabled by default without affecting standard performance.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.