NVIDIA / NVIDIA/cudf

[FEA] Improve `cudf::distinct` with cuco reduction map

Open
#13,157 4 comments 0 reactions 0 assignees View on GitHub
feature request libcudf Performance
Dominant language
C++
Stars
9.8k
Forks
1.1k
Avg merge
3d 6m
Merged PRs (30d)
278

Description

**Is your feature request related to a problem? Please describe.**
#11052 introduces the keep control option into `cudf::distinct` and makes it possible for users to perform a more efficient hash-based `drop_duplicates`. The PR uses a single hash map together with thrust algorithms to mimic the behavior of a reduction map. This whole process can be largely simplified once https://github.com/NVIDIA/cuCollections/pull/98 is ready. TODO:

- [ ] Replace `static_map` + `thrust` algos with `cuco::static_reduction_map` + `cudf::sort`
- [ ] Update Python bindings to use the hash-based algorithm
- [ ] Investigate the performance impact with various map occupancy and sort-based algo v.s. hash-based algo
- [ ] Minimize memory footprint

**Describe the solution you'd like**
Uses a `cuco::static_reduction_map` where the key is the row index and the value is the min/max index of equivalent rows (depending on the keep option).

**Describe alternatives you've considered**
We could also take a pair of row hash value and row index as the key which performs the expensive row hash computation only once for better runtime performance. This requires more memory footprint though. To be evaluated.

**Additional context**
#11656 may not be required by the new reduction map implementation.

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.