Compose thrust::find_if from a look-back prefix scan algorithm?

[lilohuang]

Hi @gevtushenko @jrhemstad and @miscco

Today, when I checked the thrust::find_if implementation, I noticed there is a code comment describing a TODO task about composing thrust::find_if from a look-back prefix scan algorithm and aborting the kernel when the first element is found. However, this code comment has been there for many years. I'm wondering whether there is a plan to realize it.

The existing implementation of thrust::find_if for the CUDA platform breaks up the sequence into separate intervals, which requires launching the reduce kernel multiple times with additional CUDA stream synchronization, which might be a little bit inefficient in some scenarios.

cccl/thrust/thrust/system/cuda/detail/find.h

Line 111 in b68256e

// XXX compose find_if from a look-back prefix scan algorithm

Thanks,
Lilo

[jrhemstad]

The existing implementation of thrust::find_if for the CUDA platform breaks up the sequence into separate intervals

Indeed, find_if uses the same implementation code path as all_of and other logical algorithms that attempt to early exit.

I wrote up quite a long time ago how this can lead to pretty poor performance: #720

It's definitely on our radar to reinvestigate the implementation of those algorithms. That will likely happen as part of or after #26.