Closed tcbrindle closed 3 weeks ago
@brycelelbach Don't worry, I'm not going to change anything out from under you: even if I get this all done and it shows an improvement, I'll wait till you've finished your work on #92 and then update cartesian_product
to use the new protocol if necessary
Patch coverage: 100.00%
and project coverage change: -0.03%
:warning:
Comparison is base (
0a0abbb
) 97.67% compared to head (9901983
) 97.65%.
:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.
@tcbrindle sounds good - I'll try to get you an updated PR sometime next week.
@tcbrindle On the topic of improving the internal iteration protocol, I'd like to see the protocol evolved to better support parallelism in the future. I'd love to use flux to prototype a next generation parallel algorithms library.
The customization point today, for_each_while
, is an early-exit for
loop abstraction.
In the non-parallel case, we can implement non-early-exit algorithms like for_each
in terms of for_each_while
with essentially zero cost. The inverse is not true; we can't implement early-exit algorithms like find
in terms of a non-early-exit for_each
.
However, in parallel, implementing non-early-exit algorithms like for_each
in terms of for_each_while
is NOT zero cost. To parallelize, you'd have to have some sort of concurrent rollback or cancellation mechanism. On some platforms, like GPUs, it's actually more efficient to implement parallel early-exit algorithms like find
by NOT actually exiting early.
Some options:
for_each
and for_each_while
.for_each_while
that indicates whether or not early-exit is needed.I'd love to use flux to prototype a next generation parallel algorithms library.
That would be awesome!
Some options:
- Have two customization points, for_each and for_each_while.
- Add a compile time parameter to for_each_while that indicates whether or not early-exit is needed.
I guess in general we'd want some way to indicate that we want parallel execution (for all algorithms where it's possible), perhaps something like the standard execution policies? In that case we could say that for_each_while
(or iterate_while
), when passed a non-sequential execution policy, doesn't do early termination. Would that be sufficient?
This has bitrotted, and I have better ideas for how to solve the problem
This is an experimental PR to try out the ideas in #99, namely replacing the existing
for_each_while(seq, pred) -> cursor_t
customisation point with a new pair of customisation points:The idea being that this will allow us to use internal iteration in more places.
A rough plan of action:
flux::iterate_while
wrapper functionsflux::for_each_while
usingiterate_while
for_each_while
custom implementations withiterate_while
customisations:T[N]
std::reference_wrapper
ranges::contiguous_range
simple_sequence_base
chain_adaptor
cycle_adaptor
filter_adaptor
flatten_adaptor
map_adaptor
passthrough_traits_base
reverse_adaptor
scan_adaptor
scan_first_adaptor
take_adaptor
take_while_adaptor
array_ptr
range_sequence
repeat_sequence
single_sequence
unfold_sequence
fold_first
to useiterate_while
iterate_while
forsubsequence
iterate_while