libstdc++: Make PSTL algorithms accept C++20 iterators [PR110512]

  Tested x86_64-linux and aarch64-linux, with TBB 2020.3 only.

Reviews requested.

-- >8 --

This is a step towards implementing the C++23 change P2408R5, "Ranges
iterators as inputs to non-Ranges algorithms". C++20 random access
iterators which do not meet the C==17RandomAccessIterator requirements
will now be recognized by the PSTL algorithms.

We can also optimize the C++17 implementation by using std::__or_, and
use std::__remove_cvref_t and std::__iter_category_t for readability.
This diverges from the upstream PSTL, but since libc++ is no longer
using that upstream (so we're the only consumer of this code) I think
it's reasonable to use libstdc++ extensions in localized places like
this. Rebasing this small header on upstream should not be difficult.

libstdc++-v3/ChangeLog:

	PR libstdc++/110512
	* include/pstl/execution_impl.h (__are_random_access_iterators):
	Recognize C++20 random access iterators, and use more efficient
	implementations.
	* testsuite/25_algorithms/pstl/110512.cc: New test.
---
 libstdc++-v3/include/pstl/execution_impl.h    | 21 ++++++++++---
 .../testsuite/25_algorithms/pstl/110512.cc    | 31 +++++++++++++++++++
 2 files changed, 47 insertions(+), 5 deletions(-)
 create mode 100644 libstdc++-v3/testsuite/25_algorithms/pstl/110512.cc
  

On Thu, 11 Jan 2024, Jonathan Wakely wrote:

> Tested x86_64-linux and aarch64-linux, with TBB 2020.3 only.
> 
> Reviews requested.
> 
> -- >8 --
> 
> This is a step towards implementing the C++23 change P2408R5, "Ranges
> iterators as inputs to non-Ranges algorithms". C++20 random access
> iterators which do not meet the C==17RandomAccessIterator requirements
> will now be recognized by the PSTL algorithms.

IIUC P2408R5 only relaxes the iterator requirements on non-mutating
algorithms, but presumably this patch relaxes the requirements for all
parallel algorithms?  Perhaps that's safe here, not sure..

Besides that LGTM.

> 
> We can also optimize the C++17 implementation by using std::__or_, and
> use std::__remove_cvref_t and std::__iter_category_t for readability.
> This diverges from the upstream PSTL, but since libc++ is no longer
> using that upstream (so we're the only consumer of this code) I think
> it's reasonable to use libstdc++ extensions in localized places like
> this. Rebasing this small header on upstream should not be difficult.
> 
> libstdc++-v3/ChangeLog:
> 
> 	PR libstdc++/110512
> 	* include/pstl/execution_impl.h (__are_random_access_iterators):
> 	Recognize C++20 random access iterators, and use more efficient
> 	implementations.
> 	* testsuite/25_algorithms/pstl/110512.cc: New test.
> ---
>  libstdc++-v3/include/pstl/execution_impl.h    | 21 ++++++++++---
>  .../testsuite/25_algorithms/pstl/110512.cc    | 31 +++++++++++++++++++
>  2 files changed, 47 insertions(+), 5 deletions(-)
>  create mode 100644 libstdc++-v3/testsuite/25_algorithms/pstl/110512.cc
> 
> diff --git a/libstdc++-v3/include/pstl/execution_impl.h b/libstdc++-v3/include/pstl/execution_impl.h
> index 64f6cc4357a..c84061848b9 100644
> --- a/libstdc++-v3/include/pstl/execution_impl.h
> +++ b/libstdc++-v3/include/pstl/execution_impl.h
> @@ -19,13 +19,24 @@ namespace __pstl
>  {
>  namespace __internal
>  {
> -
> -template <typename _IteratorTag, typename... _IteratorTypes>
> -using __are_iterators_of = std::conjunction<
> -    std::is_base_of<_IteratorTag, typename std::iterator_traits<std::decay_t<_IteratorTypes>>::iterator_category>...>;
> +#if __glibcxx_concepts
> +template<typename _Iter>
> +  concept __is_random_access_iter
> +    = std::is_base_of_v<std::random_access_iterator_tag,
> +			std::__iter_category_t<_Iter>>
> +      || std::random_access_iterator<_Iter>;
>  
>  template <typename... _IteratorTypes>
> -using __are_random_access_iterators = __are_iterators_of<std::random_access_iterator_tag, _IteratorTypes...>;
> +  using __are_random_access_iterators
> +    = std::bool_constant<(__is_random_access_iter<std::remove_cvref_t<_IteratorTypes>> && ...)>;
> +#else
> +template <typename... _IteratorTypes>
> +using __are_random_access_iterators
> +    = std::__and_<
> +	std::is_base_of<std::random_access_iterator_tag,
> +			std::__iter_category_t<std::__remove_cvref_t<_IteratorTypes>>>...
> +      >;
> +#endif
>  
>  struct __serial_backend_tag
>  {
> diff --git a/libstdc++-v3/testsuite/25_algorithms/pstl/110512.cc b/libstdc++-v3/testsuite/25_algorithms/pstl/110512.cc
> new file mode 100644
> index 00000000000..188c7c915e5
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/25_algorithms/pstl/110512.cc
> @@ -0,0 +1,31 @@
> +// { dg-do compile { target c++17 } }
> +
> +// Bug 110512 - C++20 random access iterators run sequentially with PSTL
> +
> +#include <algorithm>
> +#include <execution>
> +#include <ranges>
> +#include <testsuite_iterators.h>
> +
> +using InputIter = __gnu_test::input_iterator_wrapper<int>;
> +using FwdIter = __gnu_test::forward_iterator_wrapper<long>;
> +using RAIter = __gnu_test::random_access_iterator_wrapper<float>;
> +
> +template<typename... Iter>
> +constexpr bool all_random_access
> +  = __pstl::__internal::__are_random_access_iterators<Iter...>::value;
> +
> +using __pstl::__internal::__are_random_access_iterators;
> +static_assert( all_random_access<RAIter> );
> +static_assert( all_random_access<int*, RAIter, const long*> );
> +static_assert( ! all_random_access<RAIter, FwdIter> );
> +static_assert( ! all_random_access<FwdIter, InputIter, RAIter> );
> +
> +#if __cpp_lib_ranges
> +using IotaIter = std::ranges::iterator_t<std::ranges::iota_view<int, int>>;
> +static_assert( std::random_access_iterator<IotaIter> );
> +static_assert( all_random_access<IotaIter> );
> +static_assert( all_random_access<IotaIter, RAIter> );
> +static_assert( all_random_access<RAIter, IotaIter> );
> +static_assert( ! all_random_access<RAIter, IotaIter, FwdIter> );
> +#endif
> -- 
> 2.43.0
> 
>
  

On Fri, 12 Jan 2024 at 18:11, Patrick Palka <ppalka@redhat.com> wrote:
>
> On Thu, 11 Jan 2024, Jonathan Wakely wrote:
>
> > Tested x86_64-linux and aarch64-linux, with TBB 2020.3 only.
> >
> > Reviews requested.
> >
> > -- >8 --
> >
> > This is a step towards implementing the C++23 change P2408R5, "Ranges
> > iterators as inputs to non-Ranges algorithms". C++20 random access
> > iterators which do not meet the C==17RandomAccessIterator requirements
> > will now be recognized by the PSTL algorithms.
>
> IIUC P2408R5 only relaxes the iterator requirements on non-mutating
> algorithms, but presumably this patch relaxes the requirements for all
> parallel algorithms?  Perhaps that's safe here, not sure..

I think that technically it's UB to pass non-Cpp17Iterators to those
algos (they're not constrained, they just say the argument have to
meet the requirements). So I think allowing previously ill-formed
programs to compile when using types that satisfy
std::random_access_iterator but don't meet the
Cpp17RandomAccessIterator reqs is allowed.

However, that's not all this patch allows. Dispatching to the RA code
for types that do meet the Cpp17ForwardIterator requirements but not
the Cpp17RandomAccessIterator reqs would be a semantic change for code
that was already valid and already compiled. I think it's a good
change though? I'm not certain.