[libc++][PSTL] Implement std::stable_sort

[ldionne]

libcxx/include/CMakeLists.txt

73

Missing docs for __pstl_stable_sort too.

libcxx/include/__algorithm/pstl_backends/cpu_backend.h

23

Missing docs?

libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h

33

Let's remove the size_t = 0 unless it has a purpose.

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h

37

Same here for = 0.

[philnik]

Address comments

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[kda]

This looks to be causing breakages in sanitizer buildbots:
(intel)
https://lab.llvm.org/buildbot/#/builders/74/builds/19607
https://lab.llvm.org/buildbot/#/builders/168/builds/13779
(arm)
https://lab.llvm.org/buildbot/#/builders/239/builds/2536
https://lab.llvm.org/buildbot/#/builders/236/builds/4438

[philnik]

In D151573#4390975, @kda wrote:

This looks to be causing breakages in sanitizer buildbots:
(intel)
https://lab.llvm.org/buildbot/#/builders/74/builds/19607
https://lab.llvm.org/buildbot/#/builders/168/builds/13779
(arm)
https://lab.llvm.org/buildbot/#/builders/239/builds/2536
https://lab.llvm.org/buildbot/#/builders/236/builds/4438

This should be fixed by bb9b12907e2d08e0915813b3aaf56a3b7a4ffd0b.

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_backend.h
   __algorithm/pstl_backends/cpu_backend.h
   __algorithm/pstl_backends/cpu_backends/any_of.h
   __algorithm/pstl_backends/cpu_backends/backend.h
   __algorithm/pstl_backends/cpu_backends/fill.h
   __algorithm/pstl_backends/cpu_backends/find_if.h
   __algorithm/pstl_backends/cpu_backends/for_each.h
   __algorithm/pstl_backends/cpu_backends/serial.h
+  __algorithm/pstl_backends/cpu_backends/stable_sort.h
   __algorithm/pstl_backends/cpu_backends/thread.h
   __algorithm/pstl_backends/cpu_backends/transform.h
   __algorithm/pstl_copy.h
   __algorithm/pstl_fill.h
   __algorithm/pstl_find.h
   __algorithm/pstl_for_each.h
   __algorithm/pstl_frontend_dispatch.h
+  __algorithm/pstl_stable_sort.h
   __algorithm/pstl_transform.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
   __algorithm/ranges_clamp.h
   __algorithm/ranges_copy.h

libcxx/include/__algorithm/pstl_backends/cpu_backend.h

/*
 
   // _Functor takes a subrange for [__first, __last) that should be executed in serial
   template <class _RandomAccessIterator, class _Functor>
   void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Functor __func);
 
   // Cancel the execution of other jobs - they aren't needed anymore
   void __cancel_execution();
 
   TODO: Document the parallel backend
 */
 
 #include <__algorithm/pstl_backends/cpu_backends/any_of.h>
 #include <__algorithm/pstl_backends/cpu_backends/fill.h>
 #include <__algorithm/pstl_backends/cpu_backends/find_if.h>
 #include <__algorithm/pstl_backends/cpu_backends/for_each.h>
+#include <__algorithm/pstl_backends/cpu_backends/stable_sort.h>
 #include <__algorithm/pstl_backends/cpu_backends/transform.h>
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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_BACKENDS_CPU_BACKENDS_SERIAL_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_SERIAL_H
 
 #include <__config>
