[ENHANCEMENT]: Robin Hood Hashing performance improvement - would a PR be welcome?
Maintainers usually reply within 2 days
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 35/100
- Issue type
- Feature
- Clarity
- Needs clarification
- Activity status
- Quiet
- Tech stack
- cpp
- Domain
- hpc, performance
Research direction
Start by reviewing the cited GPURobinHoodHashing comparison and blog post, then inspect how cuco::static_map currently exposes cuco::linear_probing and cuco::double_hashing. The issue needs maintainer guidance on whether Robin Hood hashing fits as another strategy and what structure a PR should follow; done would be an agreed implementation scope.
Written by the indexing model from the issue text.
Description
Is your feature request related to a problem? Please describe.
See below.
Describe the solution you'd like
I recently decided, mostly for fun, to challenge myself to re-implement a concurrent hashing table based on Robin Hood hashing that I designed and built in 2016 as part of a project on GPU-accelerated Latent Dirichlet Allocation, but never actually got to work.
This time, I did get it to work - and according to my benchmarks, the resulting table has higher get throughput than cuCollections' static_map with either linear probing or double hashing, by quite a bit at sufficiently high load factors.
Repo for this comparison: https://github.com/aterenin/GPURobinHoodHashing. I've also got a blog post around some of the ideas and why I found this exercise interesting: https://avt.im/blog/sculpting-fragile-glass/.
I don't know what Nvidia's policy on external contributions to this library is, but if there is interest, I'd love to contribute the core algorithmic ideas to cuCollections so that other people can use them. I'd image this would look like a third option like cuco::double_hashing or cuco::linear_probing but which would implement the Robin Hood strategy. It'd probably improve performance in static_map and possibly other data structures depending on how advanced your templating logic is.
Would a PR on this be welcome? If yes, I'll put one together - I'd appreciate pointers on the cleanest way to add this structure-wise in case you have any: I value high-quality code and will work to do everything the right way. If not, no worries, feel free to just close the issue. Please let me know either way.
Describe alternatives you've considered
No response
Additional context
No response
- Dominant language
- Cuda
- Stars
- 671
- Forks
- 122
- Avg merge
- 4d 19h
- Merged PRs (30d)
- 10
Getting set up
Starts the project's dev container in your browser, under your own GitHub account.
- No Dockerfile or Docker Compose file
- Has a pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from NVIDIA/cuCollections
-
Add cuco::detail::stream_sync(cuda::stream_ref) to centralize CCCL version-specific API namingMay be free again @0z5a claimed this 24 days ago, and no pull request is open. Open
Difficulty 2/5 1-3 hours Newbie friendliness 74/100
NVIDIA/cuCollections#840 · 1 comment ·
Maintainers usually reply within 2 days
-
nvidia-runners
Difficulty 1/5 1-3 hours Newbie friendliness 25/100
NVIDIA/cuCollections#853 ·
Maintainers usually reply within 2 days
-
good first issue P2: Nice to have type: improvement
Difficulty 4/5 3-5 days Newbie friendliness 38/100
NVIDIA/cuCollections#805 · 4 comments ·
Maintainers usually reply within 2 days
-
[FEA] Add MPSC/MPMC concurrent queueMay be free again @sleeepyjack claimed this 263 days ago, and no pull request is open. Opentype: feature request
NVIDIA/cuCollections#791 · 1 assignee ·
Maintainers usually reply within 2 days
-
good first issue helps: rapids P1: Should have topic: performance type: improvement
Difficulty 5/5 Over a week Newbie friendliness 35/100
NVIDIA/cuCollections#785 · 5 comments ·
Maintainers usually reply within 2 days
All issues in NVIDIA/cuCollections
Similar issues
-
Difficulty 2/5 Under an hour Newbie friendliness 80/100
-
rotg returns the wrong sign for r when a is zero and b is negativePossibly taken @lucbv claimed this 5 days ago. Openbug
Difficulty 1/5 Under an hour Newbie friendliness 92/100
kokkos/kokkos-kernels#3328 · 1 comment · 1 assignee ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 90/100
NumericalEarth/Breeze.jl#1051 ·
Maintainers usually reply within 1 day
-
[Bug]: copy-assigning a boundary condition does not compile: `Bc::operator=` assigns to the `const` reference `m_domain`Possibly taken @gouarin claimed this 3 days ago. Openbug good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
Maintainers usually reply within 1 day
-
amr bug 🔥 diagnostics outputs
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
PHAREHUB/PHARE#1348 · 1 comment ·
Maintainers usually reply within 1 day