| 1 | //===----------------------------------------------------------------------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | |
| 9 | #ifndef _LIBCPP___PSTL_BACKENDS_STATPART_BASIS_H |
| 10 | #define _LIBCPP___PSTL_BACKENDS_STATPART_BASIS_H |
| 11 | |
| 12 | #include <__algorithm/lower_bound.h> |
| 13 | #include <__algorithm/merge.h> |
| 14 | #include <__algorithm/min.h> |
| 15 | #include <__algorithm/move.h> |
| 16 | #include <__algorithm/upper_bound.h> |
| 17 | #include <__assert> |
| 18 | #include <__atomic/atomic.h> |
| 19 | #include <__atomic/memory_order.h> |
| 20 | #include <__config> |
| 21 | #include <__execution/is_execution_policy.h> |
| 22 | #include <__functional/identity.h> |
| 23 | #include <__functional/operations.h> |
| 24 | #include <__iterator/concepts.h> |
| 25 | #include <__iterator/distance.h> |
| 26 | #include <__iterator/iterator_traits.h> |
| 27 | #include <__iterator/move_iterator.h> |
| 28 | #include <__iterator/next.h> |
| 29 | #include <__memory/allocator.h> |
| 30 | #include <__memory/construct_at.h> |
| 31 | #include <__memory/destroy.h> |
| 32 | #include <__memory/unique_ptr.h> |
| 33 | #include <__new/nothrow_t.h> |
| 34 | #include <__numeric/reduce.h> |
| 35 | #include <__optional/comparison.h> |
| 36 | #include <__optional/nullopt_t.h> |
| 37 | #include <__optional/optional.h> |
| 38 | #include <__pstl/backends/statpart/decoupled_lookback.h> |
| 39 | #include <__thread/hardware_concurrency.h> |
| 40 | #include <__type_traits/is_assignable.h> |
| 41 | #include <__type_traits/is_constructible.h> |
| 42 | #include <__type_traits/is_trivially_copyable.h> |
| 43 | #include <__utility/empty.h> |
| 44 | #include <__utility/move.h> |
| 45 | |
| 46 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
| 47 | # pragma GCC system_header |
| 48 | #endif |
| 49 | |
| 50 | _LIBCPP_PUSH_MACROS |
| 51 | #include <__undef_macros> |
| 52 | |
| 53 | #if _LIBCPP_STD_VER >= 17 |
| 54 | |
| 55 | _LIBCPP_BEGIN_NAMESPACE_STD |
| 56 | _LIBCPP_BEGIN_EXPLICIT_ABI_ANNOTATIONS |
| 57 | namespace __pstl { |
| 58 | |
| 59 | namespace __statpart { |
| 60 | |
| 61 | // The backbone of the backend: applies the function to each of the indices [0, __chunk_count) in parallel. |
| 62 | // The actual number of parallel workers and the order of application is unspecified. |
| 63 | _LIBCPP_EXPORTED_FROM_ABI void |
| 64 | __apply(size_t __chunk_count, void* __context, void (*__func)(void* __context, size_t __chunk)) noexcept; |
| 65 | |
| 66 | // The maximum number of partitions to be processed per CPU |
| 67 | constexpr inline size_t __max_partitions_per_cpu = 8; |
| 68 | |
| 69 | // The minimum number of elements to sort serially in a single partition |
| 70 | constexpr inline size_t __min_sort_partition_size = 256; |
| 71 | |
| 72 | constexpr inline size_t __lane_size = 64; |
| 73 | |
| 74 | enum class __partitioning_status { |
| 75 | // Returned when the partitioning result is not a nullopt. |
| 76 | __ok, |
| 77 | // Returned when there are not enough element to produce a single partition or the final number of partitions is fewer |
| 78 | // than 2, i.e. there's no reason to process the input in parallel. |
| 79 | __not_enough_elements, |
| 80 | // There's fewer than 2 processors available in the system, or their number is unknown, which is treated as having |
| 81 | // a single processor. In either case, fall back to serial processing. |
| 82 | __no_parallelism, |
| 83 | // Reserved for later: returned when memory could not be allocated for the stashed forward iterators. |
| 84 | __bad_alloc |
| 85 | }; |
| 86 | |
| 87 | template <class _Iterator> |
| 88 | struct _LIBCPP_HIDE_FROM_ABI __partitioning_result; |
| 89 | |
| 90 | template <class _Iterator> |
| 91 | struct _LIBCPP_HIDE_FROM_ABI __iterator_range { |
| 92 | _Iterator __first; |
| 93 | _Iterator __last; |
| 94 | }; |
| 95 | |
| 96 | // __iterator_partitions<Iter> holds a finite pre-determined set of partitions and allows querying each iterator range |
| 97 | // in O(1) time. |
| 98 | template <class _Iterator, |
| 99 | bool _IsRandomAccessOrContiguous = __has_random_access_iterator_category_or_concept<_Iterator>::value > |
| 100 | struct _LIBCPP_HIDE_FROM_ABI __iterator_partitions; |
| 101 | |
| 102 | // Specialization of __iterator_partitions<_Iterator> for random-access iterators |
| 103 | template <class _Iterator > |
| 104 | struct _LIBCPP_HIDE_FROM_ABI __iterator_partitions<_Iterator, /*_IsRandomAccessOrContiguous=*/true> { |
| 105 | _LIBCPP_HIDE_FROM_ABI size_t __partitions_count() const { return __partitions_count_; } |
| 106 | |
| 107 | _LIBCPP_HIDE_FROM_ABI size_t __max_partition_size() const { return __partition_size_ + (__remainder_ > 0 ? 1 : 0); } |
| 108 | |
| 109 | _LIBCPP_HIDE_FROM_ABI __iterator_range<_Iterator> __partition(size_t __n) const { |
| 110 | _Iterator __first = __base_ + __n * __partition_size_ + (__n < __remainder_ ? __n : __remainder_); |
| 111 | _Iterator __last = __first + __partition_size_ + (__n < __remainder_ ? 1 : 0); |
| 112 | return __iterator_range<_Iterator>{__first, __last}; |
| 113 | } |
| 114 | |
| 115 | private: |
| 116 | _Iterator __base_; |
| 117 | size_t __count_; |
| 118 | size_t __partition_size_; |
| 119 | size_t __remainder_; |
| 120 | size_t __partitions_count_; |
| 121 | |
| 122 | template <class _Iter> |
| 123 | friend __partitioning_result<_Iter> _LIBCPP_HIDE_FROM_ABI __partition(_Iter, _Iter, size_t, size_t) noexcept; |
| 124 | }; |
| 125 | |
| 126 | // Specialization of __iterator_partitions<_Iterator> for forward iterators |
| 127 | template <class _Iterator > |
| 128 | struct _LIBCPP_HIDE_FROM_ABI __iterator_partitions<_Iterator, /*_IsRandomAccessOrContiguous=*/false> { |
| 129 | _LIBCPP_HIDE_FROM_ABI size_t __partitions_count() const { return __partitions_count_; } |
| 130 | |
| 131 | _LIBCPP_HIDE_FROM_ABI size_t __max_partition_size() const { return __max_partition_size_; } |
| 132 | |
| 133 | _LIBCPP_HIDE_FROM_ABI __iterator_range<_Iterator> __partition(size_t __n) const { return __partitions_[__n]; } |
| 134 | |
| 135 | private: |
| 136 | std::unique_ptr<__iterator_range<_Iterator>[]> __partitions_; |
| 137 | size_t __partitions_count_; |
| 138 | size_t __max_partition_size_; |
| 139 | |
| 140 | template <class _Iter> |
| 141 | friend __partitioning_result<_Iter> _LIBCPP_HIDE_FROM_ABI __partition(_Iter, _Iter, size_t, size_t) noexcept; |
| 142 | }; |
| 143 | |
| 144 | // This is basically a barebones std::expected<__iterator_partitions<_Iterator>, __partitioning_status>. |
| 145 | // __partition() uses this to avoid resorting to return arguments. |
| 146 | template <class _Iterator> |
| 147 | struct _LIBCPP_HIDE_FROM_ABI __partitioning_result { |
| 148 | optional<__iterator_partitions<_Iterator>> __value_; |
| 149 | __partitioning_status __status_ = __partitioning_status::__ok; |
| 150 | }; |
| 151 | |
| 152 | // This function allows basis.h to compile when _LIBCPP_HAS_THREADS=0 |
| 153 | _LIBCPP_HIDE_FROM_ABI inline unsigned __thread_hardware_concurrency() noexcept { |
| 154 | # if _LIBCPP_HAS_THREADS |
| 155 | return std::__thread_hardware_concurrency(); |
| 156 | # else |
| 157 | return 0; |
| 158 | # endif // _LIBCPP_HAS_THREADS |
| 159 | } |
| 160 | |
| 161 | // Splits the input iterator range into a finite set of partitions, such that every iterator sub-range can be queried in |
| 162 | // a O(1) time later. |
| 163 | // If partitioning fails, returns nullopt and reports the reason in __result. |
| 164 | // __min_partition_size specifies the minimal number of elements in every partition. |
| 165 | // __workers_count is normally implicitly queried from hardware_concurrency() and should be explicitly specified only in |
| 166 | // unit tests. |
| 167 | template <class _Iterator> |
| 168 | _LIBCPP_HIDE_FROM_ABI __partitioning_result<_Iterator> |
| 169 | __partition(_Iterator __first, |
| 170 | _Iterator __last, |
| 171 | size_t __min_partition_size = 1, |
| 172 | size_t __workers_count = __statpart::__thread_hardware_concurrency()) noexcept { |
| 173 | _LIBCPP_ASSERT_INTERNAL(__min_partition_size >= 1, "minimum partition size must be at least 1 element" ); |
| 174 | |
| 175 | if (__workers_count < 2) { |
| 176 | // There's no available parallelism in the system, no reason to perform partitioning. |
| 177 | return {nullopt, __partitioning_status::__no_parallelism}; |
| 178 | } |
| 179 | |
| 180 | size_t __count = static_cast<size_t>(std::distance(__first, __last)); |
| 181 | size_t __max_partitions = __workers_count * __max_partitions_per_cpu; |
| 182 | size_t __partition_count = std::min(a: __max_partitions, b: __count / __min_partition_size); |
| 183 | if (__partition_count < 2) { |
| 184 | // not enough input data to process in parallel => no reason to build partitions |
| 185 | return {nullopt, __partitioning_status::__not_enough_elements}; |
| 186 | } |
| 187 | |
| 188 | size_t __base_partition_size = __count / __partition_count; |
| 189 | size_t __remainder = __count % __partition_count; |
| 190 | |
| 191 | if constexpr (__has_random_access_iterator_category_or_concept<_Iterator>::value) { |
| 192 | __iterator_partitions<_Iterator, true> __p; |
| 193 | __p.__base_ = __first; |
| 194 | __p.__count_ = __count; |
| 195 | __p.__partition_size_ = __base_partition_size; |
| 196 | __p.__remainder_ = __remainder; |
| 197 | __p.__partitions_count_ = __partition_count; |
| 198 | return {std::move(__p), __partitioning_status::__ok}; |
| 199 | } else { |
| 200 | __iterator_partitions<_Iterator, false> __p; |
| 201 | __p.__partitions_count_ = __partition_count; |
| 202 | __p.__max_partition_size_ = __base_partition_size + (__remainder > 0 ? 1 : 0); |
| 203 | __p.__partitions_.reset(new (std::nothrow) __iterator_range<_Iterator>[__partition_count]); |
| 204 | if (!__p.__partitions_) { |
| 205 | // Unable to allocate memory for the iterator stash, bail out. |
| 206 | return {nullopt, __partitioning_status::__bad_alloc}; |
| 207 | } |
| 208 | |
| 209 | // Traverse the forward iterator over the entire range and stash the iterators at each partition. |
| 210 | for (size_t __i = 0; __i != __partition_count; ++__i) { |
| 211 | size_t __partition_size = __base_partition_size + (__i < __remainder ? 1 : 0); |
| 212 | __p.__partitions_[__i].__first = __first; |
| 213 | __p.__partitions_[__i].__last = std::next(__first, __partition_size); |
| 214 | __first = __p.__partitions_[__i].__last; |
| 215 | } |
| 216 | return {std::move(__p), __partitioning_status::__ok}; |
| 217 | } |
| 218 | } |
| 219 | |
| 220 | // for_each with explicit partitioning: |
| 221 | // calls __func in parallel with every iterator range provided in __partitions. |
| 222 | template <class _Iterator, class _Functor> |
| 223 | _LIBCPP_HIDE_FROM_ABI void __for_each_partition(const __iterator_partitions<_Iterator>& __partitions, _Functor __func) { |
| 224 | struct __ctx_t { |
| 225 | const __iterator_partitions<_Iterator>& __partitions_; |
| 226 | _Functor& __func_; |
| 227 | } __apply_ctx{__partitions, __func}; |
| 228 | __statpart::__apply(chunk_count: __partitions.__partitions_count(), context: &__apply_ctx, func: [](void* __context, size_t __partition) { |
| 229 | __ctx_t& __ctx = *static_cast<__ctx_t*>(__context); |
| 230 | auto __range = __ctx.__partitions_.__partition(__partition); |
| 231 | __ctx.__func_(__range.__first, __range.__last); |
| 232 | }); |
| 233 | } |
| 234 | |
| 235 | // Calls __func(index) for every index in [0, __count) in parallel. |
| 236 | template <class _Functor> |
| 237 | _LIBCPP_HIDE_FROM_ABI void __for_each_index(size_t __count, _Functor __func) { |
| 238 | __statpart::__apply(chunk_count: __count, context: &__func, func: [](void* __context, size_t __index) { |
| 239 | (*static_cast<_Functor*>(__context))(__index); |
| 240 | }); |
| 241 | } |
| 242 | |
| 243 | // for_each that calls __func in parallel for every partition index available in __partitions. |
| 244 | template <class _Iterator, class _Functor> |
| 245 | _LIBCPP_HIDE_FROM_ABI void |
| 246 | __for_each_partition_index(const __iterator_partitions<_Iterator>& __partitions, _Functor __func) { |
| 247 | __statpart::__for_each_index(__partitions.__partitions_count(), std::move(__func)); |
| 248 | } |
| 249 | |
| 250 | // for_each with default implicit partitioning: |
| 251 | // calls __func in parallel with every element in [__first, __last), provided as iterator ranges. |
| 252 | template <class _Iterator, class _Functor> |
| 253 | _LIBCPP_HIDE_FROM_ABI optional<__empty> __for_each(_Iterator __first, _Iterator __last, _Functor __func) { |
| 254 | if (__first == __last) |
| 255 | return __empty{}; |
| 256 | auto __partitions = __statpart::__partition(__first, __last); |
| 257 | if (__partitions.__value_) { |
| 258 | __statpart::__for_each_partition(*__partitions.__value_, std::move(__func)); |
| 259 | return __empty{}; |
| 260 | } else if (__partitions.__status_ == __partitioning_status::__bad_alloc) { |
| 261 | return nullopt; |
| 262 | } else { |
| 263 | __func(__first, __last); |
| 264 | return __empty{}; |
| 265 | } |
| 266 | } |
| 267 | |
| 268 | // Applies the 3-legged function to sub-ranges of the input ranges in parallel: |
| 269 | // f(sub_range1_first, sub_range1_last, sub_range2_first) |
| 270 | template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BrickFunction> |
| 271 | _LIBCPP_HIDE_FROM_ABI optional<__empty> __for_each_iter_pair( |
| 272 | _RandomAccessIterator1 __first1, |
| 273 | _RandomAccessIterator1 __last1, |
| 274 | _RandomAccessIterator2 __first2, |
| 275 | _BrickFunction __f) { |
| 276 | return __statpart::__for_each( |
| 277 | __first1, |
| 278 | __last1, |
| 279 | [__first1, __first2, __f = std::move(__f)]( |
| 280 | _RandomAccessIterator1 __brick_first1, _RandomAccessIterator1 __brick_last1) { |
| 281 | _RandomAccessIterator2 __brick_first2 = __first2 + (__brick_first1 - __first1); |
| 282 | __f(__brick_first1, __brick_last1, __brick_first2); |
| 283 | }); |
| 284 | } |
| 285 | |
| 286 | template <class _Index, class _Brick, class _Compare> |
| 287 | _LIBCPP_HIDE_FROM_ABI optional<_Index> |
| 288 | __find(_Index __first, _Index __last, _Brick __f, _Compare __comp, bool __b_first) { |
| 289 | typedef typename std::iterator_traits<_Index>::difference_type _DifferenceType; |
| 290 | const _DifferenceType __n = __last - __first; |
| 291 | _DifferenceType __initial_dist = __b_first ? __n : -1; |
| 292 | std::atomic<_DifferenceType> __extremum(__initial_dist); |
| 293 | // TODO: find out what is better here: parallel_for or parallel_reduce |
| 294 | auto __res = __statpart::__for_each(__first, __last, [__comp, __f, __first, &__extremum](_Index __i, _Index __j) { |
| 295 | // See "Reducing Contention Through Priority Updates", PPoPP '13, for discussion of |
| 296 | // why using a shared variable scales fairly well in this situation. |
| 297 | if (__comp(__i - __first, __extremum)) { |
| 298 | _Index __result = __f(__i, __j); |
| 299 | // If not '__last' returned then we found what we want so put this to extremum |
| 300 | if (__result != __j) { |
| 301 | const _DifferenceType __k = __result - __first; |
| 302 | for (_DifferenceType __old = __extremum; __comp(__k, __old); __old = __extremum) { |
| 303 | __extremum.compare_exchange_weak(__old, __k); |
| 304 | } |
| 305 | } |
| 306 | } |
| 307 | }); |
| 308 | if (!__res) |
| 309 | return nullopt; |
| 310 | return __extremum.load() != __initial_dist ? __first + __extremum.load() : __last; |
| 311 | } |
| 312 | |
| 313 | template <class _RandomAccessIterator, class _Transform, class _Value, class _Combiner, class _Reduction> |
| 314 | _LIBCPP_HIDE_FROM_ABI optional<_Value> __transform_reduce( |
| 315 | _RandomAccessIterator __first, |
| 316 | _RandomAccessIterator __last, |
| 317 | _Transform __transform, |
| 318 | _Value __init, |
| 319 | _Combiner __combiner, |
| 320 | _Reduction __reduction) { |
| 321 | if (__first == __last) |
| 322 | return __init; |
| 323 | |
| 324 | // Split into partitions with at least 3 elements in each |
| 325 | auto __partitions = __statpart::__partition(__first, __last, 3); |
| 326 | if (!__partitions.__value_) { |
| 327 | if (__partitions.__status_ == __partitioning_status::__bad_alloc) { |
| 328 | // Failed to allocate memory for the partitions, propagate the error up. |
| 329 | return nullopt; |
| 330 | } else { |
| 331 | // Not enough elements to run in parallel, switch to serial implementation. |
| 332 | return __reduction(std::move(__first), std::move(__last), std::move(__init)); |
| 333 | } |
| 334 | } |
| 335 | |
| 336 | auto __destroy = [__count = __partitions.__value_->__partitions_count()](_Value* __ptr) { |
| 337 | std::destroy_n(__ptr, __count); |
| 338 | std::allocator<_Value>().deallocate(__ptr, __count); |
| 339 | }; |
| 340 | |
| 341 | // TODO: use __uninitialized_buffer |
| 342 | // TODO: allocate one element per worker instead of one element per chunk |
| 343 | unique_ptr<_Value[], decltype(__destroy)> __values( |
| 344 | std::allocator<_Value>().allocate(__partitions.__value_->__partitions_count()), __destroy); |
| 345 | |
| 346 | // __dispatch_apply is noexcept |
| 347 | __statpart::__for_each_partition_index(*__partitions.__value_, [&](size_t __index) { |
| 348 | auto __range = __partitions.__value_->__partition(__index); |
| 349 | std::__construct_at( |
| 350 | __values.get() + __index, |
| 351 | __reduction(__range.__first + 2, |
| 352 | __range.__last, |
| 353 | __combiner(__transform(__range.__first), __transform(__range.__first + 1)))); |
| 354 | }); |
| 355 | |
| 356 | return std::reduce( |
| 357 | std::make_move_iterator(__values.get()), |
| 358 | std::make_move_iterator(__values.get() + __partitions.__value_->__partitions_count()), |
| 359 | std::move(__init), |
| 360 | __combiner); |
| 361 | } |
| 362 | |
| 363 | template <class _RandomAccessIterator1, |
| 364 | class _RandomAccessIterator2, |
| 365 | class _RandomAccessIterator3, |
| 366 | class _Compare, |
| 367 | class _LeafMerge> |
| 368 | _LIBCPP_HIDE_FROM_ABI optional<__empty> |
| 369 | __merge(_RandomAccessIterator1 __first1, |
| 370 | _RandomAccessIterator1 __last1, |
| 371 | _RandomAccessIterator2 __first2, |
| 372 | _RandomAccessIterator2 __last2, |
| 373 | _RandomAccessIterator3 __result, |
| 374 | _Compare __comp, |
| 375 | _LeafMerge __leaf_merge) noexcept { |
| 376 | // Run the merge such that the longest range is partitioned. |
| 377 | // __merge_sub_ranges swaps the ranges implicitly in case the second range was the longest one. |
| 378 | auto __run = |
| 379 | [__result](auto __long_first, |
| 380 | auto __long_last, |
| 381 | auto __short_first, |
| 382 | auto __short_last, |
| 383 | auto __find_cutpoint, |
| 384 | auto __merge_sub_ranges) -> optional<__empty> { |
| 385 | // Partition the longest input range evenly. |
| 386 | auto __partitions = __statpart::__partition(__long_first, __long_last); |
| 387 | if (!__partitions.__value_) { |
| 388 | if (__partitions.__status_ == __partitioning_status::__bad_alloc) |
| 389 | return nullopt; |
| 390 | // Not enough elements to run in parallel, merge everything serially. |
| 391 | __merge_sub_ranges(__long_first, __long_last, __short_first, __short_last, __result); |
| 392 | return __empty{}; |
| 393 | } |
| 394 | |
| 395 | // Process the partitions of the longest range in parallel. |
| 396 | __statpart::__for_each_partition_index(*__partitions.__value_, [&](size_t __index) { |
| 397 | // Get the sub-range inside the longer input range. |
| 398 | auto __range = __partitions.__value_->__partition(__index); |
| 399 | |
| 400 | // Find the matching sub-range of the shorter input range: it will hold the elements that come after the last |
| 401 | // element of the previous long partition and up to the last element of this partition. |
| 402 | // This generally runs two binary searches in the smaller input range, edge partitions use existing bounds. |
| 403 | auto __short_begin = |
| 404 | __index == 0 ? __short_first : __find_cutpoint(__short_first, __short_last, __range.__first[-1]); |
| 405 | auto __short_end = |
| 406 | __index == __partitions.__value_->__partitions_count() - 1 |
| 407 | ? __short_last |
| 408 | : __find_cutpoint(__short_first, __short_last, __range.__last[-1]); |
| 409 | |
| 410 | // Derive the position in the output range and merge the sub-ranges. |
| 411 | auto __result_first = __result + (__range.__first - __long_first) + (__short_begin - __short_first); |
| 412 | __merge_sub_ranges(__range.__first, __range.__last, __short_begin, __short_end, __result_first); |
| 413 | }); |
| 414 | return __empty{}; |
| 415 | }; |
| 416 | |
| 417 | if (__last1 - __first1 > __last2 - __first2) { |
| 418 | // Preserve the order of the input ranges, partition the first range. |
| 419 | // Equal elements of the second range go after the cut => use lower_bound when cutting. |
| 420 | return __run( |
| 421 | __first1, |
| 422 | __last1, |
| 423 | __first2, |
| 424 | __last2, |
| 425 | [&](auto __first, auto __last, const auto& __value) { |
| 426 | return std::lower_bound(__first, __last, __value, __comp); |
| 427 | }, |
| 428 | [&](auto __long_first, auto __long_last, auto __short_first, auto __short_last, auto __result_first) { |
| 429 | __leaf_merge(__long_first, __long_last, __short_first, __short_last, __result_first, __comp); |
| 430 | }); |
| 431 | } else { |
| 432 | // Swap the order of the input ranges, partition the second range. |
| 433 | // Equal elements of the first range go before the cut => use upper_bound when cutting. |
| 434 | return __run( |
| 435 | __first2, |
| 436 | __last2, |
| 437 | __first1, |
| 438 | __last1, |
| 439 | [&](auto __first, auto __last, const auto& __value) { |
| 440 | return std::upper_bound(__first, __last, __value, __comp); |
| 441 | }, |
| 442 | [&](auto __long_first, auto __long_last, auto __short_first, auto __short_last, auto __result_first) { |
| 443 | __leaf_merge(__short_first, __short_last, __long_first, __long_last, __result_first, __comp); |
| 444 | }); |
| 445 | } |
| 446 | } |
| 447 | |
| 448 | template <class _RandomAccessIterator, class _Comp, class _LeafSort> |
| 449 | _LIBCPP_HIDE_FROM_ABI optional<__empty> |
| 450 | __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp, _LeafSort __leaf_sort) { |
| 451 | const auto __size = __last - __first; |
| 452 | |
| 453 | auto __partitions = __statpart::__partition(__first, __last, __min_sort_partition_size); |
| 454 | if (!__partitions.__value_) { |
| 455 | if (__partitions.__status_ == __partitioning_status::__bad_alloc) |
| 456 | return nullopt; |
| 457 | // Not enough elements to run in parallel, sort everything serially. |
| 458 | __leaf_sort(__first, __last, __comp); |
| 459 | return __empty{}; |
| 460 | } |
| 461 | |
| 462 | using _Value = __iterator_value_type<_RandomAccessIterator>; |
| 463 | |
| 464 | auto __destroy = [__size](_Value* __ptr) { |
| 465 | std::destroy_n(__ptr, __size); |
| 466 | std::allocator<_Value>().deallocate(__ptr, __size); |
| 467 | }; |
| 468 | |
| 469 | // TODO: use __uninitialized_buffer |
| 470 | unique_ptr<_Value[], decltype(__destroy)> __values(std::allocator<_Value>().allocate(__size), __destroy); |
| 471 | |
| 472 | // Initialize all elements to a moved-from state |
| 473 | // TODO: Don't do this - this can be done in the first merge - see https://llvm.org/PR63928 |
| 474 | std::__construct_at(__values.get(), std::move(*__first)); |
| 475 | for (__iterator_difference_type<_RandomAccessIterator> __i = 1; __i != __size; ++__i) { |
| 476 | std::__construct_at(__values.get() + __i, std::move(__values.get()[__i - 1])); |
| 477 | } |
| 478 | *__first = std::move(__values.get()[__size - 1]); |
| 479 | |
| 480 | __statpart::__for_each_partition( |
| 481 | *__partitions.__value_, |
| 482 | [&__leaf_sort, &__comp](_RandomAccessIterator __chunk_first, _RandomAccessIterator __chunk_last) { |
| 483 | __leaf_sort(std::move(__chunk_first), std::move(__chunk_last), __comp); |
| 484 | }); |
| 485 | |
| 486 | // A chunk span is a run of __chunk_span_size consecutive partitions, the last chunk can be shorter in case of odd |
| 487 | // number of chunk spans. Each pass merges the chunk spans pairwise, so the chunk span size doubles and the chunk |
| 488 | // count is halved (rounded up). |
| 489 | const size_t __partition_count = __partitions.__value_->__partitions_count(); |
| 490 | size_t __chunk_span_size = 1; |
| 491 | size_t __chunk_spans = __partition_count; |
| 492 | |
| 493 | // Offsets of the beginning and the end of the chunk from __first |
| 494 | auto __chunk_begin = [&](size_t __chunk) { |
| 495 | return __partitions.__value_->__partition(__chunk * __chunk_span_size).__first - __first; |
| 496 | }; |
| 497 | auto __chunk_end = [&](size_t __chunk) { |
| 498 | return __partitions.__value_->__partition(std::min(a: (__chunk + 1) * __chunk_span_size, b: __partition_count) - 1) |
| 499 | .__last - |
| 500 | __first; |
| 501 | }; |
| 502 | |
| 503 | bool __objects_are_in_buffer = false; |
| 504 | do { |
| 505 | size_t __chunk_spans_pairs = (__chunk_spans + 1) / 2; |
| 506 | auto __merge_chunks = [&](auto __from_first, auto __to_first) { |
| 507 | __statpart::__for_each_index(__chunk_spans_pairs, [&](size_t __span_pair_index) { |
| 508 | size_t __left_chunk = 2 * __span_pair_index; |
| 509 | size_t __right_chunk = __left_chunk + 1; |
| 510 | auto __pair_first = __chunk_begin(__left_chunk); |
| 511 | if (__right_chunk == __chunk_spans) { |
| 512 | // The odd chunk has no counterpart to merge with => carry it over to the other buffer as-is. |
| 513 | std::move(__from_first + __pair_first, __from_first + __chunk_end(__left_chunk), __to_first + __pair_first); |
| 514 | } else { |
| 515 | // Merge the two chunk spans into the other buffer |
| 516 | auto __pair_mid = __chunk_begin(__right_chunk); |
| 517 | auto __pair_last = __chunk_end(__right_chunk); |
| 518 | std::merge(std::make_move_iterator(__from_first + __pair_first), |
| 519 | std::make_move_iterator(__from_first + __pair_mid), |
| 520 | std::make_move_iterator(__from_first + __pair_mid), |
| 521 | std::make_move_iterator(__from_first + __pair_last), |
| 522 | __to_first + __pair_first, |
| 523 | __comp); |
| 524 | } |
| 525 | }); |
| 526 | }; |
| 527 | |
| 528 | if (__objects_are_in_buffer) |
| 529 | __merge_chunks(__values.get(), __first); |
| 530 | else |
| 531 | __merge_chunks(__first, __values.get()); |
| 532 | __objects_are_in_buffer = !__objects_are_in_buffer; |
| 533 | |
| 534 | __chunk_span_size *= 2; |
| 535 | __chunk_spans = __chunk_spans_pairs; |
| 536 | } while (__chunk_spans > 1); |
| 537 | |
| 538 | if (__objects_are_in_buffer) { |
| 539 | std::move(__values.get(), __values.get() + __size, __first); |
| 540 | } |
| 541 | |
| 542 | return __empty{}; |
| 543 | } |
| 544 | |
| 545 | // __lookback_scan() provides a basic building block for the family of scanning algorithms. |
| 546 | // It's based on the paper "Single-pass Parallel Prefix Scan with Decoupled Look-back", and follows these steps: |
| 547 | // - The input range is partitioned with at least 2 elements per partition. |
| 548 | // - A lookback storage is allocated for each of the partitions except the last one. |
| 549 | // - A higher-level algorithm can at this point allocate any scratch context it might need. |
| 550 | // - for_each_index(max_workers_count, ...) runs this lambda in parallel: |
| 551 | // - While this worker can atomically pick the next partition to process in a strictly monotonically increasing order: |
| 552 | // - Pick the partition by its index. |
| 553 | // - Process the partition with __scan_head/__scan_middle/__scan_tail, depending on the partition position in the |
| 554 | // input range. |
| 555 | // The callbacks are given the scratch context, the worker index, the range of iterators to process, and an |
| 556 | // optional pointer to the lookback partition. |
| 557 | // Callbacks follow roughly these steps (may vary between head/middle/tail): |
| 558 | // - Calculate and publish the result of their local reduction. |
| 559 | // - Obtain the inclusive prefix of the previous lookback partition. |
| 560 | // - Calculate and publish the inclusive prefix of their own lookback partition. |
| 561 | // - Perform the scanning operation. |
| 562 | // |
| 563 | // Description of the callbacks: |
| 564 | // - __setup: std::optional<OpaqueCtx>(size_t number_of_workers, size_t max_partition_size) |
| 565 | // Provides an injection point for a higher-level algorithm to allocate resources upfront. |
| 566 | // The context this callback creates is opaque to __lookback_scan and will be passed as-is to each invocation of |
| 567 | // the head/middle/tail callbacks. |
| 568 | // In case __setup() returns std::nullopt, __lookback_scan will abort the operation and return std::nullopt. |
| 569 | // - __scan_head: void(OpaqueCtx& ctx, |
| 570 | // size_t worker_idx, |
| 571 | // It chunk_first, |
| 572 | // It chunk_last, |
| 573 | // __decoupled_lookback_partition<Value> *optional_lookback_partition) |
| 574 | // - __scan_middle: void(OpaqueCtx& ctx, |
| 575 | // size_t worker_idx, |
| 576 | // It chunk_first, |
| 577 | // It chunk_last, |
| 578 | // __decoupled_lookback_partition<Value> *lookback_partition) |
| 579 | // - __scan_tail: void(OpaqueCtx& ctx, |
| 580 | // size_t worker_idx, |
| 581 | // It chunk_first, |
| 582 | // It chunk_last, |
| 583 | // __decoupled_lookback_partition<Value> *nonexistent_lookback_partition) |
| 584 | // All scanning callbacks have the same signature, but differ in how the last parameter is interpreted: |
| 585 | // The head callback will get a valid pointer in regular cases, but in the edge case of having a single partition this |
| 586 | // pointer will be nullptr. The middle callback always has a lookback partition. The tail callback never gets a |
| 587 | // lookback partition and can only use the provided pointer to access the previous one. |
| 588 | template <class _Value, class _RandomAccessIterator, class _Setup, class _ScanHead, class _ScanMiddle, class _ScanTail> |
| 589 | _LIBCPP_HIDE_FROM_ABI optional<__empty> __lookback_scan( |
| 590 | _RandomAccessIterator __first, |
| 591 | _RandomAccessIterator __last, |
| 592 | _Setup __setup, |
| 593 | _ScanHead __scan_head, |
| 594 | _ScanMiddle __scan_middle, |
| 595 | _ScanTail __scan_tail) { |
| 596 | if (__first == __last) |
| 597 | return __empty{}; // nothing to do |
| 598 | |
| 599 | // Determine how many workers we could potentially have on the hardware level. |
| 600 | // Do it only once and pass the same value to __partition below, to avoid a redundant syscall. |
| 601 | size_t __max_workers_count = __statpart::__thread_hardware_concurrency(); |
| 602 | |
| 603 | // Partition the input. |
| 604 | auto __partitioning_result = __statpart::__partition( |
| 605 | __first, |
| 606 | __last, |
| 607 | /*__min_partition_size=*/2, |
| 608 | /*__workers_count=*/__max_workers_count); |
| 609 | if (!__partitioning_result.__value_) { |
| 610 | if (__partitioning_result.__status_ == __partitioning_status::__bad_alloc) |
| 611 | return nullopt; |
| 612 | // Not enough elements or partitions to run in parallel, scan everything serially using the head scanning. |
| 613 | auto __ctx = __setup(/*worker_count=*/1, /*max_partition_size=*/static_cast<size_t>(__last - __first)); |
| 614 | if (__ctx == nullopt) |
| 615 | return nullopt; // Failed to allocate memory for the operation context |
| 616 | __scan_head(*__ctx, 0, __first, __last, nullptr); |
| 617 | return __empty{}; |
| 618 | } |
| 619 | auto& __partitions = *__partitioning_result.__value_; |
| 620 | _LIBCPP_ASSERT_INTERNAL(__partitions.__partitions_count() >= 2, "the number of partitions must be at least 2" ); |
| 621 | |
| 622 | // Allocate the lookback storage. |
| 623 | // The last partition doesn't need a storage in the lookback, hence its size is 1 less than the number of partitions. |
| 624 | optional<__decoupled_lookback<_Value>> __lookback = |
| 625 | __statpart::__make_decoupled_lookback<_Value>(__partitions.__partitions_count() - 1); |
| 626 | if (__lookback == nullopt) { |
| 627 | return nullopt; // Failed to allocate the lookback storage, report an error |
| 628 | } |
| 629 | |
| 630 | // Limit the max workers count by the number of partitions we actually have, to avoid allocating unnecessary resources |
| 631 | // later. |
| 632 | size_t __effective_max_workers_count = std::min(__max_workers_count, __partitions.__partitions_count()); |
| 633 | |
| 634 | // Allow the scanning operation to allocate upfront any context it needs |
| 635 | auto __ctx = __setup(__effective_max_workers_count, __partitions.__max_partition_size()); |
| 636 | if (__ctx == nullopt) { |
| 637 | return nullopt; // Failed to allocate the scratch context for the operation, report an error |
| 638 | } |
| 639 | |
| 640 | // Run the single-pass scan with decoupled lookback. |
| 641 | // Ask the threading backend to run up to __effective_max_workers_count workers in parallel, each of them picks the |
| 642 | // next partition to work on in a monotonically increasing order. |
| 643 | std::atomic<size_t> __next_partition_idx{0}; |
| 644 | __statpart::__for_each_index(__effective_max_workers_count, [&](size_t __worker_id) { |
| 645 | // Pick the next chunk to work on, stop once the partitions are exhausted. |
| 646 | size_t __partition_idx; |
| 647 | while ((__partition_idx = __next_partition_idx.fetch_add(op: 1, m: std::memory_order_relaxed)) < |
| 648 | __partitions.__partitions_count()) { |
| 649 | // Determine the input range of this chunk. |
| 650 | auto __partition = __partitions.__partition(__partition_idx); |
| 651 | // Depending on the position of the partition in the input, call either a head, a middle or a tail scan callback. |
| 652 | if (__partition_idx == 0) |
| 653 | __scan_head(*__ctx, // |
| 654 | __worker_id, // |
| 655 | __partition.__first, // |
| 656 | __partition.__last, // |
| 657 | &__lookback->__partition(0)); |
| 658 | else if (__partition_idx < __lookback->__size()) |
| 659 | __scan_middle(*__ctx, // |
| 660 | __worker_id, // |
| 661 | __partition.__first, // |
| 662 | __partition.__last, // |
| 663 | &__lookback->__partition(__partition_idx)); |
| 664 | else |
| 665 | __scan_tail(*__ctx, // |
| 666 | __worker_id, // |
| 667 | __partition.__first, // |
| 668 | __partition.__last, // |
| 669 | __lookback->__partitions() + __partition_idx); |
| 670 | } |
| 671 | }); |
| 672 | |
| 673 | return __empty{}; |
| 674 | } |
| 675 | |
| 676 | } // namespace __statpart |
| 677 | |
| 678 | } // namespace __pstl |
| 679 | _LIBCPP_END_EXPLICIT_ABI_ANNOTATIONS |
| 680 | _LIBCPP_END_NAMESPACE_STD |
| 681 | |
| 682 | #endif // _LIBCPP_STD_VER >= 17 |
| 683 | |
| 684 | _LIBCPP_POP_MACROS |
| 685 | |
| 686 | #endif // _LIBCPP___PSTL_BACKENDS_STATPART_BASIS_H |
| 687 | |