Sometimes you need to find the first element of an array that satisfies some property. This can be done with a
reduce composition, where the
map tags each element with its index and whether it is the element we are looking for, and then a reduction operator
op that picks the match with the lowest index one. While I know that
op is commutative, the compiler cannot figure this out on its own, so I use
reduce_comm to tell it explicitly. This permits slightly more efficient code generation for the reduction.
Note that if no element is acceptable, we return the index -1. An alternative could be to use a sum type to return the actual element we found:
Both of these solutions share a potential problem: they will always look at the entire array, even if the element we are looking for is near the beginning. When searching in parallel, some redundant (or “speculative”) work is necessary. But can we constrain it? We can of course always just write a sequential search:
No parallelism here. We can combine the sequential and the parallel approaches by writing a function that sequentially iterates through large chunks of the input, searches each chunk in parallel, and stops at the first match.
In most cases, the original
find_elem will be fast enough, as these simple
reduce compositions are quire efficient. While
find_elem_chunked can in some cases be faster, we now have the chunk size,
k, as a tunable parameter that we have to worry about, and the compiler cannot help us figure out the best value.