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