P2663R2
Interleaved complex values support in std::simd

1. Motivation

ISO/IEC 19570:2018 (1) introduced data-parallel types to the C++ Extensions for Parallelism TS. [P1928R3] is proposing to make that a part of C++ IS. Intel supports the concept of a standard interface to SIMD instruction capabilities and we have made extra suggestions for other APIs and facilities for std::simd in document [P2638R0]. One of the extra features we suggested was the ability to work with interleaved complex values. It is now becoming common for processor instruction sets to include native support for these operations (e.g., Intel AVX512-FP16, ARM Neon) and we think that allowing std::simd to directly access these features is advantageous.

This document gives more details about the motivation for supporting complex-values, the different storage and implementation alternatives, and some suggestions for a suitable API.

2. Background

Complex-valued mathematics is widely used in scientific computing and many types of engineering, with applications including physical simulations, wireless signal processing, media processing, and much more besides. C++ already supports complex-valued operations using the std::complex template available in the <complex> header file and C supports complex values by using the _Complex keyword. C++ supports floating point elements, including std::float16 (C++23), float, double or long double, though in practice compilers permit integer complex values too. Such is the importance of interleaved complex values that some mainstream processor vendors now provide native hardware support for complex-value SIMD instructions (e.g., Intel AVX512-FP16, ARM Neon v8.3).

Any complex value is represented as a pair of values, one for the real component and one for the imaginary component. In C and C++ a complex value is a pair of two values of the appropriate data type, allocated to a single unit containing 2 elements which are stored contiguously. This is illustrated in the figure below. This storage layout is used in other languages too, allowing for easy data interchange between software written in different languages, or with comparable user-defined types:

When many complex values are stored together, such as in a C-style array, a C++ std::array or a C++ std::vector, then the real and imaginary elements are interleaved in memory:

Many applications, libraries, programming languages and interfaces between diverse software components will store data in this interleaved format, and it is treated as the default layout for blocks of complex-valued data. To improve the compute efficiency of this data format both Intel and ARM have introduced native hardware support to allow efficient SIMD operations to be performed in this data format without having to resort to reformatting the data into a more SIMD-amenable form. Where the underlying target hardware does not have native support for interleaved complex values it is straight-forward to synthesize a sequence of operations which give the same effect.

Given the popularity of interleaved complex-values as a data exchange and compute format we propose that std::simd should be able to directly represent this simd format in a form exemplified as:

std::simd<std::complex<float>, std::fixed_size<5>>
std::fixed_size_simd<std::complex<double>, 9>

In all these cases the fundamental element type will be a suitable complex value, and the individual components of each complex element will be worked on as a single unit, according to the rules of complex arithmetic where appropriate. This includes:

• All numeric operators (e.g., +, /, -, *) and their derivatives (e.g., assignment operators) will operate as per their standard complex type definition. For example, the multiply operator will invoke a complex multiply for each complex element.

• Any numeric operation will apply the operation on a per-element basis, generating a simd object of the same size as the input, but modifying the element type to be the appropriate return type. For example, when applied to a simd<complex<T>>:

  • exp, sin, log, tan, cos and so on will generate a simd<complex<T>>

  • abs or norm will generate a simd<T> (i.e., real-valued SIMD equivalent).

  Note that the mathematical behaviour will also be applied appropriately (e.g., if a real or imaginary component is a NaN, then the complete operation for a complex operation will also be NaN).

