C++ template for generating small sorting networks compatible with SIMD intrinsics
Fast sorting of short sequences of simple types.
Only if:
- you need to sort many short sequences of the same length (4 - 32ish?), and performance is important
- the length of sequence is known at compile time
- you can't implement the sorting network by hand (you don't know the sequence length when writing your code).
- comparisons and swaps of pairs of elements are cheap
Especially if:
- you want to use SIMD intrinsics
A rudimentary benchmark is included, look at benchmark.cpp for the details, here is the resulting chart:
The code was compiled with clang. With gcc the results look quite different, gcc is able to vectorise the intswap version and the results are nearly as fast as the avx2 version.
Sorting networks are branchless, operate on sequences in-place and require few registers, meaning the generated code can offer great performance. As the control flow is independent of the sequence then the network can be applied efficiently to multiple sequences at once using simd instructions. The run-time is predictable and uniform, i.e. independent of the ordering of the original sequence.
Efficiency is O(n(log n)^2), but this is also potentially the size of the code. For longer sequences the size of the network will lead to a large network and a lot of generated code, this may impact performance. Since the code is branchless there is no 'early-out', a different algorithm may be more efficient if sequences start partially sorted.
Vectorized/Static-Sort Comparible performance in scalar code (but templates only over comparisons, not swaps)
MarcelPiNacy/osn Explicitly specified sorting networks up to 8 elements
Generated by std::cout << SortingNetwork<16>{};
o-o · · · · · · · · · · · · · ·
· · o-o · · · · · · · · · · · ·
o---o · · · · · · · · · · · · ·
· o---o · · · · · · · · · · · ·
· o-o · · · · · · · · · · · · ·
· · · · o-o · · · · · · · · · ·
· · · · · · o-o · · · · · · · ·
· · · · o---o · · · · · · · · ·
· · · · · o---o · · · · · · · ·
· · · · · o-o · · · · · · · · ·
o-------o · · · · · · · · · · ·
· · o-------o · · · · · · · · ·
· · o---o · · · · · · · · · · ·
· o-------o · · · · · · · · · ·
· · · o-------o · · · · · · · ·
· · · o---o · · · · · · · · · ·
· o-o · · · · · · · · · · · · ·
· · · o-o · · · · · · · · · · ·
· · · · · o-o · · · · · · · · ·
· · · · · · · · o-o · · · · · ·
· · · · · · · · · · o-o · · · ·
· · · · · · · · o---o · · · · ·
· · · · · · · · · o---o · · · ·
· · · · · · · · · o-o · · · · ·
· · · · · · · · · · · · o-o · ·
· · · · · · · · · · · · · · o-o
· · · · · · · · · · · · o---o ·
· · · · · · · · · · · · · o---o
· · · · · · · · · · · · · o-o ·
· · · · · · · · o-------o · · ·
· · · · · · · · · · o-------o ·
· · · · · · · · · · o---o · · ·
· · · · · · · · · o-------o · ·
· · · · · · · · · · · o-------o
· · · · · · · · · · · o---o · ·
· · · · · · · · · o-o · · · · ·
· · · · · · · · · · · o-o · · ·
· · · · · · · · · · · · · o-o ·
o---------------o · · · · · · ·
· · · · o---------------o · · ·
· · · · o-------o · · · · · · ·
· · o---------------o · · · · ·
· · · · · · o---------------o ·
· · · · · · o-------o · · · · ·
· · o---o · · · · · · · · · · ·
· · · · · · o---o · · · · · · ·
· · · · · · · · · · o---o · · ·
· o---------------o · · · · · ·
· · · · · o---------------o · ·
· · · · · o-------o · · · · · ·
· · · o---------------o · · · ·
· · · · · · · o---------------o
· · · · · · · o-------o · · · ·
· · · o---o · · · · · · · · · ·
· · · · · · · o---o · · · · · ·
· · · · · · · · · · · o---o · ·
· o-o · · · · · · · · · · · · ·
· · · o-o · · · · · · · · · · ·
· · · · · o-o · · · · · · · · ·
· · · · · · · o-o · · · · · · ·
· · · · · · · · · o-o · · · · ·
· · · · · · · · · · · o-o · · ·
· · · · · · · · · · · · · o-o ·