NVIDIA / NVIDIA/cudf

[FEA] Improve efficiency for hash-based groupby aggregation framework

Open
#19,513 3 comments 0 reactions 1 assignee Claimed by @ttnghia View on GitHub
feature request Spark
Dominant language
C++
Stars
9.8k
Forks
1.1k
Avg merge
3d 6m
Merged PRs (30d)
278

Description

### Problem

The hash-based groupby aggregation framework seems to have some unnecessary overhead. Recently, I tried to implement a similar pipeline as a simplified version of it and my test runs in `120us` instead of `220us` as in the hash-based framework:

Image

vs:

Image

From the experiments, I believe that we can do better to optimize the pipeline, removing overhead to improve performance much further.

### Proposed implementation

There should be many places that can be optimized. The lists below is what I plan to do and could be modified over time:
* [X] https://github.com/rapidsai/cudf/pull/19670
* [X] Use a single thread for processing each row of each output column, instead of one thread for processing one row of all output columns: https://github.com/rapidsai/cudf/pull/19764
* [x] Write output to the dense result column instead of writing to the sparse result column then compacting it using a gather map: https://github.com/rapidsai/cudf/pull/19764
* [ ] Ignore computing null mask/null count for intermediate aggregations to reduce overhead when computing compound aggregations: https://github.com/rapidsai/cudf/pull/20736
* [ ] Implement `batch_null_count` to count nulls for multiple null masks by a single kernel call, and application in groupby aggregations: https://github.com/rapidsai/cudf/pull/20872
* [ ] [FEA] Use packed_columns to store results of temporary aggregations in hash-based groupby: #20938
* [ ] [FEA] Batch computation for compound hash-based groupby aggregations #20936
* [ ] Use CUDA stream pool to asynchronously compute the intermediate variables such as generating the global hash set and initializing output columns. These steps could have a significant amount of overhead at runtime. For example, when the number of output columns is several hundreds, the overhead of creating and initializing them can be more than half of the total runtime.
* [ ] For global memory kernel, launch the kernel with fewer blocks to reduce the atomic contention.

### Tested and failed
Here are the ideas that have been tested but didn't work out:
* ~~Perform segmented processing on the input keys/values instead of computing aggregations on the entire input ranges, which would fallback to the global memory code path if the input has too many rows that cannot be computed by the shared memory kernel.~~ Prototype implemented in https://github.com/rapidsai/cudf/pull/20605 but the added overhead makes the shared memory kernel always runs slower than the global memory kernel.

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.