Feedback for P3440 (simd_mask::n_elements)

[danieltowner]

https://wiki.edg.com/bin/view/Wg21sofia2025/P344020

Name

n_elements might not be the best name. Alternative suggestions:

• first_n_elements
• set_first_n_elements
• set_mask_n
• set_first_n
• mask_of_n
• mask_with_n_set
• first_n_bits_of_mask
• first_n_of_mask
• mask_with_n_set
• (please add...)

Free function

Should it be a free function so that it can be simd-generic? It would need to take a template:

auto m0 = simd::n_elements<float>(x);

auto m1 = simd::n_elements<simd_mask<float>>(x);

Preconditions

Currently:

N <= 0 gives empty mask.
N >= size() gives full mask

Should preconditions be added to some of the possibilities?

Negative - Doesn't make sense for N to ever be negative (unless you do something tricksy like making it mean the last N, but that is horrible), so this seems reasonable.

Zero - this might indicate an error since the program should never be processing nothing and should probably have detected that and done it differently.

N == size() - A bit like Zero, this might indicate that the program has an error since it should have handled a full block differently (and using a mask can be expensive). But a common pattern in targets with cheap masks is to have a loop which processes all blocks in the same way, even if they are only partial:

for (auto b : blocks)
  process(data, n_elements(b.size())

// No special remainder handling - the loop processes full blocks or partial blocks with the same loop above.

N>size() - It might indicate an error, but when processing blocks from a larger data it would allow you to track how many remaining items are left:

for (int i=0; i<data.size(); ++i)
{
  block = spanX.subspan(i); // get last part of span
  s = partial_load<SIMD>(block); // Don't care if the block's subspan is too big.
  nm = simd::n_elements<SIMD::mask>(data.size() - i); // Maybe we shouldn't care if N is too big here either?
}

My preference is for N>0 only, which allows N>=size() for the possible coding styles above. I might be persuaded to also add N<=size() though, but not N < size().

[danieltowner]

https://isocpp.org/files/papers/D3440R2.html

Updated to match names of Working Draft, and added discussion on preconditions.

@mattkretz I think it would be easy to add a simd-generic version, but I can't convince myself that it is needed. Any time that n elements of a larger mask are needed, the code is processing blocks anyway, where it doesn't seem to make sense to want to have scalar equivalent of n_elements. Or if you have a type M which is actually a scalar, then any code which is calling n_elements<M> is likely calling M::size() too, which isn't simd-generic either. For now the options are to 1) ignore the possibility of simd-generic altogether and leave as a named constructor, or 2) make it a free-function which takes a simd::mask template so that we have the option of adding simd-generic variant later if we need it. Do you have any useful case where simd-generic version is already needed?

[mattkretz]

template <typename T>
void made_up(std::span<float> data) {
  constexpr int N = simd_generic_size_v<T>; 
  auto it = data.begin();
  auto next = it + N;
  T product = T(1);
  while (next <= data.end()) {
    T v = simd::unchecked_load<T>(it, next); // yes, load isn't simd-generic yet
    product *= v;
    it = next;
    next += N;
  }
  if (it != data.end()) {
    T v = simd::partial_load<T>(it, next);
    product *= simd::select(n_elements<T>(std::distance(it, next)), v, T(1));
  }
  return simd::reduce(product, std::multiplies<>()); // Olaf's paper makes reduce simd-generic
}

Note that n_elements<typename T::mask_type>(...) would make it much harder to use in simd-generic code. So maybe it should accept any data-parallel type and infer the mask type automatically from basic_vec specializations (and bool from vectorizable types).

[mattkretz]

To me the question of preconditions boils down to "What is an erroneous use of n_elements?". The strictest answer could be that asking for negative, zero, full-size, or more is an error in the program. E.g. in the made_up function above, std::distance(it, next) is never 0 or N by construction. That's the intent of the code and it could be helpful to diagnose if that assumption somehow gets broken.

From the implementation side I can make use of these preconditions, so there's also the performance argument.

[mattkretz]

Your example

for (int i=0; i<data.size(); ++i)
{
  block = spanX.subspan(i); // get last part of span
  s = partial_load<SIMD>(block); // Don't care if the block's subspan is too big.
  nm = simd::n_elements<SIMD::mask>(data.size() - i); // Maybe we shouldn't care if N is too big here either?
}

shouldn't pass code review IMHO. If you use partial_load like this you don't care about performance. If you don't care about performance don't use std::simd.

I do agree that there might be reasons why one might want to have a "forgiving" n_elements. Does that mean we need two functions? Ugh, rather not.

[mattkretz]

Sorry for the comment stream here...

Your motivation for n_elements was a performance argument over the basic_mask generator ctor, right? Mask([](int i) { return i < N; }) is still fairly readable and provides the safe (but potentially less optimal) solution. 🤔 So maybe ...

Aside: Oh, I failed to realize in the made_up example: If I'm arguing for preconditions, such that asking for empty and full masks is UB, then n_elements<int>(anything) is equivalent to std::unreachable(), which deletes the if (it != data.end()) branch. And that's correct for scalar T. Interesting.

So maybe we can call it out via the name?

• partial_mask_of_n<V>(n)
• make_partial_mask<V>(n)

Neither a full nor an empty mask would be called "partial mask", right?

[danieltowner]

Would anyone write code like the made_up function? I think the pragmatic approach would be to have a separate function which handled scalars explicitly, rather than trying to come up with a more complicated approach which works for anything. The made_up function already fails to compile because of unchecked_load and simd_generic_size, and even if those were fixed I'm sure we'll trip over over issues. I do think simd-generic can be useful in places, but I don't think there is reason in forcing it to work in places where it doesn't make sense.

How about making n_elements a free-function so that we have the possibility of extending it to simd-generic in future as part of a bigger push to make sure that everything in simd works like that? But keep things simple for now by only working with non-generic simd types.

I also toyed with the idea of inferring the mask if given a simd-vec-type, so I think that is worth adding.

In the earlier days of AVX-512 it was recommended that tail handling should be dealt with by masking within the whole block (i.e., a completely full mask is valid), and ARM I think made the same observation. There are still code bases which use that style, and still literature which describes that technique. If the style guide for a given code base wants to ban that style then it can, but I don't think we should prevent a legitimate use of the function. It's potentially inefficient to use it like that, but not wrong.

In our own user code bases we have been playing with algorithms which have a simd policy, and which generate the appropriate tail-handling, unchecked_load, etc. To me, working on simd-policy for algorithms like for_each or transform, and getting users to adopt them is a better way of improving efficiency than adding performance-preconditions to guide the user on how to use the result of n_elements.

I do like the variants on the name with partial_mask, but it wouldn't really work if the mask was (over)full.

[mattkretz]

Yes, the made_up function hinges on missing simd-generic loads (and stores). But that was part of the motivation to finally make load/store non-members. So I would hope we can also add that at some point. Other than that, yes, I would expect code like this to be written. Whether such code will need to be simd-generic? Probably not very often. But from my interaction with early adopters, simd-generic provides a certain peace of mind: "I'll just change my type alias from vec<float> to float and all the SIMD complexity is gone."

I do agree that we don't have to make it simd-generic in the first pass. But for the sake of efficient use of committee time I think we should do it if we think there's a chance it will otherwise happen later.

On your example of handling the tail in the main loop. This is how I'd write it:

for (int i = 0; i < N; i += V::size()) {
  auto k = i + V::size() <= N ? V::mask_type(true) : partial_mask_of_n(N - i);
  // use k-masked operations for everything
}

The "99% case" is where the mask is full. I'd like to make sure I get that mask predicted and used right away. If I call a function to create my mask from a computed value, that is potentially going to stall my work.

I agree that's inconvenient. But the alternative would be to implement n_elements as

if (n >= M::size()) [[likely]]
  return M(true);
else
  // ...

And that's pessimizing the users that use the function only when it's actually necessary.

[danieltowner]

I chased down some interesting paths in investigating the performance. It looks like this code is very sensitive to the compiler/version, and different strategies for handling the mask generation compound this further. To benchmark this I used the following code to look at performance and code generation patterns:

// extern callSomething(value, mask);

for (int i = 0; i < N; i += V::size()) {
  auto data = unchecked_load<V>(s.subspan(i));

  // Option 1 - user handles precondition explicitly
  auto k = i + V::size() <= N ? V::mask_type(true) : partial_mask_of_n(N - i);

  // Option 2 - implementation handles more relaxed input
  auto k = n_elements(N - i);

  callSomething(data, k);
}

I think that this exposes only the performance/code of the mask mechanics.

There are numerous ways to implement n_elements without a precondition (i.e., where it must handle out-of-range itself), including:

1. iota < min(_n, _Size) // For wide-elements.
2. _n < Size ? Mask(true) : iota < _n;
3. _n < Size ? Mask(true) : bzhi(_n)
4. bzhi(min(_n, _size))

(Note that bzhi is Intel specific, but other targets can use (1<<n) - 1 to achieve something similar. It allows branchless implementation).

Each of those options behaves differently on different compilers/versions (data below). In my original std::simd implementation for oneAPI I used technique 4. Technique 3 generated faster code for oneAPI and slower code for gcc. There doesn't seem to be a single technique that works optimally for all compilers I tested. Based on these results I will implement n_elements with an internal check for gcc vs. clang to pick the best strategy to use for the particular compiler.

Performance of Option 1 and Option2 was comparable when using AVX-512, regardless of compiler, but Option 2 always performed worse than Option 1 for wide elements.

If the precondition is such that the user has to write code like Option 1, then that forces the compiler to use a particular code generation pattern, which isn't always optimal. I think that if n_elements handles N>=size() for itself then the implementation can choose the best strategy, rather than being forced to explicitly handle the precondition using a sub-optimal strategy.

Data:

(numbers show performance relative to the best possible case )

Implementation	Option1-technique3	Option1-technique4	Option1-best	Option2
gcc-wide	2.8	2.8	2.8	3.74
gcc-avx512	1.4	1.86	1.4	1.4
icpx-wide	1.91	1.91	1.91	3.74
icpx-avx512	1.06	1	1	1.03