Compress functions

Detailed Description

Functions that in different way expose compressing selected elements together to beginning. This is at the core of remove_if, copy_if etc. Alternative search keywords: filter, remove, pack

Variables
constexpr callable_compress_	eve::compress = {}
	A low level function to compress one simd value based on a mask.
constexpr auto	eve::compress_copy = _::compress_callable<compress_copy_core> {}
	A function that copies selected elements from source to destination, while compressing them to the left.
constexpr auto	eve::compress_store = _::compress_callable_no_density<compress_store_core> {}
	A function that stores selected elements from an eve::simd_value to an eve::simd_compatible_ptr, while compressing them to the beginning.

Variable Documentation

compress

callable_compress_ eve::compress = {}

inlineconstexpr

A low level function to compress one simd value based on a mask.

Defined in Header

#include <eve/module/core.hpp>

Note

this is very low level function, most likely you are looking for eve::compress_copy or eve::compress_store.

• FIX-1647: eve::compress doesn't support wide<tuple> yet.
• the mask type can be any logical with the same cardinal.

Compression in simd is moving selected elements to the front of the simd_value. Unfortunately, not for all simd_value, not for all platforms that can be done efficiently. So the operation splits the input into chunks for which it's possible.

The function performs the following steps: 1) splits the simd_value and mask into chunks, that can be processed in one go. This depends on what instructions are available. 2) Each chunk, gets shuffled in a way that moves selected elements (mask == true) to the front. The tail of the resulting value is unspecified. [a, b, c, d], (false, true, false, true) -> [b, d, _, _] 3) For each chunk we also compute how many elements are selected. (in the example - 2). 4) Both shuffled chunk and a number are put in a kumi::tuple<simd_value, std::ptrdiff_t> TODO: there is a bug where sometimes it's an int and not std::ptrdiff_t. 5) Those chunks are combined together in another tuple.

List of people who's work was instrumental for building this:

• @aqrit user on Stack Overflow
• Peter Cordes

Throughout the code of compress there are references to what was taken from where as well as explanations.

Callable Signatures

namespace eve
{
   template <simd_value T, logical_simd_value L>
   auto compress(T x, L m);                       // (1)
 
   template <relative_conditional_expr C,
             simd_value T,
             logical_simd_value L>
   auto compress[C ignore](T x, L m)              // (2)
}

Parameters

• x - simd_value to compress
• m - mask which marks selected elements as true
• ignore - optional eve::relative_conditional_expr, passed in []. Ignored elements are treated as not selected.

Return value

1. kumi::tuple<kumi::tuple<simd_value, std::ptrdiff_t>, ...> - tuple of compressed chunks, constructed as described earlier.
2. The operation is performed conditionally.

Example

#include <eve/module/core.hpp>
#include <tts/tts.hpp>
 
// template to make if constexpr not activate
template <typename T>
void show_return_type(T)
{
  if constexpr (std::same_as<T, std::int8_t> && eve::current_api == eve::sse4_2)
  {
    // On sse4_2 the default wide<std::int8_t>::size() == 16
 
    // We cannot compress 16 bytes in one step,
    // We need to split it into 2 chunks of 8.
    //
    // So the result will be 2 chunks of 8.
    // We will also return how many are in each chunk
 
    // clang-format off
    eve::wide<T> in {
       1,  2,  0,  4, //
       5,  0,  6,  7, //
       8,  9, 10, 11, //
      12,  0, 14, 15, //
    };
    // clang-format on
 
    using i8x8 = eve::wide<std::int8_t, eve::fixed<8>>;
 
    using chunk = kumi::tuple<i8x8, int>;  // int should be ptrdiff_t - this is a bug
 
    // ignore will be interpreted as false in the mask
    kumi::tuple<chunk, chunk> compressed = eve::compress[eve::ignore_first(1)](in, in != 0);
 
    auto [lo, hi] = compressed;
 
    auto [lo_compressed, lo_count] = lo;
    auto [hi_compressed, hi_count] = hi;
 
    TTS_EQUAL(5, lo_count); // 2 zeroes in the first 8 elements + ignore_first
    TTS_EQUAL(7, hi_count); // 1 zero in the second 8 elements
 
    // The 'tail' after removed elements is unspecified
    // so looking at them is not helpful.
    lo_compressed.set(5, -1);
    lo_compressed.set(6, -1);
    lo_compressed.set(7, -1);
    hi_compressed.set(7, -1);
 
    TTS_EXPECT(eve::all(lo_compressed == i8x8{2, 4, 5, 6, 7, -1, -1, -1}));
    TTS_EXPECT(eve::all(hi_compressed == i8x8{8, 9, 10, 11, 12, 14, 15, -1}));
  }
}
 
// Here is how one can use `eve::compress` directly.
// This how for some platforms we can implement `compress_copy_unsafe_dense`.
int* compress_copy_using_compress_directly(const int* in, int* out)
{
  auto loaded = eve::load(in);
 
  // a tuple or compressed wides.
  // each part is not just a wide but is a tuple<wide, count>
  // so that you know how to compact values after
  //
  // So using chunk = kumi::tuple<wide<int, N1>>;
  // So kumi::tuple<chunk, ...>
  kumi::tuple compressed_whole = eve::compress(loaded, loaded != 0);
 
  kumi::for_each([&](auto compressed_lengh) {
    auto [compressed, length] = compressed_lengh;
    eve::store(compressed, out);
    out += length;
  }, compressed_whole);
 
  return out;
}
 
