eve::algo::max_element on a slice of an array

[pauljurczak]

I've got lost in template metaprogramming madness trying to find an answer. I have an array std::array<int, 4> a{3, 1, 4, 1}; and I would like to apply eve::algo::max_element() to a slice of it, say a[1:3] in Python notation. How do I do it? I can't find the meaning of relaxed_range.

[DenisYaroshevskiy]

Hi!

Thank you for trying eve.

I am not sure I 100% understand the question, so my best attempt.

NOTE: max_element is the LAST biggest elements amoung equals, {1, 4, 2, 4} - max element has number 3.

Opt 1. You have a contigious range and you just used array<int, 4> as an example

This is the code (https://godbolt.org/z/3qfsYYoEx) :

#include <eve/module/algo.hpp>
#include <span>

std::span<const int> around_max(std::span<const int> s) {
  auto res = eve::algo::max_element(s);
  EVE_ASSERT(res != s.end());
  return {res, res + 1};
}

Opt 2. You just have 4 ints.

For explicitly 4 ints you are probably better of writing something scalar with cmov - so measure.

If you were to use simd, it'd be https://godbolt.org/z/3Tde55dhd

#include <eve/module/core.hpp>
#include <array>

std::array<int, 2> around_max(std::array<int, 4> in) {
  eve::wide<int, eve::fixed<4>> w(in);
  
  // this finds max value in w and makes it so it's written
  // in all wide<int>
  auto max = eve::splat(eve::reduce)(w, eve::max);
  std::ptrdiff_t pos = *eve::last_true(w == max);

  return {in[pos], in[pos + 1]}; // this is weird but you want 2 elements
}

Please let me know if this is what you were asking.

P.S.

• sorry the doc for relaxed range is not in a good state. Created an issue [BUG] fix doc for relaxed range #1713
  Any std::contigious_range is a relaxed range. Plus different eve specific things, like eve::views.

• min_element has an alternative implementation - one_pass. Under certain condtions (for example very big arrays), it might be faster
  https://jfalcou.github.io/eve/group__algos_ga0f95320d878307ac03e21b52d4c86720.html#ga0f95320d878307ac03e21b52d4c86720

[pauljurczak]

Thank you for answering. I was asking about a simpler syntax issue. Given:

std::array<int, 16> a{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

I would like to apply eve::algo::max_element() to a slice (subarray) of a, e.g. starting at &a[3] and 8 elements long. What would be the syntax of this call? This form: eve::algo::max_value(std::span(a.begin()+3, 8)) doesn't compile. What is the correct one?

[DenisYaroshevskiy]

You need span to be a const value. Otherwise you might be in trouble.

https://godbolt.org/z/Y3Tf9Kd3n

int tst() {
  std::array a{1, 2, 3, 4};
  std::span s{&a[3], 2};
  return *eve::algo::max_value(s);
}

see std::ranges borrowed range for context https://en.cppreference.com/w/cpp/ranges/borrowed_range

[DenisYaroshevskiy]

Fyi: you don't need eve to vectorize max value. Compiler can, if you use std:: reduce with max as your op. I will write you an example later today

[pauljurczak]

I needed it for apples to apples comparison with other libraries/methods. I used std::max_element() otherwise.

[DenisYaroshevskiy]

std max element is slower then std reduce because it returns position.

Do you want a iterator (position) or just value? If you want iterator you should use element. If you want value you use value.

[DenisYaroshevskiy]

My numbers (I measured min)

This is all the algorithms you can do to get min

std::min_element is 5 tmes slower then slowest from other, let's remove it

We are left with 2 min_element implementations (algorithms have differnt tradeoffs). Now - there is also a comparison against std::reduce - which is 2-4 times faster. You can use a reduce to find a value but not position.
This is what min_value does (don't have in the benchmark).

You can ahieve this without eve like this (https://godbolt.org/z/nhEj46c9P):

std::optional<int> max_value(std::span<const int> s) {
  if (s.empty()) return std::nullopt;
  int init = *s.begin();
  return std::reduce(s.begin() + 1, s.end(), init,
    [](auto x, auto y) { return std::max(x, y); });
}

[pauljurczak]

I was looking for an example of max_element() use. I think max_value() returned more search results, so I temporarily focused on that. This is what I needed:

int tst() {
  std::array a{1, 2, 3, 47, 5, 6, 42};
  std::span s{&a[1], 4};
  return eve::algo::max_element(s)-s.begin();
}

[pauljurczak]

BTW, the benchmarks I've run are in https://github.com/pauljurczak/simd-benchmarks/blob/main/main-2-eve.cpp. Eve performs very well:

gcc    v13.1   __cplusplus=202100
{fmt}  v8.0.1
nested_loop(): 0.144  0.172 [ms]  108834
loop_std_max_element(): 0.294  0.294 [ms]  108834
xt::sum(xt::argmax(imgx, 1)): 0.097  0.104 [ms]  108834
loop_eve_max_element(): 0.012  0.012 [ms]  109599

but produces a wrong result, which is most likely my error, see loop_eve_max_element().

[DenisYaroshevskiy]

Try using eve::algo::min_element(s, eve::is_greater);

[pauljurczak]

The result changed, but is still wrong:

loop_eve_max_element(): 0.012  0.012 [ms]  109650

Perhaps you are not returning the first maximum element's position. There are rows with 2 equal peaks.

[DenisYaroshevskiy]

min_element(x, eve::is_greater) should return first element.
max_element(x) returns last.

[DenisYaroshevskiy]

this

  for (auto i=img.begin(); i<img.end(); i+=W) 
    sum += max_element(i, i+W) - i;

should be identical to

  for (auto i=img.begin(); i<img.end(); i+=W) 
    sum += eve::algo::min_element(eve::algo::as_range(i, i + w), eve::is_greater) - i;

if it's not - i'd have to dig in

[pauljurczak]

Yes, it is identical and equally fast as the previous version:

loop_eve_max_element(): 0.012  0.012 [ms]  108834

Thank you.