x86-simd-sort: AVX-512 and AVX2 sorting routines for numeric arrays

The routine families, and where the gaps are

x86-simd-sort is a C++ template library for high performance SIMD based sorting algorithms for built-in integers and floats, in 16-bit, 32-bit and 64-bit data types, and for custom defined C++ objects. The routines are accelerated using AVX-512 and AVX2 when available, and the library auto picks the best version depending on the processor it runs on.

The public surface is four families, and the gaps between them are the part to read carefully.

The built-in integer and float entry points are qsort, qselect and partial_qsort. qselect finds the k-th element, and partial_qsort sorts only the first k elements.

void x86simdsort::qsort(T* arr, size_t size, bool hasnan, bool descending, bool trailing_nans);
void x86simdsort::qselect(T* arr, size_t k, size_t size, bool hasnan, bool descending, bool trailing_nans);
void x86simdsort::partial_qsort(T* arr, size_t k, size_t size, bool hasnan, bool descending, bool trailing_nans);

The key-value family operates on two parallel arrays, a key array and a value array, with keyvalue_qsort, keyvalue_select and keyvalue_partial_sort. This is the shape you want when you have a record array and a separate key column, and the README notes that keyvalue sort is not yet supported for 16-bit data types.

The argsort family returns a vector of indices rather than sorting in place, with argsort and argselect. Argsort and argselect are not accelerated with SIMD when using 16-bit data types, so the fastest path is not available for the narrowest types.

Then there is object_qsort for custom defined class objects, which is a different shape of API from the rest because it takes a key function:

template <typename T, typename U, typename Func>
void x86simdsort::object_qsort(T *arr, U arrsize, Func key_func)

The key function is a lambda computing the key value for each object, and the return type has to be one of float, uint32_t, int32_t, double, uint64_t or int64_t. The supported element types across the library are _Float16, uint16_t, int16_t, float, uint32_t, int32_t, double, uint64_t and int64_t.

So: the SIMD-accelerated core covers 32-bit and 64-bit types, and the 16-bit paths are either absent or not accelerated. If your data is int16_t, that is a thing to check before you adopt the library rather than after.

Runtime dispatch, and the explicit AVX-512 route

The library auto picks the best version depending on the processor it is run on, and the README makes an important distinction about what that means. If you are looking for the AVX-512 or AVX2 specific implementations, the README points you at a separate README file under the src/ directory rather than at the main API.

That is the architecture. The public API is the dispatcher, and the architecture-specific kernels live behind it. Calling x86simdsort::qsort gives you the best implementation the current CPU supports, without the caller doing feature detection or branching. For a library that ends up inside a larger program, this is the right default: you take one entry point and get the acceleration the hardware offers.

The alternative is the direct route. The examples directory makes that concrete, with avx512-kv.cpp for the AVX-512 key-value routines, icl-16bit.cpp for the 16-bit paths under the Intel compiler, skx-avx2.cpp for the AVX2 path on a Skylake-X class machine, and spr-16bit.cpp for the 16-bit path on a Sapphire Rapids class machine. Each of those examples pins one implementation, which is what you would do if you are benchmarking, if you are testing a specific kernel, or if you are shipping a binary that must not depend on runtime detection.

The compiler requirements section is unusually specific, and it exists because the library is not just a template library that instantiates intrinsics, it needs compilers that emit the right instructions. A C++17 compatible compiler is the baseline. GCC 8.x or higher is required for general builds, and GCC 12 or higher is mandatory to support _Float16, which is the AVX-512FP16 work. Clang 8.0 or higher is recommended for AVX-512 support. MSVC needs Visual Studio 2019 version 16.8 or newer for C++17 and initial AVX-512 intrinsic support. The Intel C++ Compiler, icx, is fully supported in its modern LLVM-based versions and is described as often providing optimal performance for these routines.

That last point is a useful signal about who this library is for. When a compiler vendor says its own compiler often produces the best results for the routines, the library is aimed at people doing serious numerical work rather than people sorting a few thousand elements in an application.

Building and linking it, through Meson and pkg-config

The build system is Meson, and the command to build and install the library is:

meson setup --buildtype release builddir && cd builddir
meson compile
sudo meson install

