| // -*- C++ -*- |
| //===-- parallel_impl.h ---------------------------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef _PSTL_PARALLEL_IMPL_H |
| #define _PSTL_PARALLEL_IMPL_H |
| |
| #include <atomic> |
| // This header defines the minimum set of parallel routines required to support Parallel STL, |
| // implemented on top of Intel(R) Threading Building Blocks (Intel(R) TBB) library |
| |
| namespace __pstl |
| { |
| namespace __internal |
| { |
| |
| //------------------------------------------------------------------------ |
| // parallel_find |
| //----------------------------------------------------------------------- |
| /** Return extremum value returned by brick f[i,j) for subranges [i,j) of [first,last) |
| Each f[i,j) must return a value in [i,j). */ |
| template <class _ExecutionPolicy, class _Index, class _Brick, class _Compare> |
| _Index |
| __parallel_find(_ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f, _Compare __comp, bool __b_first) |
| { |
| typedef typename std::iterator_traits<_Index>::difference_type _DifferenceType; |
| const _DifferenceType __n = __last - __first; |
| _DifferenceType __initial_dist = __b_first ? __n : -1; |
| std::atomic<_DifferenceType> __extremum(__initial_dist); |
| // TODO: find out what is better here: parallel_for or parallel_reduce |
| __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last, |
| [__comp, __f, __first, &__extremum](_Index __i, _Index __j) { |
| // See "Reducing Contention Through Priority Updates", PPoPP '13, for discussion of |
| // why using a shared variable scales fairly well in this situation. |
| if (__comp(__i - __first, __extremum)) |
| { |
| _Index __res = __f(__i, __j); |
| // If not '__last' returned then we found what we want so put this to extremum |
| if (__res != __j) |
| { |
| const _DifferenceType __k = __res - __first; |
| for (_DifferenceType __old = __extremum; __comp(__k, __old); |
| __old = __extremum) |
| { |
| __extremum.compare_exchange_weak(__old, __k); |
| } |
| } |
| } |
| }); |
| return __extremum != __initial_dist ? __first + __extremum : __last; |
| } |
| |
| //------------------------------------------------------------------------ |
| // parallel_or |
| //------------------------------------------------------------------------ |
| //! Return true if brick f[i,j) returns true for some subrange [i,j) of [first,last) |
| template <class _ExecutionPolicy, class _Index, class _Brick> |
| bool |
| __parallel_or(_ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f) |
| { |
| std::atomic<bool> __found(false); |
| __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last, |
| [__f, &__found](_Index __i, _Index __j) { |
| if (!__found.load(std::memory_order_relaxed) && __f(__i, __j)) |
| { |
| __found.store(true, std::memory_order_relaxed); |
| __par_backend::__cancel_execution(); |
| } |
| }); |
| return __found; |
| } |
| |
| } // namespace __internal |
| } // namespace __pstl |
| |
| #endif /* _PSTL_PARALLEL_IMPL_H */ |