[ENHANCEMENT]: `for_each` on containers without duplicates keeps probing after the match
维护者通常 1 天内回复
已经有一个关联 PR 被合并了。
- #859 来自 @PointKernel —— 已合并
评估
调研方向
从 open_addressing_ref_impl 中标量版和协作版的 for_each 开始，定位到 equal_result::EQUAL 分支，并阅读 allows_duplicates 在那里是如何使用的。拟议的修改会在不允许重复的容器上，于回调之后停止探测，并保持 multiset 和 multimap 路径不变。运行 static_set、static_map、static_multiset 和 static_multimap 测试；测试通过且命中查找变快即完成。
由索引模型根据 Issue 内容生成。
描述
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
- 主要语言
- Cuda
- 星标
- 674
- 派生
- 123
- 平均合并
- 3 天 9 小时
- 30 天内合并 PR
- 10
环境准备
在浏览器里用你自己的 GitHub 账号启动这个项目的开发容器。
- 没有 Dockerfile 或 Docker Compose 文件
- 有 Pull Request 模板
- 阅读贡献指南
从这里开始
- 先读完整个 Issue，再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库，在一个分支上完成修改。
- 提交 Pull Request，并在描述里引用这个 Issue 编号。
NVIDIA/cuCollections 的其他 Issue
-
Add cuco::detail::stream_sync(cuda::stream_ref) to centralize CCCL version-specific API naming可能重新可做 @0z5a 于 30 天前认领，目前没有进行中的 PR。 未关闭
难度 2/5 1-3 小时 新手友好度 74/100
NVIDIA/cuCollections#840 · 1 条评论 ·
维护者通常 1 天内回复
-
nvidia-runners
难度 1/5 1-3 小时 新手友好度 25/100
NVIDIA/cuCollections#853 ·
维护者通常 1 天内回复
-
topic: performance type: feature request
难度 5/5 一周以上 新手友好度 35/100
NVIDIA/cuCollections#817 · 7 条评论 · 1 个 reaction ·
维护者通常 1 天内回复
-
good first issue P2: Nice to have type: improvement
难度 4/5 3-5 天 新手友好度 38/100
NVIDIA/cuCollections#805 · 4 条评论 ·
维护者通常 1 天内回复
-
[FEA] Add MPSC/MPMC concurrent queue可能重新可做 @sleeepyjack 于 269 天前认领，目前没有进行中的 PR。 未关闭maintainer-only type: feature request
NVIDIA/cuCollections#791 · 已指派 1 人 ·
维护者通常 1 天内回复
查看 NVIDIA/cuCollections 的全部 Issue
相似的 Issue
-
bug
难度 2/5 1-3 小时 新手友好度 85/100
MemberJunction/MJ#5864 ·
维护者通常 1 天内回复
-
URL round-trip through render_as_string drops query parameters with empty values可能已有人在做 @Nacl-HCl 今天认领。 未关闭
难度 2/5 1-3 小时 新手友好度 92/100
sqlalchemy/sqlalchemy#13697 · 1 条评论 ·
维护者通常 1 天内回复
-
C-bug O-community X-blathers-triaged
难度 2/5 1-3 小时 新手友好度 78/100
cockroachdb/cockroach#176150 · 1 条评论 ·
维护者通常 12 天内回复
-
bug
难度 2/5 1-3 小时 新手友好度 80/100
carverauto/serviceradar#5732 ·
维护者通常 1 天内回复
-
backend priority:P3 privacy-fix
难度 2/5 1-3 小时 新手友好度 78/100
维护者通常 1 天内回复