NVIDIA / NVIDIA/cccl

[FEA]: Extend cub::DeviceSegmentedSort to support custom comparators

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

Description

### Is this a duplicate?

- [X] I confirmed there appear to be no [duplicate issues](https://github.com/NVIDIA/cccl/issues) for this request and that I agree to the [Code of Conduct](CODE_OF_CONDUCT.md)

### Area

CUB

### Is your feature request related to a problem? Please describe.

I would like to be able to use `cub::DeviceSegmentedSort` with a custom comparison operator.

As @gevtushenko explained here https://github.com/NVIDIA/cccl/discussions/1061 this isn't possible today because the underlying implementation uses a radix-based sort.

### Describe the solution you'd like

We should add an overload of `DeviceSegmentedSort` that takes a custom comparator and dispatches to a non-radix-based implementation.

### Dependencies
- [ ] Extend `cub::BlockMergeSort` to support dynamically sized inputs (iterator-based API)

### Describe alternatives you've considered

The primary alternatives are:
- Materialize the concrete data compatible with radix-based sorting in memory
- Use `DeviceMergeSort` and embed the segment ids as part of the keys

### Additional context

The non-radix-based implementation of `DeviceSegmentedSort` would ideally use the existing Merge Sort functionality.

This means `DeviceSegmentedSort` with a custom comparator indirectly depends on extending `BlockMergeSort` to accept dynamically sized inputs (i.e., `[begin,end)` iterator-based API). This is because we need a variant of `BlockMergeSort` that can operate on segments larger than a single tile.

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.