[FEA] Improve cudf::gather scalability as number of columns increases
- Dominant language
- C++
- Stars
- 9.8k
- Forks
- 1.1k
- Avg merge
- 3d 6m
- Merged PRs (30d)
- 278
Description
As the number of columns increases for `cudf::gather` with the same gather map, we see the number of kernels called increase proportionally and the runtime increases linearly. We are wondering if there are better ways to group or "batch" these calls so we perform less kernel invocations that can do more work all at once, in hopes of amortizing some of the cost with many columns or deeply nested schemas.
A very simple example is below. This creates a column of 10 `int32_t` rows and adds it to a struct N times (where `N` is between 2 and 1024):
```c++
#include
#include
#include
#include
#include
#include
#include
#include
#include
int main(int argc, char** argv)
{
rmm::mr::cuda_memory_resource cuda_mr{};
rmm::mr::pool_memory_resource mr{&cuda_mr};
rmm::mr::set_current_device_resource(&mr);
using col_t = cudf::test::fixed_width_column_wrapper;
auto const values = std::vector{1,2,3,4,5,6,7,8,9,10};
for (int num_cols = 2; num_cols <= 1024; num_cols *= 2) {
std::vector> members(num_cols);
for (auto i = 0; i < num_cols; ++i) {
auto wrapper = col_t(values.begin(), values.end());
members[i] = wrapper.release();
}
auto struct_col = cudf::test::structs_column_wrapper(std::move(members));
auto gather_map = std::vector{1}; // gather 1 row
std::stringstream msg;
nvtxRangePush(msg.str().c_str());
auto result = cudf::gather(
cudf::table_view{{struct_col}},
cudf::test::fixed_width_column_wrapper(gather_map.begin(), gather_map.end()),
cudf::out_of_bounds_policy::NULLIFY);
nvtxRangePop();
std::cout << "Result: rows: " << result->num_rows() << " cols: " << result->num_columns() << std::endl;
}
return 0;
}
```
As the column count increases by 2x, the gather kernel takes 2x longer:

A similar argument can be made for columns that have nested things like arrays of structs (each with array members). The number of calls to underlying cub calls can increase drastically.
I am filing this issue to solicit comments/patches to see how we could improve this behavior.
Contributor guide
Assessment
This issue has not been assessed yet.