[FEA] New probing scheme concept
Nobody has claimed this yet.
- Dominant language
- Cuda
- Stars
- 667
- Forks
- 120
- Avg merge
- 7d 5h
- Merged PRs (30d)
- 4
Description
Part of #110 (Refactor of open address data structures)
Development branch: NVIDIA/cuCollections/refactor
Synopsis
Given a key k, a probing sequence provides a sequence of N potentially non-contiguous locations (or values) [i0, i1, i2, ... iN, EMPTY_SENTINEL] where if k exists it is present in [i0, iN].
TODOs
- Implement classes
cuco::probing_schemes::linear_probingandcuco::probing_schemes::double_hashing - Provide an option for windowed, i.e., vectorized probing via customization point object
- Enable cooperative probing
Backlog
- Use C++20-style ranges with sentinels
References
- https://godbolt.org/z/9bosKoW4v (distinct "ProbingScheme" and "Storage" concepts)
- https://godbolt.org/z/Maxe7j1o4 (probe iterator)
- https://godbolt.org/z/557fjcvvE (equality wrapper)
Contributor 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.
Research direction
Start with the refactor development branch and the existing cuco::probing_schemes::linear_probing and double_hashing classes. Review the linked Godbolt examples for the ProbingScheme, Storage, probe iterator, and equality-wrapper concepts, then investigate the unchecked windowed probing customization point and the C++20-style ranges backlog. Done means the selected probing-scheme concepts and requested option are defined consistently with the refactor.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- backend
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100