Adapt parallel algorithms to C++20

[hkaiser]

Adapt our parallel algorithms to C++20 (http://eel.is/c++draft/#algorithms)

Here is the list of algorithms mandated by the standard:

• adjacent_difference (Adjacent #5564)
• adjacent_find (Adapt adjacent_find to C++20 #4996)
• all_of any_of none_of (Adapting all_of, any_of, and none_of to C++20 #4859)
• copy copy_if copy_n (Implement customization point for hpx::copy and hpx::ranges::copy #4821)
• move (Making move conforming with C++20 #4870)
• count count_if (Adapting count and count_if to be conforming to C++20 #4865)
• 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 (Adding CPOs for hpx::reduce #4836)
• transform (Adapt transform to C++20 #5051)
• fill fill_n (Making fill and fill_n compatible with C++20 #4860)
• 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 (Add CPOs for for_each #4867)
• for_loop for_loop_n for_loop_strided for_loop_strided_n (Add CPOs for for_loop algorithms #4911)
• generate generate_n (Making generate() and generate_n conforming to C++20 #4896)
• is_heap is_heap_until (Making is_heap and is_heap_until conforming to C++20 #4965)
• 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 (Adapt min_element, max_element and minmax_element to C++20 #5241)
• make_heap (Adding parallel make_heap  #4964)
• partial_sort partial_sort_copy (Add partial_sort_copy and adapt partial sort to c++ 20 #5630)
• nth_element (Add nth_element #5592)
• sort (Adapt sort to C++ 20 #5460)
• stable_sort (Adapt stable_sort to C++ 20 #5470)
• partition (Adapt partition, partition_copy and stable_partition to C++ 20 #5540)
• partition_copy (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 (Adapt remove and remove_if to C++20 #5125)
• remove_copy remove_copy_if (Adapt remove_copy(_if) to C++20 #5150)
• replace replace_copy replace_copy_if replace_if (Adapt replace(_if) to C++20 #5192)
• reverse reverse_copy (Adapt reverse to C++20 #5225)
• rotate (Adapt rotate/rotate_copy to C++20 #5459)
• rotate_copy (Adapt rotate/rotate_copy to C++20 #5459)
• 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 (Making set algorithms conform to C++20 #4970)
• merge (Making set algorithms conform to C++20 #4970)
• 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 (Adapt unique and unique_copy to C++ 20 #5458)
• unique_copy (Adapt unique and unique_copy to C++ 20 #5458)
• 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)
• shift_left shift_right (Add shift_left and shift_right algorithms #5466)

[gonidelis]

How to adapt a parallel algorithm to C++20

1. Render the old overload under namespace parallel deprecated (e.g. hpx::parallel::for_each), according to the hpx deprecation headers. Be careful on referring to the pending HPX release version.

2. Change the base implementations (usually found as function objects under namespace hpx::parallel::v1::detail) in order to support iterator/sentinel pairs according to 3646 (just differenciate the type of last from the type of first).

3. Change the result type (if needed) on the base implementations. Mind not to create conflicts with the deprecated overloads. If there is no other way, change the result type on the deprecated overloads, too.

4. Add the C++20 overloads according to the C++20 Standard, using the tag_fallback/tag_fallback_invoke Customization Point Object (CPO) mechanism.

   1. If the algorithm has a segmented counterpart (under /libs/full/segmented_algorithms), provide the segmented overloads using tag_invoke instead of tag_fallback_invoke under namespace hpx::segmented and delete the dispatch functions (the ones with the underscore: e.g. for_each_).

5. Adapt the unit tests so they use the overloads under hpx and hpx::ranges namespaces.

   1. Mind to add tests for the overloads without an ExPolicy, in every test category (test_<algorithm>, test_<algorithm>_exception, test_<algorithm>_bad_alloc).
   2. Add tests that check the newly introduced iterator-sentinel_value overloads (test_<algorithm>_sent).

6. Provide docs for every given overload using the #if defined(DOXYGEN) - #else - #endif directives.

   1. Mind to pack the docs under namespace hpx or namespace hpx::ranges accordingly.
   2. Pay attention to the (possibly) altered result type.
   3. Be careful on documenting the overloads that do not have an ExPolicy. No parallelization is happening there.

Nitpicks and Tips

• For a given algorithm, the adaptation takes place both under /libs/parallelism/algorithms/include/hpx/parallel/algorithms/<algorithm>.hpp (non ranges overloads) and under /libs/parallelism/algorithms/include/hpx/parallel/container_algorithms/<algorithm>.hpp (ranges overloads).
• When documenting the adapted algorithms, cppreference is a good place to read about the effect of the algorithm.
• When documenting an algorithm under hpx::ranges namespace, that takes a Rng as an input source, there are no inherent first and last values. Mind to declare at the top that first is equivalent to parallel::util::begin(rng) and last is equivalent to parallel::util::end(rng).
• Disable clang-format for all the template parameters sections that include an HPX_CONCEPT_REQUIRES_ (// clang-format off/on) macro.
• Check our result types header for the newly introduced C++20 result types.
• We do not need any additional unit tests (overloads without an ExPolicy) for any of the _async tests.
• Provide static_assertions that check the validity of the iterators for every given overload: the ones with no ExPolicy usually use input iterators while the parallel ones use forward/bidirectional/random-access iterators.
• The previous bullet should be taken into consideration even for the Rng overloads. Here are some HPX custom facilities that provide an iterator-based interface for the Rng type.
• std::pair usually changes to hpx::parallel::util::in_out_result and std::tuple changes to hpx::parallel::util::in_in_out_result. std::distance, occasionally used on the base implementations, changes to detail::distance in order to support iterator/sentinel pairs.
• In order to test the iterator/sentinel-value case, you will need to include in the testing file, the iter_sent header like #include <hpx/iterator_support/tests/iter_sent.hpp>, which implements a custom sentinel facility.

[hkaiser]

This can be closed now! Thanks to everybody helping to implement, debug, and fix things!