1 // -*- C++ -*-
2 //===-- parallel_backend_tbb.h --------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9
10 #ifndef _PSTL_PARALLEL_BACKEND_TBB_H
11 #define _PSTL_PARALLEL_BACKEND_TBB_H
12
13 #include <algorithm>
14 #include <type_traits>
15
16 #include "parallel_backend_utils.h"
17
18 // Bring in minimal required subset of Intel TBB
19 #include <tbb/blocked_range.h>
20 #include <tbb/parallel_for.h>
21 #include <tbb/parallel_reduce.h>
22 #include <tbb/parallel_scan.h>
23 #include <tbb/parallel_invoke.h>
24 #include <tbb/task_arena.h>
25 #include <tbb/tbb_allocator.h>
26 #include <tbb/task.h>
27
28 #if TBB_INTERFACE_VERSION < 10000
29 # error Intel(R) Threading Building Blocks 2018 is required; older versions are not supported.
30 #endif
31
32 namespace __pstl
33 {
34 namespace __tbb_backend
35 {
36
37 //! Raw memory buffer with automatic freeing and no exceptions.
38 /** Some of our algorithms need to start with raw memory buffer,
39 not an initialize array, because initialization/destruction
40 would make the span be at least O(N). */
41 // tbb::allocator can improve performance in some cases.
42 template <typename _Tp>
43 class __buffer
44 {
45 tbb::tbb_allocator<_Tp> _M_allocator;
46 _Tp* _M_ptr;
47 const std::size_t _M_buf_size;
48 __buffer(const __buffer&) = delete;
49 void
50 operator=(const __buffer&) = delete;
51
52 public:
53 //! Try to obtain buffer of given size to store objects of _Tp type
54 __buffer(std::size_t n) : _M_allocator(), _M_ptr(_M_allocator.allocate(n)), _M_buf_size(n) {}
55 //! True if buffer was successfully obtained, zero otherwise.
56 operator bool() const { return _M_ptr != NULL; }
57 //! Return pointer to buffer, or NULL if buffer could not be obtained.
58 _Tp*
59 get() const
60 {
61 return _M_ptr;
62 }
63 //! Destroy buffer
64 ~__buffer() { _M_allocator.deallocate(_M_ptr, _M_buf_size); }
65 };
66
67 // Wrapper for tbb::task
68 inline void
69 __cancel_execution()
70 {
71 #if TBB_INTERFACE_VERSION <= 12000
72 tbb::task::self().group()->cancel_group_execution();
73 #else
74 tbb::task::current_context()->cancel_group_execution();
75 #endif
76 }
77
78 //------------------------------------------------------------------------
79 // parallel_for
80 //------------------------------------------------------------------------
81
82 template <class _Index, class _RealBody>
83 class __parallel_for_body
84 {
85 public:
86 __parallel_for_body(const _RealBody& __body) : _M_body(__body) {}
87 __parallel_for_body(const __parallel_for_body& __body) : _M_body(__body._M_body) {}
88 void
89 operator()(const tbb::blocked_range<_Index>& __range) const
90 {
91 _M_body(__range.begin(), __range.end());
92 }
93
94 private:
95 _RealBody _M_body;
96 };
97
98 //! Evaluation of brick f[i,j) for each subrange [i,j) of [first,last)
99 // wrapper over tbb::parallel_for
100 template <class _ExecutionPolicy, class _Index, class _Fp>
101 void
102 __parallel_for(_ExecutionPolicy&&, _Index __first, _Index __last, _Fp __f)
103 {
104 tbb::this_task_arena::isolate([=]() {
105 tbb::parallel_for(tbb::blocked_range<_Index>(__first, __last), __parallel_for_body<_Index, _Fp>(__f));
106 });
107 }
108
109 //! Evaluation of brick f[i,j) for each subrange [i,j) of [first,last)
110 // wrapper over tbb::parallel_reduce
111 template <class _ExecutionPolicy, class _Value, class _Index, typename _RealBody, typename _Reduction>
112 _Value
113 __parallel_reduce(_ExecutionPolicy&&, _Index __first, _Index __last, const _Value& __identity,
114 const _RealBody& __real_body, const _Reduction& __reduction)
115 {
116 return tbb::this_task_arena::isolate([__first, __last, &__identity, &__real_body, &__reduction]() -> _Value {
117 return tbb::parallel_reduce(
118 tbb::blocked_range<_Index>(__first, __last), __identity,
119 [__real_body](const tbb::blocked_range<_Index>& __r, const _Value& __value) -> _Value {
120 return __real_body(__r.begin(), __r.end(), __value);
121 },
122 __reduction);
123 });
124 }
125
126 //------------------------------------------------------------------------
127 // parallel_transform_reduce
128 //
129 // Notation:
130 // r(i,j,init) returns reduction of init with reduction over [i,j)
131 // u(i) returns f(i,i+1,identity) for a hypothetical left identity element of r
132 // c(x,y) combines values x and y that were the result of r or u
133 //------------------------------------------------------------------------
134
135 template <class _Index, class _Up, class _Tp, class _Cp, class _Rp>
136 struct __par_trans_red_body
137 {
138 alignas(_Tp) char _M_sum_storage[sizeof(_Tp)]; // Holds generalized non-commutative sum when has_sum==true
139 _Rp _M_brick_reduce; // Most likely to have non-empty layout
140 _Up _M_u;
141 _Cp _M_combine;
142 bool _M_has_sum; // Put last to minimize size of class
143 _Tp&
144 sum()
145 {
146 _PSTL_ASSERT_MSG(_M_has_sum, "sum expected");
147 return *(_Tp*)_M_sum_storage;
148 }
149 __par_trans_red_body(_Up __u, _Tp __init, _Cp __c, _Rp __r)
150 : _M_brick_reduce(__r), _M_u(__u), _M_combine(__c), _M_has_sum(true)
151 {
152 new (_M_sum_storage) _Tp(__init);
153 }
154
155 __par_trans_red_body(__par_trans_red_body& __left, tbb::split)
156 : _M_brick_reduce(__left._M_brick_reduce), _M_u(__left._M_u), _M_combine(__left._M_combine), _M_has_sum(false)
157 {
158 }
159
160 ~__par_trans_red_body()
161 {
162 // 17.6.5.12 tells us to not worry about catching exceptions from destructors.
163 if (_M_has_sum)
164 sum().~_Tp();
165 }
166
167 void
168 join(__par_trans_red_body& __rhs)
169 {
170 sum() = _M_combine(sum(), __rhs.sum());
171 }
172
173 void
174 operator()(const tbb::blocked_range<_Index>& __range)
175 {
176 _Index __i = __range.begin();
177 _Index __j = __range.end();
178 if (!_M_has_sum)
179 {
180 _PSTL_ASSERT_MSG(__range.size() > 1, "there should be at least 2 elements");
181 new (&_M_sum_storage)
182 _Tp(_M_combine(_M_u(__i), _M_u(__i + 1))); // The condition i+1 < j is provided by the grain size of 3
183 _M_has_sum = true;
184 std::advance(__i, 2);
185 if (__i == __j)
186 return;
187 }
188 sum() = _M_brick_reduce(__i, __j, sum());
189 }
190 };
191
192 template <class _ExecutionPolicy, class _Index, class _Up, class _Tp, class _Cp, class _Rp>
193 _Tp
194 __parallel_transform_reduce(_ExecutionPolicy&&, _Index __first, _Index __last, _Up __u, _Tp __init, _Cp __combine,
195 _Rp __brick_reduce)
196 {
197 __tbb_backend::__par_trans_red_body<_Index, _Up, _Tp, _Cp, _Rp> __body(__u, __init, __combine, __brick_reduce);
198 // The grain size of 3 is used in order to provide mininum 2 elements for each body
199 tbb::this_task_arena::isolate(
200 [__first, __last, &__body]() { tbb::parallel_reduce(tbb::blocked_range<_Index>(__first, __last, 3), __body); });
201 return __body.sum();
202 }
203
204 //------------------------------------------------------------------------
205 // parallel_scan
206 //------------------------------------------------------------------------
207
208 template <class _Index, class _Up, class _Tp, class _Cp, class _Rp, class _Sp>
209 class __trans_scan_body
210 {
211 alignas(_Tp) char _M_sum_storage[sizeof(_Tp)]; // Holds generalized non-commutative sum when has_sum==true
212 _Rp _M_brick_reduce; // Most likely to have non-empty layout
213 _Up _M_u;
214 _Cp _M_combine;
215 _Sp _M_scan;
216 bool _M_has_sum; // Put last to minimize size of class
217 public:
218 __trans_scan_body(_Up __u, _Tp __init, _Cp __combine, _Rp __reduce, _Sp __scan)
219 : _M_brick_reduce(__reduce), _M_u(__u), _M_combine(__combine), _M_scan(__scan), _M_has_sum(true)
220 {
221 new (_M_sum_storage) _Tp(__init);
222 }
223
224 __trans_scan_body(__trans_scan_body& __b, tbb::split)
225 : _M_brick_reduce(__b._M_brick_reduce), _M_u(__b._M_u), _M_combine(__b._M_combine), _M_scan(__b._M_scan),
226 _M_has_sum(false)
227 {
228 }
229
230 ~__trans_scan_body()
231 {
232 // 17.6.5.12 tells us to not worry about catching exceptions from destructors.
233 if (_M_has_sum)
234 sum().~_Tp();
235 }
236
237 _Tp&
238 sum() const
239 {
240 _PSTL_ASSERT_MSG(_M_has_sum, "sum expected");
241 return *const_cast<_Tp*>(reinterpret_cast<_Tp const*>(_M_sum_storage));
242 }
243
244 void
245 operator()(const tbb::blocked_range<_Index>& __range, tbb::pre_scan_tag)
246 {
247 _Index __i = __range.begin();
248 _Index __j = __range.end();
249 if (!_M_has_sum)
250 {
251 new (&_M_sum_storage) _Tp(_M_u(__i));
252 _M_has_sum = true;
253 ++__i;
254 if (__i == __j)
255 return;
256 }
257 sum() = _M_brick_reduce(__i, __j, sum());
258 }
259
260 void
261 operator()(const tbb::blocked_range<_Index>& __range, tbb::final_scan_tag)
262 {
263 sum() = _M_scan(__range.begin(), __range.end(), sum());
264 }
265
266 void
267 reverse_join(__trans_scan_body& __a)
268 {
269 if (_M_has_sum)
270 {
271 sum() = _M_combine(__a.sum(), sum());
272 }
273 else
274 {
275 new (&_M_sum_storage) _Tp(__a.sum());
276 _M_has_sum = true;
277 }
278 }
279
280 void
281 assign(__trans_scan_body& __b)
282 {
283 sum() = __b.sum();
284 }
285 };
286
287 template <typename _Index>
288 _Index
289 __split(_Index __m)
290 {
291 _Index __k = 1;
292 while (2 * __k < __m)
293 __k *= 2;
294 return __k;
295 }
296
297 //------------------------------------------------------------------------
298 // __parallel_strict_scan
299 //------------------------------------------------------------------------
300
301 template <typename _Index, typename _Tp, typename _Rp, typename _Cp>
302 void
303 __upsweep(_Index __i, _Index __m, _Index __tilesize, _Tp* __r, _Index __lastsize, _Rp __reduce, _Cp __combine)
304 {
305 if (__m == 1)
306 __r[0] = __reduce(__i * __tilesize, __lastsize);
307 else
308 {
309 _Index __k = __split(__m);
310 tbb::parallel_invoke(
311 [=] { __tbb_backend::__upsweep(__i, __k, __tilesize, __r, __tilesize, __reduce, __combine); },
312 [=] {
313 __tbb_backend::__upsweep(__i + __k, __m - __k, __tilesize, __r + __k, __lastsize, __reduce, __combine);
314 });
315 if (__m == 2 * __k)
316 __r[__m - 1] = __combine(__r[__k - 1], __r[__m - 1]);
317 }
318 }
319
320 template <typename _Index, typename _Tp, typename _Cp, typename _Sp>
321 void
322 __downsweep(_Index __i, _Index __m, _Index __tilesize, _Tp* __r, _Index __lastsize, _Tp __initial, _Cp __combine,
323 _Sp __scan)
324 {
325 if (__m == 1)
326 __scan(__i * __tilesize, __lastsize, __initial);
327 else
328 {
329 const _Index __k = __split(__m);
330 tbb::parallel_invoke(
331 [=] { __tbb_backend::__downsweep(__i, __k, __tilesize, __r, __tilesize, __initial, __combine, __scan); },
332 // Assumes that __combine never throws.
333 //TODO: Consider adding a requirement for user functors to be constant.
334 [=, &__combine] {
335 __tbb_backend::__downsweep(__i + __k, __m - __k, __tilesize, __r + __k, __lastsize,
336 __combine(__initial, __r[__k - 1]), __combine, __scan);
337 });
338 }
339 }
340
341 // Adapted from Intel(R) Cilk(TM) version from cilkpub.
342 // Let i:len denote a counted interval of length n starting at i. s denotes a generalized-sum value.
343 // Expected actions of the functors are:
344 // reduce(i,len) -> s -- return reduction value of i:len.
345 // combine(s1,s2) -> s -- return merged sum
346 // apex(s) -- do any processing necessary between reduce and scan.
347 // scan(i,len,initial) -- perform scan over i:len starting with initial.
348 // The initial range 0:n is partitioned into consecutive subranges.
349 // reduce and scan are each called exactly once per subrange.
350 // Thus callers can rely upon side effects in reduce.
351 // combine must not throw an exception.
352 // apex is called exactly once, after all calls to reduce and before all calls to scan.
353 // For example, it's useful for allocating a __buffer used by scan but whose size is the sum of all reduction values.
354 // T must have a trivial constructor and destructor.
355 template <class _ExecutionPolicy, typename _Index, typename _Tp, typename _Rp, typename _Cp, typename _Sp, typename _Ap>
356 void
357 __parallel_strict_scan(_ExecutionPolicy&&, _Index __n, _Tp __initial, _Rp __reduce, _Cp __combine, _Sp __scan,
358 _Ap __apex)
359 {
360 tbb::this_task_arena::isolate([=, &__combine]() {
361 if (__n > 1)
362 {
363 _Index __p = tbb::this_task_arena::max_concurrency();
364 const _Index __slack = 4;
365 _Index __tilesize = (__n - 1) / (__slack * __p) + 1;
366 _Index __m = (__n - 1) / __tilesize;
367 __buffer<_Tp> __buf(__m + 1);
368 _Tp* __r = __buf.get();
369 __tbb_backend::__upsweep(_Index(0), _Index(__m + 1), __tilesize, __r, __n - __m * __tilesize, __reduce,
370 __combine);
371
372 // When __apex is a no-op and __combine has no side effects, a good optimizer
373 // should be able to eliminate all code between here and __apex.
374 // Alternatively, provide a default value for __apex that can be
375 // recognized by metaprogramming that conditionlly executes the following.
376 size_t __k = __m + 1;
377 _Tp __t = __r[__k - 1];
378 while ((__k &= __k - 1))
379 __t = __combine(__r[__k - 1], __t);
380 __apex(__combine(__initial, __t));
381 __tbb_backend::__downsweep(_Index(0), _Index(__m + 1), __tilesize, __r, __n - __m * __tilesize, __initial,
382 __combine, __scan);
383 return;
384 }
385 // Fewer than 2 elements in sequence, or out of memory. Handle has single block.
386 _Tp __sum = __initial;
387 if (__n)
388 __sum = __combine(__sum, __reduce(_Index(0), __n));
389 __apex(__sum);
390 if (__n)
391 __scan(_Index(0), __n, __initial);
392 });
393 }
394
395 template <class _ExecutionPolicy, class _Index, class _Up, class _Tp, class _Cp, class _Rp, class _Sp>
396 _Tp
397 __parallel_transform_scan(_ExecutionPolicy&&, _Index __n, _Up __u, _Tp __init, _Cp __combine, _Rp __brick_reduce,
398 _Sp __scan)
399 {
400 __trans_scan_body<_Index, _Up, _Tp, _Cp, _Rp, _Sp> __body(__u, __init, __combine, __brick_reduce, __scan);
401 auto __range = tbb::blocked_range<_Index>(0, __n);
402 tbb::this_task_arena::isolate([__range, &__body]() { tbb::parallel_scan(__range, __body); });
403 return __body.sum();
404 }
405
406 //------------------------------------------------------------------------
407 // parallel_stable_sort
408 //------------------------------------------------------------------------
409
410 //------------------------------------------------------------------------
411 // stable_sort utilities
412 //
413 // These are used by parallel implementations but do not depend on them.
414 //------------------------------------------------------------------------
415 #define _PSTL_MERGE_CUT_OFF 2000
416
417 template <typename _Func>
418 class __func_task;
419 template <typename _Func>
420 class __root_task;
421
422 #if TBB_INTERFACE_VERSION <= 12000
423 class __task : public tbb::task
424 {
425 public:
426 template <typename _Fn>
427 __task*
428 make_continuation(_Fn&& __f)
429 {
430 return new (allocate_continuation()) __func_task<typename std::decay<_Fn>::type>(std::forward<_Fn>(__f));
431 }
432
433 template <typename _Fn>
434 __task*
435 make_child_of(__task* parent, _Fn&& __f)
436 {
437 return new (parent->allocate_child()) __func_task<typename std::decay<_Fn>::type>(std::forward<_Fn>(__f));
438 }
439
440 template <typename _Fn>
441 __task*
442 make_additional_child_of(tbb::task* parent, _Fn&& __f)
443 {
444 return new (tbb::task::allocate_additional_child_of(*parent))
445 __func_task<typename std::decay<_Fn>::type>(std::forward<_Fn>(__f));
446 }
447
448 inline void
449 recycle_as_continuation()
450 {
451 tbb::task::recycle_as_continuation();
452 }
453
454 inline void
455 recycle_as_child_of(__task* parent)
456 {
457 tbb::task::recycle_as_child_of(*parent);
458 }
459
460 inline void
461 spawn(__task* __t)
462 {
463 tbb::task::spawn(*__t);
464 }
465
466 template <typename _Fn>
467 static inline void
468 spawn_root_and_wait(__root_task<_Fn>& __root)
469 {
470 tbb::task::spawn_root_and_wait(*__root._M_task);
471 }
472 };
473
474 template <typename _Func>
475 class __func_task : public __task
476 {
477 _Func _M_func;
478
479 tbb::task*
480 execute()
481 {
482 return _M_func(this);
483 };
484
485 public:
486 template <typename _Fn>
487 __func_task(_Fn&& __f) : _M_func{std::forward<_Fn>(__f)}
488 {
489 }
490
491 _Func&
492 body()
493 {
494 return _M_func;
495 }
496 };
497
498 template <typename _Func>
499 class __root_task
500 {
501 tbb::task* _M_task;
502
503 public:
504 template <typename... Args>
505 __root_task(Args&&... args)
506 : _M_task{new (tbb::task::allocate_root()) __func_task<_Func>{_Func(std::forward<Args>(args)...)}}
507 {
508 }
509
510 friend class __task;
511 friend class __func_task<_Func>;
512 };
513
514 #else // TBB_INTERFACE_VERSION <= 12000
515 class __task : public tbb::detail::d1::task
516 {
517 protected:
518 tbb::detail::d1::small_object_allocator _M_allocator{};
519 tbb::detail::d1::execution_data* _M_execute_data{};
520 __task* _M_parent{};
521 std::atomic<int> _M_refcount{};
522 bool _M_recycle{};
523
524 template <typename _Fn>
525 __task*
526 allocate_func_task(_Fn&& __f)
527 {
528 _PSTL_ASSERT(_M_execute_data != nullptr);
529 tbb::detail::d1::small_object_allocator __alloc{};
530 auto __t =
531 __alloc.new_object<__func_task<typename std::decay<_Fn>::type>>(*_M_execute_data, std::forward<_Fn>(__f));
532 __t->_M_allocator = __alloc;
533 return __t;
534 }
535
536 public:
537 __task*
538 parent()
539 {
540 return _M_parent;
541 }
542
543 void
544 set_ref_count(int __n)
545 {
546 _M_refcount.store(__n, std::memory_order_release);
547 }
548
549 template <typename _Fn>
550 __task*
551 make_continuation(_Fn&& __f)
552 {
553 auto __t = allocate_func_task(std::forward<_Fn&&>(__f));
554 __t->_M_parent = _M_parent;
555 _M_parent = nullptr;
556 return __t;
557 }
558
559 template <typename _Fn>
560 __task*
561 make_child_of(__task* __parent, _Fn&& __f)
562 {
563 auto __t = allocate_func_task(std::forward<_Fn&&>(__f));
564 __t->_M_parent = __parent;
565 return __t;
566 }
567
568 template <typename _Fn>
569 __task*
570 make_additional_child_of(__task* __parent, _Fn&& __f)
571 {
572 auto __t = make_child_of(__parent, std::forward<_Fn>(__f));
573 _PSTL_ASSERT(__parent->_M_refcount.load(std::memory_order_relaxed) > 0);
574 ++__parent->_M_refcount;
575 return __t;
576 }
577
578 inline void
579 recycle_as_continuation()
580 {
581 _M_recycle = true;
582 }
583
584 inline void
585 recycle_as_child_of(__task* parent)
586 {
587 _M_recycle = true;
588 _M_parent = parent;
589 }
590
591 inline void
592 spawn(__task* __t)
593 {
594 _PSTL_ASSERT(_M_execute_data != nullptr);
595 tbb::detail::d1::spawn(*__t, *_M_execute_data->context);
596 }
597
598 template <typename _Fn>
599 static inline void
600 spawn_root_and_wait(__root_task<_Fn>& __root)
601 {
602 tbb::detail::d1::execute_and_wait(*__root._M_func_task, __root._M_context, __root._M_wait_object,
603 __root._M_context);
604 }
605
606 template <typename _Func>
607 friend class __func_task;
608 };
609
610 template <typename _Func>
611 class __func_task : public __task
612 {
613 _Func _M_func;
614
615 __task*
616 execute(tbb::detail::d1::execution_data& __ed) override
617 {
618 _M_execute_data = &__ed;
619 _M_recycle = false;
620 __task* __next = _M_func(this);
621 return finalize(__next);
622 };
623
624 __task*
625 cancel(tbb::detail::d1::execution_data& __ed) override
626 {
627 return finalize(nullptr);
628 }
629
630 __task*
631 finalize(__task* __next)
632 {
633 bool __recycle = _M_recycle;
634 _M_recycle = false;
635
636 if (__recycle)
637 {
638 return __next;
639 }
640
641 auto __parent = _M_parent;
642 auto __alloc = _M_allocator;
643 auto __ed = _M_execute_data;
644
645 this->~__func_task();
646
647 _PSTL_ASSERT(__parent != nullptr);
648 _PSTL_ASSERT(__parent->_M_refcount.load(std::memory_order_relaxed) > 0);
649 if (--__parent->_M_refcount == 0)
650 {
651 _PSTL_ASSERT(__next == nullptr);
652 __alloc.deallocate(this, *__ed);
653 return __parent;
654 }
655
656 return __next;
657 }
658
659 friend class __root_task<_Func>;
660
661 public:
662 template <typename _Fn>
663 __func_task(_Fn&& __f) : _M_func(std::forward<_Fn>(__f))
664 {
665 }
666
667 _Func&
668 body()
669 {
670 return _M_func;
671 }
672 };
673
674 template <typename _Func>
675 class __root_task : public __task
676 {
677 __task*
678 execute(tbb::detail::d1::execution_data& __ed) override
679 {
680 _M_wait_object.release();
681 return nullptr;
682 };
683
684 __task*
685 cancel(tbb::detail::d1::execution_data& __ed) override
686 {
687 _M_wait_object.release();
688 return nullptr;
689 }
690
691 __func_task<_Func>* _M_func_task{};
692 tbb::detail::d1::wait_context _M_wait_object{0};
693 tbb::task_group_context _M_context{};
694
695 public:
696 template <typename... Args>
697 __root_task(Args&&... args) : _M_wait_object{1}
698 {
699 tbb::detail::d1::small_object_allocator __alloc{};
700 _M_func_task = __alloc.new_object<__func_task<_Func>>(_Func(std::forward<Args>(args)...));
701 _M_func_task->_M_allocator = __alloc;
702 _M_func_task->_M_parent = this;
703 _M_refcount.store(1, std::memory_order_relaxed);
704 }
705
706 friend class __task;
707 };
708 #endif // TBB_INTERFACE_VERSION <= 12000
709
710 template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _Compare, typename _Cleanup,
711 typename _LeafMerge>
712 class __merge_func
713 {
714 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType1;
715 typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _DifferenceType2;
716 typedef typename std::common_type<_DifferenceType1, _DifferenceType2>::type _SizeType;
717 typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type _ValueType;
718
719 _RandomAccessIterator1 _M_x_beg;
720 _RandomAccessIterator2 _M_z_beg;
721
722 _SizeType _M_xs, _M_xe;
723 _SizeType _M_ys, _M_ye;
724 _SizeType _M_zs;
725 _Compare _M_comp;
726 _LeafMerge _M_leaf_merge;
727 _SizeType _M_nsort; //number of elements to be sorted for partial_sort alforithm
728
729 static const _SizeType __merge_cut_off = _PSTL_MERGE_CUT_OFF;
730
731 bool _root; //means a task is merging root task
732 bool _x_orig; //"true" means X(or left ) subrange is in the original container; false - in the buffer
733 bool _y_orig; //"true" means Y(or right) subrange is in the original container; false - in the buffer
734 bool _split; //"true" means a merge task is a split task for parallel merging, the execution logic differs
735
736 bool
737 is_partial() const
738 {
739 return _M_nsort > 0;
740 }
741
742 struct __move_value
743 {
744 template <typename Iterator1, typename Iterator2>
745 void
746 operator()(Iterator1 __x, Iterator2 __z)
747 {
748 *__z = std::move(*__x);
749 }
750 };
751
752 struct __move_value_construct
753 {
754 template <typename Iterator1, typename Iterator2>
755 void
756 operator()(Iterator1 __x, Iterator2 __z)
757 {
758 ::new (std::addressof(*__z)) _ValueType(std::move(*__x));
759 }
760 };
761
762 struct __move_range
763 {
764 template <typename Iterator1, typename Iterator2>
765 Iterator2
766 operator()(Iterator1 __first1, Iterator1 __last1, Iterator2 __first2)
767 {
768 if (__last1 - __first1 < __merge_cut_off)
769 return std::move(__first1, __last1, __first2);
770
771 auto __n = __last1 - __first1;
772 tbb::parallel_for(tbb::blocked_range<_SizeType>(0, __n, __merge_cut_off),
773 [__first1, __first2](const tbb::blocked_range<_SizeType>& __range) {
774 std::move(__first1 + __range.begin(), __first1 + __range.end(),
775 __first2 + __range.begin());
776 });
777 return __first2 + __n;
778 }
779 };
780
781 struct __move_range_construct
782 {
783 template <typename Iterator1, typename Iterator2>
784 Iterator2
785 operator()(Iterator1 __first1, Iterator1 __last1, Iterator2 __first2)
786 {
787 if (__last1 - __first1 < __merge_cut_off)
788 {
789 for (; __first1 != __last1; ++__first1, ++__first2)
790 __move_value_construct()(__first1, __first2);
791 return __first2;
792 }
793
794 auto __n = __last1 - __first1;
795 tbb::parallel_for(tbb::blocked_range<_SizeType>(0, __n, __merge_cut_off),
796 [__first1, __first2](const tbb::blocked_range<_SizeType>& __range) {
797 for (auto i = __range.begin(); i != __range.end(); ++i)
798 __move_value_construct()(__first1 + i, __first2 + i);
799 });
800 return __first2 + __n;
801 }
802 };
803
804 struct __cleanup_range
805 {
806 template <typename _Iterator>
807 void
808 operator()(_Iterator __first, _Iterator __last)
809 {
810 if (__last - __first < __merge_cut_off)
811 _Cleanup()(__first, __last);
812 else
813 {
814 auto __n = __last - __first;
815 tbb::parallel_for(tbb::blocked_range<_SizeType>(0, __n, __merge_cut_off),
816 [__first](const tbb::blocked_range<_SizeType>& __range) {
817 _Cleanup()(__first + __range.begin(), __first + __range.end());
818 });
819 }
820 }
821 };
822
823 public:
824 __merge_func(_SizeType __xs, _SizeType __xe, _SizeType __ys, _SizeType __ye, _SizeType __zs, _Compare __comp,
825 _Cleanup, _LeafMerge __leaf_merge, _SizeType __nsort, _RandomAccessIterator1 __x_beg,
826 _RandomAccessIterator2 __z_beg, bool __x_orig, bool __y_orig, bool __root)
827 : _M_xs(__xs), _M_xe(__xe), _M_ys(__ys), _M_ye(__ye), _M_zs(__zs), _M_x_beg(__x_beg), _M_z_beg(__z_beg),
828 _M_comp(__comp), _M_leaf_merge(__leaf_merge), _M_nsort(__nsort), _root(__root),
829 _x_orig(__x_orig), _y_orig(__y_orig), _split(false)
830 {
831 }
832
833 bool
834 is_left(_SizeType __idx) const
835 {
836 return _M_xs == __idx;
837 }
838
839 template <typename IndexType>
840 void
841 set_odd(IndexType __idx, bool __on_off)
842 {
843 if (is_left(__idx))
844 _x_orig = __on_off;
845 else
846 _y_orig = __on_off;
847 }
848
849 __task*
850 operator()(__task* __self);
851
852 private:
853 __merge_func*
854 parent_merge(__task* __self) const
855 {
856 return _root ? nullptr : &static_cast<__func_task<__merge_func>*>(__self->parent())->body();
857 }
858 bool
859 x_less_y()
860 {
861 const auto __nx = (_M_xe - _M_xs);
862 const auto __ny = (_M_ye - _M_ys);
863 _PSTL_ASSERT(__nx > 0 && __ny > 0);
864
865 _PSTL_ASSERT(_x_orig == _y_orig);
866 _PSTL_ASSERT(!is_partial());
867
868 if (_x_orig)
869 {
870 _PSTL_ASSERT(std::is_sorted(_M_x_beg + _M_xs, _M_x_beg + _M_xe, _M_comp));
871 _PSTL_ASSERT(std::is_sorted(_M_x_beg + _M_ys, _M_x_beg + _M_ye, _M_comp));
872 return !_M_comp(*(_M_x_beg + _M_ys), *(_M_x_beg + _M_xe - 1));
873 }
874
875 _PSTL_ASSERT(std::is_sorted(_M_z_beg + _M_xs, _M_z_beg + _M_xe, _M_comp));
876 _PSTL_ASSERT(std::is_sorted(_M_z_beg + _M_ys, _M_z_beg + _M_ye, _M_comp));
877 return !_M_comp(*(_M_z_beg + _M_zs + __nx), *(_M_z_beg + _M_zs + __nx - 1));
878 }
879 void
880 move_x_range()
881 {
882 const auto __nx = (_M_xe - _M_xs);
883 const auto __ny = (_M_ye - _M_ys);
884 _PSTL_ASSERT(__nx > 0 && __ny > 0);
885
886 if (_x_orig)
887 __move_range_construct()(_M_x_beg + _M_xs, _M_x_beg + _M_xe, _M_z_beg + _M_zs);
888 else
889 {
890 __move_range()(_M_z_beg + _M_zs, _M_z_beg + _M_zs + __nx, _M_x_beg + _M_xs);
891 __cleanup_range()(_M_z_beg + _M_zs, _M_z_beg + _M_zs + __nx);
892 }
893
894 _x_orig = !_x_orig;
895 }
896 void
897 move_y_range()
898 {
899 const auto __nx = (_M_xe - _M_xs);
900 const auto __ny = (_M_ye - _M_ys);
901
902 if (_y_orig)
903 __move_range_construct()(_M_x_beg + _M_ys, _M_x_beg + _M_ye, _M_z_beg + _M_zs + __nx);
904 else
905 {
906 __move_range()(_M_z_beg + _M_zs + __nx, _M_z_beg + _M_zs + __nx + __ny, _M_x_beg + _M_ys);
907 __cleanup_range()(_M_z_beg + _M_zs + __nx, _M_z_beg + _M_zs + __nx + __ny);
908 }
909
910 _y_orig = !_y_orig;
911 }
912 __task*
913 merge_ranges(__task* __self)
914 {
915 _PSTL_ASSERT(_x_orig == _y_orig); //two merged subrange must be lie into the same buffer
916
917 const auto __nx = (_M_xe - _M_xs);
918 const auto __ny = (_M_ye - _M_ys);
919 const auto __n = __nx + __ny;
920
921 // need to merge {x} and {y}
922 if (__n > __merge_cut_off)
923 return split_merging(__self);
924
925 //merge to buffer
926 if (_x_orig)
927 {
928 _M_leaf_merge(_M_x_beg + _M_xs, _M_x_beg + _M_xe, _M_x_beg + _M_ys, _M_x_beg + _M_ye, _M_z_beg + _M_zs,
929 _M_comp, __move_value_construct(), __move_value_construct(), __move_range_construct(),
930 __move_range_construct());
931 _PSTL_ASSERT(parent_merge(__self)); //not root merging task
932 }
933 //merge to "origin"
934 else
935 {
936 _PSTL_ASSERT(_x_orig == _y_orig);
937
938 _PSTL_ASSERT(is_partial() || std::is_sorted(_M_z_beg + _M_xs, _M_z_beg + _M_xe, _M_comp));
939 _PSTL_ASSERT(is_partial() || std::is_sorted(_M_z_beg + _M_ys, _M_z_beg + _M_ye, _M_comp));
940
941 const auto __nx = (_M_xe - _M_xs);
942 const auto __ny = (_M_ye - _M_ys);
943
944 _M_leaf_merge(_M_z_beg + _M_xs, _M_z_beg + _M_xe, _M_z_beg + _M_ys, _M_z_beg + _M_ye, _M_x_beg + _M_zs,
945 _M_comp, __move_value(), __move_value(), __move_range(), __move_range());
946
947 __cleanup_range()(_M_z_beg + _M_xs, _M_z_beg + _M_xe);
948 __cleanup_range()(_M_z_beg + _M_ys, _M_z_beg + _M_ye);
949 }
950 return nullptr;
951 }
952
953 __task*
954 process_ranges(__task* __self)
955 {
956 _PSTL_ASSERT(_x_orig == _y_orig);
957 _PSTL_ASSERT(!_split);
958
959 auto p = parent_merge(__self);
960
961 if (!p)
962 { //root merging task
963
964 //optimization, just for sort algorithm, //{x} <= {y}
965 if (!is_partial() && x_less_y()) //we have a solution
966 {
967 if (!_x_orig)
968 { //we have to move the solution to the origin
969 move_x_range(); //parallel moving
970 move_y_range(); //parallel moving
971 }
972 return nullptr;
973 }
974 //else: if we have data in the origin,
975 //we have to move data to the buffer for final merging into the origin.
976 if (_x_orig)
977 {
978 move_x_range(); //parallel moving
979 move_y_range(); //parallel moving
980 }
981 // need to merge {x} and {y}.
982 return merge_ranges(__self);
983 }
984 //else: not root merging task (parent_merge() == NULL)
985 //optimization, just for sort algorithm, //{x} <= {y}
986 if (!is_partial() && x_less_y())
987 {
988 const auto id_range = _M_zs;
989 p->set_odd(id_range, _x_orig);
990 return nullptr;
991 }
992 //else: we have to revert "_x(y)_orig" flag of the parent merging task
993 const auto id_range = _M_zs;
994 p->set_odd(id_range, !_x_orig);
995
996 return merge_ranges(__self);
997 }
998
999 //splitting as merge task into 2 of the same level
1000 __task*
1001 split_merging(__task* __self)
1002 {
1003 _PSTL_ASSERT(_x_orig == _y_orig);
1004 const auto __nx = (_M_xe - _M_xs);
1005 const auto __ny = (_M_ye - _M_ys);
1006
1007 _SizeType __xm{};
1008 _SizeType __ym{};
1009 if (__nx < __ny)
1010 {
1011 __ym = _M_ys + __ny / 2;
1012
1013 if (_x_orig)
1014 __xm = std::upper_bound(_M_x_beg + _M_xs, _M_x_beg + _M_xe, *(_M_x_beg + __ym), _M_comp) - _M_x_beg;
1015 else
1016 __xm = std::upper_bound(_M_z_beg + _M_xs, _M_z_beg + _M_xe, *(_M_z_beg + __ym), _M_comp) - _M_z_beg;
1017 }
1018 else
1019 {
1020 __xm = _M_xs + __nx / 2;
1021
1022 if (_y_orig)
1023 __ym = std::lower_bound(_M_x_beg + _M_ys, _M_x_beg + _M_ye, *(_M_x_beg + __xm), _M_comp) - _M_x_beg;
1024 else
1025 __ym = std::lower_bound(_M_z_beg + _M_ys, _M_z_beg + _M_ye, *(_M_z_beg + __xm), _M_comp) - _M_z_beg;
1026 }
1027
1028 auto __zm = _M_zs + ((__xm - _M_xs) + (__ym - _M_ys));
1029 __merge_func __right_func(__xm, _M_xe, __ym, _M_ye, __zm, _M_comp, _Cleanup(), _M_leaf_merge, _M_nsort,
1030 _M_x_beg, _M_z_beg, _x_orig, _y_orig, _root);
1031 __right_func._split = true;
1032 auto __merge_task = __self->make_additional_child_of(__self->parent(), std::move(__right_func));
1033 __self->spawn(__merge_task);
1034 __self->recycle_as_continuation();
1035
1036 _M_xe = __xm;
1037 _M_ye = __ym;
1038 _split = true;
1039
1040 return __self;
1041 }
1042 };
1043
1044 template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename __M_Compare, typename _Cleanup,
1045 typename _LeafMerge>
1046 __task*
1047 __merge_func<_RandomAccessIterator1, _RandomAccessIterator2, __M_Compare, _Cleanup, _LeafMerge>::
1048 operator()(__task* __self)
1049 {
1050 //a. split merge task into 2 of the same level; the special logic,
1051 //without processing(process_ranges) adjacent sub-ranges x and y
1052 if (_split)
1053 return merge_ranges(__self);
1054
1055 //b. General merging of adjacent sub-ranges x and y (with optimization in case of {x} <= {y} )
1056
1057 //1. x and y are in the even buffer
1058 //2. x and y are in the odd buffer
1059 if (_x_orig == _y_orig)
1060 return process_ranges(__self);
1061
1062 //3. x is in even buffer, y is in the odd buffer
1063 //4. x is in odd buffer, y is in the even buffer
1064 if (!parent_merge(__self))
1065 { //root merge task
1066 if (_x_orig)
1067 move_x_range();
1068 else
1069 move_y_range();
1070 }
1071 else
1072 {
1073 const _SizeType __nx = (_M_xe - _M_xs);
1074 const _SizeType __ny = (_M_ye - _M_ys);
1075 _PSTL_ASSERT(__nx > 0);
1076 _PSTL_ASSERT(__nx > 0);
1077
1078 if (__nx < __ny)
1079 move_x_range();
1080 else
1081 move_y_range();
1082 }
1083
1084 return process_ranges(__self);
1085 }
1086
1087 template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _Compare, typename _LeafSort>
1088 class __stable_sort_func
1089 {
1090 public:
1091 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType1;
1092 typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _DifferenceType2;
1093 typedef typename std::common_type<_DifferenceType1, _DifferenceType2>::type _SizeType;
1094
1095 private:
1096 _RandomAccessIterator1 _M_xs, _M_xe, _M_x_beg;
1097 _RandomAccessIterator2 _M_zs, _M_z_beg;
1098 _Compare _M_comp;
1099 _LeafSort _M_leaf_sort;
1100 bool _M_root;
1101 _SizeType _M_nsort; //zero or number of elements to be sorted for partial_sort alforithm
1102
1103 public:
1104 __stable_sort_func(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __zs,
1105 bool __root, _Compare __comp, _LeafSort __leaf_sort, _SizeType __nsort,
1106 _RandomAccessIterator1 __x_beg, _RandomAccessIterator2 __z_beg)
1107 : _M_xs(__xs), _M_xe(__xe), _M_x_beg(__x_beg), _M_zs(__zs), _M_z_beg(__z_beg), _M_comp(__comp),
1108 _M_leaf_sort(__leaf_sort), _M_root(__root), _M_nsort(__nsort)
1109 {
1110 }
1111
1112 __task*
1113 operator()(__task* __self);
1114 };
1115
1116 #define _PSTL_STABLE_SORT_CUT_OFF 500
1117
1118 template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _Compare, typename _LeafSort>
1119 __task*
1120 __stable_sort_func<_RandomAccessIterator1, _RandomAccessIterator2, _Compare, _LeafSort>::operator()(__task* __self)
1121 {
1122 typedef __merge_func<_RandomAccessIterator1, _RandomAccessIterator2, _Compare, __utils::__serial_destroy,
1123 __utils::__serial_move_merge>
1124 _MergeTaskType;
1125
1126 const _SizeType __n = _M_xe - _M_xs;
1127 const _SizeType __nmerge = _M_nsort > 0 ? _M_nsort : __n;
1128 const _SizeType __sort_cut_off = _PSTL_STABLE_SORT_CUT_OFF;
1129 if (__n <= __sort_cut_off)
1130 {
1131 _M_leaf_sort(_M_xs, _M_xe, _M_comp);
1132 _PSTL_ASSERT(!_M_root);
1133 return nullptr;
1134 }
1135
1136 const _RandomAccessIterator1 __xm = _M_xs + __n / 2;
1137 const _RandomAccessIterator2 __zm = _M_zs + (__xm - _M_xs);
1138 const _RandomAccessIterator2 __ze = _M_zs + __n;
1139 _MergeTaskType __m(_MergeTaskType(_M_xs - _M_x_beg, __xm - _M_x_beg, __xm - _M_x_beg, _M_xe - _M_x_beg,
1140 _M_zs - _M_z_beg, _M_comp, __utils::__serial_destroy(),
1141 __utils::__serial_move_merge(__nmerge), _M_nsort, _M_x_beg, _M_z_beg,
1142 /*x_orig*/ true, /*y_orig*/ true, /*root*/ _M_root));
1143 auto __parent = __self->make_continuation(std::move(__m));
1144 __parent->set_ref_count(2);
1145 auto __right = __self->make_child_of(
1146 __parent, __stable_sort_func(__xm, _M_xe, __zm, false, _M_comp, _M_leaf_sort, _M_nsort, _M_x_beg, _M_z_beg));
1147 __self->spawn(__right);
1148 __self->recycle_as_child_of(__parent);
1149 _M_root = false;
1150 _M_xe = __xm;
1151
1152 return __self;
1153 }
1154
1155 template <class _ExecutionPolicy, typename _RandomAccessIterator, typename _Compare, typename _LeafSort>
1156 void
1157 __parallel_stable_sort(_ExecutionPolicy&&, _RandomAccessIterator __xs, _RandomAccessIterator __xe, _Compare __comp,
1158 _LeafSort __leaf_sort, std::size_t __nsort = 0)
1159 {
1160 tbb::this_task_arena::isolate([=, &__nsort]() {
1161 //sorting based on task tree and parallel merge
1162 typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _ValueType;
1163 typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
1164 const _DifferenceType __n = __xe - __xs;
1165 if (__nsort == __n)
1166 __nsort = 0; // 'partial_sort' becames 'sort'
1167
1168 const _DifferenceType __sort_cut_off = _PSTL_STABLE_SORT_CUT_OFF;
1169 if (__n > __sort_cut_off)
1170 {
1171 __buffer<_ValueType> __buf(__n);
1172 __root_task<__stable_sort_func<_RandomAccessIterator, _ValueType*, _Compare, _LeafSort>> __root{
1173 __xs, __xe, __buf.get(), true, __comp, __leaf_sort, __nsort, __xs, __buf.get()};
1174 __task::spawn_root_and_wait(__root);
1175 return;
1176 }
1177 //serial sort
1178 __leaf_sort(__xs, __xe, __comp);
1179 });
1180 }
1181
1182 //------------------------------------------------------------------------
1183 // parallel_merge
1184 //------------------------------------------------------------------------
1185 template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _RandomAccessIterator3,
1186 typename _Compare, typename _LeafMerge>
1187 class __merge_func_static
1188 {
1189 _RandomAccessIterator1 _M_xs, _M_xe;
1190 _RandomAccessIterator2 _M_ys, _M_ye;
1191 _RandomAccessIterator3 _M_zs;
1192 _Compare _M_comp;
1193 _LeafMerge _M_leaf_merge;
1194
1195 public:
1196 __merge_func_static(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys,
1197 _RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp,
1198 _LeafMerge __leaf_merge)
1199 : _M_xs(__xs), _M_xe(__xe), _M_ys(__ys), _M_ye(__ye), _M_zs(__zs), _M_comp(__comp), _M_leaf_merge(__leaf_merge)
1200 {
1201 }
1202
1203 __task*
1204 operator()(__task* __self);
1205 };
1206
1207 //TODO: consider usage of parallel_for with a custom blocked_range
1208 template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _RandomAccessIterator3,
1209 typename __M_Compare, typename _LeafMerge>
1210 __task*
1211 __merge_func_static<_RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator3, __M_Compare, _LeafMerge>::
1212 operator()(__task* __self)
1213 {
1214 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType1;
1215 typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _DifferenceType2;
1216 typedef typename std::common_type<_DifferenceType1, _DifferenceType2>::type _SizeType;
1217 const _SizeType __n = (_M_xe - _M_xs) + (_M_ye - _M_ys);
1218 const _SizeType __merge_cut_off = _PSTL_MERGE_CUT_OFF;
1219 if (__n <= __merge_cut_off)
1220 {
1221 _M_leaf_merge(_M_xs, _M_xe, _M_ys, _M_ye, _M_zs, _M_comp);
1222 return nullptr;
1223 }
1224
1225 _RandomAccessIterator1 __xm;
1226 _RandomAccessIterator2 __ym;
1227 if (_M_xe - _M_xs < _M_ye - _M_ys)
1228 {
1229 __ym = _M_ys + (_M_ye - _M_ys) / 2;
1230 __xm = std::upper_bound(_M_xs, _M_xe, *__ym, _M_comp);
1231 }
1232 else
1233 {
1234 __xm = _M_xs + (_M_xe - _M_xs) / 2;
1235 __ym = std::lower_bound(_M_ys, _M_ye, *__xm, _M_comp);
1236 }
1237 const _RandomAccessIterator3 __zm = _M_zs + ((__xm - _M_xs) + (__ym - _M_ys));
1238 auto __right = __self->make_additional_child_of(
1239 __self->parent(), __merge_func_static(__xm, _M_xe, __ym, _M_ye, __zm, _M_comp, _M_leaf_merge));
1240 __self->spawn(__right);
1241 __self->recycle_as_continuation();
1242 _M_xe = __xm;
1243 _M_ye = __ym;
1244
1245 return __self;
1246 }
1247
1248 template <class _ExecutionPolicy, typename _RandomAccessIterator1, typename _RandomAccessIterator2,
1249 typename _RandomAccessIterator3, typename _Compare, typename _LeafMerge>
1250 void
1251 __parallel_merge(_ExecutionPolicy&&, _RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe,
1252 _RandomAccessIterator2 __ys, _RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp,
1253 _LeafMerge __leaf_merge)
1254 {
1255 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType1;
1256 typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _DifferenceType2;
1257 typedef typename std::common_type<_DifferenceType1, _DifferenceType2>::type _SizeType;
1258 const _SizeType __n = (__xe - __xs) + (__ye - __ys);
1259 const _SizeType __merge_cut_off = _PSTL_MERGE_CUT_OFF;
1260 if (__n <= __merge_cut_off)
1261 {
1262 // Fall back on serial merge
1263 __leaf_merge(__xs, __xe, __ys, __ye, __zs, __comp);
1264 }
1265 else
1266 {
1267 tbb::this_task_arena::isolate([=]() {
1268 typedef __merge_func_static<_RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator3,
1269 _Compare, _LeafMerge>
1270 _TaskType;
1271 __root_task<_TaskType> __root{__xs, __xe, __ys, __ye, __zs, __comp, __leaf_merge};
1272 __task::spawn_root_and_wait(__root);
1273 });
1274 }
1275 }
1276
1277 //------------------------------------------------------------------------
1278 // parallel_invoke
1279 //------------------------------------------------------------------------
1280 template <class _ExecutionPolicy, typename _F1, typename _F2>
1281 void
1282 __parallel_invoke(_ExecutionPolicy&&, _F1&& __f1, _F2&& __f2)
1283 {
1284 //TODO: a version of tbb::this_task_arena::isolate with variadic arguments pack should be added in the future
1285 tbb::this_task_arena::isolate([&]() { tbb::parallel_invoke(std::forward<_F1>(__f1), std::forward<_F2>(__f2)); });
1286 }
1287
1288 } // namespace __tbb_backend
1289 } // namespace __pstl
1290
1291 #endif /* _PSTL_PARALLEL_BACKEND_TBB_H */