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