PointKernel opened a new pull request, #14:
URL: https://github.com/apache/datasketches-cuda/pull/14
## Description
Alternative to the block-local duplicate filter in #12, offered so both can
be reviewed side by side.
This PR replaces the direct-mapped block-local cache in the Theta screen
kernel with an exact set built on cuCollections open addressing in shared
memory, and adds the benchmark harness and the measured comparison behind the
choice.
Stacked on #12. The reviewable surface is
`include/datasketches/cuda/detail/theta/dedup_filter.cuh`; everything else in
the diff is the Theta migration already under review there.
### Why an exact set
A direct-mapped cache gives each hash exactly one slot, so two hashes that
collide evict each other and it forgets constantly. An exact set does not: an
insert both tests membership and claims ownership, so it should catch strictly
more duplicates before they reach the radix sort.
### Why it needs an occupancy guard
Open addressing degenerates as it fills, and a full table is worse than
slow. `insert` returns a bare `bool`, so a false result means either "already
present" or "no room left", and those require opposite actions. Treating full
as duplicate drops distinct hashes and silently corrupts the sketch; emitting
on every false gives up nearly all deduplication.
This does not resolve the ambiguity, it prevents it. A block-scope counter
tracks occupied slots, and above half load the filter stops consulting the
table and emits. No probe ever runs against a table that could be full, so a
failed insert is unambiguously a duplicate. Degrading to pass-through rather
than resetting keeps cost proportional to benefit: input distinct enough to
saturate the table has no duplicates left to find, and a reset would buy a
fresh table for that same input at the price of a block-wide barrier.
Sizing the table to avoid the problem is not available. A block is handed
2048 keys, so holding them all at 50% load needs 4096 slots, which at a 16-byte
slot is 64 KiB against a 48 KiB per-block limit.
### The slot is the key alone, and that required private API
`fixed_capacity_map_ref` stores a `pair<uint64_t, uint32_t>` slot that pads
to 16 bytes. This filter never reads the payload. Using
`__open_addressing_ref_impl` and `__slot_storage_ref` directly with an 8-byte
key-only slot halves the table and is worth 6.7%, the single largest
improvement found.
**This is the main thing I want reviewed.** Depending on cuco internals is
not something to merge lightly. It is also the strongest evidence that the
public API cannot express this filter efficiently today, and the concrete ask
is a public key-only set ref over caller-provided storage.
### Results
B200, CCCL `cba1df57`, 120 configurations per variant (`{cold, warm}` x
`{U32, U64, F32, F64}` x `{2^20, 2^24, 10^8}` keys x 6 arrival distributions x
`lg_k {12, 20}`), three interleaved repeats on one idle GPU. Speedup against no
filter, so above 1 is faster. Run-to-run spread on identical code is about 0.7%.
| Filter | geomean r1 / r2 / r3 | mean | worst | local dups | no local dups
| warm only |
|---|---|---|---|---|---|---|
| direct-mapped, 1024 slots (#12) | 1.193 / 1.193 / 1.195 | **1.194** | 0.79
| 1.545 | 0.922 | 1.082 |
| cuco open-addressing set (this PR) | 1.136 / 1.149 / 1.151 | **1.145** |
0.70 | 1.497 | 0.877 | 1.039 |
| cuco open-addressing map | 1.068 / 1.068 / 1.082 | **1.073** | 0.55 |
1.404 | 0.820 | 0.968 |
Head to head, the set is at 0.959 of the direct-mapped cache, i.e. **the
direct-mapped filter is 4.2% faster**, and the set wins 54 of 360 measured
configurations.
### The honest recommendation
I am not asking to merge this over #12 on the numbers. The set is correct
everywhere, never falls off the open-addressing cliff, and reaches 1.497 on the
duplicate-heavy inputs it exists to serve, but it is 4.2% behind ten lines of
direct-mapped cache that carry no library dependency. The reason is that the
free `__match_any_sync` warp stage that runs before either structure has
already removed most of the duplicates worth removing.
It is worth reviewing anyway because it establishes what a correct use of a
shared-memory hash table costs here, it rules out the historical
open-addressing failure as a capacity-control bug rather than anything
intrinsic, and it produces a concrete API ask for cuco.
`docs/theta/filter_comparison.md` has the full matrix, the screen-kernel
counters, and the four APIs that would change the answer.
### Also in this PR
- A key-type axis and a named arrival-distribution axis on the update
benchmark. Duplicate count and duplicate locality are separate properties, and
a benchmark varying only one cannot tell an optimization that exploits locality
from one that does nothing.
- The filter behind a small interface so alternatives are a one-file change.
- nvbench pinned, so the harness cannot drift between runs of a multi-branch
comparison.
## Checklist
- [x] Builds with `-DCMAKE_CUDA_ARCHITECTURES=100` against the pinned CCCL
- [x] All 15 test binaries pass, including `THETA_TYPED_PARITY_TEST` byte
parity against the CPU sketch
- [x] `upstream/main` merged and re-tested before push
- [ ] Reviewer input wanted on the dependency on cuco internals
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
