[libc++][PSTL] Implement std::count{,_if}

[philnik]

Use new dispatching approach

[philnik]

Try to fix CI

[ldionne]

libcxx/include/__algorithm/pstl_count.h

2

We should update the backend documentation comment.

45

I think we should implement this using reduce instead, like in the original PSTL. I think we should implement std::reduce before we implement this one.

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/pstl.count.pass.cpp

56

Can you also test a 3 element range with {yes, no, yes}? Right now, the tests would pass if we were counting the number of consecutive elements equal to the value, kind of like equal_range I guess.

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/pstl.count_if.pass.cpp

56

Same for {yes no yes}.

[philnik]

Address comments

[philnik]

Rebased

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

• Rebase
• Try to fix CI

libcxx/include/CMakeLists.txt

set(files
   __algorithm/partial_sort.h
   __algorithm/partial_sort_copy.h
   __algorithm/partition.h
   __algorithm/partition_copy.h
   __algorithm/partition_point.h
   __algorithm/pop_heap.h
   __algorithm/prev_permutation.h
   __algorithm/pstl_any_all_none_of.h
+  __algorithm/pstl_count.h
   __algorithm/pstl_fill.h
   __algorithm/pstl_find.h
   __algorithm/pstl_for_each.h
   __algorithm/push_heap.h
   __algorithm/ranges_adjacent_find.h
   __algorithm/ranges_all_of.h
   __algorithm/ranges_any_of.h
   __algorithm/ranges_binary_search.h

libcxx/include/__algorithm/pstl_count.h

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_PSTL_COUNT_H
+#define _LIBCPP___ALGORITHM_PSTL_COUNT_H
+
+#include <__algorithm/count.h>
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__pstl/internal/parallel_impl.h>
+#include <__pstl/internal/unseq_backend_simd.h>
+#include <__type_traits/is_execution_policy.h>
+#include <__type_traits/remove_cvref.h>
+#include <__utility/terminate_on_exception.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Predicate,
+          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI __iter_diff_t<_ForwardIterator>
+count_if(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
+  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
+                __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
+    return std::__terminate_on_exception([&] {
+      return __pstl::__par_backend::__parallel_reduce(
+          __pstl::__internal::__par_backend_tag{},
+          __policy,
+          __first,
+          __last,
+          __iter_diff_t<_ForwardIterator>(0),
+          [&__policy, __pred](_ForwardIterator __brick_first,
+                              _ForwardIterator __brick_last,
+                              __iter_diff_t<_ForwardIterator> __value) {
+            return __value +
+                   std::count_if(std::__remove_parallel_policy(__policy), __brick_first, __brick_last, __pred);
+          },
+          plus{});
+    });
+  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
+                       __is_cpp17_random_access_iterator<_ForwardIterator>::value)
+    return __pstl::__unseq_backend::__simd_count(__first, __last - __first, __pred);
+  else {
+    return std::count_if(__first, __last, __pred);
+  }
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Tp,
+          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI __iter_diff_t<_ForwardIterator>
+count(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
+  return std::count_if(__policy, __first, __last, [&](__iter_reference<_ForwardIterator> __v) {
+    return __v == __value;
+  });
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_COUNT_H

libcxx/include/algorithm

 #include <__algorithm/partial_sort.h>
 #include <__algorithm/partial_sort_copy.h>
 #include <__algorithm/partition.h>
 #include <__algorithm/partition_copy.h>
 #include <__algorithm/partition_point.h>
 #include <__algorithm/pop_heap.h>
 #include <__algorithm/prev_permutation.h>
 #include <__algorithm/pstl_any_all_none_of.h>
+#include <__algorithm/pstl_count.h>
 #include <__algorithm/pstl_fill.h>
 #include <__algorithm/pstl_find.h>
 #include <__algorithm/pstl_for_each.h>
 #include <__algorithm/push_heap.h>
 #include <__algorithm/ranges_adjacent_find.h>
 #include <__algorithm/ranges_all_of.h>
 #include <__algorithm/ranges_any_of.h>
 #include <__algorithm/ranges_binary_search.h>

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/pstl.count.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// template<class ExecutionPolicy, class ForwardIterator, class T>
+//   typename iterator_traits<ForwardIterator>::difference_type
+//     count(ExecutionPolicy&& exec,
+//           ForwardIterator first, ForwardIterator last, const T& value);
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <vector>
+
+#include "test_macros.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+EXECUTION_POLICY_SFINAE_TEST(count);
+
+static_assert(sfinae_test_count<int, int*, int*, bool (*)(int)>);
+static_assert(!sfinae_test_count<std::execution::parallel_policy, int*, int*, int>);
+
+template <class Iter>
+struct Test {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    { // simple test
+      int a[]            = {1, 2, 3, 4, 5};
+      decltype(auto) ret = std::count(policy, std::begin(a), std::end(a), 3);
+      static_assert(std::is_same_v<decltype(ret), typename std::iterator_traits<Iter>::difference_type>);
+      assert(ret == 1);
+    }
+
+    { // test that an empty range works
+      std::array<int, 0> a;
+      decltype(auto) ret = std::count(policy, std::begin(a), std::end(a), 3);
+      static_assert(std::is_same_v<decltype(ret), typename std::iterator_traits<Iter>::difference_type>);
+      assert(ret == 0);
+    }
+
+    { // test that a single-element range works
+      int a[] = {1};
+      decltype(auto) ret = std::count(policy, std::begin(a), std::end(a), 1);
+      static_assert(std::is_same_v<decltype(ret), typename std::iterator_traits<Iter>::difference_type>);
+      assert(ret == 1);
+    }
+
+    { // test that a two-element range works
+      int a[] = {1, 3};
+      decltype(auto) ret = std::count(policy, std::begin(a), std::end(a), 3);
+      static_assert(std::is_same_v<decltype(ret), typename std::iterator_traits<Iter>::difference_type>);
+      assert(ret == 1);
+    }
+
+    { // test that a large range works
+      std::vector<int> a(100, 2);
+      decltype(auto) ret = std::count(policy, std::begin(a), std::end(a), 2);
+      static_assert(std::is_same_v<decltype(ret), typename std::iterator_traits<Iter>::difference_type>);
+      assert(ret == 100);
+    }
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/pstl.count_if.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// template<class ExecutionPolicy, class ForwardIterator, class Predicate>
+//   typename iterator_traits<ForwardIterator>::difference_type
+//     count_if(ExecutionPolicy&& exec,
+//              ForwardIterator first, ForwardIterator last, Predicate pred);
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <vector>
+
+#include "test_macros.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+EXECUTION_POLICY_SFINAE_TEST(count_if);
+
+static_assert(sfinae_test_count_if<int, int*, int*, bool (*)(int)>);
+static_assert(!sfinae_test_count_if<std::execution::parallel_policy, int*, int*, int>);
+
+template <class Iter>
+struct Test {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    { // simple test
+      int a[]            = {1, 2, 3, 4, 5};
+      decltype(auto) ret = std::count_if(policy, std::begin(a), std::end(a), [](int i) { return i < 3; });
+      static_assert(std::is_same_v<decltype(ret), typename std::iterator_traits<Iter>::difference_type>);
+      assert(ret == 2);
+    }
+
+    { // test that an empty range works
+      std::array<int, 0> a;
+      decltype(auto) ret = std::count_if(policy, std::begin(a), std::end(a), [](int i) { return i < 3; });
+      static_assert(std::is_same_v<decltype(ret), typename std::iterator_traits<Iter>::difference_type>);
+      assert(ret == 0);
+    }
+
+    { // test that a single-element range works
+      int a[] = {1};
+      decltype(auto) ret = std::count_if(policy, std::begin(a), std::end(a), [](int i) { return i < 3; });
+      static_assert(std::is_same_v<decltype(ret), typename std::iterator_traits<Iter>::difference_type>);
+      assert(ret == 1);
+    }
+
+    { // test that a two-element range works
+      int a[] = {1, 3};
+      decltype(auto) ret = std::count_if(policy, std::begin(a), std::end(a), [](int i) { return i < 3; });
+      static_assert(std::is_same_v<decltype(ret), typename std::iterator_traits<Iter>::difference_type>);
+      assert(ret == 1);
+    }
+
+    { // test that a large range works
+      std::vector<int> a(100, 2);
+      decltype(auto) ret = std::count_if(policy, std::begin(a), std::end(a), [](int i) { return i < 3; });
+      static_assert(std::is_same_v<decltype(ret), typename std::iterator_traits<Iter>::difference_type>);
+      assert(ret == 100);
+    }
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+  return 0;
+}