## File: README.md # Efficient and performance-portable vector software [//]: # (placeholder, do not remove) Highway is a C++ library that provides portable SIMD/vector intrinsics. [Documentation](https://google.github.io/highway/en/master/) 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](https://github.com/kfjahnke/zimt/blob/main/examples/multi_isa_example/multi_simd_isa.md). **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: - [SIMD programming with Highway talk](https://www.youtube.com/watch?v=R57biOOhnJM) - [SIMD for C++ Developers](http://const.me/articles/simd/simd.pdf) - [Algorithms for Modern Hardware](https://en.algorithmica.org/hpc/) - [Optimizing software in C++](https://agner.org/optimize/optimizing_cpp.pdf) - [Improving performance with SIMD intrinsics in three use cases](https://stackoverflow.blog/2020/07/08/improving-performance-with-simd-intrinsics-in-three-use-cases/) ## Examples Online demos using Compiler Explorer: - [multiple targets with dynamic dispatch](https://gcc.godbolt.org/z/KM3ben7ET) (more complicated, but flexible and uses best available SIMD) - [single target using -m flags](https://gcc.godbolt.org/z/rGnjMevKG) (simpler, but requires/only uses the instruction set enabled by compiler flags) 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. * Audio: [Zimtohrli perceptual metric](https://github.com/google/zimtohrli) * Browsers: Chromium (+Vivaldi), Firefox (+floorp / foxhound / librewolf / Waterfox) * Computational biology: [RNA analysis](https://github.com/bnprks/BPCells), [long-sequence preprocessing](https://github.com/OpenGene/fastplong) * Computer graphics: ghostty-org/ghostty, [Sparse voxel renderer](https://github.com/rools/voxl), [tgfx 2D Graphics library](https://github.com/Tencent/tgfx) * Cryptography: google/distributed_point_functions, google/shell-encryption * Data structures: bkille/BitLib * Image codecs: eustas/2im, [Grok JPEG 2000](https://github.com/GrokImageCompression/grok), [JPEG XL](https://github.com/libjxl/libjxl), [JPEGenc](https://github.com/osamu620/JPEGenc), [Jpegli](https://github.com/google/jpegli), [libaom](https://aomedia.googlesource.com/aom/), [OpenHTJ2K](https://github.com/osamu620/OpenHTJ2K) * Image processing: awxkee/aire, cloudinary/ssimulacra2, [libvips](https://github.com/libvips/libvips), m-ab-s/media-autobuild_suite, * Image viewers: AlienCowEatCake/ImageViewer, diffractor/diffractor, [Lux panorama/image viewer](https://bitbucket.org/kfj/pv/), mirillis/jpegxl-wic * Information retrieval: [iresearch database index](https://github.com/iresearch-toolkit/iresearch), michaeljclark/zvec, [nebula interactive analytics / OLAP](https://github.com/varchar-io/nebula), [`ScaNN` Scalable Nearest Neighbors](https://github.com/google-research/google-research/tree/7a269cb2ce0ae1db591fe11b62cbc0be7d72532a/scann), * Machine learning: array2d/deepx, [gemma.cpp](https://github.com/google/gemma.cpp), Tensorflow, Numpy, zpye/SimpleInfer * Programming languages: [AOT-compiled python](https://github.com/exaloop/codon), oven-sh/bun, V8/V8, yinqiwen/rapidudf * Robotics: [MIT Model-Based Design and Verification](https://github.com/RobotLocomotion/drake) * Vector search: 1yefuwang1/vectorlite, vespa-engine/vespa Other * [Evaluation of C++ SIMD Libraries](https://www.mnm-team.org/pub/Fopras/rock23/): "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](https://github.com/kfjahnke/zimt): C++11 template library to process n-dimensional arrays with multi-threaded SIMD code * [vectorized Quicksort](https://github.com/google/highway/tree/master/hwy/contrib/sort) ([paper](https://arxiv.org/abs/2205.05982)) Highway can also be installed via a package manager or from a repository: Click to expand BSD repositories * [DragonFlyBSD](https://github.com/DragonFlyBSD/DPorts/tree/master/devel/highway) * [FreeBSD](https://cgit.freebsd.org/ports/tree/devel/highway) * [GhostBSD](https://github.com/ghostbsd/ghostbsd-ports/tree/main/devel/highway) * [MidnightBSD](https://www.midnightbsd.org/mports/devel/highway/README.html) Click to expand cross platform package repositories * [conan-io](https://conan.io/center/recipes/highway) * [conda-forge](https://anaconda.org/channels/conda-forge/packages/libhwy/overview) * [EasyBuild](https://docs.easybuild.io/version-specific/supported-software/h/Highway/) * [Homebrew](https://formulae.brew.sh/formula/highway) * [microsoft/vcpkg](https://vcpkg.io/en/package/highway) * [spack](https://packages.spack.io/package.html?name=highway) * [xmake-io/xmake-repo](https://github.com/xmake-io/xmake-repo/tree/dev/packages/h/highway) Click to expand linux package repositories Obtained from [repology](https://repology.org/project/highway-simd-library/versions) [](https://repology.org/project/highway-simd-library/versions) Click to expand Windows package repositories * [fd00/yacp](https://github.com/fd00/yacp/tree/master/highway) * [MSYS2](https://packages.msys2.org/search?t=binpkg&q=highway) Click to expand other operating systems and environments where Highway has been used * [OPNsense](https://opnsense.org/) * [Xilinx/Vitis_Libraries](https://github.com/Xilinx/Vitis_Libraries) ## 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](g3doc/release_testing_process.md) for details. ### Related modules 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](https://github.com/vectorclass). It includes many functions including a complete math library. If you have existing code using x86/NEON intrinsics, you may be interested in [SIMDe](https://github.com/simd-everywhere/simde), which emulates those intrinsics using other platforms' intrinsics or autovectorization. [xSIMD](https://github.com/xtensor-stack/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](https://github.com/ashvardanian/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](https://github.com/google/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](https://github.com/google/highway/issues/1279). ## Building highway - Using vcpkg highway is now available in [vcpkg](https://github.com/Microsoft/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](https://github.com/Microsoft/vcpkg) on the vcpkg repository. ## Quick start You can use the `benchmark` inside examples/ as a starting point. A [quick-reference page](g3doc/quick_reference.md) briefly lists all operations and their parameters, and the [instruction_matrix](g3doc/instruction_matrix.md) indicates the number of instructions per operation. The [FAQ](g3doc/faq.md) 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` (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` 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`. 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](g3doc/quick_reference.md)). 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](g3doc/quick_reference.md)) 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](https://github.com/kfjahnke/zimt/blob/multi_isa/examples/multi_isa_example/multi_simd_isa.md) 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`: ``` #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](https://developercommunity.visualstudio.com/t/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`. 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 ``` for (size_t i = 0; i < count; i += N) LoopBody(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: ``` for (size_t i = 0; i < count; i += N) LoopBody(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`): ``` 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: ``` size_t i = 0; for (; i + N <= count; i += N) LoopBody(d, i, 0); for (; i < count; ++i) LoopBody(CappedTag(), 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: ``` size_t i = 0; for (; i + N <= count; i += N) { LoopBody(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 * [Highway introduction (slides)](g3doc/highway_intro.pdf) * [Overview of instructions per operation on different architectures](g3doc/instruction_matrix.md) * [Design philosophy and comparison](g3doc/design_philosophy.md) * [Implementation details](g3doc/impl_details.md) ## Acknowledgments We have used [farm-sve](https://gitlab.inria.fr/bramas/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: janwas@google.com --- ## 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 ``` struct DoubleUnit : UnrollerUnit { using TT = ScalableTag; inline Vec Func(ptrdiff_t idx, Vec x, Vec 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` ``` 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](https://opensource.googleblog.com/2022/06/Vectorized%20and%20performance%20portable%20Quicksort.html) and [paper](https://arxiv.org/abs/2205.05982). ## 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. ``` export CC=clang-15 export CXX=clang++-15 ``` Then run the usual CMake workflow, also documented in the Highway README, e.g.: ``` 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. ``` 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: ``` 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: ``` 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 ``` ``` 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: ``` [ 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](https://github.com/Voultapher/sort-research-rs/blob/main/writeup/intel_avx512/text.md) 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](https://lemire.me/blog/2018/08/15/the-dangers-of-avx-512-throttling-a-3-impact/) 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](https://travisdowns.github.io/blog/2020/01/17/avxfreq1.html#summary) 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](https://github.com/intel/x86-simd-sort), released as open source around October 2022, and [vxsort](https://github.com/damageboy/vxsort-cpp/tree/master). 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.