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 _BackendTag, class _ExecutionPolicy, class _Index, class _Brick, class _Compare>
32 _Index
__parallel_find(_BackendTag __tag,_ExecutionPolicy && __exec,_Index __first,_Index __last,_Brick __f,_Compare __comp,bool __b_first)33 __parallel_find(_BackendTag __tag, _ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f,
34 _Compare __comp, bool __b_first)
35 {
36 typedef typename std::iterator_traits<_Index>::difference_type _DifferenceType;
37 const _DifferenceType __n = __last - __first;
38 _DifferenceType __initial_dist = __b_first ? __n : -1;
39 std::atomic<_DifferenceType> __extremum(__initial_dist);
40 // TODO: find out what is better here: parallel_for or parallel_reduce
41 __par_backend::__parallel_for(__tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
42 [__comp, __f, __first, &__extremum](_Index __i, _Index __j)
43 {
44 // See "Reducing Contention Through Priority Updates", PPoPP '13, for discussion of
45 // why using a shared variable scales fairly well in this situation.
46 if (__comp(__i - __first, __extremum))
47 {
48 _Index __res = __f(__i, __j);
49 // If not '__last' returned then we found what we want so put this to extremum
50 if (__res != __j)
51 {
52 const _DifferenceType __k = __res - __first;
53 for (_DifferenceType __old = __extremum; __comp(__k, __old);
54 __old = __extremum)
55 {
56 __extremum.compare_exchange_weak(__old, __k);
57 }
58 }
59 }
60 });
61 return __extremum != __initial_dist ? __first + __extremum : __last;
62 }
63
64 //------------------------------------------------------------------------
65 // parallel_or
66 //------------------------------------------------------------------------
67 //! Return true if brick f[i,j) returns true for some subrange [i,j) of [first,last)
68 template <class _BackendTag, class _ExecutionPolicy, class _Index, class _Brick>
69 bool
__parallel_or(_BackendTag __tag,_ExecutionPolicy && __exec,_Index __first,_Index __last,_Brick __f)70 __parallel_or(_BackendTag __tag, _ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f)
71 {
72 std::atomic<bool> __found(false);
73 __par_backend::__parallel_for(__tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
74 [__f, &__found](_Index __i, _Index __j)
75 {
76 if (!__found.load(std::memory_order_relaxed) && __f(__i, __j))
77 {
78 __found.store(true, std::memory_order_relaxed);
79 __par_backend::__cancel_execution();
80 }
81 });
82 return __found;
83 }
84
85 } // namespace __internal
86 } // namespace __pstl
87
88 _PSTL_HIDE_FROM_ABI_POP
89
90 #endif /* _PSTL_PARALLEL_IMPL_H */
91