NVIDIA / NVIDIA/cccl

Consider dropping `DeviceSegmentedRadixSort` by adding an overload for begin and end bits in `DeviceSegmentedSort`

Open
#6,609 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
2.5k
Forks
486
Avg merge
2d 6h
Merged PRs (30d)
295

Description

`DeviceSegmentedSort` is almost always preferred to `DeviceSegmentedRadixSort`. From [the docs](https://nvidia.github.io/cccl/cub/api/structcub_1_1DeviceSegmentedSort.html):

>Differences from DeviceSegmentedRadixSort

>DeviceSegmentedRadixSort is optimized for significantly large segments (tens of thousands of items and more). Nevertheless, some domains produce a wide range of segment sizes. DeviceSegmentedSort partitions segments into size groups and specialize sorting algorithms for each group. This approach leads to better resource utilization in the presence of segment size imbalance or moderate segment sizes (up to thousands of items). This algorithm is more complex and consists of multiple kernels. This fact leads to longer compilation times as well as larger binaries sizes.

For the next release, we should consider removing `DeviceSegmentedRadixSort` and just adding an overload to `DeviceSegmentedSort` that accepts the begin and end bits. If those are specified, we would dispatch segmented radix sort, while using the normal segmented sort in other cases. Some considerations:

1. Is `DeviceSegmentedSort` better in all cases? We should benchmark this to verify
2. `DeviceSegmentedSort` is currently not graph capturable. It would be bad practice to only be able to graph capture when the begin and end bits are specified.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.