Is your feature request related to a problem? Please describe.
cuco::detail::probing_iterator::operator++ currently advances a probe with:
curr_index_ = (curr_index_ + step_size_) % upper_bound_;
The plain % here is expensive.
For dynamic extents, upper_bound_ uses fast_int, so every additional probe executes the
fast division/remainder path. This is still more expensive than necessary in a hot loop, especially
for unsuccessful lookups and high-occupancy tables where probe chains are longer.
The addition may also overflow the extent's integer type before the remainder is evaluated, even
though the mathematically reduced index is representable.
Describe the solution you'd like
Use the probing iterator invariants:
0 <= curr_index_ < upper_bound_
0 < step_size_ <= upper_bound_
Their sum can cross upper_bound_ at most once, so the update can be expressed without modulo or a
potentially overflowing addition:
auto const remaining = upper_bound_ - curr_index_;
curr_index_ = step_size_ >= remaining ? step_size_ - remaining
: curr_index_ + step_size_;
Additional context
PR #836 contains a prototype of this optimization while fixing the index-safety bug in #834.
A focused NVBench comparison of upstream/dev against that PR on an NVIDIA RTX PRO 6000 Blackwell
Max-Q (sm_120, CUDA 13.1.115, GCC 14.3, Release, 20 million int32_t keys) produced:
| Configuration group |
Cases |
Faster |
Unchanged |
Slower |
| Default extent, double hashing |
15 |
14 |
1 |
0 |
extent<int32_t>, double hashing |
21 |
21 |
0 |
0 |
extent<int32_t>, linear probing |
12 |
9 |
3 |
0 |
| Total |
48 |
44 |
4 |
0 |
Representative improvements:
- default-extent
contains at 0.8 occupancy: 8.9-10.3%;
- default-extent
find at 0.8 occupancy: 7.6-11.6%;
extent<int32_t> linear-probing lookups at 0.8-0.9 occupancy: 11.2-12.3%;
- insert at 0.9 occupancy: approximately 5%.
The largest improvements occur for high occupancy and non-matching lookups, which execute the most
iterator increments. Low-occupancy linear-probing cases were statistically unchanged.
Is your feature request related to a problem? Please describe.
cuco::detail::probing_iterator::operator++currently advances a probe with:The plain
%here is expensive.For dynamic extents,
upper_bound_usesfast_int, so every additional probe executes thefast division/remainder path. This is still more expensive than necessary in a hot loop, especially
for unsuccessful lookups and high-occupancy tables where probe chains are longer.
The addition may also overflow the extent's integer type before the remainder is evaluated, even
though the mathematically reduced index is representable.
Describe the solution you'd like
Use the probing iterator invariants:
Their sum can cross
upper_bound_at most once, so the update can be expressed without modulo or apotentially overflowing addition:
Additional context
PR #836 contains a prototype of this optimization while fixing the index-safety bug in #834.
A focused NVBench comparison of
upstream/devagainst that PR on an NVIDIA RTX PRO 6000 BlackwellMax-Q (
sm_120, CUDA 13.1.115, GCC 14.3, Release, 20 millionint32_tkeys) produced:extent<int32_t>, double hashingextent<int32_t>, linear probingRepresentative improvements:
containsat 0.8 occupancy: 8.9-10.3%;findat 0.8 occupancy: 7.6-11.6%;extent<int32_t>linear-probing lookups at 0.8-0.9 occupancy: 11.2-12.3%;The largest improvements occur for high occupancy and non-matching lookups, which execute the most
iterator increments. Low-occupancy linear-probing cases were statistically unchanged.