Skip to content

[ENHANCEMENT]: Avoid expensive modulo when advancing open-addressing probe iterators #837

Description

@sleeepyjack

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.

Metadata

Metadata

Assignees

Labels

topic: performancePerformance related issuetype: improvementImprovement / enhancement to an existing function

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions