Use Onesweep Radix Sort for U{8,16}
- Dominant language
- C++
- Stars
- 2.5k
- Forks
- 487
- Avg merge
- 2d 7h
- Merged PRs (30d)
- 296
Description
Currently, [onesweep](https://arxiv.org/pdf/2206.01784.pdf) algorithm is used for Pascal+ on a condition that `sizeof(KeyT) >= sizeof(uint32_t)`. Preliminary benchmarks show that onesweep is significantly faster for U{8,16} as well:
```
## [0] NVIDIA GeForce RTX 3090
| T | Elements | Ref Time | Ref Noise | Cmp Time | Cmp Noise | Diff | %Diff | Status |
|----------|------------|------------|-------------|------------|-------------|--------------|---------|----------|
| I8 | 2^16 | 34.866 us | 5.92% | 19.881 us | 5.38% | -14.985 us | -42.98% | FAIL |
| I8 | 2^20 | 43.454 us | 1.16% | 26.592 us | 1.99% | -16.863 us | -38.81% | FAIL |
| I8 | 2^24 | 235.937 us | 0.38% | 108.105 us | 1.31% | -127.832 us | -54.18% | FAIL |
| I8 | 2^28 | 3.351 ms | 1.48% | 1.330 ms | 0.67% | -2021.061 us | -60.31% | FAIL |
| I16 | 2^16 | 49.374 us | 1.26% | 32.574 us | 1.51% | -16.799 us | -34.03% | FAIL |
| I16 | 2^20 | 77.932 us | 1.56% | 44.806 us | 1.28% | -33.126 us | -42.51% | FAIL |
| I16 | 2^24 | 528.558 us | 0.58% | 321.376 us | 0.89% | -207.182 us | -39.20% | FAIL |
| I16 | 2^28 | 7.076 ms | 0.65% | 4.810 ms | 1.08% | -2265.630 us | -32.02% | FAIL |
```
I suggest we benchmark onesweep on a wider range on GPUs and switch to it completely. If there's no performance regressions, we should remove old implementation.
Contributor guide
Research direction
Start by locating the Pascal+ radix-sort path that selects onesweep only when sizeof(KeyT) >= sizeof(uint32_t), then benchmark U8 and U16 across a wider GPU range. Compare the results with the existing implementation and check for regressions; done means using onesweep for these key sizes and removing the old implementation only if performance remains favorable.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- performance
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100