[ENHANCEMENT]: `for_each` on containers without duplicates keeps probing after the match
Maintainers usually reply within 2 days
A pull request for this has already been merged.
- #859 by @PointKernel — merged
Assessment
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Newbie friendliness
- 72/100
Research direction
Start in the scalar and cooperative for_each of open_addressing_ref_impl, at the equal_result::EQUAL case, and read how allows_duplicates is used there. The proposed change stops probing after the callback for non-duplicate containers and leaves the multiset and multimap paths alone. Run the static_set, static_map, static_multiset and static_multimap tests; done means they pass and hit lookups get faster.
Written by the indexing model from the issue text.
Description
Is your feature request related to a problem? Please describe.
On static_set/static_map, ref.for_each(key, cb) keeps probing after calling cb on the match, up to the next empty slot, although a key is held at most once there (find and contains already stop at the match). Every hit pays for the rest of its cluster:
// static_map<uint64_t, uint64_t> ref with cuco::op::for_each, 64 dependent lookups per thread
for (int i = 0; i < 64; ++i) {
uint64_t next = ~0ull;
ref.for_each(key, [&](auto const& slot) { next = slot.second; });
key = next;
}
RTX 4090, load factor 0.5, 167,936 threads, 2^17 slots: hits take 0.589 ms, 0.226 ms with the change below; misses are unchanged (0.34 ms).
Describe the solution you'd like
End the probe at the match when the container has no duplicates, in the scalar and cooperative for_each of open_addressing_ref_impl:
case detail::equal_result::EQUAL: {
callback_op(bucket_slots[i()]);
+ if constexpr (not allows_duplicates) { should_return = true; } // cooperative: empty = true
The multiset and multimap paths are unchanged. With it the static_set, static_map, static_multiset and static_multimap tests pass (415/415, sm_89).
🤖 Generated with Claude Code
- 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 23 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
-
topic: performance type: feature request
Difficulty 5/5 Over a week Newbie friendliness 35/100
NVIDIA/cuCollections#817 · 7 comments · 1 reaction ·
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 262 days ago, and no pull request is open. Opentype: feature request
NVIDIA/cuCollections#791 · 1 assignee ·
Maintainers usually reply within 2 days
All issues in NVIDIA/cuCollections
Similar issues
-
Difficulty 1/5 Under an hour Newbie friendliness 77/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
Wetzel402/Skylite-UX#125 ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
oracle/rust-oracledb#53 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 85/100
objectionary/eo-graphs#82 ·