Potential speedup for count_if and suggested reduce_if
- Dominant language
- C++
- Stars
- 2.5k
- Forks
- 486
- Avg merge
- 2d 6h
- Merged PRs (30d)
- 295
Description
The current implementation of count_if uses a transform_reduce where the predicate is used to drive a 0-1 output which is then added up.
The computation could be sped up by discovering (per thread-block and warp) that no element returned 1, thus this warp/thread block does not need to participate in the reduction.
The implementation could also make use of a modified "reduce", called "reduce_if" which would apply a predicate to each element and discard those for which the predicate is false.
Having a reduce_if will have other benefits. It would allow skipping a separate copy_if step required when only some elements should be summed up (say).
See http://stackoverflow.com/questions/23334793/conditional-reduction-in-cuda for a discussion on this particular example.
Here is some real-world code that makes use of a (hand-crafted) conditional reduction: https://github.com/victorprad/InfiniTAM/blob/master/InfiniTAM/ITMLib/Engine/DeviceSpecific/CUDA/ITMDepthTracker_CUDA.cu#L113
In that code, each thread computes a summand (consisting of A[] and b) which is only used when the function constructing it returns "isValidPoint = true". The whole thread-block votes in "**shared** bool should_prefix" whether it has to participate in the reduction, which is the case only when at least one thread had "isValidPoint == true". Otherwise the threadblock can terminate early.
It might be beneficial to refine this vote a little bit to be computed per-warp, such that some warps can exit early.
Contributor guide
Assessment
This issue has not been assessed yet.