+#include <cstddef>
 
 #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
 
 namespace __par_backend {
 inline namespace __serial_cpu_backend {
 
 template <class _RandomAccessIterator, class _Fp>
 _LIBCPP_HIDE_FROM_ABI void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Fp __f) {
   __f(__first, __last);
 }
 
+template <class _RandomAccessIterator, class _Compare, class _LeafSort>
+_LIBCPP_HIDE_FROM_ABI void __parallel_stable_sort(
+    _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _LeafSort __leaf_sort, size_t = 0) {
+  __leaf_sort(__first, __last, __comp);
+}
+
 _LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {}
 
 // TODO: Complete this list
 
 } // namespace __serial_cpu_backend
 } // namespace __par_backend
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_SERIAL_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/stable_sort.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_BACKENDS_CPU_BACKENDS_STABLE_SORT_H
+#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_STABLE_SORT_H
+
+#include <__algorithm/pstl_backends/cpu_backends/backend.h>
+#include <__algorithm/stable_sort.h>
+#include <__config>
+#include <__type_traits/is_execution_policy.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 _RandomAccessIterator, class _Comp>
+_LIBCPP_HIDE_FROM_ABI void
+__pstl_stable_sort(__cpu_backend_tag, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
+  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy>) {
+    std::__terminate_on_exception([&] {
+      __par_backend::__parallel_stable_sort(
+          __first, __last, __comp, [](_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
+            std::stable_sort(__first, __last, __comp);
+          });
+    });
+  } else {
+    std::stable_sort(__first, __last, __comp);
+  }
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_STABLE_SORT_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.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_BACKENDS_CPU_BACKENDS_THREAD_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_THREAD_H
 
 #include <__assert>
 #include <__config>
+#include <cstddef>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 // This backend implementation is for testing purposes only and not meant for production use. This will be replaced
 // by a proper implementation once the PSTL implementation is somewhat stable.
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace __par_backend {
 inline namespace __thread_cpu_backend {
 
 template <class _RandomAccessIterator, class _Fp>
 _LIBCPP_HIDE_FROM_ABI void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Fp __f) {
   __f(__first, __last);
 }
 
+template <class _RandomAccessIterator, class _Compare, class _LeafSort>
+_LIBCPP_HIDE_FROM_ABI void __parallel_stable_sort(
+    _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _LeafSort __leaf_sort, size_t = 0) {
+  __leaf_sort(__first, __last, __comp);
+}
+
 _LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {}
 
 } // namespace __thread_cpu_backend
 } // namespace __par_backend
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_THREAD_H

