1 // -*- C++ -*-
2 //===----------------------------------------------------------------------===//
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_IMPL_H
11 #define _PSTL_PARALLEL_IMPL_H
12
13 #include "pstl_config.h"
14
15 #include <atomic>
16 // This header defines the minimum set of parallel routines required to support Parallel STL,
17 // implemented on top of Intel(R) Threading Building Blocks (Intel(R) TBB) library
18
19 _PSTL_HIDE_FROM_ABI_PUSH
20
21 namespace __pstl
22 {
23 namespace __internal
24 {
25
26 //------------------------------------------------------------------------
27 // parallel_find
28 //-----------------------------------------------------------------------
29 /** Return extremum value returned by brick f[i,j) for subranges [i,j) of [first,last)
30 Each f[i,j) must return a value in [i,j). */
31 template <class _ExecutionPolicy, class _Index, class _Brick, class _Compare>
32 _Index
__parallel_find(_ExecutionPolicy && __exec,_Index __first,_Index __last,_Brick __f,_Compare __comp,bool __b_first)33 __parallel_find(_ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f, _Compare __comp, bool __b_first)
34 {
35 typedef typename std::iterator_traits<_Index>::difference_type _DifferenceType;
36 const _DifferenceType __n = __last - __first;
37 _DifferenceType __initial_dist = __b_first ? __n : -1;
38 std::atomic<_DifferenceType> __extremum(__initial_dist);
39 // TODO: find out what is better here: parallel_for or parallel_reduce
40 __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last,
41 [__comp, __f, __first, &__extremum](_Index __i, _Index __j) {
42 // See "Reducing Contention Through Priority Updates", PPoPP '13, for discussion of
43 // why using a shared variable scales fairly well in this situation.
44 if (__comp(__i - __first, __extremum))
45 {
46 _Index __res = __f(__i, __j);
47 // If not '__last' returned then we found what we want so put this to extremum
48 if (__res != __j)
49 {
50 const _DifferenceType __k = __res - __first;
51 for (_DifferenceType __old = __extremum; __comp(__k, __old);
52 __old = __extremum)
53 {
54 __extremum.compare_exchange_weak(__old, __k);
55 }
56 }
57 }
58 });
59 return __extremum != __initial_dist ? __first + __extremum : __last;
60 }
61
62 //------------------------------------------------------------------------
63 // parallel_or
64 //------------------------------------------------------------------------
65 //! Return true if brick f[i,j) returns true for some subrange [i,j) of [first,last)
66 template <class _ExecutionPolicy, class _Index, class _Brick>
67 bool
__parallel_or(_ExecutionPolicy && __exec,_Index __first,_Index __last,_Brick __f)68 __parallel_or(_ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f)
69 {
70 std::atomic<bool> __found(false);
71 __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last,
72 [__f, &__found](_Index __i, _Index __j) {
73 if (!__found.load(std::memory_order_relaxed) && __f(__i, __j))
74 {
75 __found.store(true, std::memory_order_relaxed);
76 __par_backend::__cancel_execution();
77 }
78 });
79 return __found;
80 }
81
82 } // namespace __internal
83 } // namespace __pstl
84
85 _PSTL_HIDE_FROM_ABI_POP
86
87 #endif /* _PSTL_PARALLEL_IMPL_H */
88