Adapt all parallel algorithms to Ranges TS

[hkaiser]

The proposed ranges library includes slight (mostly non-breaking) changes to the standard algorithms. Those are described in N4569: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/n4569.pdf

Edit: here is an updated version of this document: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4685.pdf

We should adapt our algorithms to conform to this proposal (as much as possible).

Here is the list of algorithms which need to be adapted:

• adjacent_difference (Adjacent #5564)
• adjacent_find (Adapt adjacent_find to C++20 #4996)
• all_of any_of none_of (Adapted parallel::{all_of|any_of|none_of} for Ranges TS (see #1668) #2985)
• copy copy_if copy_n ( Adding first batch of container algorithms  #1911)
• move (Added range version of parallel::move #3028)
• count count_if (Adapted parallel::{count|count_if} for Ranges TS (see #1668) #3169)
• equal (Adapting hpx::equal to be conforming to C++20 #4883) mismatch (Adapting mismatch to C++20 #4884)
• exclusive_scan (Adapt exclusive_scan to C++20 #5436) inclusive_scan (Adapt inclusive_scan to C++ 20 #5439)
• reduce
• transform (see Adapt transform for #1668 #1671)
• fill fill_n (see parallel::{fill|fill_n} updated for Ranges TS. #3194)
• find find_end find_first_of find_if find_if_not (Adapting hpx::find and friends to C++20 #4885)
• for_each for_each_n (see Adapt transform for #1668 #1671)
• generate generate_n (see More segmented algorithms #1968)
• is_heap is_heap_until (see Adapt parallel::is_heap and parallel::is_heap_until to Ranges TS. #2788)
• is_partitioned (Adapt is_partitioned to C++20 #5006)
• is_sorted is_sorted_until (Adapt is_sorted and is_sorted_until to C++20 #5025)
• lexicographical_compare (Adapt lexicographical_compare to C++20 #5350)
• max_element min_element minmax_element (More segmented algorithms #1968)
• make_heap (Adding parallel make_heap  #4964)
• sort ( Adding first batch of container algorithms  #1911)
• partial_sort partial_sort_copy (Add partial_sort_copy and adapt partial sort to c++ 20 #5630)
• nth_element (Add nth_element #5592)
• stable_sort (Adding range version of stable sort #4817)
• partition (Implement parallel::partition. #2778, Adapt partition, partition_copy and stable_partition to C++ 20 #5540)
• partition_copy (see Implement parallel::partition_copy. #2716, Adapt partition, partition_copy and stable_partition to C++ 20 #5540)
• stable_partition (Adapt partition, partition_copy and stable_partition to C++ 20 #5540)
• remove remove_if (see Implement parallel::remove and parallel::remove_if #3086)
• remove_copy remove_copy_if (Container algorithms #1922)
• replace replace_copy replace_copy_if replace_if (Container algorithms #1922)
• reverse reverse_copy (Container algorithms #1922)
• rotate rotate_copy (Container algorithms #1922)
• search search_n (Adapt search to C++20 and Range TS #5066)
• set_difference set_intersection set_symmetric_difference set_union includes (Making set algorithms conform to C++20 #4970)
• inplace_merge (Implement parallel::inplace_merge. #2978) merge (Implement parallel::merge. #2833)
• swap_ranges (Adapt swap_ranges to C++ 20 #5449)
• uninitialized_copy uninitialized_copy_n (Adapt uninitialized_copy and uninitialized_copy_n to C++ 20 #5371)
• uninitialized_fill uninitialized_fill_n (Adapt uninitialized_fill and uninitialized_fill_n to C++ 20 #5402)
• uninitialized_default_construct uninitialized_default_construct_n (Adapt uninitialized_default_construct and uninitialized_default_construct_n to C++ 20 #5415)
• uninitialized_value_construct uninitialized_value_construct_n (Adapt uninitialized_value_construct and uninitialized_value_construct_n to C++ 20 #5416)
• uninitialized_move uninitialized_move_n (Adapt uninitialized_move and uninitialized_move_n to C++ 20 #5389)
• destroy, destroy_n (Making destroy and destroy_n conforming to C++20 #4869)
• unique (see Implement parallel::unique. #2867)
• unique_copy (see Implement parallel::unique_copy. #2754)

These were added by N4310:

• transform_reduce (Making transform_reduce conforming to C++20 #4925)
• transform_exclusive_scan (Adapt transform_exclusive_scan to C++ 20 #5440) transform_inclusive_scan (Adapt transform_inclusive_scan to C++ 20 #5444)

[dcbdan]

While we are at these changes, should we also set up benchmarks to test the correctness and efficiency of the algorithms? If so, what is the best way to do that?

[hkaiser]

Yes, every new feature requires to add corresponding tests. Performance regressions are more difficult to detect as we don't have a consistent automatic testing system for this. However, any ideas are appreciated.

[dcbdan]

What about requiring that each commit for this issue adds the results of performance tests on

• small, medium, large datasets (whatever those may be),
• 1, 2, ..., 64 processors,
• a selection of compute nodes on Hermione?

Then add a python script that plots strong scaling for a chosen dataset, compute node and algorithm. This way we and anyone else has assurance that the algorithms are indeed faster than sequential.

[sithhell]

What about requiring that each commit for this issue adds the results of performance tests on
small, medium, large datasets (whatever those may be), 1, 2, ..., 64 processors,
a selection of compute nodes on Hermione?

Then add a python script that plots strong scaling for a chosen dataset, compute node and algorithm. This way we and anyone else has assurance that the algorithms are indeed faster than sequential.

We already have that here: http://faui36a.informatik.uni-erlangen.de/perf-o-matic/graph.html

It still has some rough edges, but the basic features are there (plotting
performance regressions, easy addition of new benchmarks, see here:
https://github.com/STEllAR-GROUP/performance_tests and here for an example
benchmark script:
https://github.com/STEllAR-GROUP/performance_tests/blob/master/scripts/hpx_benchmark/osu_latency.py).
It is run every night.