How to find first position satisfying a condition in SIMD vector?

[pauljurczak]

I'm looking for a function similar to VLC's horizontal_find_first:

[DenisYaroshevskiy]

https://jfalcou.github.io/eve/group__core__reduction_gafe526beb78cfe17529587bbfff4bb597.html#gafe526beb78cfe17529587bbfff4bb597

[pauljurczak]

Thank you. In case you were interested, I compared the same function implemented with VCL and eve (see https://github.com/pauljurczak/simd-benchmarks/blob/main/main-5-vcl-eve.cpp). VCL version is a bit faster (gcc and clang timings below):

Ubuntu 22.04.3 LTS on AMD Ryzen 7 3800X 8-Core Processor
gcc    v13.1   __cplusplus=202100
{fmt}  v8.0.1
loop_eve_max_element(): 8.937  9.037 [us]  108834
loop_eve_nested(): 4.849  4.919 [us]  108834
loop_vc_nested(): 3.597  3.777 [us]  108834
loop_vc_unrolled(): 3.596  3.827 [us]  108834

Ubuntu 22.04.3 LTS on AMD Ryzen 7 3800X 8-Core Processor
clang v17.0.6 (++20231209124227+6009708b4367-1~exp1~20231209124336.77) C++
{fmt}  v8.0.1
loop_eve_max_element(): 6.742  6.813 [us]  108834
loop_eve_nested(): 4.328  4.358 [us]  108834
loop_vc_nested(): 4.568  4.669 [us]  108834
loop_vc_unrolled(): 3.737  4.589 [us]  108834

I'm surprised by huge performance penalty on Intel i3-N305 CPU (same binary):

Ubuntu 23.10 on Intel(R) Core(TM) i3-N305
gcc    v13.1   __cplusplus=202100
{fmt}  v8.0.1
loop_eve_max_element(): 15.565  15.630 [us]  108834
loop_eve_nested(): 13.296  13.396 [us]  108834
loop_vc_nested(): 11.804  11.922 [us]  108834
loop_vc_unrolled(): 11.421  11.868 [us]  108834

Ubuntu 23.10 on Intel(R) Core(TM) i3-N305
clang v17.0.6 (++20231209124227+6009708b4367-1~exp1~20231209124336.77) C++
{fmt}  v8.0.1
loop_eve_max_element(): 12.671  12.814 [us]  108834
loop_eve_nested(): 13.198  13.285 [us]  108834
loop_vc_nested(): 12.377  12.451 [us]  108834
loop_vc_unrolled(): 10.439  12.399 [us]  108834

[DenisYaroshevskiy]

VCL version is a bit faster
Not surprising, they require at least one element set. So to get the same behaviour as eve, in vc you'd have to do any + first_true
On clang you can also do *eve::first_true(x) to get same behaviour and perf as vc.

Generally speaking this is a very nieche benchmark, also I can construct a case where it would be relevant, it's highly unusual.

======================

As far as results are concerned - you are not comparing apples to apples.

1. I am not going to comment much about your code, because I have some correcntess concerns.

2. To get eve::min_element perform better, tell it that the range is divisible and it shouldn't align accesses. https://godbolt.org/z/bjjzPo49n

auto first_max(std::span<const std::uint8_t, 256> s)
{
  return eve::algo::min_element
      [eve::algo::no_aligning]
      [eve::algo::divisible_by_cardinal](s, eve::is_greater);
}

3. Because the width is known, using both eve and vc I'd try to use a "wider" register emulation.
   https://godbolt.org/z/6hf99ce1v

Here is eve's version

std::ptrdiff_t first_max(std::span<const std::uint8_t, 256> s)
{
  using wide = eve::wide<std::uint8_t, eve::fixed<256>>; 

  wide w(s.data());
  wide max_elem = eve::splat(eve::maximum)(w);
  return *eve::first_true(w == max_elem);
}