sort

eve::sort = functor<sort_t>

inlineconstexpr

Header file

#include <eve/module/core.hpp>

Sorting algorithm, based on sortin networks.

Note

this sort is unstable.

Also our implementation is not directly based on any specific one, people we are definetly not the first people to do this. Here is a list of previous work that was looked at.

• A Novel Hybrid Quicksort Algorithm Vectorized using AVX-512 on Intel Skylake: arXiv:1704.08579
• damageboy (and his github) https://bits.houmus.org/2020-01-28/this-goes-to-eleven-pt1
• Berenger Bramas A fast vectorized sorting implementation based on the ARM scalable vector extension https://www.researchgate.net/publication/351656348_A_fast_vectorized_sorting_implementation_based_on_the_ARM_scalable_vector_extension_SVE
• Intel x86-simd-sort https://github.com/intel/x86-simd-sort
• Google's: Vectorized and performance-portable Quicksort Mark Blacher, Joachim Giesen, Peter Sanders, Jan Wassenberg https://opensource.googleblog.com/2022/06/Vectorized%20and%?20performance%20portable%20Quicksort.html
• A Question of Sorts http://seven-degrees-of-freedom.blogspot.com/2010/07/question-of-sorts.html
• Kyle Hegeman (@khegeman) https://github.com/khegeman/floki

Callable Signatures

namespace eve
{
   // Regular overloads
   constexpr auto sort(value auto  x);                    noexcept; // 1
   constexpr auto sort(value auto  x, ordering auto less) noexcept; // 1
}

Parameters

• x - simd_value to sort
• less - simd strict weak ordering. Defaults to eve::is_less.

Return value

1. sorted x.

Example

// revision 1
#include <eve/module/core.hpp>
#include <iostream>
 
int main()
{
  auto myless =  [](auto z1, auto z2){ return z1 > z2; };
 
  eve::wide wf0{0.0, 1.0, 2.0, 3.0, -1.0, -2.0, -3.0, -4.0};
  eve::wide wi0{0, 1, 2, 3, -1, -2, -3, -4};
  eve::wide wu0{0u, 1u, 2u, 3u, 4u, 5u, 6u, 7u};
 
  std::cout << "<- wf0               = " << wf0 << "\n";
  std::cout << "<- wi0               = " << wi0 << "\n";
  std::cout << "<- wu0               = " << wu0 << "\n";
 
  std::cout << "-> sort(wf0)         = " << eve::sort(wf0) << "\n";
  std::cout << "-> sort(wf0, myless) = " << eve::sort(wf0, myless)  << "\n";
  std::cout << "-> sort(wu0)         = " << eve::sort(wu0) << "\n";
  std::cout << "-> sort(wu0, myless) = " << eve::sort(wu0, myless)  << "\n";
  std::cout << "-> sort(wi0)         = " << eve::sort(wi0) << "\n";
  std::cout << "-> sort(wi0, myless) = " << eve::sort(wi0, myless)  << "\n";
}