libstdc++-v3/include/pstl/parallel_impl.h

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