Changed buffer API to receive policy instance.

[MikeDvorskiy]

Summary

Changed buffer API to receive policy instance. It may be necessary for the other back-ends, where dynamic memory is not available and custom memory allocator may be provided by a custom policy.

[ldionne]

I don't see a big problem with this change per-se, but can you please expand on the bit where you say:

It may be necessary for the other back-ends, where dynamic memory is not available and custom memory allocator may be provided by a custom policy.

How would you somehow handle allocation through a custom policy?

[rodgert]

In D59704#1439794, @ldionne wrote:

I don't see a big problem with this change per-se, but can you please expand on the bit where you say:

It may be necessary for the other back-ends, where dynamic memory is not available and custom memory allocator may be provided by a custom policy.

How would you somehow handle allocation through a custom policy?

Assuming, at some point we figure out how to get p0443 executors and p1019 style execution policy types, which communicate executors to the algorithm, which allocator to use becomes a property query against the executor. The default executor and it's associated properties are a library implementation detail, but the way that the algorithms respond to the presence of those properties should be the same.

Similarly, the execution policy will ultimately need to be communicated to the basis functions of the backend as well, and I am planning on resurrecting my prototype of that change in the next week.

I'd like to be careful about making these sorts of changes until we have had a chance to have the next follow up coordination meeting that Alexey has proposed.

[MikeDvorskiy]

In D59704#1439794, @ldionne wrote:

How would you somehow handle allocation through a custom policy?

For example a custom policy has get_memory_pool method which provide an interface for memory allocation/access.
Of course, this "contract"(provided by a custom policy) must be known a custom corresponding parallel back-end as well. But Parallel STL core implementation have not to know about this "contract".

I agree with Thomas, in that case it is connected with the executors, because the custom policy specifies certain "backend"... and works like an "executor". And in the future, just an executor should specify back-end.
On the the other hand, "the executors" are not finalized yet.. and it may take many time (months mb). The change so minor.. and the change helps us to sync-up, and when an "executors solution" comes, we will change the code places quickly. That change may not be taken for libcstd integration.

[ldionne]

My main problem with this change is that we don't seem to have a backend right now that requires this change. I'd defer doing this until we have a real reason to do so.

[MikeDvorskiy]

At least, it "extends" signature of functions of a back-end that helps (now) to support several back-ends in the same time (by overloading).

[ldionne]

[Github PR transition cleanup]

Libc++ doesn't use the code under /pstl/ anymore, so I am neutral on this.