• The simd_mask associated with a simd<complex<T>> will have each individual mask bit refer to a complete complex element, not to sub-components of the complex elements. When the simd_mask is backed by a compact representation (e.g., AVX-512), then each individual bit will refer to a complete complex element. When the simd_mask is backed by an element mask (i.e., multiple bits filling a container of the same size as the simd element) then the size of each bit element will be twice the size of the underlying complex value type (e.g., a simd_mask<complex<_Float16>> would be equivalent to something like simd<uint32_t>, since sizeof(uint32_t) == 2 * sizeof(_Float16).

• Operations or functions which are invalid for complex values will be removed. This includes relational operators (e.g., <, <=, >, >=) and those derived from them such, as min or max.

• Any operation which moves or reorders elements will move entire complex values. For example, any sort of permute, resize, split, concat, insert, extract or indexing operation works on complete complex elements as though they are atomic units.

• Reduction operations apply at the level of complex values (this follows from the previous bullet), provided the mathematical operation is valid (e.g., reduce-max would not be available).

One of the aims of std::simd is to make it possible to write a generic code, which can use either a scalar type or a data-parallel type interchangeably. To this end, std::simd provides overloads of many of the standard functions which operate in data-parallel mode. The same should apply to a simd of complex values; it should be possible to write an algorithm which uses either std::complex<T> or simd<std::complex<T>> with only a type replacement, not with major API changes. To this end std::simd should include some member functions, such as real or imag, to mirror those found in std::complex.

Note that an alternative way to create parallel complex values is to allow std::complex to use simd elements, such as std::complex<simd<float>>. This storage layout is called separated storage and discussion of this format is outside the scope of this paper.

3. Overview of updates required to support std::complex simd elements

There are three ways in which std::simd needs to change to accommodate std::complex elements:

• Modify the definition of vectorizable types and the operations on them to allow for complex elements. These modifications are small in nature and don’t change the fundamental std::simd API.

• Add a small number of methods to std::simd to mimic those found in std::complex. These modifications allow a std:::simd<complex<T>> value to be easily inserted into source code by text or template replacement in place of a std::complex value without requiring a rewrite.

• Add a set of overloads and free functions to allow simd<complex<T>> to reflect the different behaviours of complex (e.g., sin, cos, exp, log).

Each of these points will now be discussed in more detail.

3.1. std::simd base modifications

In its current definition, std::simd allows the element type to be any cv-unqualified arithmetic type other than bool. The first modification is to extend the set of allowable element types to include any type which is valid for std::complex.

Any simd operation or function which relies only on an element being an atomic container which can be arbitrarily moved or duplicated as a single unit will continue to operate as expected. For example, all the following will work on simd<complex<T>> without modification:

• Constructors or copy_to/copy_from functions for loading and storing values to and from contiguous iterators

• Broadcast constructor

• Index operations

• Reordering operations, such as split, concat, permute, resize, insert and extract.

• Masking selection operations (using a mask to include or exclude values from an operation or copy).

simd_mask’s of complex values do not need to have any special behaviour since the mask is simply a collection of boolean values, and the underlying element type makes no difference.

Constructors, including generator functions, which work on atomic units (e.g., broadcasting constructor) will work without modification.

Numeric operations (binary, unary, and compound-assignment) are mostly covered by [P1928R3] remark:

A simd object initialized with the results of applying the indicated operator to lhs and rhs as a binary element-wise operation

In the case of complex values this has the practical effect of ensuring that operators will perform their complex operations without changing the definition of std::simd (e.g., operator* will perform complex-valued multiplication). Furthermore, another [P1928R3] remark:

Each of these operators shall not participate in overload resolution unless the indicated operator can be applied to objects of type value_type

ensures that operators which are not permitted for complex numbers (e.g., operator%, operator<<, operator&) will be removed from the overload set.

There are some operators and functions in std::simd where further protection needs to be introduced to ensure that the operator cannot be applied to complex elements since they do not support the required operations:

• Increment/decrement operators (++, --).

• operator~

• relational operators, such as <, <=, > and >=.

• horizontal min/max reductions

• min/max/clamp

Additional constraints will need to be added to those operators (e.g., relational operators will require their type to satisfy the std::totally_ordered constraint).

Note that some functions in std::simd are already excluded from the overload set through existing constraints (e.g., reductions).

3.2. Additional complex methods for std::simd

It is desirable for std::simd to be source- or template-replaceable with respect to its underlying element type. For example, given a simple code fragment which works with std::complex:

auto my_fn(auto cmplx_value)
{
    std::complex<float> rotator (0, 1);
    return (cmplx_value * rotator).real();
}

In this example the function will work with a std::complex<float> input. Ideally it should also work with an input of type simd<complex<float>>. For this to happen, firstly the operator* must work with a scalar value, and secondly it should be possible for the real() method to be invoked on a simd<complex<T>> value.

std::complex provides a number of member functions:

• Constructors

• operator= (assignment)

• operator+=, operator-=, operator*=, operator/=

• real

• imag

The assignment operator and the compound-assignment operators are already provided by std::simd, so no further action is required. The remaining member functions that are required are considered in the following sub-sections.

3.2.1. Constructors

Conversion and copy methods already exist in std::simd and can be used for complex SIMD values. An additional constructor is needed to match the std::complex constructor which can build a complex value from separate real and imaginary components: constructed from real and imaginary simd values.

template<typename U, typename UAbi>
requires is_complex_number<T>
constexpr simd(const simd<U, UAbi>& r, const simd<U, UAbi>& i = {})

This constructor is constrained so that it can only be used for SIMD values with complex elements (some suitable concept will be added to enforce this). Like its std::complex counterpart it can be used to build a complex value from real components only with insertion of zero imaginaries. This constructor can be used as in the following example:

fixed_size_simd, float, 8> reals = ...;
fixed_size_simd, float, 8> imaginaries = ...;

// Create a real-valued complex number (i.e., zero imaginaries)
fixed_size_simd<std::complex<float>, 8> realAsComplex (reals);

// Create a complex value from real and imaginary simd inputs
fixed_size_simd<std::complex<float>, 8> cmplx (reals, imaginaries);

3.2.2. Real/imag accessors

It should be possible to separately read or write the real and imaginary components. For example, given a simd of std::complex<float> values, the real components of the simd will be extracted as a value of type std::simd<float> instead. Similarly, given a simd<float> value those values can be inserted into the simd as the real components of each respective value.

The read accessors for std::complex come in two variants: a free function, and a member function. These would be defined in std::simd as follows:

// Free functions for accessing real/imaginary components
template <typename T> constexpr simd<T> real(const simd<complex<T>>&);
template <typename T> constexpr simd<T> imag(const simd<complex<T>>&);

// Member functions of std::simd for accessing real/imaginary components.
constexpr simd<T> std::simd<std::complex<T>>::real() const;
constexpr simd<T> std::simd<std::complex<T>>::imag() const;

The write accessors for std::complex are provided as member functions which allow the real and imaginary components of an existing complex value to be overwritten.

constexpr void std::simd<std::complex<T>>::real(const simd<T>& reals);
constexpr void std::simd<std::complex<T>>::imag(const simd<T>& reals);

The advantage of making real and imag members of std::simd is an API consistency between std::complex<T> and std::simd<std::complex<T>> for both getters and setters A disadvantage though is the real and imag seem too specific to be provided for std::simd Please see § 3.3.1 Alternative design for real and imag for more design considerations.

3.3. Additional free functions

The free functions for std::complex include numeric operators, such as +, -, * and /. These are already proposed in [P1928R3] and need not be considered further.

The remaining free functions which should be specialized for std::simd<complex<T>> include:

All of these functions should operate element-wise in the same way as their scalar counterparts. Note that although most of these functions take complex inputs and generate complex outputs, some of these functions generate real-valued outputs (e.g., abs returns the magnitude, which is real-valued), or accept a input which is real-valued (e.g., conj can accept a real-valued value and return a complex value).

3.3.1. Alternative design for real and imag

Instead of making real and imag member functions we could provide them only as free functions. Free function getters are already included in the proposal, but the setters would be removed as member functions and replaced by the following:

// Setters
template <typename T>
void real(simd<complex<T>>&, simd<T>);

template <typename T>
void imag(simd<complex<T>>&, simd<T>);

The member function getters would also be removed.

The advantage of that approach is it keeps std::complex specific functions outside of std::simd class. The disadvantage though is inconsistency with existing real and imag free functions for std::complex, which allow reading only. Please see § 3.2.2 Real/imag accessors for initial design.

We would like to hear the feedback of C++ standard committee what design looks more appropriate.

4. Implementation experience

Intel have written an example implementation of std::simd which includes the extensions to support interleaved complex values. We have been able to generate efficient code both on targets with native support (e.g., AVX512_FP16), and also on targets without native support which require synthesized code sequences.

5. Wording

TBD

6. Polls

6.1. Kona 2022 SG1 polls

Poll: After significant experience with the TS, we recommend that the next version (the TS version with improvements) of std::simd target the IS (C++26)

Poll: Future papers and future revisions of existing papers that target std::simd should go directly to LEWG. (We do not believe there are SG1 issues with std::simd today.)

7. Revision History

R1 => R2

• Add more content for proposal overview

• Rewrite to bikeshed

R0 => R1

• Add polls from Kona SG1 2022