Hacktoberfest 2026：メンテナが10月に向けて印を付けた、オープンで初心者向けの issue。 Hacktoberfest の issue を見る

[ENHANCEMENT]: `for_each` on containers without duplicates keeps probing after the match

クローズ 初心者向け
  • 何か問題がありますか？
#858 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 2 日以内に返信

関連するプルリクエストがすでにマージされています。

  • #859 @PointKernel による — マージ済み

評価

難易度
2/5
見積もり時間
1〜3時間
初心者へのやさしさ
72/100
issue の種類
機能追加
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
cpp
領域
databases

調査の方向性

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
スター
671
フォーク
122
平均マージ
4日 19時間
マージ済み PR（30日）
10

環境構築

Codespaces で開く

このプロジェクトの開発コンテナを、あなたの GitHub アカウントでブラウザ上に起動します。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

NVIDIA/cuCollections のほかの issue

NVIDIA/cuCollections の issue をすべて見る

似ている issue

Databases の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。