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
57namespace __pstl {
58
59namespace __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
67constexpr inline size_t __max_partitions_per_cpu = 8;
68
69// The minimum number of elements to sort serially in a single partition
70constexpr inline size_t __min_sort_partition_size = 256;
71
72constexpr inline size_t __lane_size = 64;
73
74enum 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
87template <class _Iterator>
88struct _LIBCPP_HIDE_FROM_ABI __partitioning_result;
89
90template <class _Iterator>
91struct _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.
98template <class _Iterator,
99 bool _IsRandomAccessOrContiguous = __has_random_access_iterator_category_or_concept<_Iterator>::value >
100struct _LIBCPP_HIDE_FROM_ABI __iterator_partitions;
101
102// Specialization of __iterator_partitions<_Iterator> for random-access iterators
103template <class _Iterator >
104struct _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
115private:
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
127template <class _Iterator >
128struct _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
135private:
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.
146template <class _Iterator>
147struct _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.
167template <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.
222template <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.
236template <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.
244template <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.
252template <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)
270template <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
286template <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
313template <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
363template <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
448template <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.
588template <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