Repository navigation
[cudax][cuco] Lookups should be able to return values, not just slots #12489
Description
Problem
Every per-element lookup in cuda::experimental::cuco returns an iterator into live slot
storage: find on fixed_capacity_map_ref, insert_and_find on both containers. For the common
case, reading what matched, that is the wrong default.
- The caller pays a second random load to dereference it. A value-returning form pays nothing
extra, because the slot is already in registers for the key comparison. - Iterators are invalidated by
clear()and by destruction. Values are not. - The iterator is mutable, so it is also a way to corrupt the table.
- Under heterogeneous equivalence the stored key is the interesting half of a match, and
fixed_capacity_map::findcannot return it at all: it writes mapped values only.
fixed_capacity_set has no find in any form, so there is no way to retrieve a stored key
without inserting. That is visible in
#12382, which adds insert_and_find to the set as
part of the migration tracked in #11128.
Proposal
A second family of lookups returning materialized values, which most callers should reach for.
Iterators stay for the cases below. Both families exist per element on the *_ref and as host
bulk operations.
| Family | Operations | Returns |
|---|---|---|
| Value | get, insert_and_get |
a copy of the stored element (slot_type) |
| Slot | find, insert_and_find |
an iterator into slot storage |
Use the slot family to update payloads in place (atomics on it->second), to recover a slot
index with it - begin(), or for elements large enough that a pointer beats a copy. Callers
narrow a result with a projecting output iterator, not with extra API surface.
Making keys const throughout is a smaller cleanup in the same direction, included below.
This breaks source compatibility with the standalone cuCollections API, deliberately: the
containers are still experimental, and this is the cheapest point to fix the shape.
Types
| Today | Proposed | |
|---|---|---|
Set value_type |
K |
K |
Set iterator / const_iterator |
K* / const K* |
const K* for both, as std::set |
Map value_type |
pair<K, T> |
pair<const K, T> |
Map iterator / const_iterator |
pair<K, T>* / const pair<K, T>* |
pair<const K, T>* / const pair<const K, T>* |
slot_type, materialized |
— | K (set), pair<K, T> (map) |
A value_type with a const member is not assignable, so values and bulk output ranges use
slot_type. Set begin(), end() and data() become const-qualified. Map find gains the
usual iterator / const_iterator overload pair; today one const method returns a mutable
iterator.
Device API, per element
Cooperative-group overloads return the same types.
| Set today | Set proposed | Map today | Map proposed | |
|---|---|---|---|---|
insert(v) |
bool |
bool |
bool |
bool |
contains(p) |
bool |
bool |
bool |
bool |
get(p) |
— | K |
— | pair<K, T> |
insert_and_get(v) |
— | pair<K, bool> |
— | pair<pair<K, T>, bool> |
find(p) |
— | const_iterator |
iterator |
iterator / const_iterator |
insert_and_find(v) |
pair<const_iterator, bool> |
unchanged | pair<iterator, bool> |
unchanged |
insert stays the cheap form that returns only bool. The _find and _get suffixes say what
else comes back; the insert half is conditional, the lookup half is not.
Host API, bulk and stream-based
Results go to output ranges; each form has an _async variant.
| Set today | Set proposed | Map today | Map proposed | |
|---|---|---|---|---|
insert |
size_type |
size_type |
size_type |
size_type |
contains |
bool per probe |
same | bool per probe |
same |
get |
— | K per probe |
— | pair<K, T> per probe |
insert_and_get |
— | K + bool |
— | pair<K, T> + bool |
find |
— | const K* per probe |
T per probe |
pair<const K, T>* per probe |
insert_and_find |
stored key + bool |
const K* + bool |
T + bool |
pair<const K, T>* + bool |
Today's map find, which writes mapped values only, becomes get plus a projecting iterator:
same output bytes, and a default that is correct under heterogeneous equivalence.
Miss and full container
| Value family | Slot family | |
|---|---|---|
| Not found | empty_key_sentinel (set), {empty_key, empty_value} (map) |
end() |
| Insert into a full container | {empty slot, false} |
{end(), false} |
Activity