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
      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
      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 */