Extend and improve `BlockTopK` for unordered `k`
- Dominant language
- C++
- Stars
- 2.5k
- Forks
- 486
- Avg merge
- 2d 6h
- Merged PRs (30d)
- 295
Description
This issue is a collection of potential further extensions and possible improvements to `BlockTopK`, following https://github.com/NVIDIA/cccl/issues/7092.
- [ ] Add option to extend and include tied keys across the k-th position in the results
- [ ] Evaluate unrolling loop over passes that finds the splitter prefix ([comment](https://github.com/NVIDIA/cccl/pull/7384#discussion_r2892281811))
- [ ] Evaluate use of BlockHistogram and BlockAdjacentDifference ([comment](https://github.com/NVIDIA/cccl/pull/7384#discussion_r2883889451))
- [ ] Clarify and evaluate use of `cuda::atomic` ([comment](https://github.com/NVIDIA/cccl/pull/7384#discussion_r2892220329))
- [ ] Reuse data already in registers from `compute_bin_offsets` in `choose_bucket` ([comment](https://github.com/NVIDIA/cccl/pull/7384#discussion_r2883944056))
- [ ] Add option to enforce not writing more than `k` items
- [ ] Benchmark whether we need to forceinline all the member functions and drop them if they're not beneficial
- [ ] Add support for custom keys
- [ ] Extend interface to pass constraints/guarantees on `k`
- [ ] Add support for passing items via shared memory (and `cuda::std::array`/`span`)
- [ ] Add support for passing items in strided/striped arrangement, returning items in strided/striped arrangement
- [ ] Add variant that materializes reduced candidate set while determining the splitter prefix
- [ ] Add optimized path for shorter-than-4B-key-types, where we pack key and value/index into a 4B word
- [ ] Consider splitting the branch that was unified in https://github.com/NVIDIA/cccl/pull/7384/commits/f96304e79bb0d8ac23c833461245c4655c48e148 again. It gave 2% slowdown in some cases.
Contributor guide
Assessment
This issue has not been assessed yet.