include/pstl/internal/algorithm_impl.h

 _OutputIterator
 pattern_copy_if(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
                 _OutputIterator __result, _UnaryPredicate __pred, _IsVector __is_vector, /*parallel=*/std::true_type)
 {
     typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
     const _DifferenceType __n = __last - __first;
     if (_DifferenceType(1) < __n)
     {
-        par_backend::buffer<bool> __mask_buf(__n);
-        return except_handler([&__exec, __n, __first, __result, __is_vector, __pred, &__mask_buf]() {
+        par_backend::buffer<bool> __mask_buf(std::forward<_ExecutionPolicy>(__exec), __n);
+        return except_handler([&__exec, __n, __first, __last, __result, __is_vector, __pred, &__mask_buf]() {
             bool* __mask = __mask_buf.get();
             _DifferenceType __m{};
             par_backend::parallel_strict_scan(
                 std::forward<_ExecutionPolicy>(__exec), __n, _DifferenceType(0),
                 [=](_DifferenceType __i, _DifferenceType __len) { // Reduce
                     return brick_calc_mask_1<_DifferenceType>(__first + __i, __first + (__i + __len), __mask + __i,
                                                               __pred, __is_vector)
                         .first;

 template <class _ExecutionPolicy, class _ForwardIterator, class _CalcMask, class _IsVector>
 _ForwardIterator
 remove_elements(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _CalcMask __calc_mask,
                 _IsVector __is_vector)
 {
     typedef typename std::iterator_traits<_ForwardIterator>::difference_type _DifferenceType;
     typedef typename std::iterator_traits<_ForwardIterator>::value_type _Tp;
     _DifferenceType __n = __last - __first;
-    par_backend::buffer<bool> __mask_buf(__n);
+    par_backend::buffer<bool> __mask_buf(std::forward<_ExecutionPolicy>(__exec), __n);
     // 1. find a first iterator that should be removed
     return except_handler([&]() {
         bool* __mask = __mask_buf.get();
         _DifferenceType __min = par_backend::parallel_reduce(
             std::forward<_ExecutionPolicy>(__exec), _DifferenceType(0), __n, __n,
             [__first, __mask, &__calc_mask, __is_vector](_DifferenceType __i, _DifferenceType __j,
                                                          _DifferenceType __local_min) -> _DifferenceType {
                 // Create mask
return except_handler([&]() {
         // No elements to remove - exit
         if (__min == __n)
         {
             return __last;
         }
         __n -= __min;
         __first += __min;
 
-        par_backend::buffer<_Tp> __buf(__n);
+        par_backend::buffer<_Tp> __buf(std::forward<_ExecutionPolicy>(__exec), __n);
         _Tp* __result = __buf.get();
         __mask += __min;
         _DifferenceType __m{};
         // 2. Elements that doesn't satisfy pred are moved to result
         par_backend::parallel_strict_scan(
             std::forward<_ExecutionPolicy>(__exec), __n, _DifferenceType(0),
             [__mask, __is_vector](_DifferenceType __i, _DifferenceType __len) {
                 return brick_count(__mask + __i, __mask + __i + __len, [](bool __val) { return __val; }, __is_vector);

 pattern_unique_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
                     _OutputIterator __result, _BinaryPredicate __pred, _IsVector __is_vector,
                     /*parallel=*/std::true_type)
 {
     typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
     const _DifferenceType __n = __last - __first;
     if (_DifferenceType(2) < __n)
     {
-        par_backend::buffer<bool> __mask_buf(__n);
+        par_backend::buffer<bool> __mask_buf(std::forward<_ExecutionPolicy>(__exec), __n);
         if (_DifferenceType(2) < __n)
         {
             return internal::except_handler([&__exec, __n, __first, __result, __pred, __is_vector, &__mask_buf]() {
                 bool* __mask = __mask_buf.get();
                 _DifferenceType __m{};
                 par_backend::parallel_strict_scan(
                     std::forward<_ExecutionPolicy>(__exec), __n, _DifferenceType(0),
                     [=](_DifferenceType __i, _DifferenceType __len) -> _DifferenceType { // Reduce

 pattern_rotate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
                _IsVector __is_vector, /*is_parallel=*/std::true_type)
 {
     typedef typename std::iterator_traits<_ForwardIterator>::value_type _Tp;
     auto __n = __last - __first;
     auto __m = __middle - __first;
     if (__m <= __n / 2)
     {
-        par_backend::buffer<_Tp> __buf(__n - __m);
+        par_backend::buffer<_Tp> __buf(std::forward<_ExecutionPolicy>(__exec), __n - __m);
         return except_handler([&__exec, __n, __m, __first, __middle, __last, __is_vector, &__buf]() {
             _Tp* __result = __buf.get();
             par_backend::parallel_for(
                 std::forward<_ExecutionPolicy>(__exec), __middle, __last,
                 [__middle, __result, __is_vector](_ForwardIterator __b, _ForwardIterator __e) {
                     brick_uninitialized_move(__b, __e, __result + (__b - __middle), __is_vector);
                 });
 
             par_backend::parallel_for(
                 std::forward<_ExecutionPolicy>(__exec), __first, __middle,
                 [__last, __middle, __is_vector](_ForwardIterator __b, _ForwardIterator __e) {
                     brick_move(__b, __e, __b + (__last - __middle), __is_vector);
                 });
 
             par_backend::parallel_for(std::forward<_ExecutionPolicy>(__exec), __result, __result + (__n - __m),
                                       [__first, __result, __is_vector](_Tp* __b, _Tp* __e) {
                                           brick_move(__b, __e, __first + (__b - __result), __is_vector);
                                       });
 
             return __first + (__last - __middle);
         });
     }
     else
     {
-        par_backend::buffer<_Tp> __buf(__m);
+        par_backend::buffer<_Tp> __buf(std::forward<_ExecutionPolicy>(__exec), __m);
         return except_handler([&__exec, __n, __m, __first, __middle, __last, __is_vector, &__buf]() {
             _Tp* __result = __buf.get();
             par_backend::parallel_for(
                 std::forward<_ExecutionPolicy>(__exec), __first, __middle,
                 [__first, __result, __is_vector](_ForwardIterator __b, _ForwardIterator __e) {
                     brick_uninitialized_move(__b, __e, __result + (__b - __first), __is_vector);
                 });
 
pattern_partition_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
                        _OutputIterator1 __out_true, _OutputIterator2 __out_false, _UnaryPredicate __pred,
                        _IsVector __is_vector, /*is_parallelization=*/std::true_type)
 {
     typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
     typedef std::pair<_DifferenceType, _DifferenceType> _ReturnType;
     const _DifferenceType __n = __last - __first;
     if (_DifferenceType(1) < __n)
     {
-        par_backend::buffer<bool> __mask_buf(__n);
+        par_backend::buffer<bool> __mask_buf(std::forward<_ExecutionPolicy>(__exec), __n);
         return internal::except_handler(
             [&__exec, __n, __first, __out_true, __out_false, __is_vector, __pred, &__mask_buf]() {
                 bool* __mask = __mask_buf.get();
                 _ReturnType __m{};
                 par_backend::parallel_strict_scan(
                     std::forward<_ExecutionPolicy>(__exec), __n, std::make_pair(_DifferenceType(0), _DifferenceType(0)),
                     [=](_DifferenceType __i, _DifferenceType __len) { // Reduce
                         return internal::brick_calc_mask_1<_DifferenceType>(__first + __i, __first + (__i + __len),
#endif
                 },
                 __n1);
             return __d_first + __n1;
         }
         else
         {
             typedef typename std::iterator_traits<_ForwardIterator>::value_type _T1;
             typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _T2;
-            par_backend::buffer<_T1> __buf(__n1);
+            par_backend::buffer<_T1> __buf(std::forward<_ExecutionPolicy>(__exec), __n1);
             _T1* __r = __buf.get();
 
             par_backend::parallel_stable_sort(std::forward<_ExecutionPolicy>(__exec), __r, __r + __n1, __comp,
                                               [__n2, __first, __r](_T1* __i, _T1* __j, _Compare __comp) {
                                                   _ForwardIterator __it = __first + (__i - __r);
 
                                                   // 1. Copy elements from input to raw memory
                                                   for (_T1* __k = __i; __k != __j; ++__k, ++__it)
pattern_inplace_merge(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __middle,
                       /*is_parallel=*/std::true_type)
 {
     if (__first == __last || __first == __middle || __middle == __last)
     {
         return;
     }
     typedef typename std::iterator_traits<_BidirectionalIterator>::value_type _Tp;
     auto __n = __last - __first;
-    par_backend::buffer<_Tp> __buf(__n);
+    par_backend::buffer<_Tp> __buf(std::forward<_ExecutionPolicy>(__exec), __n);
     _Tp* __r = __buf.get();
     except_handler([&]() {
         auto __move_values = [](_BidirectionalIterator __x, _Tp* __z) {
             invoke_if_else(std::is_trivial<_Tp>(), [&]() { *__z = std::move(*__x); },
                            [&]() { ::new (std::addressof(*__z)) _Tp(std::move(*__x)); });
         };
 
         auto __move_sequences = [](_BidirectionalIterator __first1, _BidirectionalIterator __last1, _Tp* __first2) {
struct _SetRange
         {
             return __len == 0;
         }
     };
 
     const _DifferenceType __n1 = __last1 - __first1;
     const _DifferenceType __n2 = __last2 - __first2;
 
-    par_backend::buffer<_T> __buf(__size_func(__n1, __n2));
+    par_backend::buffer<_T> __buf(std::forward<_ExecutionPolicy>(__exec), __size_func(__n1, __n2));
 
     return except_handler([&__exec, __n1, __first1, __last1, __first2, __last2, __result, __is_vector, __comp,
                            __size_func, __set_op, &__buf]() {
         auto __buffer = __buf.get();
         _DifferenceType __m{};
         auto __scan = [=](_DifferenceType, _DifferenceType, const _SetRange& __s) { // Scan
             if (!__s.empty())
                 brick_move(__buffer + __s.__buf_pos, __buffer + (__s.__buf_pos + __s.__len), __result + __s.__pos,

include/pstl/internal/parallel_backend_tbb.h

class buffer
     _Tp* _M_ptr;
     const std::size_t _M_buf_size;
     buffer(const buffer&) = delete;
     void
     operator=(const buffer&) = delete;
 
   public:
     //! Try to obtain buffer of given size to store objects of _Tp type
-    buffer(std::size_t n) : _M_allocator(), _M_ptr(_M_allocator.allocate(n)), _M_buf_size(n) {}
+    template <typename _ExecutionPolicy>
+    buffer(_ExecutionPolicy&&, std::size_t __n) : _M_allocator(), _M_ptr(_M_allocator.allocate(__n)), _M_buf_size(__n) {}
     //! True if buffer was successfully obtained, zero otherwise.
     operator bool() const { return _M_ptr != NULL; }
     //! Return pointer to buffer, or  NULL if buffer could not be obtained.
     _Tp*
     get() const
     {
         return _M_ptr;
     }

 // reduce and scan are each called exactly once per subrange.
 // Thus callers can rely upon side effects in reduce.
 // combine must not throw an exception.
 // apex is called exactly once, after all calls to reduce and before all calls to scan.
 // For example, it's useful for allocating a buffer used by scan but whose size is the sum of all reduction values.
 // T must have a trivial constructor and destructor.
 template <class _ExecutionPolicy, typename _Index, typename _Tp, typename _Rp, typename _Cp, typename _Sp, typename _Ap>
 void
-parallel_strict_scan(_ExecutionPolicy&&, _Index __n, _Tp __initial, _Rp __reduce, _Cp __combine, _Sp __scan, _Ap __apex)
+parallel_strict_scan(_ExecutionPolicy&& __exec, _Index __n, _Tp __initial, _Rp __reduce, _Cp __combine, _Sp __scan, _Ap __apex)
 {
-    tbb::this_task_arena::isolate([=, &__combine]() {
+    tbb::this_task_arena::isolate([=, &__exec, &__combine]() {
         if (__n > 1)
         {
             _Index __p = tbb::this_task_arena::max_concurrency();
             const _Index __slack = 4;
             _Index __tilesize = (__n - 1) / (__slack * __p) + 1;
             _Index __m = (__n - 1) / __tilesize;
-            buffer<_Tp> __buf(__m + 1);
+            buffer<_Tp> __buf(std::forward<_ExecutionPolicy>(__exec), __m + 1);
             _Tp* __r = __buf.get();
             par_backend::upsweep(_Index(0), _Index(__m + 1), __tilesize, __r, __n - __m * __tilesize, __reduce,
                                  __combine);
             // When __apex is a no-op and __combine has no side effects, a good optimizer
             // should be able to eliminate all code between here and __apex.
             // Alternatively, provide a default value for __apex that can be
             // recognized by metaprogramming that conditionlly executes the following.
             size_t __k = __m + 1;
else
         _M_xe = __xm;
         _M_inplace = !_M_inplace;
     }
     return this;
 }
 
 template <class _ExecutionPolicy, typename _RandomAccessIterator, typename _Compare, typename _LeafSort>
 void
-parallel_stable_sort(_ExecutionPolicy&&, _RandomAccessIterator __xs, _RandomAccessIterator __xe, _Compare __comp,
+parallel_stable_sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __xs, _RandomAccessIterator __xe, _Compare __comp,
                      _LeafSort __leaf_sort, std::size_t __nsort = 0)
 {
-    tbb::this_task_arena::isolate([=, &__nsort]() {
+    tbb::this_task_arena::isolate([=, &__exec, &__nsort]() {
         //sorting based on task tree and parallel merge
         typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _ValueType;
         typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
         const _DifferenceType __n = __xe - __xs;
         if (__nsort == 0)
             __nsort = __n;
 
         const _DifferenceType __sort_cut_off = __PSTL_STABLE_SORT_CUT_OFF;
         if (__n > __sort_cut_off)
         {
             assert(__nsort > 0 && __nsort <= __n);
-            buffer<_ValueType> __buf(__n);
+            buffer<_ValueType> __buf(std::forward<_ExecutionPolicy>(__exec), __n);
             using tbb::task;
             task::spawn_root_and_wait(*new (task::allocate_root())
                                           stable_sort_task<_RandomAccessIterator, _ValueType*, _Compare, _LeafSort>(
                                               __xs, __xe, (_ValueType*)__buf.get(), 2, __comp, __leaf_sort, __nsort));
             return;
         }
         //serial sort
         __leaf_sort(__xs, __xe, __comp);

include/pstl/internal/parallel_backend_utils.h

else
         for (; __zs != __ze; ++__zs)
             new (&*__zs) _ValueType;
     }
 }
 
 template <typename _Buf>
 class stack
 {
-    typedef typename std::iterator_traits<decltype(_Buf(0).get())>::value_type _ValueType;
+    typedef typename std::iterator_traits<decltype(std::declval<_Buf>().get())>::value_type _ValueType;
     typedef typename std::iterator_traits<_ValueType*>::difference_type _DifferenceType;
 
     _Buf _M_buf;
     _ValueType* _M_ptr;
     _DifferenceType _M_maxsize;
 
     stack(const stack&) = delete;
     void
     operator=(const stack&) = delete;
 
   public:
-    stack(_DifferenceType __max_size) : _M_buf(__max_size), _M_maxsize(__max_size) { _M_ptr = _M_buf.get(); }
+    template <typename _ExecutionPolicy>
+    stack(_ExecutionPolicy&& __exec, _DifferenceType __max_size)
+        : _M_buf(std::forward<_ExecutionPolicy>(__exec), __max_size), _M_maxsize(__max_size) { _M_ptr = _M_buf.get(); }
 
     ~stack()
     {
         assert(size() <= _M_maxsize);
         while (!empty())
             pop();
     }