Once installed, you use `pkg-config --cflags --libs x86simdsortcpp` to populate the right cflags and ldflags to compile and link your C++ program. The pkg-config name is x86simdsortcpp, which is worth noting because it differs from the repository name.

The build options are exposed through meson_options.txt. You can build the test suite and the benchmarking suite by configuring with -Dbuild_tests=true and -Dbuild_benchmarks=true. The test suite uses googletest and the benchmark suite uses google benchmark, and the README notes that google benchmark v1.9.2 or newer is required.

The Makefile at the top of the repository is a convenience wrapper around Meson, and it is a good place to see which build configurations the project actually cares about. There are targets for test, test_openmp, test_asan, bench, debug, sharedlib, staticlib, install and clean. Most test targets pass --warnlevel 2 and --werror, so warnings are build failures, and the asan target adds -Db_sanitize=address,undefined with -Dfatal_sanitizers=true, which is a sanitiser build with the address and undefined behaviour checks promoted to fatal errors. The sharedlib and staticlib targets differ by the -Dlib_type=static option, so both linking models are supported.

The repository also includes a top-level Makefile that coexists with the meson.build at the root, plus example.c, a scripts/ directory, a utils/ directory, a run-bench.py driver and a benchmarks/ directory. There is a SECURITY.md, a CODE_OF_CONDUCT.md, a CONTRIBUTING.md and a.clang-format.

For a Meson-based project that already uses subprojects, the README documents the integration path. You create a subprojects directory, copy x86-simd-sort into it, and add two lines to your meson.build:

xss = subproject('x86-simd-sort')
xss_dep = xss.get_variable('x86simdsortcpp_dep')

That vendored subproject route is worth preferring over a system install when you want the build to be reproducible across a fleet of machines, since the version travels with the source tree.

OpenMP parallel sorting, and the threshold you do not control

The README states that qsort, argsort and keyvalue_qsort can achieve even greater performance, up to a 3x speedup, through parallelization with OpenMP. By default OpenMP support is disabled, and you enable it with the -Duse_openmp=true flag when configuring Meson. If you are using only the static SIMD implementations, the instructions are to compile with -fopenmp -DXSS_USE_OPENMP.

Two details follow that are worth understanding. First, the parallelisation applies to three named routines, not to the whole library. qselect, partial_qsort, the keyvalue select and partial_sort variants and object_qsort are not in that list, so a workload that only needs a selection or a partial sort gets no threading benefit.

Second, the threading decision is not yours. OpenMP-based parallel sorting routines are used for arrays larger than a specific threshold where threading makes sense, and the threshold is internal to the library. Below it, the parallel path is not taken. The threshold is not given a value in the README, so if you are tuning for a specific array size you have to measure rather than predict.

The number of threads is limited to a maximum of 16, and you can control it with the OMP_NUM_THREADS environment variable. That cap is a deliberate choice and it is worth understanding why it exists in this kind of library. Sorting is memory-bound, and past a certain number of threads the working set contention dominates the arithmetic, so a hard ceiling avoids the failure mode where a machine with 64 logical cores gets a 64-way sort that is slower than a 16-way one. Setting OMP_NUM_THREADS below the cap is a legitimate tuning knob, particularly in a container with a CPU quota, where the library's thread count would otherwise exceed what the cgroup allows.

A practical note for anyone running this in a container: OpenMP will spawn up to 16 threads regardless of how many CPUs the container has, and the oversubscription penalty is real. Pinning OMP_NUM_THREADS to the container's CPU allocation is the difference between a parallel sort that helps and one that hurts.

Where x86-simd-sort is the wrong tool

There are three limits, and the first one is the most common reason a project like this gets rejected.

The first is that the acceleration is x86-specific by construction, and it requires recent x86. The library targets AVX-512 and AVX2, and the compiler requirements start at GCC 8, Clang 8 and MSVC 16.8. If your build has to produce binaries for ARM, for a GPU, or for an x86 CPU older than Haswell, this library does not apply. A project that ships a single portable binary across architectures is not a candidate.

