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

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

[Jonathan Wakely]

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

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

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

[Patrick Palka]

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
> 
> 

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

[Jonathan Wakely]

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.

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

[Dvorskiy, Mikhail]

Hi everyone,

Let me explain a reason of the issue connected with _PSTL_USAGE_WARNINGS macro with GCC14.

Firstly, there is no such issue on version GCC 13.2.0, because _PSTL_PRAGMA_MESSAGE is defined in #pragma message only if _PSTL_USAGE_WARNINGS > 0, please have a look:
https://github.com/gcc-mirror/gcc/blob/releases/gcc-13.2.0/libstdc%2B%2B-v3/include/pstl/pstl_config.h#L160

On GCC trunk there is another preprocessor logic - _PSTL_PRAGMA_MESSAGE is defined in #pragma message when _PSTL_USAGE_WARNINGS is merely defined.
https://github.com/gcc-mirror/gcc/blame/9693459e030977d6e906ea7eb587ed09ee4fddbd/libstdc%2B%2B-v3/include/pstl/pstl_config.h#L180 
while _PSTL_USAGE_WARNINGS is defined to 0 by default:
https://github.com/gcc-mirror/gcc/blame/9693459e030977d6e906ea7eb587ed09ee4fddbd/libstdc%2B%2B-v3/include/pstl/pstl_config.h#L29

Best regards,
Mikhail Dvorskiy

-----Original Message-----
From: Jonathan Wakely <jwakely@redhat.com> 
Sent: Saturday, January 13, 2024 12:20 PM
To: Pilar Latiesa <pilarlatiesa@gmail.com>
Cc: libstdc++@gcc.gnu.org; gcc-patches@gcc.gnu.org
Subject: Re: [PATCH] libstdc++: Make PSTL algorithms accept C++20 iterators [PR110512]

On Sat, 13 Jan 2024 at 09:36, Pilar Latiesa <pilarlatiesa@gmail.com> wrote:
>
> Hi Jonathan
>
> Thanks so much for implementing this.
>
> There are a couple of typos in the patch description: 's/C==17RandomAccessIterator/Cpp17RandomAccessIterator/' and 's/__or_/__and_/'.

Thanks for the comments, I'll fix those.

>
> I've applied your patch localy and it works fine for all my use cases, which admitedly simply consist of using views::zip and views::enumerate with std::for_each. My tbb version is 2020.1.

Thanks for checking it, all feedback is useful.

>
> Unrelated to your patch, with GCC 14, I'm getting a ton of notes for code like:
>
> void f(std::vector<int> &v)
>   { std::for_each(std::execution::par, v.begin(), v.end(), [](int &i) 
> { i *= 2; }); }
>
> indicating that some internal functions are not vectorized.
>
> I very much like getting warnings if an algorithm happens to fall back to its serial version, but in this case I didn't even asked for (unseq) vectorization, yet I got bunch of notes: "Vectorized algorithm unimplemented, redirected to serial" and the algorithm itself is indeed parallelized.
>
> The notes are so confusing that I would suggest undefining _PSTL_USAGE_WARNINGS for G++ (in fact, I don't understand the logic that uses this macro in pstl_config.h).

Yeah, I've seen some of those, and I'm afraid I don't have any ideas about them for now. Could you report it to bugzilla so we don't forget to look into it? Thanks!

Intel Deutschland GmbH
Registered Address: Am Campeon 10, 85579 Neubiberg, Germany
Tel: +49 89 99 8853-0, www.intel.de <http://www.intel.de>
Managing Directors: Christin Eisenschmid, Sharon Heck, Tiffany Doon Silva  
Chairperson of the Supervisory Board: Nicole Lau
Registered Office: Munich
Commercial Register: Amtsgericht Muenchen HRB 186928

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

[Jonathan Wakely]

On Sat, 13 Jan 2024 at 09:36, Pilar Latiesa <pilarlatiesa@gmail.com> wrote:
>
> Hi Jonathan
>
> Thanks so much for implementing this.
>
> There are a couple of typos in the patch description: 's/C==17RandomAccessIterator/Cpp17RandomAccessIterator/' and 's/__or_/__and_/'.

Thanks for the comments, I'll fix those.

>
> I've applied your patch localy and it works fine for all my use cases, which admitedly simply consist of using views::zip and views::enumerate with std::for_each. My tbb version is 2020.1.

Thanks for checking it, all feedback is useful.

>
> Unrelated to your patch, with GCC 14, I'm getting a ton of notes for code like:
>
> void f(std::vector<int> &v)
>   { std::for_each(std::execution::par, v.begin(), v.end(), [](int &i) { i *= 2; }); }
>
> indicating that some internal functions are not vectorized.
>
> I very much like getting warnings if an algorithm happens to fall back to its serial version, but in this case I didn't even asked for (unseq) vectorization, yet I got bunch of notes: "Vectorized algorithm unimplemented, redirected to serial" and the algorithm itself is indeed parallelized.
>
> The notes are so confusing that I would suggest undefining _PSTL_USAGE_WARNINGS for G++ (in fact, I don't understand the logic that uses this macro in pstl_config.h).

Yeah, I've seen some of those, and I'm afraid I don't have any ideas
about them for now. Could you report it to bugzilla so we don't forget
to look into it? Thanks!

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

[Pilar Latiesa]

[-- Attachment #1: Type: text/plain, Size: 1095 bytes --]

Hi Jonathan

Thanks so much for implementing this.

There are a couple of typos in the patch description:
's/C==17RandomAccessIterator/Cpp17RandomAccessIterator/' and
's/__or_/__and_/'.

I've applied your patch localy and it works fine for all my use cases,
which admitedly simply consist of using views::zip and views::enumerate
with std::for_each. My tbb version is 2020.1.


Unrelated to your patch, with GCC 14, I'm getting a ton of notes for code
like:

void f(std::vector<int> &v)
  { std::for_each(std::execution::par, v.begin(), v.end(), [](int &i) { i
*= 2; }); }

indicating that some internal functions are not vectorized.

I very much like getting warnings if an algorithm happens to fall back to
its serial version, but in this case I didn't even asked for (unseq)
vectorization, yet I got bunch of notes: "Vectorized algorithm
unimplemented, redirected to serial" and the algorithm itself is indeed
parallelized.

The notes are so confusing that I would suggest undefining
_PSTL_USAGE_WARNINGS for G++ (in fact, I don't understand the logic that
uses this macro in pstl_config.h).