The C and C++ Include Header Files

/usr/include/c++/11/pstl/unseq_backend_simd.h


$ cat -n /usr/include/c++/11/pstl/unseq_backend_simd.h

     1	// -*- C++ -*-
     2	//===-- unseq_backend_simd.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_UNSEQ_BACKEND_SIMD_H
    11	#define _PSTL_UNSEQ_BACKEND_SIMD_H
    12	
    13	#include <type_traits>
    14	
    15	#include "utils.h"
    16	
    17	// This header defines the minimum set of vector routines required
    18	// to support parallel STL.
    19	namespace __pstl
    20	{
    21	namespace __unseq_backend
    22	{
    23	
    24	// Expect vector width up to 64 (or 512 bit)
    25	const std::size_t __lane_size = 64;
    26	
    27	template <class _Iterator, class _DifferenceType, class _Function>
    28	_Iterator
    29	__simd_walk_1(_Iterator __first, _DifferenceType __n, _Function __f) noexcept
    30	{
    31	    _PSTL_PRAGMA_SIMD
    32	    for (_DifferenceType __i = 0; __i < __n; ++__i)
    33	        __f(__first[__i]);
    34	
    35	    return __first + __n;
    36	}
    37	
    38	template <class _Iterator1, class _DifferenceType, class _Iterator2, class _Function>
    39	_Iterator2
    40	__simd_walk_2(_Iterator1 __first1, _DifferenceType __n, _Iterator2 __first2, _Function __f) noexcept
    41	{
    42	    _PSTL_PRAGMA_SIMD
    43	    for (_DifferenceType __i = 0; __i < __n; ++__i)
    44	        __f(__first1[__i], __first2[__i]);
    45	    return __first2 + __n;
    46	}
    47	
    48	template <class _Iterator1, class _DifferenceType, class _Iterator2, class _Iterator3, class _Function>
    49	_Iterator3
    50	__simd_walk_3(_Iterator1 __first1, _DifferenceType __n, _Iterator2 __first2, _Iterator3 __first3,
    51	              _Function __f) noexcept
    52	{
    53	    _PSTL_PRAGMA_SIMD
    54	    for (_DifferenceType __i = 0; __i < __n; ++__i)
    55	        __f(__first1[__i], __first2[__i], __first3[__i]);
    56	    return __first3 + __n;
    57	}
    58	
    59	// TODO: check whether __simd_first() can be used here
    60	template <class _Index, class _DifferenceType, class _Pred>
    61	bool
    62	__simd_or(_Index __first, _DifferenceType __n, _Pred __pred) noexcept
    63	{
    64	#if _PSTL_EARLYEXIT_PRESENT
    65	    _DifferenceType __i;
    66	    _PSTL_PRAGMA_VECTOR_UNALIGNED
    67	    _PSTL_PRAGMA_SIMD_EARLYEXIT
    68	    for (__i = 0; __i < __n; ++__i)
    69	        if (__pred(__first[__i]))
    70	            break;
    71	    return __i < __n;
    72	#else
    73	    _DifferenceType __block_size = 4 < __n ? 4 : __n;
    74	    const _Index __last = __first + __n;
    75	    while (__last != __first)
    76	    {
    77	        int32_t __flag = 1;
    78	        _PSTL_PRAGMA_SIMD_REDUCTION(& : __flag)
    79	        for (_DifferenceType __i = 0; __i < __block_size; ++__i)
    80	            if (__pred(*(__first + __i)))
    81	                __flag = 0;
    82	        if (!__flag)
    83	            return true;
    84	
    85	        __first += __block_size;
    86	        if (__last - __first >= __block_size << 1)
    87	        {
    88	            // Double the block _Size.  Any unnecessary iterations can be amortized against work done so far.
    89	            __block_size <<= 1;
    90	        }
    91	        else
    92	        {
    93	            __block_size = __last - __first;
    94	        }
    95	    }
    96	    return false;
    97	#endif
    98	}
    99	
   100	template <class _Index, class _DifferenceType, class _Compare>
   101	_Index
   102	__simd_first(_Index __first, _DifferenceType __begin, _DifferenceType __end, _Compare __comp) noexcept
   103	{
   104	#if _PSTL_EARLYEXIT_PRESENT
   105	    _DifferenceType __i = __begin;
   106	    _PSTL_PRAGMA_VECTOR_UNALIGNED // Do not generate peel loop part
   107	        _PSTL_PRAGMA_SIMD_EARLYEXIT for (; __i < __end; ++__i)
   108	    {
   109	        if (__comp(__first, __i))
   110	        {
   111	            break;
   112	        }
   113	    }
   114	    return __first + __i;
   115	#else
   116	    // Experiments show good block sizes like this
   117	    const _DifferenceType __block_size = 8;
   118	    alignas(__lane_size) _DifferenceType __lane[__block_size] = {0};
   119	    while (__end - __begin >= __block_size)
   120	    {
   121	        _DifferenceType __found = 0;
   122	        _PSTL_PRAGMA_VECTOR_UNALIGNED // Do not generate peel loop part
   123	            _PSTL_PRAGMA_SIMD_REDUCTION(|
   124	                                        : __found) for (_DifferenceType __i = __begin; __i < __begin + __block_size;
   125	                                                        ++__i)
   126	        {
   127	            const _DifferenceType __t = __comp(__first, __i);
   128	            __lane[__i - __begin] = __t;
   129	            __found |= __t;
   130	        }
   131	        if (__found)
   132	        {
   133	            _DifferenceType __i;
   134	            // This will vectorize
   135	            for (__i = 0; __i < __block_size; ++__i)
   136	            {
   137	                if (__lane[__i])
   138	                {
   139	                    break;
   140	                }
   141	            }
   142	            return __first + __begin + __i;
   143	        }
   144	        __begin += __block_size;
   145	    }
   146	
   147	    //Keep remainder scalar
   148	    while (__begin != __end)
   149	    {
   150	        if (__comp(__first, __begin))
   151	        {
   152	            return __first + __begin;
   153	        }
   154	        ++__begin;
   155	    }
   156	    return __first + __end;
   157	#endif //_PSTL_EARLYEXIT_PRESENT
   158	}
   159	
   160	template <class _Index1, class _DifferenceType, class _Index2, class _Pred>
   161	std::pair<_Index1, _Index2>
   162	__simd_first(_Index1 __first1, _DifferenceType __n, _Index2 __first2, _Pred __pred) noexcept
   163	{
   164	#if _PSTL_EARLYEXIT_PRESENT
   165	    _DifferenceType __i = 0;
   166	    _PSTL_PRAGMA_VECTOR_UNALIGNED
   167	    _PSTL_PRAGMA_SIMD_EARLYEXIT
   168	    for (; __i < __n; ++__i)
   169	        if (__pred(__first1[__i], __first2[__i]))
   170	            break;
   171	    return std::make_pair(__first1 + __i, __first2 + __i);
   172	#else
   173	    const _Index1 __last1 = __first1 + __n;
   174	    const _Index2 __last2 = __first2 + __n;
   175	    // Experiments show good block sizes like this
   176	    const _DifferenceType __block_size = 8;
   177	    alignas(__lane_size) _DifferenceType __lane[__block_size] = {0};
   178	    while (__last1 - __first1 >= __block_size)
   179	    {
   180	        _DifferenceType __found = 0;
   181	        _DifferenceType __i;
   182	        _PSTL_PRAGMA_VECTOR_UNALIGNED // Do not generate peel loop part
   183	            _PSTL_PRAGMA_SIMD_REDUCTION(|
   184	                                        : __found) for (__i = 0; __i < __block_size; ++__i)
   185	        {
   186	            const _DifferenceType __t = __pred(__first1[__i], __first2[__i]);
   187	            __lane[__i] = __t;
   188	            __found |= __t;
   189	        }
   190	        if (__found)
   191	        {
   192	            _DifferenceType __i2;
   193	            // This will vectorize
   194	            for (__i2 = 0; __i2 < __block_size; ++__i2)
   195	            {
   196	                if (__lane[__i2])
   197	                    break;
   198	            }
   199	            return std::make_pair(__first1 + __i2, __first2 + __i2);
   200	        }
   201	        __first1 += __block_size;
   202	        __first2 += __block_size;
   203	    }
   204	
   205	    //Keep remainder scalar
   206	    for (; __last1 != __first1; ++__first1, ++__first2)
   207	        if (__pred(*(__first1), *(__first2)))
   208	            return std::make_pair(__first1, __first2);
   209	
   210	    return std::make_pair(__last1, __last2);
   211	#endif //_PSTL_EARLYEXIT_PRESENT
   212	}
   213	
   214	template <class _Index, class _DifferenceType, class _Pred>
   215	_DifferenceType
   216	__simd_count(_Index __index, _DifferenceType __n, _Pred __pred) noexcept
   217	{
   218	    _DifferenceType __count = 0;
   219	    _PSTL_PRAGMA_SIMD_REDUCTION(+ : __count)
   220	    for (_DifferenceType __i = 0; __i < __n; ++__i)
   221	        if (__pred(*(__index + __i)))
   222	            ++__count;
   223	
   224	    return __count;
   225	}
   226	
   227	template <class _InputIterator, class _DifferenceType, class _OutputIterator, class _BinaryPredicate>
   228	_OutputIterator
   229	__simd_unique_copy(_InputIterator __first, _DifferenceType __n, _OutputIterator __result,
   230	                   _BinaryPredicate __pred) noexcept
   231	{
   232	    if (__n == 0)
   233	        return __result;
   234	
   235	    _DifferenceType __cnt = 1;
   236	    __result[0] = __first[0];
   237	
   238	    _PSTL_PRAGMA_SIMD
   239	    for (_DifferenceType __i = 1; __i < __n; ++__i)
   240	    {
   241	        _PSTL_PRAGMA_SIMD_ORDERED_MONOTONIC(__cnt : 1)
   242	        if (!__pred(__first[__i], __first[__i - 1]))
   243	        {
   244	            __result[__cnt] = __first[__i];
   245	            ++__cnt;
   246	        }
   247	    }
   248	    return __result + __cnt;
   249	}
   250	
   251	template <class _InputIterator, class _DifferenceType, class _OutputIterator, class _Assigner>
   252	_OutputIterator
   253	__simd_assign(_InputIterator __first, _DifferenceType __n, _OutputIterator __result, _Assigner __assigner) noexcept
   254	{
   255	    _PSTL_USE_NONTEMPORAL_STORES_IF_ALLOWED
   256	    _PSTL_PRAGMA_SIMD
   257	    for (_DifferenceType __i = 0; __i < __n; ++__i)
   258	        __assigner(__first + __i, __result + __i);
   259	    return __result + __n;
   260	}
   261	
   262	template <class _InputIterator, class _DifferenceType, class _OutputIterator, class _UnaryPredicate>
   263	_OutputIterator
   264	__simd_copy_if(_InputIterator __first, _DifferenceType __n, _OutputIterator __result, _UnaryPredicate __pred) noexcept
   265	{
   266	    _DifferenceType __cnt = 0;
   267	
   268	    _PSTL_PRAGMA_SIMD
   269	    for (_DifferenceType __i = 0; __i < __n; ++__i)
   270	    {
   271	        _PSTL_PRAGMA_SIMD_ORDERED_MONOTONIC(__cnt : 1)
   272	        if (__pred(__first[__i]))
   273	        {
   274	            __result[__cnt] = __first[__i];
   275	            ++__cnt;
   276	        }
   277	    }
   278	    return __result + __cnt;
   279	}
   280	
   281	template <class _InputIterator, class _DifferenceType, class _BinaryPredicate>
   282	_DifferenceType
   283	__simd_calc_mask_2(_InputIterator __first, _DifferenceType __n, bool* __mask, _BinaryPredicate __pred) noexcept
   284	{
   285	    _DifferenceType __count = 0;
   286	
   287	    _PSTL_PRAGMA_SIMD_REDUCTION(+ : __count)
   288	    for (_DifferenceType __i = 0; __i < __n; ++__i)
   289	    {
   290	        __mask[__i] = !__pred(__first[__i], __first[__i - 1]);
   291	        __count += __mask[__i];
   292	    }
   293	    return __count;
   294	}
   295	
   296	template <class _InputIterator, class _DifferenceType, class _UnaryPredicate>
   297	_DifferenceType
   298	__simd_calc_mask_1(_InputIterator __first, _DifferenceType __n, bool* __mask, _UnaryPredicate __pred) noexcept
   299	{
   300	    _DifferenceType __count = 0;
   301	
   302	    _PSTL_PRAGMA_SIMD_REDUCTION(+ : __count)
   303	    for (_DifferenceType __i = 0; __i < __n; ++__i)
   304	    {
   305	        __mask[__i] = __pred(__first[__i]);
   306	        __count += __mask[__i];
   307	    }
   308	    return __count;
   309	}
   310	
   311	template <class _InputIterator, class _DifferenceType, class _OutputIterator, class _Assigner>
   312	void
   313	__simd_copy_by_mask(_InputIterator __first, _DifferenceType __n, _OutputIterator __result, bool* __mask,
   314	                    _Assigner __assigner) noexcept
   315	{
   316	    _DifferenceType __cnt = 0;
   317	    _PSTL_PRAGMA_SIMD
   318	    for (_DifferenceType __i = 0; __i < __n; ++__i)
   319	    {
   320	        if (__mask[__i])
   321	        {
   322	            _PSTL_PRAGMA_SIMD_ORDERED_MONOTONIC(__cnt : 1)
   323	            {
   324	                __assigner(__first + __i, __result + __cnt);
   325	                ++__cnt;
   326	            }
   327	        }
   328	    }
   329	}
   330	
   331	template <class _InputIterator, class _DifferenceType, class _OutputIterator1, class _OutputIterator2>
   332	void
   333	__simd_partition_by_mask(_InputIterator __first, _DifferenceType __n, _OutputIterator1 __out_true,
   334	                         _OutputIterator2 __out_false, bool* __mask) noexcept
   335	{
   336	    _DifferenceType __cnt_true = 0, __cnt_false = 0;
   337	    _PSTL_PRAGMA_SIMD
   338	    for (_DifferenceType __i = 0; __i < __n; ++__i)
   339	    {
   340	        _PSTL_PRAGMA_SIMD_ORDERED_MONOTONIC_2ARGS(__cnt_true : 1, __cnt_false : 1)
   341	        if (__mask[__i])
   342	        {
   343	            __out_true[__cnt_true] = __first[__i];
   344	            ++__cnt_true;
   345	        }
   346	        else
   347	        {
   348	            __out_false[__cnt_false] = __first[__i];
   349	            ++__cnt_false;
   350	        }
   351	    }
   352	}
   353	
   354	template <class _Index, class _DifferenceType, class _Tp>
   355	_Index
   356	__simd_fill_n(_Index __first, _DifferenceType __n, const _Tp& __value) noexcept
   357	{
   358	    _PSTL_USE_NONTEMPORAL_STORES_IF_ALLOWED
   359	    _PSTL_PRAGMA_SIMD
   360	    for (_DifferenceType __i = 0; __i < __n; ++__i)
   361	        __first[__i] = __value;
   362	    return __first + __n;
   363	}
   364	
   365	template <class _Index, class _DifferenceType, class _Generator>
   366	_Index
   367	__simd_generate_n(_Index __first, _DifferenceType __size, _Generator __g) noexcept
   368	{
   369	    _PSTL_USE_NONTEMPORAL_STORES_IF_ALLOWED
   370	    _PSTL_PRAGMA_SIMD
   371	    for (_DifferenceType __i = 0; __i < __size; ++__i)
   372	        __first[__i] = __g();
   373	    return __first + __size;
   374	}
   375	
   376	template <class _Index, class _BinaryPredicate>
   377	_Index
   378	__simd_adjacent_find(_Index __first, _Index __last, _BinaryPredicate __pred, bool __or_semantic) noexcept
   379	{
   380	    if (__last - __first < 2)
   381	        return __last;
   382	
   383	    typedef typename std::iterator_traits<_Index>::difference_type _DifferenceType;
   384	    _DifferenceType __i = 0;
   385	
   386	#if _PSTL_EARLYEXIT_PRESENT
   387	    //Some compiler versions fail to compile the following loop when iterators are used. Indices are used instead
   388	    const _DifferenceType __n = __last - __first - 1;
   389	    _PSTL_PRAGMA_VECTOR_UNALIGNED
   390	    _PSTL_PRAGMA_SIMD_EARLYEXIT
   391	    for (; __i < __n; ++__i)
   392	        if (__pred(__first[__i], __first[__i + 1]))
   393	            break;
   394	
   395	    return __i < __n ? __first + __i : __last;
   396	#else
   397	    // Experiments show good block sizes like this
   398	    //TODO: to consider tuning block_size for various data types
   399	    const _DifferenceType __block_size = 8;
   400	    alignas(__lane_size) _DifferenceType __lane[__block_size] = {0};
   401	    while (__last - __first >= __block_size)
   402	    {
   403	        _DifferenceType __found = 0;
   404	        _PSTL_PRAGMA_VECTOR_UNALIGNED // Do not generate peel loop part
   405	            _PSTL_PRAGMA_SIMD_REDUCTION(|
   406	                                        : __found) for (__i = 0; __i < __block_size - 1; ++__i)
   407	        {
   408	            //TODO: to improve SIMD vectorization
   409	            const _DifferenceType __t = __pred(*(__first + __i), *(__first + __i + 1));
   410	            __lane[__i] = __t;
   411	            __found |= __t;
   412	        }
   413	
   414	        //Process a pair of elements on a boundary of a data block
   415	        if (__first + __block_size < __last && __pred(*(__first + __i), *(__first + __i + 1)))
   416	            __lane[__i] = __found = 1;
   417	
   418	        if (__found)
   419	        {
   420	            if (__or_semantic)
   421	                return __first;
   422	
   423	            // This will vectorize
   424	            for (__i = 0; __i < __block_size; ++__i)
   425	                if (__lane[__i])
   426	                    break;
   427	            return __first + __i; //As far as found is true a __result (__lane[__i] is true) is guaranteed
   428	        }
   429	        __first += __block_size;
   430	    }
   431	    //Process the rest elements
   432	    for (; __last - __first > 1; ++__first)
   433	        if (__pred(*__first, *(__first + 1)))
   434	            return __first;
   435	
   436	    return __last;
   437	#endif
   438	}
   439	
   440	// It was created to reduce the code inside std::enable_if
   441	template <typename _Tp, typename _BinaryOperation>
   442	using is_arithmetic_plus = std::integral_constant<bool, std::is_arithmetic<_Tp>::value &&
   443	                                                            std::is_same<_BinaryOperation, std::plus<_Tp>>::value>;
   444	
   445	template <typename _DifferenceType, typename _Tp, typename _BinaryOperation, typename _UnaryOperation>
   446	typename std::enable_if<is_arithmetic_plus<_Tp, _BinaryOperation>::value, _Tp>::type
   447	__simd_transform_reduce(_DifferenceType __n, _Tp __init, _BinaryOperation, _UnaryOperation __f) noexcept
   448	{
   449	    _PSTL_PRAGMA_SIMD_REDUCTION(+ : __init)
   450	    for (_DifferenceType __i = 0; __i < __n; ++__i)
   451	        __init += __f(__i);
   452	    return __init;
   453	}
   454	
   455	template <typename _Size, typename _Tp, typename _BinaryOperation, typename _UnaryOperation>
   456	typename std::enable_if<!is_arithmetic_plus<_Tp, _BinaryOperation>::value, _Tp>::type
   457	__simd_transform_reduce(_Size __n, _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __f) noexcept
   458	{
   459	    const _Size __block_size = __lane_size / sizeof(_Tp);
   460	    if (__n > 2 * __block_size && __block_size > 1)
   461	    {
   462	        alignas(__lane_size) char __lane_[__lane_size];
   463	        _Tp* __lane = reinterpret_cast<_Tp*>(__lane_);
   464	
   465	        // initializer
   466	        _PSTL_PRAGMA_SIMD
   467	        for (_Size __i = 0; __i < __block_size; ++__i)
   468	        {
   469	            ::new (__lane + __i) _Tp(__binary_op(__f(__i), __f(__block_size + __i)));
   470	        }
   471	        // main loop
   472	        _Size __i = 2 * __block_size;
   473	        const _Size last_iteration = __block_size * (__n / __block_size);
   474	        for (; __i < last_iteration; __i += __block_size)
   475	        {
   476	            _PSTL_PRAGMA_SIMD
   477	            for (_Size __j = 0; __j < __block_size; ++__j)
   478	            {
   479	                __lane[__j] = __binary_op(__lane[__j], __f(__i + __j));
   480	            }
   481	        }
   482	        // remainder
   483	        _PSTL_PRAGMA_SIMD
   484	        for (_Size __j = 0; __j < __n - last_iteration; ++__j)
   485	        {
   486	            __lane[__j] = __binary_op(__lane[__j], __f(last_iteration + __j));
   487	        }
   488	        // combiner
   489	        for (_Size __j = 0; __j < __block_size; ++__j)
   490	        {
   491	            __init = __binary_op(__init, __lane[__j]);
   492	        }
   493	        // destroyer
   494	        _PSTL_PRAGMA_SIMD
   495	        for (_Size __j = 0; __j < __block_size; ++__j)
   496	        {
   497	            __lane[__j].~_Tp();
   498	        }
   499	    }
   500	    else
   501	    {
   502	        for (_Size __i = 0; __i < __n; ++__i)
   503	        {
   504	            __init = __binary_op(__init, __f(__i));
   505	        }
   506	    }
   507	    return __init;
   508	}
   509	
   510	// Exclusive scan for "+" and arithmetic types
   511	template <class _InputIterator, class _Size, class _OutputIterator, class _UnaryOperation, class _Tp,
   512	          class _BinaryOperation>
   513	typename std::enable_if<is_arithmetic_plus<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
   514	__simd_scan(_InputIterator __first, _Size __n, _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init,
   515	            _BinaryOperation, /*Inclusive*/ std::false_type)
   516	{
   517	    _PSTL_PRAGMA_SIMD_SCAN(+ : __init)
   518	    for (_Size __i = 0; __i < __n; ++__i)
   519	    {
   520	        __result[__i] = __init;
   521	        _PSTL_PRAGMA_SIMD_EXCLUSIVE_SCAN(__init)
   522	        __init += __unary_op(__first[__i]);
   523	    }
   524	    return std::make_pair(__result + __n, __init);
   525	}
   526	
   527	// As soon as we cannot call __binary_op in "combiner" we create a wrapper over _Tp to encapsulate __binary_op
   528	template <typename _Tp, typename _BinaryOp>
   529	struct _Combiner
   530	{
   531	    _Tp __value;
   532	    _BinaryOp* __bin_op; // Here is a pointer to function because of default ctor
   533	
   534	    _Combiner() : __value{}, __bin_op(nullptr) {}
   535	    _Combiner(const _Tp& value, const _BinaryOp* bin_op) : __value(value), __bin_op(const_cast<_BinaryOp*>(bin_op)) {}
   536	    _Combiner(const _Combiner& __obj) : __value{}, __bin_op(__obj.__bin_op) {}
   537	
   538	    void
   539	    operator()(const _Combiner& __obj)
   540	    {
   541	        __value = (*__bin_op)(__value, __obj.__value);
   542	    }
   543	};
   544	
   545	// Exclusive scan for other binary operations and types
   546	template <class _InputIterator, class _Size, class _OutputIterator, class _UnaryOperation, class _Tp,
   547	          class _BinaryOperation>
   548	typename std::enable_if<!is_arithmetic_plus<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
   549	__simd_scan(_InputIterator __first, _Size __n, _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init,
   550	            _BinaryOperation __binary_op, /*Inclusive*/ std::false_type)
   551	{
   552	    typedef _Combiner<_Tp, _BinaryOperation> _CombinerType;
   553	    _CombinerType __init_{__init, &__binary_op};
   554	
   555	    _PSTL_PRAGMA_DECLARE_REDUCTION(__bin_op, _CombinerType)
   556	
   557	    _PSTL_PRAGMA_SIMD_SCAN(__bin_op : __init_)
   558	    for (_Size __i = 0; __i < __n; ++__i)
   559	    {
   560	        __result[__i] = __init_.__value;
   561	        _PSTL_PRAGMA_SIMD_EXCLUSIVE_SCAN(__init_)
   562	        _PSTL_PRAGMA_FORCEINLINE
   563	        __init_.__value = __binary_op(__init_.__value, __unary_op(__first[__i]));
   564	    }
   565	    return std::make_pair(__result + __n, __init_.__value);
   566	}
   567	
   568	// Inclusive scan for "+" and arithmetic types
   569	template <class _InputIterator, class _Size, class _OutputIterator, class _UnaryOperation, class _Tp,
   570	          class _BinaryOperation>
   571	typename std::enable_if<is_arithmetic_plus<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
   572	__simd_scan(_InputIterator __first, _Size __n, _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init,
   573	            _BinaryOperation, /*Inclusive*/ std::true_type)
   574	{
   575	    _PSTL_PRAGMA_SIMD_SCAN(+ : __init)
   576	    for (_Size __i = 0; __i < __n; ++__i)
   577	    {
   578	        __init += __unary_op(__first[__i]);
   579	        _PSTL_PRAGMA_SIMD_INCLUSIVE_SCAN(__init)
   580	        __result[__i] = __init;
   581	    }
   582	    return std::make_pair(__result + __n, __init);
   583	}
   584	
   585	// Inclusive scan for other binary operations and types
   586	template <class _InputIterator, class _Size, class _OutputIterator, class _UnaryOperation, class _Tp,
   587	          class _BinaryOperation>
   588	typename std::enable_if<!is_arithmetic_plus<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
   589	__simd_scan(_InputIterator __first, _Size __n, _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init,
   590	            _BinaryOperation __binary_op, std::true_type)
   591	{
   592	    typedef _Combiner<_Tp, _BinaryOperation> _CombinerType;
   593	    _CombinerType __init_{__init, &__binary_op};
   594	
   595	    _PSTL_PRAGMA_DECLARE_REDUCTION(__bin_op, _CombinerType)
   596	
   597	    _PSTL_PRAGMA_SIMD_SCAN(__bin_op : __init_)
   598	    for (_Size __i = 0; __i < __n; ++__i)
   599	    {
   600	        _PSTL_PRAGMA_FORCEINLINE
   601	        __init_.__value = __binary_op(__init_.__value, __unary_op(__first[__i]));
   602	        _PSTL_PRAGMA_SIMD_INCLUSIVE_SCAN(__init_)
   603	        __result[__i] = __init_.__value;
   604	    }
   605	    return std::make_pair(__result + __n, __init_.__value);
   606	}
   607	
   608	// [restriction] - std::iterator_traits<_ForwardIterator>::value_type should be DefaultConstructible.
   609	// complexity [violation] - We will have at most (__n-1 + number_of_lanes) comparisons instead of at most __n-1.
   610	template <typename _ForwardIterator, typename _Size, typename _Compare>
   611	_ForwardIterator
   612	__simd_min_element(_ForwardIterator __first, _Size __n, _Compare __comp) noexcept
   613	{
   614	    if (__n == 0)
   615	    {
   616	        return __first;
   617	    }
   618	
   619	    typedef typename std::iterator_traits<_ForwardIterator>::value_type _ValueType;
   620	    struct _ComplexType
   621	    {
   622	        _ValueType __min_val;
   623	        _Size __min_ind;
   624	        _Compare* __min_comp;
   625	
   626	        _ComplexType() : __min_val{}, __min_ind{}, __min_comp(nullptr) {}
   627	        _ComplexType(const _ValueType& val, const _Compare* comp)
   628	            : __min_val(val), __min_ind(0), __min_comp(const_cast<_Compare*>(comp))
   629	        {
   630	        }
   631	        _ComplexType(const _ComplexType& __obj)
   632	            : __min_val(__obj.__min_val), __min_ind(__obj.__min_ind), __min_comp(__obj.__min_comp)
   633	        {
   634	        }
   635	
   636	        _PSTL_PRAGMA_DECLARE_SIMD
   637	        void
   638	        operator()(const _ComplexType& __obj)
   639	        {
   640	            if (!(*__min_comp)(__min_val, __obj.__min_val) &&
   641	                ((*__min_comp)(__obj.__min_val, __min_val) || __obj.__min_ind - __min_ind < 0))
   642	            {
   643	                __min_val = __obj.__min_val;
   644	                __min_ind = __obj.__min_ind;
   645	            }
   646	        }
   647	    };
   648	
   649	    _ComplexType __init{*__first, &__comp};
   650	
   651	    _PSTL_PRAGMA_DECLARE_REDUCTION(__min_func, _ComplexType)
   652	
   653	    _PSTL_PRAGMA_SIMD_REDUCTION(__min_func : __init)
   654	    for (_Size __i = 1; __i < __n; ++__i)
   655	    {
   656	        const _ValueType __min_val = __init.__min_val;
   657	        const _ValueType __current = __first[__i];
   658	        if (__comp(__current, __min_val))
   659	        {
   660	            __init.__min_val = __current;
   661	            __init.__min_ind = __i;
   662	        }
   663	    }
   664	    return __first + __init.__min_ind;
   665	}
   666	
   667	// [restriction] - std::iterator_traits<_ForwardIterator>::value_type should be DefaultConstructible.
   668	// complexity [violation] - We will have at most (2*(__n-1) + 4*number_of_lanes) comparisons instead of at most [1.5*(__n-1)].
   669	template <typename _ForwardIterator, typename _Size, typename _Compare>
   670	std::pair<_ForwardIterator, _ForwardIterator>
   671	__simd_minmax_element(_ForwardIterator __first, _Size __n, _Compare __comp) noexcept
   672	{
   673	    if (__n == 0)
   674	    {
   675	        return std::make_pair(__first, __first);
   676	    }
   677	    typedef typename std::iterator_traits<_ForwardIterator>::value_type _ValueType;
   678	
   679	    struct _ComplexType
   680	    {
   681	        _ValueType __min_val;
   682	        _ValueType __max_val;
   683	        _Size __min_ind;
   684	        _Size __max_ind;
   685	        _Compare* __minmax_comp;
   686	
   687	        _ComplexType() : __min_val{}, __max_val{}, __min_ind{}, __max_ind{}, __minmax_comp(nullptr) {}
   688	        _ComplexType(const _ValueType& min_val, const _ValueType& max_val, const _Compare* comp)
   689	            : __min_val(min_val), __max_val(max_val), __min_ind(0), __max_ind(0),
   690	              __minmax_comp(const_cast<_Compare*>(comp))
   691	        {
   692	        }
   693	        _ComplexType(const _ComplexType& __obj)
   694	            : __min_val(__obj.__min_val), __max_val(__obj.__max_val), __min_ind(__obj.__min_ind),
   695	              __max_ind(__obj.__max_ind), __minmax_comp(__obj.__minmax_comp)
   696	        {
   697	        }
   698	
   699	        void
   700	        operator()(const _ComplexType& __obj)
   701	        {
   702	            // min
   703	            if ((*__minmax_comp)(__obj.__min_val, __min_val))
   704	            {
   705	                __min_val = __obj.__min_val;
   706	                __min_ind = __obj.__min_ind;
   707	            }
   708	            else if (!(*__minmax_comp)(__min_val, __obj.__min_val))
   709	            {
   710	                __min_val = __obj.__min_val;
   711	                __min_ind = (__min_ind - __obj.__min_ind < 0) ? __min_ind : __obj.__min_ind;
   712	            }
   713	
   714	            // max
   715	            if ((*__minmax_comp)(__max_val, __obj.__max_val))
   716	            {
   717	                __max_val = __obj.__max_val;
   718	                __max_ind = __obj.__max_ind;
   719	            }
   720	            else if (!(*__minmax_comp)(__obj.__max_val, __max_val))
   721	            {
   722	                __max_val = __obj.__max_val;
   723	                __max_ind = (__max_ind - __obj.__max_ind < 0) ? __obj.__max_ind : __max_ind;
   724	            }
   725	        }
   726	    };
   727	
   728	    _ComplexType __init{*__first, *__first, &__comp};
   729	
   730	    _PSTL_PRAGMA_DECLARE_REDUCTION(__min_func, _ComplexType);
   731	
   732	    _PSTL_PRAGMA_SIMD_REDUCTION(__min_func : __init)
   733	    for (_Size __i = 1; __i < __n; ++__i)
   734	    {
   735	        auto __min_val = __init.__min_val;
   736	        auto __max_val = __init.__max_val;
   737	        auto __current = __first + __i;
   738	        if (__comp(*__current, __min_val))
   739	        {
   740	            __init.__min_val = *__current;
   741	            __init.__min_ind = __i;
   742	        }
   743	        else if (!__comp(*__current, __max_val))
   744	        {
   745	            __init.__max_val = *__current;
   746	            __init.__max_ind = __i;
   747	        }
   748	    }
   749	    return std::make_pair(__first + __init.__min_ind, __first + __init.__max_ind);
   750	}
   751	
   752	template <class _InputIterator, class _DifferenceType, class _OutputIterator1, class _OutputIterator2,
   753	          class _UnaryPredicate>
   754	std::pair<_OutputIterator1, _OutputIterator2>
   755	__simd_partition_copy(_InputIterator __first, _DifferenceType __n, _OutputIterator1 __out_true,
   756	                      _OutputIterator2 __out_false, _UnaryPredicate __pred) noexcept
   757	{
   758	    _DifferenceType __cnt_true = 0, __cnt_false = 0;
   759	
   760	    _PSTL_PRAGMA_SIMD
   761	    for (_DifferenceType __i = 0; __i < __n; ++__i)
   762	    {
   763	        _PSTL_PRAGMA_SIMD_ORDERED_MONOTONIC_2ARGS(__cnt_true : 1, __cnt_false : 1)
   764	        if (__pred(__first[__i]))
   765	        {
   766	            __out_true[__cnt_true] = __first[__i];
   767	            ++__cnt_true;
   768	        }
   769	        else
   770	        {
   771	            __out_false[__cnt_false] = __first[__i];
   772	            ++__cnt_false;
   773	        }
   774	    }
   775	    return std::make_pair(__out_true + __cnt_true, __out_false + __cnt_false);
   776	}
   777	
   778	template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
   779	_ForwardIterator1
   780	__simd_find_first_of(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first,
   781	                     _ForwardIterator2 __s_last, _BinaryPredicate __pred) noexcept
   782	{
   783	    typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferencType;
   784	
   785	    const _DifferencType __n1 = __last - __first;
   786	    const _DifferencType __n2 = __s_last - __s_first;
   787	    if (__n1 == 0 || __n2 == 0)
   788	    {
   789	        return __last; // according to the standard
   790	    }
   791	
   792	    // Common case
   793	    // If first sequence larger than second then we'll run simd_first with parameters of first sequence.
   794	    // Otherwise, vice versa.
   795	    if (__n1 < __n2)
   796	    {
   797	        for (; __first != __last; ++__first)
   798	        {
   799	            if (__unseq_backend::__simd_or(
   800	                    __s_first, __n2,
   801	                    __internal::__equal_value_by_pred<decltype(*__first), _BinaryPredicate>(*__first, __pred)))
   802	            {
   803	                return __first;
   804	            }
   805	        }
   806	    }
   807	    else
   808	    {
   809	        for (; __s_first != __s_last; ++__s_first)
   810	        {
   811	            const auto __result = __unseq_backend::__simd_first(
   812	                __first, _DifferencType(0), __n1, [__s_first, &__pred](_ForwardIterator1 __it, _DifferencType __i) {
   813	                    return __pred(__it[__i], *__s_first);
   814	                });
   815	            if (__result != __last)
   816	            {
   817	                return __result;
   818	            }
   819	        }
   820	    }
   821	    return __last;
   822	}
   823	
   824	template <class _RandomAccessIterator, class _DifferenceType, class _UnaryPredicate>
   825	_RandomAccessIterator
   826	__simd_remove_if(_RandomAccessIterator __first, _DifferenceType __n, _UnaryPredicate __pred) noexcept
   827	{
   828	    // find first element we need to remove
   829	    auto __current = __unseq_backend::__simd_first(
   830	        __first, _DifferenceType(0), __n,
   831	        [&__pred](_RandomAccessIterator __it, _DifferenceType __i) { return __pred(__it[__i]); });
   832	    __n -= __current - __first;
   833	
   834	    // if we have in sequence only one element that pred(__current[1]) != false we can exit the function
   835	    if (__n < 2)
   836	    {
   837	        return __current;
   838	    }
   839	
   840	    _DifferenceType __cnt = 0;
   841	    _PSTL_PRAGMA_SIMD
   842	    for (_DifferenceType __i = 1; __i < __n; ++__i)
   843	    {
   844	        _PSTL_PRAGMA_SIMD_ORDERED_MONOTONIC(__cnt : 1)
   845	        if (!__pred(__current[__i]))
   846	        {
   847	            __current[__cnt] = std::move(__current[__i]);
   848	            ++__cnt;
   849	        }
   850	    }
   851	    return __current + __cnt;
   852	}
   853	} // namespace __unseq_backend
   854	} // namespace __pstl
   855	
   856	#endif /* _PSTL_UNSEQ_BACKEND_SIMD_H */