void validate_compress_copy(auto f)
{
  constexpr std::size_t N = eve::wide<int>::size();
  std::array<int, N> in = {};
 
  for (std::size_t i = 0; i != N; ++i) {
    if (i % 4 == 0) in[i] = 0;
    else
    {
      in[i] = i;
    }
  }
 
  std::array<int, N> expected = {};
  std::copy_if(in.begin(), in.end(), expected.begin(), [](int x) { return x != 0; });
 
  std::array<int, N> out = {};
  auto* o = f(in.data(), out.data());
  std::fill(o, out.data() + out.size(), 0);
 
  TTS_EQUAL(expected, out);
}
 
int main()
{
  show_return_type(std::int8_t{0});
  validate_compress_copy(compress_copy_using_compress_directly);
}

compress_copy

auto eve::compress_copy = _::compress_callable<compress_copy_core> {}

inlineconstexpr

A function that copies selected elements from source to destination, while compressing them to the left.

Defined in Header

#include <eve/module/core.hpp>

If this function doesn't work for you, maybe you are looking for eve::compress_store or eve::compress. However this function is faster.

You can think about this function as std::copy_if but instead of a predicate, you pass in logical_simd_value. Similar to std::copy_if it returns you a pointer to where the output ended.

Note

: you might be missing information about the last selected element written, but unfortunately that adds overhead we couldn't fix (#1656)

There are the following two modifiers:

• safe/unsafe - unsafe version is allowed to write up to mask.size() elements, even if not all are selected. Those values are undefined. safe is not allowed to perform those writes, at the price of being slower for certain usecases.
• dense/sparse - whether or not you expect a lot of selected elements.

Note

safe version only touch selected elements. So, for example, other threads can read/write them without a race condition.

Preloaded values

Very often the mask is computed based on the values loaded from input. We would expect the optimizer to eliminate duplicated loads, but for some very complex pointer-like it might not be able to.

So we provide overloads where you can pass an already preloaded value. It should match loaded value from in, otherwise the behaviour is unspecified.

Masked Calls

You can pass up to two eve::relative_conditional_expr ignore modifiers. 1st is the input side ignore:

• the ignored elements can are not loaded (same as load[ignore])
• they are treated as not selected, regardless of the mask value 2nd is the output side ignore:
• elements that are ignored, will not be written. having initial offset is equivalent to offsetting the o + offset. followed by keep_first(count) Example: if the eve::ignore_extrema(1, L::size() - 2) is passed,

compress_store

auto eve::compress_store = _::compress_callable_no_density<compress_store_core> {}

inlineconstexpr

A function that stores selected elements from an eve::simd_value to an eve::simd_compatible_ptr, while compressing them to the beginning.

Defined in Header

#include <eve/module/core.hpp>

This function behaves like eve::compress_copy[dense] but as input it takes loaded register.

See also

eve::compres_copy for explained behaviour.

Warning

you should use eve::compress_copy if possible, it has more opportunities for optimizations.

Callable Signatures

namespace eve
{
   template <relative_conditional_expr C1,
             relative_conditional_expr C2,
             simd_value T,
             logical_simd_value L,
             typename O>
   auto compress_store
       [safe/unsafe]
       [C1 ignore_in][C2 ignore_out]
       (T x, L m, O o)  -> unaligned_t<O> // (1)
}

Parameters

• safe/unsafe - mode of the operation - required
• ignore_in - optional, ignored elements considered not selected.
• ignore_out - optional, defaults to ignore_in. controls part of the output where the data will be written.
• x: simd_value to compress
• m: mask indicating selected elements
• o: pointer-like where to write the elements

Return value

• o after the last selected element written

Example

#include <eve/module/core.hpp>
#include <tts/tts.hpp>
 
using n = eve::fixed<4>;
using w_t = eve::wide<int, n>;
using l_t = eve::logical<eve::wide<std::uint8_t, n>>; // Note the type mismatch
 
int main()
{
  w_t in { 1,     2,      3,      4 };
  l_t m  { false, true, true, false };
 
  {
    // We have to have 4 elements in the output, even if only 2 are selected.
    std::array<int, 4> out {};
 
    int* o = eve::compress_store[eve::unsafe](in, m, out.data());
    TTS_EQUAL(2, o - out.data());  // 2 elements are selected and written
 
    // We don't know what elements are after
    out[2] = -1;
    out[3] = -1;
    TTS_EQUAL((std::array{2, 3, -1, -1}), out);
  }
 
  {
    // Here we know we won't write more than selected,
    // at the price of it being more expensive
    std::array<int, 2> out {};
    int* o = eve::compress_store[eve::safe](in, m, out.data());
 
    TTS_EQUAL(o - out.data(), 2);
    TTS_EQUAL((std::array{2, 3}), out);
  }
 
  {
    // Ignore output defaults to the input ignore.
    std::array<int, 3> out {-1, 0, 0};
    int* o = eve::compress_store[eve::unsafe][eve::keep_between(1, 3)](in, m, out.data());
 
    TTS_EQUAL(o - out.data(), 3);
    TTS_EQUAL((std::array{-1, 2, 3}), out);
  }
 
  {
    // But can be separate
    std::array<int, 3> out {0, -1, -1};
    int* o = eve::compress_store[eve::unsafe][eve::ignore_none][eve::keep_first(1)](in, m, out.data());
    TTS_EQUAL(o - out.data(), 1);
    TTS_EQUAL((std::array{2, -1, -1}), out);
  }
}