NVIDIA / NVIDIA/cudf

[FEA] Refactors and next steps for segmented reductions

Open
#10,432 6 comments 2 reactions 1 assignee Claimed by @davidwendt View on GitHub
0 - Backlog feature request libcudf
Dominant language
C++
Stars
9.8k
Forks
1.1k
Avg merge
3d 6m
Merged PRs (30d)
278

Description

This is issue contains a few proposals for improving the segmented reduction code introduced in #9621.

## Investigate sort-groupby aggregations
(Idea from @ttnghia)

With the ability to perform segmented reductions, sort-based groupby may be able to use [`group_offsets`](https://github.com/rapidsai/cudf/blob/57ff6f55b9fd44e8a8e10282d3f95d5f38e299ef/cpp/src/groupby/sort/sort_helper.cu#L188) to define its segments, rather than materializing a full column of sorted/monotonic [`group_labels`](https://github.com/rapidsai/cudf/blob/57ff6f55b9fd44e8a8e10282d3f95d5f38e299ef/cpp/src/groupby/sort/sort_helper.cu#L213). In effect, this allows us to replace a call to [`thrust::reduce_by_key`](https://github.com/rapidsai/cudf/blob/57ff6f55b9fd44e8a8e10282d3f95d5f38e299ef/cpp/src/groupby/sort/group_single_pass_reduction_util.cuh#L186) algorithm with a call to [`cub::DeviceSegmentedReduce::Reduce`](https://github.com/rapidsai/cudf/blob/7ff195677fc52ffc21e8c1060b0f270587d6995b/cpp/include/cudf/detail/reduction.cuh#L267), while eliminating the need to compute the `group_labels` column. I think this should be a more efficient algorithm, and also will require less intermediate memory allocation. Benchmarks should be performed when making this change.

## Refactor internal use of indices to 2N style (match CUB)

The indexing scheme used for segmented reduction is currently "N+1", like how list offsets are indexed. We want to refactor this to use "2N" indexing. This would align with `cub::DeviceSegmentedReduce::Reduce` and permit greater flexibility in the API internals. [See discussion here](https://github.com/rapidsai/cudf/pull/9621#discussion_r796250853) for details.

- @bdice: After discussion with @davidwendt, we decided this is not necessary in the short term. We can resolve this issue without changing the current implementation. The current implementation of N+1 aligns with segmented sort behavior. If there is a compelling need to change this in the future for expanded functionality, we can revisit.

## Compound reductions like mean

The segmented reduction code currently supports "simple" reductions. Support for "compound" reductions is needed. This includes multi-step calculations like mean, standard deviation, or sum of squares. Non-segmented compound reductions are defined here: https://github.com/rapidsai/cudf/blob/c1638869116aae2c6dde6024394279a2fb79e685/cpp/src/reductions/compound.cuh

## Fixes for output_type precision

@isVoid and I filed #9988 while working on #9621 because the documentation doesn't align with the implementation for when data is cast to the output dtype relative to when the reduction is performed. This affects segmented reduction as well.

## Explore rewriting `get_null_replacing_element_transformer` with nullate

It may be possible to clean up the [implementation of null element handling here](https://github.com/rapidsai/cudf/blob/7ff195677fc52ffc21e8c1060b0f270587d6995b/cpp/src/reductions/simple_segmented.cuh#L75-L85) by using [nullate](https://github.com/rapidsai/cudf/blob/c1638869116aae2c6dde6024394279a2fb79e685/cpp/include/cudf/column/column_device_view.cuh#L53).

- @bdice: After discussion with @davidwendt, we decided this is not worth changing. It might eliminate one or two lines of duplicate code but doesn't offer any benefits to compile time.

## Extend to more data types

We need to review the types supported by non-segmented reductions and ensure that segmented reductions support the same types. Decimal support has been requested here: https://github.com/rapidsai/cudf/issues/10417

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.