libcxx/include/__algorithm/pstl_stable_sort.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_STABLE_SORT_H
+#define _LIBCPP___ALGORITHM_PSTL_STABLE_SORT_H
+
+#include <__algorithm/pstl_backend.h>
+#include <__config>
+#include <__functional/operations.h>
+#include <__type_traits/is_execution_policy.h>
+#include <__type_traits/remove_cvref.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 _RandomAccessIterator,
+          class _Comp                                         = less<>,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void
+stable_sort(_ExecutionPolicy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp = {}) {
+  using _Backend = typename __select_backend<_RawPolicy>::type;
+  std::__pstl_stable_sort<_RawPolicy>(_Backend{}, std::move(__first), std::move(__last), std::move(__comp));
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_STABLE_SORT_H

libcxx/include/algorithm

 #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_copy.h>
 #include <__algorithm/pstl_fill.h>
 #include <__algorithm/pstl_find.h>
 #include <__algorithm/pstl_for_each.h>
+#include <__algorithm/pstl_stable_sort.h>
 #include <__algorithm/pstl_transform.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>
 #include <__algorithm/ranges_clamp.h>
 #include <__algorithm/ranges_copy.h>

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/pstl.stable_sort.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// <algorithm>
+
+// template<class ExecutionPolicy, class RandomAccessIterator>
+//   void stable_sort(ExecutionPolicy&& exec,
+//                    RandomAccessIterator first, RandomAccessIterator last);
+//
+// template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
+//   void stable_sort(ExecutionPolicy&& exec,
+//                    RandomAccessIterator first, RandomAccessIterator last,
+//                    Compare comp);
+
+#include <algorithm>
+#include <atomic>
+#include <cassert>
+#include <vector>
+
+#include "test_macros.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+EXECUTION_POLICY_SFINAE_TEST(stable_sort);
+
+static_assert(sfinae_test_stable_sort<int, int*, int*, bool (*)(int)>);
+static_assert(!sfinae_test_stable_sort<std::execution::parallel_policy, int*, int*, bool (*)(int, int)>);
+
+struct OrderedValue {
+  int value;
+  double original_order;
+  bool operator==(const OrderedValue& other) const { return other.value == value; }
+
+  auto operator<(const OrderedValue& rhs) const { return value < rhs.value; }
+  auto operator>(const OrderedValue& rhs) const { return value > rhs.value; }
+};
+
+template <class Iter, std::size_t N>
+void test_one(std::array<int, N> input, std::array<int, N> expected) {
+  std::stable_sort(Iter(input.data()), Iter(input.data() + input.size()));
+  assert(input == expected);
+}
+
+template <class Iter>
+struct Test {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+
+    // Empty sequence.
+    test_one<Iter, 0>({}, {});
+    // 1-element sequence.
+    test_one<Iter, 1>({1}, {1});
+    // 2-element sequence.
+    test_one<Iter, 2>({2, 1}, {1, 2});
+    // 3-element sequence.
+    test_one<Iter, 3>({2, 1, 3}, {1, 2, 3});
+    // Longer sequence.
+    test_one<Iter, 8>({2, 1, 3, 6, 8, 4, 11, 5}, {1, 2, 3, 4, 5, 6, 8, 11});
+    // Longer sequence with duplicates.
+    test_one<Iter, 7>({2, 1, 3, 6, 2, 8, 6}, {1, 2, 2, 3, 6, 6, 8});
+    // All elements are the same.
+    test_one<Iter, 3>({1, 1, 1}, {1, 1, 1});
+    // Already sorted.
+    test_one<Iter, 5>({1, 2, 3, 4, 5}, {1, 2, 3, 4, 5});
+    // Reverse-sorted.
+    test_one<Iter, 5>({5, 4, 3, 2, 1}, {1, 2, 3, 4, 5});
+    // Repeating pattern.
+    test_one<Iter, 6>({1, 2, 1, 2, 1, 2}, {1, 1, 1, 2, 2, 2});
+
+    { // The sort is stable (equivalent elements remain in the same order).
+      using V        = OrderedValue;
+      using Array    = std::array<V, 20>;
+      Array in       = {V{10, 10.1}, {12, 12.1}, {3, 3.1},   {5, 5.1}, {3, 3.2}, {3, 3.3}, {11, 11.1},
+                        {12, 12.2},  {4, 4.1},   {4, 4.2},   {4, 4.3}, {1, 1.1}, {6, 6.1}, {3, 3.4},
+                        {10, 10.2},  {8, 8.1},   {12, 12.3}, {1, 1.2}, {1, 1.3}, {5, 5.2}};
+      Array expected = {V{1, 1.1},  {1, 1.2},   {1, 1.3},   {3, 3.1},   {3, 3.2},   {3, 3.3},  {3, 3.4},
+                        {4, 4.1},   {4, 4.2},   {4, 4.3},   {5, 5.1},   {5, 5.2},   {6, 6.1},  {8, 8.1},
+                        {10, 10.1}, {10, 10.2}, {11, 11.1}, {12, 12.1}, {12, 12.2}, {12, 12.3}};
+
+      std::stable_sort(policy, in.begin(), in.end());
+      assert(in == expected);
+    }
+
+    { // A custom comparator works and is stable.
+      using V     = OrderedValue;
+      using Array = std::array<V, 11>;
+
+      Array in = {
+          V{1, 1.1},
+          {2, 2.1},
+          {2, 2.2},
+          {3, 3.1},
+          {2, 2.3},
+          {3, 3.2},
+          {4, 4.1},
+          {5, 5.1},
+          {2, 2.4},
+          {5, 5.2},
+          {1, 1.2}};
+      Array expected = {
+          V{5, 5.1},
+          {5, 5.2},
+          {4, 4.1},
+          {3, 3.1},
+          {3, 3.2},
+          {2, 2.1},
+          {2, 2.2},
+          {2, 2.3},
+          {2, 2.4},
+          {1, 1.1},
+          {1, 1.2}};
+
+      std::stable_sort(policy, in.begin(), in.end(), std::greater{});
+      assert(in == expected);
+    }
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::random_access_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+  std::set_terminate(terminate_successful);
+  int a[] = {1, 2};
+  try {
+    std::stable_sort(std::execution::par, std::begin(a), std::end(a), [](int, int) -> bool { throw int{}; });
+  } catch (int) {
+    assert(false);
+  }
+#endif
+
+  return 0;
+}