The second is that it accelerates sorting, and sorting is often not the bottleneck you think it is. The library's own benchmark suite exists to answer that question, and the README's Details section points at the performance of object_qsort relative to std::sort, which is the comparison a reader should make first. If your array fits in cache, or if the surrounding code dominates, a vectorised sort buys little. The usual trigger for reaching for this is a large array that is sorted repeatedly, for example inside a numerical pipeline where sorting is one stage among many, and where the same values are re-sorted every iteration.

The third is the API surface mismatch. These routines are not std::sort. There is no comparator, so the sort order is fixed, and the NaN handling is exposed as explicit boolean parameters, hasnan, descending and trailing_nans, which you must set correctly for your data. There is no stable variant listed among the routines, so if you need a stable sort, or a custom comparator, or a heterogeneous comparison, this library does not provide it. The object_qsort route exists for the custom-comparator case, but it constrains the key type to six specific numeric types and it costs O(N) space.

The space cost is worth quantifying because the README does it for you. object_qsort requires arrsize * sizeof(key_t) bytes for a vector of all the keys and an additional arrsize * sizeof(uint32_t) bytes for the indexes of the object array. The library recommends using object_qsort when the array size is less than or equal to UINT32_MAX, and the indexes are 32-bit because the whole design is bounded by a 32-bit index space.

And the last practical limit is the build weight. This is a C++ library with a SIMD kernel per architecture, a Meson build, a compiler-version floor, and a runtime dispatcher. For a project whose sort takes 2 milliseconds, that is a lot of moving parts to introduce.

x86-simd-sort against a plain std::sort

The alternative is to keep using std::sort, and the difference in approach is straightforward.

std::sort is introsort: a quicksort with a depth limit that falls back to heapsort, with insertion sort for small partitions. It is a good general algorithm, it is portable, it is in every standard library, and it is good at what it is. Its weakness is that it operates on one element at a time, so a branch mispredict costs a pipeline flush and a single comparison is a poor unit of work for a vector unit.

A SIMD sort changes the unit of work. Instead of comparing one element against a pivot, it compares a vector of elements against a vector of pivots, and it partitions in blocks sized to the register width. That is why the library is AVX-512 and AVX2 specific rather than generic: the whole approach depends on knowing the width of the machine's vector registers at compile time for the kernel, and on the hardware's support for the mask and permute instructions the kernel needs.

The second alternative is a vendor library: a tuned implementation of the same idea with the same hardware target, which is likely faster but adds a toolchain dependency. The difference is that x86-simd-sort is a standalone library you can vendor as a Meson subproject, with no toolchain dependency beyond a C++17 compiler, and it is BSD-3-Clause licensed.

The third option, which is the one most projects should consider first, is to change the algorithm rather than the implementation. If you are sorting the same array repeatedly, or sorting an array whose order you then discard, a radix sort, or a counting sort for a small range of integer values, or a partial selection where you only need the k-th element, may beat any comparison sort. The library does offer qselect and partial_qsort, which are the right tools when you need only the k smallest, and the topics list includes quickselect, partialsort and argsort, which tells you the library was designed with those use cases in mind rather than only for full sorts.

So the honest comparison is between three things: std::sort, which you already have and which is hard to beat on small or unsorted-in-the-worst-way data; a vendor library, which is likely faster but adds a toolchain dependency; and this one, which is vendored, permissively licensed, and built specifically for the x86 vector unit. The reason to choose the third over the first is a measurement, and the measurement is what the benchmark suite in the repository is for.

Editorial conclusion

Adopt x86-simd-sort if sorting large numeric arrays is a measured bottleneck in your C++ code, and you are on x86 with either AVX2 or AVX-512 available, and you can accept a C++17 minimum and a dispatching library in your build. Do not adopt it for small arrays, for stable-sort requirements, or for non-x86 targets, since the acceleration is x86-specific by construction. Verify first that the routine you want exists for your element type, because the 16-bit and key-value paths have documented gaps, and that your compiler is new enough for the instruction set you need, since AVX-512FP16 support requires GCC 12 or newer.

Frequently asked questions

Official sources

1. Issues
2. License: BSD-3-Clause
3. numpy/x86-simd-sort on GitHub
4. README
5. Releases