---
title: "7. Single-thread optimisation"
url: https://cpuperf.com/learn/single-thread-optimisation/
source: https://github.com/usamahz/cpu-performance-engineering/blob/deb5a0bac46760503b6f4a2608bdfed470c8532e/README.md#L337
commit: deb5a0bac46760503b6f4a2608bdfed470c8532e
---
## 7. Single-thread optimisation

A loop the compiler reports as vectorised can still run at scalar speed: a float reduction stays one serial chain until reassociation is permitted.

### Data layout and loop transforms

- [Intel Optimization Reference Manual](https://www.intel.com/content/www/us/en/content-details/671488/intel-64-and-ia-32-architectures-optimization-reference-manual-volume-1.html) - Where Intel states when a structure of arrays beats an array of structures, strided and hybrid cases included.
- [ispc: A SPMD Compiler for High-Performance CPU Programming](https://pharr.org/matt/assets/ispc.pdf) - Measures one kernel in both layouts and traces the gain to the gathers the array-of-structures form forces.
- [A Data Locality Optimizing Algorithm](https://dl.acm.org/doi/10.1145/113445.113449) - Defines interchange, skewing, reversal and tiling as one family and proves when each keeps a loop nest legal.
- [The Cache Performance and Optimizations of Blocked Algorithms](https://dl.acm.org/doi/10.1145/106972.106981) - Traces the drops in a blocked loop's speed curve to self-interference misses, and shows when copying a tile pays.
- [Auto-Vectorization in LLVM](https://llvm.org/docs/Vectorizers.html) - Where LLVM lists what its loop and SLP vectorisers accept: interleaving, reductions, if-conversion and runtime checks.

Reproduce it: [misc/benchmarks/07-aos-vs-soa-simd](https://cpuperf.com/benchmarks/07-aos-vs-soa-simd/), array of structs against structure of arrays, scalar against NEON.

### SIMD instruction sets

- [Intel Intrinsics Guide](https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html) - Maps each intrinsic to its instruction and CPUID flag, with the vendor's latency and throughput per microarchitecture.
- [Intel Software Developer Manuals](https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html) - The normative semantics of every Intel vector instruction, with the masking, rounding and fault rules intrinsics hide.
- [Introduction to SVE](https://support.arm.com/documentation/102476/latest/) - Where Arm explains vector-length-agnostic loops and predication, the model that removes remainder loops entirely.
- [Arm C Language Extensions](https://arm-software.github.io/acle/) - The specification the NEON and SVE intrinsics come from, so it settles what a compiler must accept and what is a bug.
- [Arm Architecture Reference Manual for A-profile architecture](https://support.arm.com/documentation/ddi0487/latest/) - The normative definition of NEON, SVE and SVE2 instructions and of the scalable vector and predicate register model.

### SIMD libraries and measured kernels

- [Highway](https://github.com/google/highway) - Defines sizeless vector types with run-time dispatch, so one source serves SVE and every fixed-width ISA.
- [xsimd](https://github.com/xtensor-stack/xsimd) - Fixes a batch type per ISA and width, the compile-time vector length model, and still reaches NEON and SVE.
- [Faster Base64 Encoding and Decoding Using AVX2 Instructions](https://arxiv.org/abs/1704.00605) - Where shuffle-based lookup replacing a byte loop is worked through step by step, with the measurement method spelt out.
- [Parsing Gigabytes of JSON per Second](https://arxiv.org/abs/1902.08318) - Shows branch-free structural indexing with carry-less multiply and shuffles, measured against conventional parsers.
- [simdjson](https://github.com/simdjson/simdjson) - Where that technique ships, with a kernel per ISA and the harness that keeps its published comparisons reproducible.
- [Hyperscan: A Fast Multi-pattern Regex Matcher for Modern CPUs](https://www.usenix.org/conference/nsdi19/presentation/wang-xiang) - Decomposes regexes into string and automaton pieces so both run on SIMD, the design inside the matcher Snort embeds.

### Branchless code and bit manipulation

- [Branch Prediction and the Performance of Interpreters](https://inria.hal.science/hal-01100647) - Counter evidence that current predictors absorb interpreter dispatch, so a branch removal must be measured, not assumed.
- [Hacker's Delight, 2nd Edition](https://www.informit.com/store/hackers-delight-9780321842688) - Derives the branch-free integer tricks, division by a constant among them, with proofs rather than as a catalogue.
- [Faster sorted array unions by reducing branches](https://lemire.me/blog/2021/07/14/faster-sorted-array-unions-by-reducing-branches/) - A worked branchless merge with code whose gain vanishes when the compiler emits no conditional move.
- [Array Layouts for Comparison-Based Searching](https://arxiv.org/abs/1509.05053) - Measures branch-free search over sorted, Eytzinger and B-tree layouts, the winner changing with size and prefetch.
- [Faster Population Counts Using AVX2 Instructions](https://arxiv.org/abs/1611.07612) - Shows a carry-save adder tree in vector registers beating the dedicated instruction, timed as the minimum of many runs.