highway Documentation

Performance-portable, length-agnostic SIMD with runtime dispatch

5,730 stars C++ C++ 1 file · ~11,964 tokens #avx#avx-512#avx-instructions#avx2#avx512#intrinsics#neon#simd
RAW Doc

File: README.md

Efficient and performance-portable vector software

Highway is a C++ library that provides portable SIMD/vector intrinsics.

Documentation

Previously licensed under Apache 2, now dual-licensed as Apache 2 / BSD-3.

Why

We are passionate about high-performance software. We see major untapped
potential in CPUs (servers, mobile, desktops). Highway is for engineers who want
to reliably and economically push the boundaries of what is possible in
software.

How

CPUs provide SIMD/vector instructions that apply the same operation to multiple
data items. This can reduce energy usage e.g. fivefold because fewer
instructions are executed. We also often see 5-10x speedups.

Highway makes SIMD/vector programming practical and workable according to these
guiding principles:

Does what you expect: Highway is a C++ library with carefully-chosen
functions that map well to CPU instructions without extensive compiler
transformations. The resulting code is more predictable and robust to code
changes/compiler updates than autovectorization.

Works on widely-used platforms: Highway supports seven architectures; the
same application code can target various instruction sets, including those with
'scalable' vectors (size unknown at compile time). Highway only requires C++17
(language features, not necessarily the library) and supports four families of
compilers. If you want to use Highway on other platforms, please raise an issue.

Flexible to deploy: Applications using Highway can run on heterogeneous
clouds or client devices, choosing the best available instruction set at
runtime. Alternatively, developers may choose to target a single instruction set
without any runtime overhead. In both cases, the application code is the same
except for swapping HWY_STATIC_DISPATCH with HWY_DYNAMIC_DISPATCH plus one
line of code. See also @kfjahnke's
introduction to dispatching.

Suitable for a variety of domains: Highway provides an extensive set of
operations, used for image processing (floating-point), compression, video
analysis, linear algebra, cryptography, sorting and random generation. We
recognise that new use-cases may require additional ops and are happy to add
them where it makes sense (e.g. no performance cliffs on some architectures). If
you would like to discuss, please file an issue.

Rewards data-parallel design: Highway provides tools such as Gather,
MaskedLoad, and FixedTag to enable speedups for legacy data structures. However,
the biggest gains are unlocked by designing algorithms and data structures for
scalable vectors. Helpful techniques include batching, structure-of-array
layouts, and aligned/padded allocations.

We recommend these resources for getting started:

Examples

Online demos using Compiler Explorer:

We have prepared several tutorial-like examples in hwy/examples; see the
Basics:

  • sum_array_advanced.cc: 4x unrolling and remainder handling.
  • dot_product_unroll.cc: similar to sum_array_advanced, plus reduction.
  • matrix_transpose_scatter_gather: shows/compares Scatter and Gather.

Infrastructure:

  • benchmark.cc: dot product with remainder-free loops and benchmarking.
  • profiler_example: shows how to use the our built-in profiler for measuring
    the time cost of annotated zones.
  • skeleton*: a complete example of a module with runtime dispatch.

Challenges:

  • masks_and_logic.cc: visualizes masks/comparisons with ASCII art.
  • ctf_aes.cc: capture the flag, brute-force AES password guessing.

We observe that Highway is referenced in the following open source projects,
found via sourcegraph.com. Most are GitHub repositories. If you would like to
add your project or link to it directly, feel free to raise an issue or contact
us via the below email.

Other

  • Evaluation of C++ SIMD Libraries:
    "Highway excelled with a strong performance across multiple SIMD extensions
    [..]. Thus, Highway may currently be the most suitable SIMD library for many
    software projects."
  • zimt: C++11 template library to process n-dimensional arrays with multi-threaded SIMD code
  • vectorized Quicksort (paper)

Highway can also be installed via a package manager or from a repository:

Click to expand BSD repositories

Click to expand cross platform package repositories

Click to expand linux package repositories

Obtained from repology

text
Click to expand Windows package repositories

Current status

Targets

