Sort eve::wide? Bitonic sorting networks.

[bjodah]

First off: thank you for working on EVE, it is truly an amazing project.

I was just searching the documentation for how to sort a eve::wide instance efficiently, but couldn't find anything (currently I only need a simple eve::wide sort(eve::wide input) function, but I could imagine that e.g. "argsort" could be useful too).

I believe a bitonic sorter lends it well to SIMD (but I might be missing something). Is this on some roadmap perhaps? I guess 2, 4, 8, 16, 32, 64 would cover most (all?) use cases.

All the best,
Björn

P.S. As I'm writing this I thought I should at least search and see if Highway has an implementation, and just as an FYI, it looks like they have one.

[jfalcou]

Hi and thanks for trying out EVE :)

Sorting is definitively on our algorithm roadmap but that's for raneg-based sorting of data.
Now, wide level sort could probably implemented as a small case bitonic sort indeed.

This is something we can discuss with @DenisYaroshevskiy and see how we can layout this work.

[DenisYaroshevskiy]

sort of a wide is something I am working on. It's required for sorting a range. But yeah - it's not yet implemented.

We have eve::minmax and eve::shuffle_v2 is being actively developed - all for this reason.

To be clear - I'm not sure when it will be done, a few months I guess but smth may get in the way.

UPD: there is one pr to merge in the next few days, but after that there'd be enough tools to build a somewhat ok sort. For a proper eve::sort that'd be more work but for you to build the case you need, you'd have enough.

[bjodah]

That's awesome guys. Godspeed!

[DenisYaroshevskiy]

If you use highway as an example on how to do it, please don't show it to us - that might create us tension for in the future.

Godbolt doent seem to update the trunk, but this works locally:

#include <eve/module/core.hpp>

using w2 = eve::wide<int, eve::fixed<2>>;

template <typename T>
T sort_adjacent_pairs(T ab, auto less)
{
  T ba = eve::shuffle(ab, eve::fix_pattern<T::size()>([](int i, int /*size*/) {
    // size == T::size() if you need it
    if (i % 2) return i - 1;
    else       return i + 1;
  }));

  // minmax docs: https://jfalcou.github.io/eve/group__core__arithmetic_ga915e97f159edb127bff40c450f4cbe59.html#ga915e97f159edb127bff40c450f4cbe59
  auto [min_ab, max_ab] = eve::minmax(less)(ab, ba);

  // https://jfalcou.github.io/eve/group__core__named__shuffles_gae93d09601f86249bbd239747c107cb69.html#gae93d09601f86249bbd239747c107cb69
  return eve::blend(min_ab, max_ab, [](int i, int /*size*/) { return i % 2; });
}

#include <iostream>

int main()
{
  eve::wide<int, eve::fixed<2>> in{ 1, 0 };
  std::cout << "in: " << in << " out: " << sort_adjacent_pairs(in, eve::is_less) << std::endl;
}

Output:

in: (1, 0) out: (0, 1)

This should be enough tools to do a working sort, if you are blocked.
If you are targeting a modern enough platfrom, it is probably be good enough.

The place I was going to look it was intel's sort - they have a good license and I asked someone.
https://github.com/intel/x86-simd-sort/blob/0890de5da189018bd1032210b23ed11d8fc4f62f/src/avx512-64bit-common.h#L11-L21

There is also https://bits.houmus.org/2020-01-28/this-goes-to-eleven-pt1
but the bitonic sort is only on github.

[DenisYaroshevskiy]

Another thing you might look at is: eve::swap_adjacent(x, eve::lane<G>).
https://jfalcou.github.io/eve/group__core__named__shuffles_gaa73e3ec48a859648ac298f5a73b5c6a5.html#gaa73e3ec48a859648ac298f5a73b5c6a5

In the older version it's called eve::swap_adjacent_groups

[bjodah]

@DenisYaroshevskiy, got it, I haven't done more than the quick google search. I have yet to try to implement something, but so far I simply track eve main branch as a git submodule so I hope to fiddle with this a bit.

A nice write up in the form of an academic paper (Bramas, 2017) can be found on arxiv as well. Perhaps it is of some use?

[DenisYaroshevskiy]

Done: https://jfalcou.github.io/eve/group__core__simd_gae7b27b48927ea3e9aad82f702a388b28.html#gae7b27b48927ea3e9aad82f702a388b28