1. Motivation
ISO/IEC 19570:2018 introduced data-parallel types to the C++ Extensions
for Parallelism TS. [P1915R0] asked for feedback on
in Parallelism TS 2. [P1928R4] aims to make that a part of C++ IS. Intel supports the concept of a
standard interface to SIMD instruction capabilities and has made further
suggestions for other APIs and facilities for
in document [P2638R0].
One of the extra features we suggested was the ability to be able to permute
elements across or within SIMD values. These operations are critical for
supporting formatting of data in preparation for other operations (e.g.,
transpose, strided operations, interleaving, and many more), but are relatively
poorly supported in the current
proposal. Many modern SIMD processors
include sophisticated support for permutation instructions so in this document we
shall propose a set of API functions which make those underlying instructions
accessible in a generic way.
In this document we shall start with some background into the current
proposal and extensions, describe the state of the art on other simd libraries,
and then describe a proposal for some new API functions to add to
.
2. Revision History
R7 => R8
-
Added parameter to
to be consistent with the API proposed forgather_from
in [P3299R0], and in particular, to allow element type conversions as part of the gather operation.load_from
R6 => R7
-
Changed default behaviour of out-of-range gather/scatter to UB to be consistent with [P3299R0].
R5 => R6
-
Removed section on named permutation generator functions. These will be put into their own paper.
-
Modified
andgather_from
to use ranges instead of iterators. Added more details about their behaviour and our implementation experience.scatter_to -
Removed section on using [DNMSO]. This will be revisited if that paper makes further progress.
R4 => R5
-
Renamed
andgather
toscatter
andgather_from
.scatter_to -
Made masking overloads for
andgather_from
part of the proposal rather than a design option.scatter_to -
Added Flags to
andgather_from
to control memory behaviour.scatter_to -
Added a design option discussing the merits of making
andgather_from
member functions.scatter_to -
Switched to using new names for functions like
andsimd_split
.simd_cat
R3 => R4
-
Renamed
/simd
tosimd_mask
/basic_simd
to match [P1928R4].basic_simd_mask -
Replaced deduced masks with nested typedefs (i.e., use
instead ofbasic_simd < T , ABI >:: mask_type
).basic_simd_mask < T , MaskABI > -
Replaced fixed_size types with their new counterparts (e.g.,
would now befixed_size_simd < T , 5 >
).simd < T , 5 > -
Removed design option to allow
andcompress
to take simd value parameters which are different sizes. This would always lead to some silent loss of data (either the mask or the values being compressed).expand -
Reordered mask parameter position (it now matches
,simd_select
, etc., by having the mask appear first).copy_to
R2 => R3
-
Added more detail about compiler’s ability to optimise a generated sequence
-
Made memory operations (gather/scatter) a class of its own, rather than trying to make them appear like special forms of the other types of permute.
-
Moved special indexes and generator size parameter description into main body of text rather than being a design option.
-
Added fill value parameters for compress and expand functions.
-
Improved wording and examples for memory permutations (gather/scatter).
-
Added wording for static permute, dynamic permute, mask permute and gather/scatter.
R1 => R2
-
Rewrite to bikeshed
-
Add more content for proposal overview.
R0 => R1
-
Add polls from Kona SG1 2022
3. Background
In ISO/IEC 19570:2018 there were only a few functions which could be used to
achieve any sort of element permutation across or within
values.
Those functions were relatively modest in scope and they built upon the ability
to split and concatenate simd values at compile-time. For example, a simd value
containing 5 elements could be split into two smaller pieces of sizes 2 and 3
respectively:
simd < float , 5 > x ; …const auto [ piece0 , piece1 ] = simd_split < 3 > ( x );
Those smaller pieces could be acted on using any of the
features, and
then later recombined using
, possibly in a different order or with
duplication:
The
and
functions can be used to achieve several permutation
effects, but they are unwieldy for anything complicated, and since they
are also compile-time they preclude any dynamic runtime permutation.
In [P2638R0] Intel suggested extra operations to insert and extract SIMD values to and from other SIMD containers:
const auto t = extract < 2 , 5 > ( v ); // Read out 3 SIMD values, starting from position 2 insert < 5 > ( v , t ); // Put the 3 previously read values back into the container at position 5
These are convenient, but they still don’t allow arbitrary or expressive permute operations.
Two suggestions were made in [P0918R1]: add an arbitrary compile-time shuffle function, and add a specific type of permutation called an interleave. The compile-time shuffle can be used as follows:
const auto p = shuffle < 3 , 4 , 1 , 1 , 2 , 3 > ( x ); // p::value_type will be the same as x::value_type // p::size will be 6
The indexes can be arbitrary, and therefore allow any duplication and reordering
of elements. The output
object will have the same number of elements as there are
supplied indexes, and the type of the SIMD output will be that of the input.
It is noted also in the shuffle API that this function can be applied
to
values too, and that shuffling across multiple SIMD values can be
achieved by first concatenating the values into a single larger SIMD:
In addition to the shuffle function, [P0918R1] also proposes a function called
interleave which accepts two SIMD values and interleaves respective elements
into a new SIMD value which is twice the size. For example, given inputs
and
, the output would be
.
Interleaving is a common operation and is often directly supported by processors
with explicit instructions (e.g., Intel’s
), so as in [P0918R1] and
also in other simd libraries there will be named functions which expose that
instruction. There will be other common permutation operations which also have
specialist hardware support and it is common for them to be exposed in named
functions also. For example, [Highway] provides
,
,
,
, and so on, which map efficiently to
underlying instructions. While this can ensure that good code is generated for
specific function, it does mean that:
-
the set of named functions can only include those features available on all potential targets
-
portability is reduced by exposing functions only on those targets which support them.
Neither of these is desirable, and in our suggestions below we provide an alternative.
4. Extending std :: simd
to support permutations
There are four classes of permutation which could be supported by
;
-
using compile-time computed indexes
-
using another SIMD as a dynamic index
-
using a bit-mask for selecting active elements
-
permuting memory (gather and scatter)
Modern processor instruction sets typically support all 4 of these classes of instruction. In the following sections we shall examine in more detail each of these classes and the potential APIs needed to expose those features to the user. We shall also examine what it means to permute memory, and whether named functions should be provided for common permutation patterns.
could be modified to allow permutations either by adding to the
base definition of
itself (specifically, to include a new
or
), or by introducing
overloaded free functions which extend
. We shall consider both
options below.
Note that a
is a special case of a type of SIMD and can therefore be
permuted in the same way as a conventional SIMD. In our discussions below we
assume that the permutations would apply equally to a
unless we note
otherwise.
4.1. Using compile-time computed indexes
The first proposal is to provide a
function which accepts a
compile-time function which is used to generate the indexes to use in the
permutation. This is a very powerful concept: firstly, it allows the task of
computing the indexes to be offloaded to the compiler using an index-generating
function, and secondly it works on
values of arbitrary size. It’s
definition would be something like:
template < std :: size_t SizeSelector = 0 , typename T , typename Abi , typename PermuteGenerator > constexpr simd < T , output - size > permute ( const basic_simd < T , Abi >& v , PermuteGenerator && fn )
It can be used as in the following example:
const auto dupEvenIndex = []( size_t idx ) -> size_t { return ( idx / 2 ) * 2 ; }; const auto de = permute ( values , dupEvenIndex );
Note that the permutation function maps from the index of each output element to
the index which should be used as the source for that position. So, for example,
the
function would map the output indexes
to the
source indexes
. This example permutation is common enough that it
has hardware support in Intel processors, and the compiler can map the above
function directly to the corresponding instruction:
By default, the permute function will generate as many elements in the output
simd as there were input values, but the output size can be explicitly specified
if it cannot be inferred or it needs to be modified. For example, the following
permute generates 4 values with a stride of 3 (i.e., indexes
).
4.1.1. Special generator indexes
The obvious index representation to return from each generator invocation is to
return an integral value in the range
. The compiler can enforce
at compile-time that the index is in the valid range and dynamic indexes would
not be permitted. In addition, there are three other types of index value which can be returned which give the compiler even more flexibility.
-
Negative indexes represent reverse indexes, which are intepreted as indexes taken from the end of the simd instead of the beginning. So -1 would be the last element, -2 the penultimate element, and so on.
-
The special index named
will instead a zero value at the indicated element position, rather than copying a value from the input simd.simd_zero_element -
The special index named
will indicate to the compiler that the element at the indicated position can be left in an uninitialized state. This gives an opportunity for more efficient code generation where the programmer knows that an element is unused.simd_uninit_element
Here is an example where zeros are inserted into the even-indexed output positions of a SIMD value while the odd-indexed values are copied directly from the input.
4.1.2. Generator function size argument
It can be useful to create libraries of common permutation generator functions
to handle common use cases, but such functions need to be able to know the
extent of the indexes that they are allowed to permute. The generator function
is allowed to accept an optional
argument giving
the size of the SIMD value being permuted. For example, the following generator
extracts elements of a SIMD starting at the half-way point:
auto topHalf = []( std :: integral auto idx , std :: size_t simd_size ) { return ( simd_size / 2 ) + idx ; };
4.1.3. Design option - more special constants
There are other possible special constants that could be given special status in the compile-time permute, including the ability to insert NaN, +ve infinity, -ve infinite, max_value, min_value, and so on. Should these be adopted too?
4.1.4. Implementation experience
In other simd or vector libraries which provide named specific permute
functions, the reason often given is that it allows specific hardware
instructions to be used to efficiently implement those permutes. For example,
Intel has the
instruction as noted above, so some libraries
provide functions in their API with names which reflect this (e.g., such a
function might be called
). The disadvantages are that it hinders
portability, and only allows access to the hardware features that the authors of
the library have chosen to expose.
Using the generator-based approach makes it easier to access a wide range of
underlying special purpose instructions, or to fall back to equivalent
instructions sequences where they are not available, but it is desirable that
such behavior should be efficient. To judge whether the generator-based
permutation API was efficient and useful we implemented the extensions in the
Intel
library and looked at the performance of different compile-time
patterns and their generated instruction sequences. We found that GCC and LLVM
were able to determine the correct hardware instructions to use for a variety of
common permutation patterns, and in some cases the compiler was even able to use
the side-effects of other instructions to effect permutations in ways that human
programmers had overlooked. In all cases, where the pattern was too complicated
to map to native hardware features the compiler fell back to using general
purpose permutation patterns, such as Intel’s
family of
instructions.
The generator function works by creating a list of compile-time constants which are used to perform the permutation. Because the list is compile-time it can be generated using completely arbitrary (and potentially very inefficient) code, but the outcome will always be a list of constants. Therefore the compiler’s ability to generate a permutation is dependent upon how well it can convert a list of constants into a permutation, not how well the programmer is at writing clear permute functions.
As a small illustration of the compiler’s ability, the following table shows some compile-time function permute calls and the code that the LLVM 14.0.0 compiler has generated for each:
Permute call | Purpose | Output from clang 14.0.0 |
| Duplicate even elements |
|
| Swap even/odd elements in each pair (complex-valued IQ swap) |
|
| Extract upper half of a 16-element vector. Note that the instruction sequence accepts a zmm input and returns a ymm output. |
|
In each case the compiler has accepted the compile-time index constants and converted them into an instruction which efficiently implements the desired permutation. We can safely leave the compiler to determine the best instruction from an arbitrary compile-time function.
4.2. Using another SIMD as the dynamic index
The second proposal for the permute API is to allow the required indexes to be passed in using a second SIMD value containing the run-time indexes:
template < typename T , typename AbiT , std :: integral Idx , typename AbiIdx > constexpr simd < T , basic_simd < Idx , AbiIdx >:: size () > permute ( const basic_simd < T , AbiT >& v , const basic_simd < Idx , AbiIdx >& indexes )
This can be used as in the following example:
simd < unsigned , 8 > indexes = getIndexes (); simd < float , 5 > values = getValues (); ... const auto result = permute ( values , indexes ); // result::value_type is float // result::size is 8
The permute function will return a new SIMD value which has the same element type as the input value being permuted, and the same number of elements as the indexing SIMD (i.e., float and 8 in the example above). The permute may duplicate or arbitrarily reorder the values. The index values must be of integral type, with no implicit conversions from other types permitted. The behavior is undefined if any index is outside the valid index range. Dynamic permutes across multiple input values are handled by concatenating the input values together. The indexes in the selector will only be treated as indexes, and will never have special properties as described above (e.g., no zero element selection)
In addition to the function called permute, a subscript operator will also be provided:
template < std :: integral Idx , typename AbiIdx > constexpr simd < T , basic_simd < Idx , AbiIdx >:: size () > simd :: operator []( const basic_simd < Idx , AbiIdx > & indexes ) const ;
Here is an example of how this could be used:
simd < int , 8 > indexes = getIndexes (); simd < float , 5 > values = getValues (); ... const auto result = values [ indexes ]; // result::value_type is float // result::size is 8
4.2.1. Design option - C++23 multi-index subscript
Sometimes the subscripts to use in a permute might be known at compile time, but to use them in a permutation requires them to be put into an index simd first:
constexpr simd < int > indexes = { 3 , 6 , 1 , 6 }; // Note - assumes initialiser list from P2876R0. auto output = values [ indexes ];
In C++23 multi-subscript operator was introduced and this could be used to allow a more compact representation:
auto output = values [ 3 , 6 , 1 , 6 ]; // output::value_type is values::value_type // output::size is 4
It would be good if it could also appear on the left-hand-side;
output_simd [ 2 , 5 , 6 ] = x ; // Overwrite selected elements with a single value.
Should non-constant indexes be allowed too? Our experience with GCC and LLVM suggests that work would be needed on their code generation for non-constant variable indexes to be improved though, as they are both currently poor at this.
Should
be reserved for slicing or sub-ranges?
4.2.2. Implementation experience
We implemented the runtime-indexed permute API in Intel’s example
implementation. Small index operations (e.g., indexing one native sized simd by
another) were mapped directly onto the underlying native instruction and so were
as efficient as calling an intrinsic. More complicated cases for permutation,
such as where either the index or data SIMD parameters were bigger than a
native register are also handled with comparable efficiency to hand-written
intrinsic code.
4.3. Permutation using simd masks (compress/expand)
A third variant of permutation is where a
is used as a proxy for an
index sequence instead. The presence or absence of an element in the
will cause the element to be used or not. The following diagrams illustrate this:
On the left the values in the SIMD are compressed; only those elements which
have their respective
element set will be copied into the next
available space in the output SIMD. Their relative order will be maintained, and
the selected elements will be stored contiguously in the output. The output
value will have the same number of elements as the input value, with any unused
elements being left in a valid but unspecified state. The behavior of the
function is similar to
, although other simd libraries may
call this function compression or compaction instead. The expansion function on
the right of the diagram has the opposite effect, copying values from a
contiguous region to potentially non-contiguous positions indicated by a mask
bit. The two functions have prototypes as follows:
template < typename T , typename Abi > constexpr basic_simd < T , Abi > compress ( const typename basic_simd < T , Abi >:: mask_type & mask , const basic_simd < T , Abi >& value ); template < typename T , typename Abi > constexpr basic_simd < T , Abi > compress ( const typename basic_simd < T , Abi >:: mask_type & mask , const basic_simd < T , Abi >& value , T fill_value ); template < typename T , typename Abi > constexpr basic_simd < T , Abi > expand ( const typename basic_simd < T , Abi >:: mask_type & mask , const basic_simd < T , Abi >& value , const simd < T , Abi >& original );
In both functions all
or
values must have the
same
and
.
A compression operation is typically used to throw away unwanted values (i.e., values which do not satisfy the mask condition). Unwanted positions in the output will be left unspecified, unless the user supplies a third parameter specifying the value which should be used to fill those unwanted positions.
An expansion operation is typically used to overwrite selected elements of some existing SIMD value with new values taken from the contiguous beginning of another SIMD value. The expansion operation therefore has a slightly different meaning for its fill value.
4.3.1. Unused value element initialisation
In the design shown above the
function comes in two variants, the first of which leaves unused values in the output in an unitialised but valid state, and the second function provides a default value to use for the initialisation. Is is worth looking at this in more detail to understand why there isn’t a single function which always initializes its unused elements. Consider a compression operation:
simd < int , 6 > values = ...; simd_mask < int , 6 > mask = ...; auto compressed = compress ( values , mask ); // compressed::value_type is int // compressed::size is 6
The output value has the same size as the mask selector, but the actual mask bits won’t be known until run-time. This raises the question of what values should be put into the unused output elements.
The current proposal would leave the unused elements in a valid but unspecified
state. This is comparable to functions like
and
. The alternative is for the compress function to leave
the unused values in a value-initialized state.
The advantage of an unspecified state is that the code doesn’t need to make a special effort to insert values which might not be used anyway, but has the disadvantage that the unspecified state might catch out the unwary user. Using a value initialized state helps the unwary user by providing a default state which is sane and repeatable, but may come with a performance cost.
Intel have an example implementation of
, and our experience with
that demonstrates that when native support is available (e.g., with AVX-512 ISA)
it makes no difference to performance whether the unused values are initialising
to specific value or left uninitialized, since the instruction itself inserts
the values into unused positions as an integrated part of its operation.
However, a synthesized code sequence is more expensive when setting the elements
to a specific value since it is necessary to also compute the population count
of the mask, turn that into a mask and then arrange for the unused values to be
overwritten with something else using that mask.
Given that the compress function is essentially only extracting valid values from the input SIMD and discarding the others, and that there is a potential performance penalty that comes from initialising unused values, then we think that the default should be to leave unused elements in unspecified states.
Related to this is what to do when a programmer does want to initialize unused
values to a known value. With the proposed interface the programmer would be
required to compute a new partial mask from their original selection mask (i.e.,
compute the population count of the original mask, and then turn that into a
mask of the lower elements), and then use that to conditionally blend in their
desired value. This can be inefficient, and for targets like Intel AVX-512, it
doesn’t exploit the hardware’s ability to automatically insert a value anyway.
For this reason we propose that an overload of
is provided that
accepts a third parameter giving a value to insert into unused elements:
template < typename T , typename Abi > basic_simd < T , Abi > compress ( const basic_simd < T , Abi >& value , const typename basic_simd < T , Abi >:: mask_type & mask , T default_value );
This makes the programmer’s intent explicit in the code, it simplifies the code, and it allows those targets which support automatic insertion of a value to efficiently make use of that feature.
4.3.2. Implementation experience
In Intel’s example implementation of
we have implemented
permute-by-mask. On modern processors which support AVX-512 or VBMI2 we found
the mapping from
or
to be efficient, and allowed
a natural representation of this compaction operation where needed. Implementing
permute-by-mask on older processors which lacked native support was a little
harder, but could still be implemented as efficiently as an experienced
programmer could achieve using hand-written intrinsics. Determining the most
efficient implementation under all conditions however showed that less experienced
programmers would struggle to implement this feature. Therefore, making this
feature available in
itself removed any non-portable calls to native
compression/expansion instructions, and also allowed the library implementer to
use efficient sequences for different scenarios.
4.4. Memory-based permutes
When permuting values which are stored in memory, the operations are normally called gather (reading data from memory), or scatter (writing values to memory). We propose that four functions are provided which implement these two operations, each provided in masked and unmasked forms.
4.4.1. Range-based gather function
The gather function is defined as follows:
template < typename ReturnType = void , typename Range , std :: integral Idx , typename AbiIdx , typename ... Flags > requires std :: ranges :: sized_range < Range > && std :: ranges :: contiguous_range < Range > constexpr ( see later ) gather_from ( const Range && in , const simd < Idx , AbiIdx >& indexes , simd_flags < Flags ... > f = {}); template < typename ReturnType = void , typename Range , std :: integral Idx , typename AbiIdx , typename ... Flags > constexpr ( see later ) gather_from ( Range && in , const typename simd < Idx , AbiIdx >:: mask_type & mask , const simd < Idx , AbiIdx >& indexes , simd_flags < Flags ... > f = {});
The gather operation loads values from within a constrained contiguous finite
range. By default it returns a new
whose type is deduced from the input
parameters: it will have the same element type as the input range elements and
the same number of elements as the supplied index simd. Alternatively, the user
may provide an template parameter specifying the return type, either as a
or as a scalar type. That enables the user to perform a conversion
as part of the gather operation. The return template parameter matches the
proposal for
in [P3299R0].
If an index is supplied which is outside the valid input range then we have two
options for how the implementation should behave. The first option is to make
this undefined behaviour, while the second option is to make the gather safe by
replacing invalid indexes by some default value. The extra code introduced in
the second option may reduce performance. In common with our reasoning in [P3299R0] (Range constuctors), we think that
is a low-level
library which should place performance above safety, and we propose that gather
operations will give undefined behaviour if an invalid index is used.
In the masked overload the mask’s parameter type matches that of the supplied indexes since it is effectively turning indexes on and off. Any values which are unmasked will be value initialized in the result.
Both overloads accept a flags parameter which will mirror any control over the
memory operations provided by
, and the memory-loading constructors
(e.g., cache bypass, prefetching). In addition, the flag called
introduced in [P3299R0] can also be used, and will prevent
any out-of-bounds accesses to the input range, and will insert a
default-initialised value for the corresponding element.
The default
function could be used as follows:
int array [ 1024 ]; simd < unsigned > indexes = GetIndexes (); ... const auto r1 = gather_from ( array , indexes );
By specifying a return type parameter a conversion can be implemented as part of the gather:
int array [ 1024 ]; simd < unsigned > indexes = GetIndexes (); ... const auto r1 = gather_from < float > ( array , indexes );
Or the return type can be a compelte simd type which specifies both the element type and the required ABI:
int array [ 1024 ]; simd < unsigned > indexes = GetIndexes (); using OutType = simd < float , simd < unsigned >:: size > ; ... const auto r1 = gather_from < OutType > ( array , indexes );
4.4.2. Range-based scatter function
The scatter function is defined as:
template < typename Range , typename T , typename TAbi , std :: integral Idx , typename IdxAbi , typename ... Flags > constexpr void scatter_to ( const simd < T , TAbi >& values , Range && out , const simd < Idx , IdxAbi >& indexes , simd_flags < Flags ... > f = {}); template < std :: contiguous_iterator Iter , typename T , typename TAbi , std :: integral Idx , typename IdxAbi , typename ... Flags > constexpr void scatter_to ( const simd < T , TAbi >& values , Range && out , const typename simd < Idx , AbiIdx >:: mask_type & mask , const simd < Idx , IdxAbi >& indexes , simd_flags < Flags ... > f = {});
The scatter function will write each input value to the respective indexed position of the output range. The output range must be contiguous and finite. If an index falls outside the valid input range then this is Undefined Behaviour, and the programmer is responsible for ensuring that the indexes are valid.
In the masked overload, the mask parameter type has been chosen to match the
index type to be consistent with the
function. The values
written to memory will be of the range’s value type, with a conversion from the
input type taking place if they are different. The conversion to the range value type
must be value preserving, unless
is passed as an option.
The
function should accept any flags similar to those found in
, allowing control over effects such memory caching, write-through, and
so on. An extra flag called
will be introduced to provide
dynamic range checking of the indexes to suppress writes outside the valid
range. The use of this flag will generate extra runtime code which may degrade
execution performance, but will improve memory safety.
The memory writes performed by
are unsequenced. The programmer
cannot rely on the values being written to the output range in any order.
The scatter could be used as follows:
int array [ 1024 ]; simd < int > values = ...; simd < int > indexes = ...; simd < int >:: mask_type mask = ...; ... scatter_to ( values , array , mask , indexes );
4.4.3. A note on iterator-based gather and scatter
In early revisions of this paper there was a proposal to make
and
accept contiguous iterators to indicate where to gather and scatter
to memory. Although these functions directly mirrored common hardware
instructions, which also accept a pointer and a vector of indexes, the functions
are potentially very dangerous. Given a pointer, and a large enough index
element type, any part of the execution space can be read or written, with
writes being particularly catastrophic if mis-handled. In common with the
direction being taken in [P3299R0] to make other memory-related operations
range-safe, we have replaced the iterator-based gather and scatter operations
with range-based operations.
If a programmer only has an iterator referencing the region from which to gather or scatter, then they must convert that iterator to a suitable range. For example, if there exists a pointer to a lookup table, and it is known that the lookup table can only contain
entries, then the programmer could implement that as follows:
const uint16_t * ptr = ...; const simd < unsigned > indexes = ...; ... auto v = gather_from ( std :: span ( ptr , N ), indexes );
Using a raw iterator and converting it to a span or range should be only a
stop-gap measure, and ideally the code should be refactored to allow the
appropriate input range to be used directly. Therefore to encourage good use of
ranges no iterator-based overloads for
and
are
provided.
4.4.4. Implementation experience
Intel’s example implementation of
has been modified to include both
iterator-based and range-based versions of
and
, with
and without runtime checking. The code has been evaluated for performance.
Our benchmarking showed that the addition of range checking, value-initialization, and write suppression for invalid indexes did not significantly degrade execution performance on modern machines running AVX-512. In fact, we found that the choice of index values (i.e., what happens if the indexes are in the same cache line, adjacent cache lines, consecutive, reversed, etc.) had a much greater impact on execution performance than whether the range check was present or not.
When rewriting older iterator-based code in terms of the range-based API, we could implement the code as follows:
const uint16_t * ptr = ...; const simd < unsigned > indexes = ...; // Original iterator-based API auto v_old = gather_from ( ptr , indexes ); // New API auto v_new = gather_from ( std :: span ( ptr , N ), indexes );
The generated code for these two uses is identical, so the performance levels of the original API can be achieved while using an API which encourages the programmer to think about the ranges that they are using for scatter and gather.
4.4.5. A note on proposing that gather_from
and scatter_to
should be member functions
At Varna 2023 there was a suggestion to make
and
become member functions. Reasons for this included:
-
to match
andcopy_from
, which are the closest equivalents to these memory operations that already exist, and which are already members (though they are the only ones).copy_to -
to allow
to perform a conversion from the iterator type to the object’s own element type. Note thatgather_from
already accepts an iterator of one type and a value simd of another element type, so scatter-conversion is already supported.scatter_to -
to allow a masked
to partially overwrite an existing simd value (i.e., maskedgather_from
currently has no way of specifying what value should be used for unused elements and uses value initialization).gather_from
Since that meeting [P3299R0] (range-based constructors) has been suggested. In
particular non-member
and
replace member
and
respectively, with improved memory safety, and with conversion capabilities.
LEWG gave strong direction to pursue the ideas of [P3299R0] and we have
incorporated the mechanisms into this proposal, and we will abandon any further
exploration of gather/scatter member functions.
5. Summary
In this document we have described four styles of interface for handling permutes: compile-time generated, simd-indexed, mask-indexed, and memory based. In combination, these interfaces allow all types of common permute to be expressed in a way which is clean, concise, and efficient for the compiler to implement.
6. Wording
6.1. Modify [simd.flags]
Add the following:
inline constexpr simd_flags simd_flag_checked {}; inline constexpr simd_flags simd_flag_default_init {};
Note: simd_flag_default_init is also specified in [P3299R0].
6.2. Add new section [simd.static_permute]
�
static permute [simd.static_permute]
simd constexpr static int simd_zero_element = /* Implementation defined */ ; constexpr static int simd_uninit_element = /* Implementation defined */ ; Constraints:
These cannot take values which could be mistaken for valid index values, so they must be outside the range
.
[ 0. . max - impl - size ) Remarks:
Special constants can be returned by the permutation generator function to indicate special behavior of that element.
// Free function to generate compile-time permute of simd template < std :: size_t SizeSelector = 0 , typename T , typename Abi , typename PermuteGenerator > constexpr simd < T , output - size > permute ( const basic_simd < T , Abi >& v , PermuteGenerator && fn ) // Free function to generate compile-time permute of simd_mask template < std :: size_t SizeSelector = 0 , typename T , typename Abi , typename PermuteGenerator > constexpr simd_mask < T , output - size > permute ( const basic_simd_mask < T , Abi >& v , PermuteGenerator && fn ) Constraints:
is
std :: integral < std :: invoke_result < PermuteGenerator , std :: size_t > || std :: integral < std :: invoke_result < PermuteGenerator , std :: size_t , std :: size_t > true
.Returns:
A
or
basic_simd object of size
basic_simd_mask (see below) where the ith element is initialized as follows. For each output index
output - size the result of the expression
[ 0. . output - size ) , or
simd ( gen ( integral_constant < size_t , i > ())) is computed. The result index
simd ( gen ( integral_constant < size_t , i > (), integral_constant < size_t , output - size )) is used to select a value from
x as follows:
v
A value in the range
will use
[ 0. . size ) .
v [ x ] The value
will use
simd_zero_element .
T () The value
will use a valid but unspecified value of the compiler’s choosing.
simd_uninit_element Any other value is undefined.
The
will be the same as
output - size if
v . size is zero, otherwise it will be set to
SizeSelector .
SizeSelector Remarks:
The calls to the generator are unsequenced with respect to each other.
6.3. Add new section [simd.dynamic_permute]
�dynamic permute [simd.dynamic_permute]
simd // Free function to permute simd by dynamic index template < typename T , typename AbiT , std :: integral Idx , typename AbiIdx > constexpr simd < T , basic_simd < Idx , AbiIdx >:: size () > permute ( const basic_simd < T , AbiT >& v , const basic_simd < Idx , AbiIdx >& indexes ) // Free function to permute simd mask by dynamic index template < typename T , typename AbiT , std :: integral Idx , typename AbiIdx > constexpr simd_mask < T , basic_simd_mask < Idx , AbiIdx >:: size () > permute ( const basic_simd_mask < T , AbiT >& v , const basic_simd_mask < Idx , AbiIdx >& indexes ) // Member function to permute simd by dynamic index using subscript operator template < std :: integral Idx , typename AbiIdx > constexpr simd < T , basic_simd < Idx , AbiIdx >:: size () > basic_simd :: operator []( const basic_simd < Idx , AbiIdx >& indexes ) // Member function to permute a simd mask by dynamic index using subscript operator template < std :: integral Idx , typename AbiIdx > constexpr simd_mask < T , basic_simd < Idx , AbiIdx >:: size () > basic_simd_mask :: operator []( const basic_simd < Idx , AbiIdx >& indexes ) Preconditions:
All values in
must be in the range
indexes .
[ 0. . size ) All index elements must be integral types.
Returns:
A
or
basic_simd object of size
basic_simd_mask where the ith element is a copy of
simd_size_v < Idx , AbiIdx > if i is in the range
v [ indexes [ i ]] or undefined otherwise.
[ 0. . v . size )
6.4. Add new section [simd.mask_permute]
�mask permute [simd.mask_permute]
simd // Free function to compress simd values using a mask selector ( 1 ) template < typename T , typename Abi > constexpr basic_simd < T , Abi > compress ( const basic_simd < T , Abi >:: mask_type & selector , const basic_simd < T , Abi >& v ) // Free function to compress simd_mask elements using a mask selector ( 2 ) template < typename T , typename Abi > constexpr basic_simd_mask < T , Abi > compress ( const basic_simd_mask < T , Abi >& selector , const basic_simd_mask < T , Abi >& v ) // Free function to compress simd values using a mask selector // with a fill value for unused elements ( 3 ) template < typename T , typename Abi > constexpr basic_simd < T , Abi > compress ( const basic_simd_mask < T , Abi >:: mask_type & selector , const basic_simd < T , Abi >& v , T fill_value ) // Free function to compress simd_mask elements using a mask selector // with a fill value for unused elements ( 4 ) template < typename T , typename Abi > constexpr basic_simd_mask < T , Abi > compress ( const basic_simd_mask < T , Abi >& selector , const basic_simd_mask < T , Abi >& v , T fill_value ) Returns:
A
or
basic_simd object in which the first
basic_simd_mask values are copies of those elements in
[ 0. . reduce_count ( selector )) whose corresponding mask element is set. The relative order of the values from
v is unchanged.
v For (1) and (2) output values in the range
will be valid but unspecified values of type T.
[ reduce_count ( selector )... v . size )) For (3) and (4) output values in the range
will be copies of
[ reduce_count ( selector )... v . size )) .
fill_value Remarks:
The
operation is used to throw away unwanted values, so the
compress is used to put sane values into unused positions. This is in contrast to
fill_value where the operation is typically used to overwrite selected elements of an existing SIMD value and so unused positions come from another SIMD value.
expand // Free function to expand simd values using a mask selector template < typename T , typename Abi > constexpr basic_simd < T , Abi > expand ( const typename basic_simd < T , Abi >:: mask_type & selector , const basic_simd < T , Abi >& v , const basic_simd < T , Abi >& original = ()) // Free function to expand simd_mask elements using a mask selector template < typename T , typename Abi > constexpr basic_simd_mask < T , Abi > expand ( const basic_simd < T , Abi >:: mask_type & selector , const basic_simd_mask < T , Abi >& v , const basic_simd < T , Abi >& original = ()) Returns:
A
or
basic_simd object in which the first
basic_simd_mask values are copied to those output elements whose respective selector elements are set. Any output elements whose respective selector elements are not set will have the corresponding element from
[ 0. . reduce_count ( selector )) copied into that position.
original Remarks:
is often used to overwrite selected positions in an existing SIMD value, so these functions take a complete SIMD value as the source from which to take unused mask selector elements. This is in contrast to
expand where the compression operation is effectively throwing away unwanted elements and the
compress is being used to put sane values into unused positions.
fill_value
6.5. Add new section [simd.memory_permute]
�memory permute [simd.memory_permute]
simd template < typename ReturnType = void , typename GatherRange , std :: integral Idx , typename Abi , typename ... Flags > constexpr ( see below ) gather_from ( GatherRange && in , const simd < Idx , Abi >& indexes , simd_flags < Flags ... > f = {}); template < typename ReturnType = void , typename GatherRange , std :: integral Idx , typename Abi , typename ... Flags > constexpr ( see below ) gather_from ( GatherRange && in , const typename simd < Idx , AbiIdx >:: mask_type & mask , const simd < Idx , Abi >& indexes , simd_flags < Flags ... > f = {}); Constraints:
is
std :: integral < Idx > true
.
is
std :: ranges :: contiguous_range < GatherRange > true
.
is
std :: ranges :: sized_range < GatherRange > true
.If the ReturnType parameter is not defaulted then it must be a
whose size is
basic_simd , or it must be a vectorizable scalar type.
basic_simd < Idx , AbiIdx >:: size Mandates
If the template parameter pack
does not contain the type identifying
Flags then the conversion from
simd_flag_convert to the element type of the return value is value-preserving.
range__value_t < GatherRange > Returns:
The return type will vary, depending upon the first template parameter supplied at a call site:
If no parameter is supplied then an object of type
will be returned.
simd < std :: ranges :: range_value_t < GatherRange > , std :: basic_simd < Idx , AbiIdx >:: size > If a
is supplied then a value of that
basic_simd type will be returned.
basic_simd If a scalar vectorizable type is supplied then a value of type
will be returned.
rebind_simd_t < ReturnType , basic_simd < Idx , AbiIdx > For all possible
return types (deduced from the first template parameter) the ith element of the return value will be a copy of the value
basic_simd , or if the mask’s respective bit is
in [ indexes [ i ]] false
then return a value initialized element. Iffalls outside the supplied range and
indexes [ i ] parameter pack contains the type identifying
Flags ... then a value initialized element will be returned, otherwise, the behavior is undefined.
simd_flag_default_init template < typename T , typename TAbi , typename ScatterRange , std :: integral Idx , typename IdxAbi , typename ... Flags > constexpr void scatter_to ( const simd < T , TAbi >& value , ScatterRange && out , const simd < Idx , IdxAbi >& indexes , simd_flags f = {}); template < typename T , typename TAbi , typename ScatterRange , std :: integral Idx , typename IdxAbi , typename ... Flags > constexpr void scatter_to ( const simd < T , TAbi >& value , ScatterRange && out , const typename simd < Idx , AbiIdx >:: mask_type & mask , const simd < Idx , IdxAbi >& indexes , simd_flags < Flags ... > f = {}); Constraints:
is
std :: integral < Idx > true
.
is
simd_size_v < simd < T , TAbi >> == simd_size_v < simd < Idx , IdxAbi >> true
.
is
std :: ranges :: contiguous_range < ScatterRange > true
.
is
std :: ranges :: sized_range < ScatterRange > true
.Preconditions:
If the template parameter pack
does not contain the type identifying
Flags then all indexes are contained within the given range.
simd_flag_checked Mandates: If the template parameter pack Flags does not contain the type identifying
, then the conversion from
simd_flag_convert to
T is value-preserving.
std :: ranges :: range_value_t < It > Effects:
For all i in the range
the value at
[ 0. . simd_size_v < Idx , IdxAbi > ) will be a copy of
out [ indexes [ i ]] converted from
value [ i ] to the range value type, unless a mask is provided and
T is
mask [ i ] false
in which case no memory write for that element will occur. If an index falls outside the valid range and andparameter pack contains the type identifying
Flags ... then no memory write for that element will occur. Otherwise, the behavior is undefined.
simd_flag_checked Remarks:
7. Acknowledgments
Thank you to Matthias Kretz for useful offline discussions regarding the behaviour and contents of the permutation API.
8. Polls
8.1. Varna Meeting - 16th May 2023
POLL: SIMD permute should not support negative indices
SF | F | N | A | SA |
---|---|---|---|---|
2 | 10 | 0 | 0 | 0 |
POLL: SIMD permute should always pass both an index and a size to the invocable.
SF | F | N | A | SA |
---|---|---|---|---|
2 | 2 | 6 | 3 | 1 |
POLL: Rename
to
and
to
and make them member functions that do conversion and take
(like
/
).
SF | F | N | A | SA |
---|---|---|---|---|
6 | 8 | 1 | 0 | 0 |
8.2. Telecon Meeting - 2nd May 2023
Poll: We should promise more committee time to pursuing P2664R2 (Proposal to extend
with permutation API), knowing that our time is scarce and this will leave less time for other work.
SF | F | N | A | SA |
---|---|---|---|---|
6 | 4 | 1 | 0 | 0 |
Poll: Pursue extended indices in the permute callable (e.g., negative indices, special values for zero element, etc.).
SF | F | N | A | SA |
---|---|---|---|---|
5 | 4 | 1 | 0 | 0 |
Poll: Pursue multi-index subscripting for dynamic permutations in the initial revision.
SF | F | N | A | SA |
---|---|---|---|---|
0 | 1 | 8 | 2 | 0 |
Poll : Pursue
subscripting for dynamic permutations in the initial revision.
SF | F | N | A | SA |
---|---|---|---|---|
1 | 6 | 2 | 0 | 0 |
Poll: Pursue
subscripting for dynamic expand (
) in the initial revision.
SF | F | N | A | SA |
---|---|---|---|---|
0 | 0 | 7 | 2 | 0 |