Highway supports 27 targets, listed in alphabetical order of platform:

  • Any: EMU128, SCALAR;
  • Armv7+: NEON_WITHOUT_AES, NEON, NEON_BF16, SVE, SVE2, SVE_256,
    SVE2_128;
  • IBM Z: Z14, Z15;
  • LoongArch: LSX, LASX;
  • POWER: PPC8 (v2.07), PPC9 (v3.0), PPC10 (v3.1B, not yet supported due
    to compiler bugs, see #1207; also requires QEMU 7.2);
  • RISC-V: RVV (1.0);
  • WebAssembly: WASM, WASM_EMU256 (a 2x unrolled version of wasm128,
    enabled if HWY_WANT_WASM2 is defined. This will remain supported until it
    is potentially superseded by a future version of WASM.);
  • x86:
    • SSE2
    • SSSE3 (~Intel Core)
    • SSE4 (~Nehalem, also includes AES + CLMUL).
    • AVX2 (~Haswell, also includes BMI2 + F16 + FMA)
    • AVX3 (~Skylake, AVX-512F/BW/CD/DQ/VL)
    • AVX3_DL (~Icelake, includes BitAlg + CLMUL + GFNI + VAES +
      VBMI + VBMI2 + VNNI + VPOPCNT),
    • AVX3_ZEN4 (AVX3_DL plus BF16, optimized for AMD Zen4; requires opt-in
      by defining HWY_WANT_AVX3_ZEN4 if compiling for static dispatch, but
      enabled by default for runtime dispatch),
    • AVX3_SPR (~Sapphire Rapids, includes AVX-512FP16)
    • AVX10_2 (~Diamond Rapids)

Our policy is that unless otherwise specified, targets will remain supported as
long as they can be (cross-)compiled with currently supported Clang or GCC, and
tested using QEMU. If the target can be compiled with LLVM trunk and tested
using our version of QEMU without extra flags, then it is eligible for inclusion
in our continuous testing infrastructure. Otherwise, the target will be manually
tested before releases with selected versions/configurations of Clang and GCC.

SVE was initially tested using farm_sve (see acknowledgments).

Versioning

Highway releases aim to follow the semver.org system (MAJOR.MINOR.PATCH),
incrementing MINOR after backward-compatible additions and PATCH after
backward-compatible fixes. We recommend using releases (rather than the Git tip)
because they are tested more extensively, see below.

The current version 1.0 signals an increased focus on backwards compatibility.
Applications using documented functionality will remain compatible with future
updates that have the same major version number.

Testing

Continuous integration tests build with a recent version of Clang (running on
native x86, or QEMU for RISC-V and Arm) and MSVC 2019 (v19.28, running on native
x86).

Before releases, we also test on x86 with Clang and GCC, and Armv7/8 via GCC
cross-compile. See the testing process for
details.

The contrib directory contains SIMD-related utilities: an image class with
aligned rows, a math library (16 functions already implemented, mostly
trigonometry), and functions for computing dot products and sorting.

Other libraries

If you only require x86 support, you may also use Agner Fog's
VCL vector class library. It includes many
functions including a complete math library.

If you have existing code using x86/NEON intrinsics, you may be interested in
SIMDe, which emulates those
intrinsics using other platforms' intrinsics or autovectorization.

xSIMD is a header only C++ library. It
supports Arm, Power, RISC-V, WebAssembly and x86 targets. Has a high level
interface, but fewer supported operations.

NumKong a SIMD accelerated math C
library focused on operations such as dot products and mixed precision matrix
multiplications. It can be used from C++, Go, Python, Rust, Swift and
WebAssembly. Accelerated operations are available on Arm, LoongArch, Power,
RISC-V and x86.

Installation

This project uses CMake to generate and build. In a Debian-based system you can
install it via:

bash
sudo apt install cmake

Highway's unit tests use googletest.
By default, Highway's CMake downloads this dependency at configuration time.
You can avoid this by setting the HWY_SYSTEM_GTEST CMake variable to ON and
installing gtest separately:

bash
sudo apt install libgtest-dev

Alternatively, you can define HWY_TEST_STANDALONE=1 and remove all occurrences
of gtest_main in each BUILD file, then tests avoid the dependency on GUnit.

Running cross-compiled tests requires support from the OS, which on Debian is
provided by the qemu-user-binfmt package.

To build Highway as a shared or static library (depending on BUILD_SHARED_LIBS),
the standard CMake workflow can be used:

bash
mkdir -p build && cd build
cmake ..
make -j && make test

Or you can run run_tests.sh (run_tests.bat on Windows).

Bazel is also supported for building, but it is not as widely used/tested.

When building for Armv7, a limitation of current compilers requires you to add
-DHWY_CMAKE_ARM7:BOOL=ON to the CMake command line; see #834 and #1032. We
understand that work is underway to remove this limitation.

To benefit from Armv8/v9 vusdot and vusdotq instructions, you can add "+i8mm" to
the -march compiler flag, assuming the target CPU(s) support that.

Building on 32-bit x86 is not officially supported, and AVX2/3 are disabled by
default there. Note that johnplatts has successfully built and run the Highway
tests on 32-bit x86, including AVX2/3, on GCC 7/8 and Clang 8/11/12. On Ubuntu
22.04, Clang 11 and 12, but not later versions, require extra compiler flags
-m32 -isystem /usr/i686-linux-gnu/include. Clang 10 and earlier require the
above plus -isystem /usr/i686-linux-gnu/include/c++/12/i686-linux-gnu. See
#1279.

Building highway - Using vcpkg

highway is now available in vcpkg

bash
vcpkg install highway

The highway port in vcpkg is kept up to date by Microsoft team members and community contributors. If the version is out of date, please create an issue or pull request on the vcpkg repository.

Quick start

You can use the benchmark inside examples/ as a starting point.

A quick-reference page briefly lists all operations
and their parameters, and the instruction_matrix
indicates the number of instructions per operation.

The FAQ answers questions about portability, API design and
where to find more information.

We recommend using full SIMD vectors whenever possible for maximum performance
portability. To obtain them, pass a ScalableTag<float> (or equivalently
HWY_FULL(float)) tag to functions such as Zero/Set/Load. There are two
alternatives for use-cases requiring an upper bound on the lanes:

  • For up to N lanes, specify CappedTag<T, N> or the equivalent
    HWY_CAPPED(T, N). The actual number of lanes will be N rounded down to
    the nearest power of two, such as 4 if N is 5, or 8 if N is 8. This is
    useful for data structures such as a narrow matrix. A loop is still required
    because vectors may actually have fewer than N lanes.

  • For exactly a power of two N lanes, specify FixedTag<T, N>. The largest
    supported N depends on the target, but is guaranteed to be at least
    16/sizeof(T).

Due to ADL restrictions, user code calling Highway ops must either:

  • Reside inside namespace hwy { namespace HWY_NAMESPACE {; or
  • prefix each op with an alias such as namespace hn = hwy::HWY_NAMESPACE; hn::Add(); or
  • add using-declarations for each op used: using hwy::HWY_NAMESPACE::Add;.

Additionally, each function that calls Highway ops (such as Load) must either
be prefixed with HWY_ATTR, OR reside between HWY_BEFORE_NAMESPACE() and
HWY_AFTER_NAMESPACE(). Lambda functions currently require HWY_ATTR before
their opening brace.

Do not use namespace-scope nor static initializers for SIMD vectors because
this can cause SIGILL when using runtime dispatch and the compiler chooses an
initializer compiled for a target not supported by the current CPU. Instead,
constants initialized via Set should generally be local (const) variables.

The entry points into code using Highway differ slightly depending on whether
they use static or dynamic dispatch. In both cases, we recommend that the
top-level function receives one or more pointers to arrays, rather than
target-specific vector types.

  • For static dispatch, HWY_TARGET will be the best available target among
    HWY_BASELINE_TARGETS, i.e. those allowed for use by the compiler (see
    quick-reference). Functions inside
    HWY_NAMESPACE can be called using HWY_STATIC_DISPATCH(func)(args) within
    the same module they are defined in. You can call the function from other
    modules by wrapping it in a regular function and declaring the regular
    function in a header.

  • For dynamic dispatch, a table of function pointers is generated via the
    HWY_EXPORT macro that is used by HWY_DYNAMIC_DISPATCH(func)(args) to
    call the best function pointer for the current CPU's supported targets. A
    module is automatically compiled for each target in HWY_TARGETS (see
    quick-reference) if HWY_TARGET_INCLUDE is
    defined and foreach_target.h is included. Note that the first invocation
    of HWY_DYNAMIC_DISPATCH, or each call to the pointer returned by the first
    invocation of HWY_DYNAMIC_POINTER, involves some CPU detection overhead.
    You can prevent this by calling the following before any invocation of
    HWY_DYNAMIC_*: hwy::GetChosenTarget().Update(hwy::SupportedTargets());.

See also a separate
introduction to dynamic dispatch
by @kfjahnke.

When using dynamic dispatch, foreach_target.h is included from translation
units (.cc files), not headers. Headers containing vector code shared between
several translation units require a special include guard, for example the
following taken from examples/skeleton-inl.h:

text
#if defined(HIGHWAY_HWY_EXAMPLES_SKELETON_INL_H_) == defined(HWY_TARGET_TOGGLE)
#ifdef HIGHWAY_HWY_EXAMPLES_SKELETON_INL_H_
#undef HIGHWAY_HWY_EXAMPLES_SKELETON_INL_H_
#else
#define HIGHWAY_HWY_EXAMPLES_SKELETON_INL_H_
#endif

#include "hwy/highway.h"
// Your vector code
#endif

By convention, we name such headers -inl.h because their contents (often
function templates) are usually inlined.

Compiler flags

Applications should be compiled with optimizations enabled. Without inlining
SIMD code may slow down by factors of 10 to 100. For clang and GCC, -O2 is
generally sufficient.

For Clang and GCC, we recommend using dynamic dispatch (see Quick start),
because this avoids the need for extra compiler flags which may be incompatible
with other libraries and always uses the best available instructions. If you
know exactly which CPU you are running on, you can specify that as the baseline
target, which avoids generating code for any older instruction sets. Compiler
flags must match the predefined macro checks for HWY_BASELINE_* in
detect_targets.h. They can also be deduced from the HWY_TARGET_STR in
set_macros-inl.h. For x86, suggested flags are currently:

  • HWY_AVX2: -march=x86-64-v3 -maes -mpclmul, or -march=haswell -maes
  • HWY_AVX3: -march=x86-64-v4, or -march=skx
  • HWY_AVX3_DL: -march=icelake-server
  • HWY_ZEN4: -march=znver4
  • HWY_AVX3_SPR: -march=icelake-server -mavx512fp16 -mavx512bf16
  • HWY_AVX10_2: -march=novalake (requires GCC 16 or Clang 22)

See also the godbolt examples above mentioning -m targets.

For MSVC, we recommend compiling with /Gv to allow non-inlined functions to
pass vector arguments in registers. If intending to use the AVX2 target together
with half-width vectors (e.g. for PromoteTo), it is also important to compile
with /arch:AVX2. This seems to be the only way to reliably generate
VEX-encoded SSE instructions on MSVC. Sometimes MSVC generates VEX-encoded SSE
instructions, if they are mixed with AVX, but not always, see
DevCom-10618264.
Otherwise, mixing VEX-encoded AVX2 instructions and non-VEX SSE may cause severe
performance degradation. Unfortunately, with /arch:AVX2 option, the resulting
binary will then require AVX2. Note that no such flag is needed for clang and
GCC because they support target-specific attributes, which we use to ensure
proper VEX code generation for AVX2 targets.

Strip-mining loops

When vectorizing a loop, an important question is whether and how to deal with
a number of iterations ('trip count', denoted count) that does not evenly
divide the vector size N = Lanes(d). For example, it may be necessary to avoid
writing past the end of an array.

In this section, let T denote the element type and d = ScalableTag<T>.
Assume the loop body is given as a function template void LoopBody(D d, size_t index, size_t max_n).

"Strip-mining" is a technique for vectorizing a loop by transforming it into an
outer loop and inner loop, such that the number of iterations in the inner loop
matches the vector width. Then, the inner loop is replaced with vector
operations.

Highway offers several strategies for loop vectorization:

  • Ensure all inputs/outputs are padded. Then the (outer) loop is simply

    text
    for (size_t i = 0; i < count; i += N) LoopBody<false>(d, i, 0);

    Here, the template parameter and second function argument are not needed.

    This is the preferred option, unless N is in the thousands and vector
    operations are pipelined with long latencies. This was the case for
    supercomputers in the 90s, but nowadays ALUs are cheap and we see most
    implementations split vectors into 1, 2 or 4 parts, so there is little cost
    to processing entire vectors even if we do not need all their lanes. Indeed
    this avoids the (potentially large) cost of predication or partial
    loads/stores on older targets, and does not duplicate code.

  • Process whole vectors and include previously processed elements
    in the last vector:

    text
    for (size_t i = 0; i < count; i += N) LoopBody<false>(d, HWY_MIN(i, count - N), 0);

    This is the second preferred option provided that count >= N
    and LoopBody is idempotent. Some elements might be processed twice, but
    a single code path and full vectorization is usually worth it. Even if
    count < N, it usually makes sense to pad inputs/outputs up to N.

  • Use the Transform* functions in hwy/contrib/algo/transform-inl.h. This
    takes care of the loop and remainder handling and you simply define a
    generic lambda function (C++14) or functor which receives the current vector
    from the input/output array, plus optionally vectors from up to two extra
    input arrays, and returns the value to write to the input/output array.

    Here is an example implementing the BLAS function SAXPY (alpha * x + y):

    text
    Transform1(d, x, n, y, [](auto d, const auto v, const auto v1) HWY_ATTR {
  return MulAdd(Set(d, alpha), v, v1);
});

  • Process whole vectors as above, followed by a scalar loop:

    text
    size_t i = 0;
for (; i + N <= count; i += N) LoopBody<false>(d, i, 0);
for (; i < count; ++i) LoopBody<false>(CappedTag<T, 1>(), i, 0);

    The template parameter and second function arguments are again not needed.

    This avoids duplicating code, and is reasonable if count is large.
    If count is small, the second loop may be slower than the next option.

  • Process whole vectors as above, followed by a single call to a modified
    LoopBody with masking:

    text
    size_t i = 0;
for (; i + N <= count; i += N) {
  LoopBody<false>(d, i, 0);
}
if (i < count) {
  LoopBody(d, i, count - i);
}

    Now the template parameter and third function argument can be used inside
    LoopBody to non-atomically 'blend' the first num_remaining lanes of v
    with the previous contents of memory at subsequent locations:
    BlendedStore(v, FirstN(d, num_remaining), d, pointer);. Similarly,
    MaskedLoad(FirstN(d, num_remaining), d, pointer) loads the first
    num_remaining elements and returns zero in other lanes.

    This is a good default when it is infeasible to ensure vectors are padded,
    but is only safe #if !HWY_MEM_OPS_MIGHT_FAULT!
    In contrast to the scalar loop, only a single final iteration is needed.
    The increased code size from two loop bodies is expected to be worthwhile
    because it avoids the cost of masking in all but the final iteration.

Additional resources

Acknowledgments

We have used farm-sve by Berenger
Bramas; it has proved useful for checking the SVE port on an x86 development
machine.

This is not an officially supported Google product.
Contact: [email protected]

File: docs/index.rst

Highway, a C++ library that provides portable SIMD/vector intrinsics

.. toctree::
:maxdepth: 2
:caption: Contents:

README
quick_reference
design_philosophy
faq
impl_details
instruction_matrix
release_testing_process

File: hwy/contrib/unroller/README.md

Unroller

All contents of the unroller folder are experimental and subject to changes.

Unroller is a templated function that automatically implements common optimizations that are usually handled by compilers when writing scalar code. Modern CPUs operate much more efficiently when non-dependent calculations are packed into an instruction pipeline. For scalar code, this often means a compiler will take a one-line loop, and compile it down to hundreds of lines of machine code in order to fully capture these efficiencies.

As of today (2023-07-06), compilers are not nearly as good at implementing these optimizations for code written in SIMD intrinsics. Unroller is a templated function that takes in an UnrollerUnit of SIMD instructions, and then implements unrolling, reordering, hoisting and tail-handling (URHT optimizations) of arrays of data being processed with SIMD intrinsics.

`UnrollerUnit`

UnrollerUnit and UnrollerUnit2D are a base classes of functions that Unroller needs implemented in order to properly handle URHT. UnrollerUnit has default implementations for all but the Func method, which defines the SIMD operation to be applied. Many examples of how to implement these functions are in the tests.

Doubling values of an array example

text
struct DoubleUnit : UnrollerUnit<DoubleUnit, int, int> {
  using TT = ScalableTag;
  inline Vec<TT> Func(ptrdiff_t idx, Vec<TT> x, Vec<TT> y) {
    TT d;
    return Mul(x, Set(d, 2));
  }
};

Leaving all other methods in their default state, the following code will double all the values in array a and place them in r

text
DoubleUnit dblunit;
int r[N];
Unroller(dblunit, a, r, N);

File: hwy/contrib/sort/README.md

Vectorized and performance-portable Quicksort

Introduction

As of 2022-06-07 this sorts large arrays of built-in types about ten times as
fast as LLVM's std::sort. Note that other algorithms such as pdqsort can be
about twice as fast as LLVM's std::sort as of 2023-06.

See also our
blog post
and paper.

Instructions

Here are instructions for reproducing our results with cross-platform CMake,
Linux, or AWS (SVE, NEON).

CMake, any platform

Please first ensure that Clang (tested with 13.0.1 and 15.0.6) is installed, and
if it is not the default compiler, point the CC and CXX environment variables to
it, e.g.

text
export CC=clang-15
export CXX=clang++-15

Then run the usual CMake workflow, also documented in the Highway README, e.g.:

text
mkdir -p build && cd build && cmake .. && make -j
taskset -c 2 tests/bench_sort

The optional taskset -c 2 part reduces the variability of measurements by
preventing the OS from migrating the benchmark between cores.

Linux

Please first ensure golang, and Clang (tested with 13.0.1) are installed via
your system's package manager.

text
go install github.com/bazelbuild/bazelisk@latest
git clone https://github.com/google/highway
cd highway
CC=clang CXX=clang++ ~/go/bin/bazelisk build -c opt hwy/contrib/sort:all
bazel-bin/hwy/contrib/sort/sort_test
bazel-bin/hwy/contrib/sort/bench_sort

AWS Graviton3

Instance config: amazon linux 5.10 arm64, c7g.8xlarge (largest allowed config is
32 vCPU). Initial launch will fail. Wait a few minutes for an email saying the
config is verified, then re-launch. See IPv4 hostname in list of instances.

ssh -i /path/key.pem ec2-user@hostname

Note that the AWS CMake package is too old for llvm, so we build it first:

text
wget https://cmake.org/files/v3.23/cmake-3.23.2.tar.gz
tar -xvzf cmake-3.23.2.tar.gz && cd cmake-3.23.2/
./bootstrap -- -DCMAKE_USE_OPENSSL=OFF
make -j8 && sudo make install
cd ..

AWS clang is at version 11.1, which generates unnecessary AND instructions
which slow down the sort by 1.15x. We tested with clang trunk as of June 13
(which reports Git hash 8f6512fea000c3a0d394864bb94e524bee375069). To build:

text
git clone --depth 1 https://github.com/llvm/llvm-project.git
cd llvm-project
mkdir -p build && cd build
/usr/local/bin/cmake ../llvm -DLLVM_ENABLE_PROJECTS="clang" -DLLVM_ENABLE_RUNTIMES="libcxx;libcxxabi" -DCMAKE_BUILD_TYPE=Release
make -j32 && sudo make install
text
sudo yum install go
go install github.com/bazelbuild/bazelisk@latest
git clone https://github.com/google/highway
cd highway
CC=/usr/local/bin/clang CXX=/usr/local/bin/clang++ ~/go/bin/bazelisk build -c opt --copt=-march=armv8.2-a+sve hwy/contrib/sort:all
bazel-bin/hwy/contrib/sort/sort_test
bazel-bin/hwy/contrib/sort/bench_sort

The above command line enables SVE, which is currently only available on
Graviton 3. You can also test NEON on the same processor, or other Arm CPUs, by
changing the -march= option to --copt=-march=armv8.2-a+crypto. Note that
such flags will be unnecessary once Clang supports #pragma target for NEON and
SVE intrinsics, as it does for x86.

Results

bench_sort outputs the instruction set (AVX3 refers to AVX-512), the sort
algorithm (std for std::sort, vq for our vqsort), the type of keys being
sorted (f32 is float), the distribution of keys (uniform32 for uniform random
with range 0-2^32), the number of keys, then the throughput of sorted keys (i.e.
number of key bytes output per second).

Example excerpt from Xeon 6154 (Skylake-X) CPU clocked at 3 GHz:

text
[ RUN      ] BenchSortGroup/BenchSort.BenchAllSort/AVX3
      AVX3:          std:     f32: uniform32: 1.00E+06   54 MB/s ( 1 threads)
      AVX3:           vq:     f32: uniform32: 1.00E+06 1143 MB/s ( 1 threads)

Additional results

Thanks to Lukas Bergdoll, who did a thorough performance analysis
on various sort implementations. This helped us identify a performance bug,
caused by obtaining entropy from the OS on each call. This was fixed in #1334
and we look forward to the updated results.

Optimizations for small arrays

Our initial focus was on large arrays. Since the VQSort paper was published,
we have improved its performance for small arrays:

  • Previously, each call to VQSort obtained entropy from the OS. Unpredictable
    seeding does help avoid worst-cases, and the cost is negligible when the
    input size is at least 100K elements. However, the overhead is very costly
    for arrays of just 100 or 1000, so we now obtain entropy only once per
    thread and cache the seeds in TLS. This significantly improves the
    performance on subsequent calls. Users can also explicitly initialize the
    random generator.

  • We also improved the efficiency of our sorting network for inputs shorter
    than half its size. Our approach avoids costly transposes by interpreting
    inputs as a 2D matrix. Previously, we always used 16 rows, which means only
    a single vector lane is active for up to 16 elements. We have added 8x2 and
    8x4 networks which use more lanes when available, and also 4x1 and 8x1
    networks for very small inputs.

  • Previously we also loaded (overlapping) full vectors, with the offsets
    determined by the number of columns. Now we use the minimum vector size
    sufficient for the number of columns, which enables higher IPC on Skylake
    and reduces the cost of unaligned loads.

    Unfortunately this decreases code reuse; VQSort now consists of about 1500
    instructions (https://gcc.godbolt.org/z/ojYKfjPe6). The size of sorting
    networks has nearly doubled to 10.8 KiB, 70% of the total. Although large,
    this still fits comfortably within 32 KiB instruction caches, and possibly
    even in micro-op caches (DSB, 1500-2300 micro-ops), especially given that
    not all instructions are guaranteed to execute.

Study of AVX-512 downclocking

We study whether AVX-512 downclocking affects performance. Using the GHz
reported by perf, we find an upper bound on the effects of downclocking, and
observe that its effect is negligible when compared to scalar code.

This issue has somehow attracted far more attention than seems warranted. An
attempt by Daniel Lemire to measure the
worst-case
only saw a 3% decrease, and Intel CPUs since Icelake, as well as AMD Zen4,
are much less impacted by throttling, if at all. By contrast, "Silver" and
"Bronze" Intel Xeons have more severe throttling and would require a large(r)
speedup from AVX-512 to outweigh the downclocking. However, these CPUs are
marketed towards "entry compute, network and storage" and "small business and
storage server solutions", and are thus less suitable for the high-performance
workloads we consider.

Our test workstation runs Linux (6.1.20-2rodete1-amd64) and has the same Xeon
Gold 6154 CPU used in our paper because its Skylake microarchitecture is the
most (potentially) affected. The compiler is a Clang similar to the LLVM trunk.

We added a new 'cold' benchmark that initializes random seeds, fills an array
with a constant except at one random index, calls VQSort, and then prints a
random element to ensure the computations are not elided. To run it, we build
bench_sort with -DSORT_ONLY_COLD=1 and then invoke
taskset -c 6 setarch -R x86_64 perf stat -r 15 -d bench_sort. The taskset and
setarch serve to reduce variability by avoiding thread migration, and disabling
address space randomization. -r 15 requests 15 runs so that perf can display
the variability of the measurements: < 1% for cycles, instructions, L1 dcache
loads; LLC miss variability is much higher (> 10%) presumably due to the
remaining background activity on this machine.

For our measurements, we use the GHz value reported by perf. This does not
include time spent in the kernel, and is thus noisy for short runtimes. Note
that running perf under sudo is not an option because it results in
"Workload failed: Cannot allocate memory". We see results between 2.6 - 2.9 GHz
when running AVX-512 code. This is relative to 3.0 GHz nominal; we disabled
Turbo Boost via MSR and ran sudo cpupower frequency-set --governor performance
to prevent unnecessary frequency reductions. To the best of our knowledge, the
remaining gap is explained by time spent in the kernel (in particular handling
page faults) and downclocking. Thus an upper-bound for the latter is
(3 - 2.9)/3 to (3 - 2.6)/3, or 1.03 - 1.13x. Such a frequency reduction
would already be negligible compared to the 2-4x increase in work per cycle from
512-bit SIMD relative to 256 or 128-bit SIMD, which is typically less or not at
all affected by downclocking.

To further tighten this bound, we compare AVX-512 code vs. non-AVX-512 code, in
the form of std::sort. Ensuring the remainder of the binary does not use
AVX-512 is nontrivial. Library functions such as memset are known to use
AVX-512, and they would not show up in a disassembly of our binary. Neither
would they raise exceptions if run on a CPU lacking AVX-512 support, because
software typically verifies CPU support before running AVX-512. As a first step,
we take care to avoid calls to such library functions in our test, which is more
feasible with a self-contained small binary. In particular, array
zero-initialization typically compiles to memset (verified with clang-16), so
we manually initialize the array to the return value of an Unpredictable1
function whose implementation is not visible to the compiler. This indeed
compiles to a scalar loop. To further increase confidence that the binary lacks
AVX-512 instructions before VQSort, we replace the initialization loop with
AVX-512 stores. This indeed raises the measured throughput from a fairly
consistent 9 GB/s to 9-15 GB/s, likely because some of the AVX-512 startup now
occurs outside of our timings. We examine this effect in the next section, but
for now we can conclude that because adding AVX-512 makes a difference, the
binary was otherwise not using it. Now we can revert to scalar initialization
and compare the GHz reported for VQSort vs. std::sort. Across three runs, the
ranges are 2.8-2.9 and 2.8-2.8 GHz. Thus we conclude: if there is any
downclocking for a single core running AVX-512 on this Skylake-X CPU, the effect
is under the noise floor of our measurement, and certainly far below any
speedup one can reasonably predict from 512-bit SIMD. We expect this result to
generalize to AMD Zen4 and any Gold/Platinum Intel Xeon.

Study of AVX-512 startup overhead

In the previous section, we saw that downclocking is negligible on our system,
but there is a noticeable benefit to warming up AVX-512 before the sort. To
understand why, we refer to Travis Downs' excellent
measurements
of how Skylake reacts to an AVX-512 instruction: 8-20 us of reduced instruction
throughput, an additional potential halt of 10 us, and then downclocking.
Note that downclocking is negligible on a single core per the previous section.

We choose the array length of 10K unsigned 64-bit keys such that VQSort
completes in 7-10 us. Thus in this benchmark, VQSort (almost) finishes before
AVX-512 is fully warmed up, and the speedup is reduced because the startup costs
are amortized over relatively little data. Across five series of 15 runs, the
average of average throughputs is 9.3 GB/s, implying a runtime of 8.6 us
including startup costs.

Note that the two-valued, almost all-equal input distribution is quite skewed.
The above throughput does not reflect the performance attainable on other
distributions, especially uniform random. However, this choice is deliberate
because Quicksort can terminate early if all values in a partition are equal.
When measuring such a 'best-case' input, we are more likely to observe the cost
of startup overhead in surrounding code. Otherwise, this overhead might be
hidden by the increase in sorting time.

Now let us compare this throughput to the previously mentioned measurement with
AVX-512 warmed up (via slow scatter instructions so that initialization takes
about 100 us, well in excess of the warmup period): 15.2 GB/s, or 5.3 us without
startup cost. It appears the 10 us halt is not happening, possibly because we do
not use SIMD floating-point nor multiplication instructions. Thus we only
experience reduced instruction throughput and/or increased latency. The ratio
between cold and warmed-up time is only 1.6, which is plausible if the Skylake
throttling is actually rounding latencies up to a multiple of four cycles, as
Downs speculates. Indeed a large fraction of the SIMD instructions especially in
the VQSort base case are cross-lane or 64-bit min/max operations with latencies
of 3 cycles on Skylake, so their slowdown might only be 1.3x. The measured 1.6x
could plausibly derive from 7/8 of 1.3x and 1/8 of 4x for single-cycle latency
instructions.

Assuming this understanding of AVX-512 startup cost is valid, how long does it
remain active before the CPU reverts to the previous settings? The CPU cannot
know what future instructions are coming, and to prevent unnecessary
transitions, it has a hysteresis (delay after the last AVX-512 instruction
before shutting down) which Downs measures as 680 us. Thus our benchmark
subsequently sleeps for 100 ms to ensure the next run of the binary sees the
original CPU state. Indeed we find for the five series that the slopes of the
lines of best fit are negative in one case, positive in two, and flat in two,
indicating there is no consistent pattern of benefit for earlier or later runs.

What are the implications for users of VQSort? If the surrounding code executes
an AVX-512 instruction at least every 500 us, then AVX-512 remains active and
any call to VQSort will benefit from it, no matter how small the input.
This is a reasonable expectation for modern systems whose designers were aware
of data-oriented programming principles, because many (though not all) domains
and operations can benefit from SIMD. By contrast, consider the case of dropping
VQSort into an existing legacy system that does not yet use SIMD. In the case of
10K input sizes, we still observe a 2.3x speedup vs. std::sort. However, the
following code may have to deal with throttling for the remainder of the 20 us
startup period. With VQSort we have 8.6 us runtime plus up to 11.4 us throttled
code (potentially running at quarter speed) plus the remaining 3/4 of 11.4 for a
total of 28.6. With std::sort we have 19.5 us runtime plus 20 us of normal
subsequent code, or 39.5 us. Thus the overall speedup for the 20 us region plus
VQSort shrinks to 1.4x, and it is possible to imagine an actual slowdown for
sufficiently small inputs, when factoring in the throttling of subsequent code.
This unfortunate 'beggar thy neighbor' effect cannot be solved at the level of
individual building blocks such as a sort, and must instead be addressed at the
system level. For example:

  • vectorizing more and more parts of the code to amortize startup cost;
  • relying on newer CPUs than Skylake (launched 2015!) which have little or no
    AVX-512 startup overhead, such as Intel Icelake (2021) or AMD Zen4 (2022);
  • ensuring sorts (or anything else using AVX-512) process at least 100 KiB
    of data, such that the expected speedup outweighs any startup cost.

Any of these solutions are sufficient to render AVX-512 startup overhead a
non-issue.

Comparison with Intel's x86-simd-sort and vxsort

Our May 2022 paper compared performance with ips4o and std::sort. We now add
results for Intel's x86-simd-sort,
released as open source around October 2022, and
vxsort. We find that
VQSort is generally about 1.4 times as fast as either, and in a few cases equal
or up to 2% slower.

Note that vxsort was open-sourced around May 2020; we were unaware of it at the
time of writing because it had been published in the form of a blog series. We
imported both from Github on 2023-06-06 at about 10:15 UTC. Both are integrated
into our bench_sort, running on the same Linux OS and Xeon 6154 CPU mentioned
above. We use uniform random inputs, because vxsort and x86-simd-sort appear to
have much less robust handling of skewed input distributions. They choose the
pivot as the median of three keys, or of 64 bytes, respectively. By contrast,
VQSort draws a 384 byte sample and analyzes their distribution, which improves
load balance and prevents recursing into all-equal partitions. Lacking this, the
other algorithms are more vulnerable to worst-cases. Choosing uniform random
thus prevents disadvantaging the other algorithms.

We sample performance across a range of input sizes and types:

  • To isolate the performance of the sorting networks used by all three
    algorithms, we start with powers of two up to 128. VQSort is generally the
    fastest for 64-bit keys with the following exceptions: tie with vxsort at
    N=2 (537 MB/s), slower than vxsort at N=16 (2114 vs. 2147), tie with
    x86-simd-sort at N=32 (2643 MB/s). Note that VQSort is about 1.6 times as
    fast as both others for N=128; possibly because its 2D structure enables
    larger networks.

  • The kPow10 mode in bench_sort measures power of ten input sizes between
    10 and 100K. Note that this covers non-power of two sizes, as well as the
    crossover point between sorting networks and Quicksort recursion. The
    speedups of VQSort relative to x86-simd-sort range from 1.33 to 1.81
    (32-bit keys), and 1.25 to 1.68 (64-bit keys), with geomeans of 1.48 and
    1.44. The speedups of VQSort relative to vxsort range from 1.08 to 2.10
    (32-bit keys), and 1.00 to 1.47 (64-bit keys), with geomeans of 1.41 and
    1.20. Note that vxsort matches VQSort at 10 64-bit elements; in all other
    cases, VQSort is strictly faster.

  • Finally, we study the effect of key type at a fixed input size of 10K
    elements. x86-simd-sort requires AVX512-VBMI2 for int16, which our CPU does
    not support. Also, both other algorithms do not support 128-bit keys, thus
    we only consider 32/64-bit integer and float types. The results in MB/s are:

    Type VQSort x86-simd-sort vxsort
    f32 1551 798 823
    f64 1773 1147 745
    i32 1509 1042 968
    i64 1365 1043 1145

    VQSort is the fastest for each type, in some cases even about twice as fast.
    Interestingly, vxsort performs at its best on i64, whereas the others are at
    their best for f64. A potential explanation is that this CPU can execute two
    f64 min/max per cycle, but only one i64.

In conclusion, VQSort is generally more efficient than vxsort and x86-simd-sort
across a range of input sizes and types. Occasionally, it is up to 2% slower,
but the geomean of its speedup (32-bit keys and power-of-ten sizes) vs. vxsort
is 1.41, and 1.48 vs. x86-simd-sort.

Explore Related Technologies & Topics

View All 9,111+ Repositories →

Discover similar high-velocity repositories, agent skills, and OpenAPI specifications across the ecosystem.

#avx Browse avx catalog → #avx-512 Browse avx-512 catalog → #avx-instructions Browse avx-instructions catalog → #avx2 Browse avx2 catalog → #avx512 Browse avx512 catalog → #intrinsics Browse intrinsics catalog → ⚡ MCP Servers Model Context Protocol → 🧠 Agent Skills Prompt & rule files → 🔌 OpenAPI Specs REST & Swagger schemas →