Pangram verdict · v3.3
We believe that this document is a mix of AI-generated, AI-assisted, and human-written content
AI likelihood · overall
MixedArticle text · 1,498 words · 7 segments analyzed
Trust your compiler C++ programmers absorb a lot of performance wisdom by osmosis: fast inverse square root1, XOR swap2, hand-unrolled loops3, Duff’s device4, exceptions are slow, virtual calls are slow, division is slow, lookup tables often beat maths. Even if once true, hardware, software, and compiler advances have drastically changed the landscape to the point where many are not now. John Carmack’s DEC Alpha and Pentium Pro bear little resemblance to a modern Zen 5 x86_64 core - a piece of silicon who’s branch predictor alone likely has more transistors than all the workstations in the iD offices of the time. On top of that, LLVM’s Clang and GNU’s GCC are advanced enough to write optimal code from the naive input. For instance, both compilers have optimisation passes that essentially check if a code segment is actually just popcount in disguise5. In fact, writing “clever” code may be “worse” code; it could obscure intent from the optimiser, potentially costing you vectorisation, inlining, and target-specific lowering. In this article we walk through a few old tricks, compare them with the obvious version, and see how they behave. The numbers below were produced on: Ubuntu 24.04 LTS (With updated Linux kernel 6.18.1) AMD Ryzen 9 9950X, 16 cores / 32 threads 128 GB of DDR5/3600 memory Clang 21.1.1, -O3 -ffast-math -mtune=native The post comes with benchmark code. All benchmarks use Google Benchmark. 6 Content Part 1: New dogs, old tricks Fast inverse square root Popcount and bit-twiddling Numerical recipes and row pointers const& everywhere vs forwarding intent Part 2: The library Ranges and algorithms Exceptions vs std::expected vs error codes Virtual vs static polymorphism How to use the benchmarks Closing remarks Part 1: New dogs, old tricks Fast inverse
square root The Q_rsqrt from Quake III7, reproduced here: float Q_rsqrt( float number ) { long i; float x2, y; const float threehalfs = 1.5F;
x2 = number * 0.5F; y = number; i = * ( long * ) &y; i = 0x5f3759df - ( i >> 1 ); y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); return y; } There are numerous articles explaining how this works1, which we will skip here. In short, late 90s CPUs floating point units were nothing like today’s. During the development of Quake 3 Arena, iD’s developers discovered that a lot of time was being spent determining vertex normals used for their new lighting model. Much of this time was being spent in one operation: the inverse square root. Their approach was to forgo accuracy, and take a “estimate and improve” approach for this one operation. It could beat the naive 1.0f / sqrtf(x) by a wide margin: FSQRT and FDIV could take over 500 cycles in the 8087 FPU, while iD’s method used cheap integer operations plus one Newton iteration 8. Modern CPUs Intel introduced rsqrtss and rsqrtps to the x86 family of architectures with SSE 9; AVX later added the vrsqrtss and vrsqrtps forms for wider SIMD widths. These instructions compute an approximate reciprocal square root directly, with a documented error bound and substantially lower latency than x87 fsqrt10.
ARMv8/AArch64 has comparable reciprocal-square-root estimate instructions11: ISAScalarPackedWidthx86-64 SSErsqrtssrsqrtps4 x f32x86-64 AVXvrsqrtssvrsqrtps8 x f32ARMv8 NEONfrsqrte (scalar)frsqrte4 x f32 Why this matters? Writing this code in modern C++ might look something like: constexpr float Q_rsqrt(float number) noexcept { static_assert(sizeof(float) == sizeof(std::uint32_t)); auto i = std::bit_cast<std::uint32_t>(number); auto magic = 0x5f3759dfu - (i >> 1); auto y = std::bit_cast<float>(magic); return y * (1.5f - (number * 0.5f * y * y)); } Compare that with the naive version: constexpr float naive_rsqrt(float x) noexcept { return 1.0f / std::sqrt(x); } Now compare the relevant assembly produced with -std=c++23 -O3 -ffast-math -march=znver4 on Compiler Explorer using Clang 21.1.0. The benchmark run used -march=native; the assembly excerpt uses znver4 so the target is explicit. The -ffast-math part matters: it lets the compiler make aggressive, potentially lossy floating-point assumptions1213, so this example assumes positive, finite inputs and does not preserve every strict IEEE floating-point edge case. Q_rsqrt(float): movd eax, xmm0 sar eax mov ecx, 1597463007 sub ecx, eax mulss xmm0, dword ptr [rip + .LCPI0_0] movd xmm1, ecx movdqa xmm2, xmm1 mulss xmm2, xmm1 mulss xmm0, xmm2 addss xmm0, dword ptr [rip + .LCPI0_1] mulss xmm0,
xmm1 ret
naive_rsqrt(float): vrsqrtss xmm1, xmm0, xmm0 vmulss xmm0, xmm0, xmm1 vfmadd213ss xmm0, xmm1, dword ptr [rip + .LCPI1_0] vmulss xmm1, xmm1, dword ptr [rip + .LCPI1_1] vmulss xmm0, xmm1, xmm0 ret Benchmarking This makes sense in theory, but is it actually true now? BenchmarkTime (scalar)Time (n=1024)Time (n=65536)Q_sqrt380 ns24.5 ns1865 nsnaive_rsqrt373 ns25.0 ns2161 ns The scalar case is effectively a draw, with the obvious version slightly ahead.
In the array kernels, the Quake version is somewhat faster in this particular run, but not in a way that justifies the trick as a default: the source is less clear, has a narrower useful domain, and is still only competitive because the compiler and CPU are already doing the hard work. Additionally, the naive way provides you with explicit bounds on error. Take-away Let the compiler do the work. You get comparable performance, better-defined code, and an implementation that says what it means. Popcount and bit-twiddling C++20 gave us <bit>: std::popcount, std::countl_zero, std::countr_zero, std::bit_width, std::has_single_bit, and friends14. On x86, when the relevant target features are enabled, many of these map to a single instruction: Functionx86-64 (BMI/POPCNT)ARMv8std::popcountpopcntcnt + addvstd::countl_zerolzcntclzstd::countr_zerotzcntrbit + clz Compare: constexpr int modern(std::uint64_t x) noexcept { return std::popcount(x); }
constexpr int kernighan(std::uint64_t x) noexcept { int c = 0; while (x != 0U) { x &= x - 1U; ++c; } return c; }
constexpr int swar(std::uint64_t x) noexcept { x = x - ((x >> 1) & 0x5555'5555'5555'5555ULL); x = (x & 0x3333'3333'3333'3333ULL) + ((x >> 2) &
0x3333'3333'3333'3333ULL); x = (x + (x >> 4)) & 0x0f0f'0f0f'0f0f'0f0fULL; return static_cast<int>((x * 0x0101'0101'0101'0101ULL) >> 56); } With -march=native and popcnt available, pop_modern can be one instruction. More interestingly, modern compilers may recognise the old tricks as popcount too: in this benchmark configuration, the Kernighan loop and SWAR version also collapse to popcnt. Without the target instruction, the distinction comes back: Kernighan is a data-dependent loop, while SWAR is a short sequence of shifts and masks. The standard spelling makes the intent explicit either way. Before C++20 you could use __builtin_popcountll with GCC/Clang or __popcnt64 with MSVC. std::popcount is the portable spelling15, and on targets without a hardware popcnt, the implementation can still provide an efficient software fallback. Benchmarks BenchmarkTimeBM_popcount_modern94.5 nsBM_popcount_kernighan94.5 nsBM_popcount_swar94.5 ns Take-away Use <bit>, unless you’re targeting a freestanding embedded environment that doesn’t ship it. Numerical recipes and row pointers Part of the inherited wisdom is that row-pointer access to a matrix is faster than index calculation. That was easier to believe when multiplication was more expensive, address-generation hardware was less capable, and compilers had less room to simplify indexing. Numerical Recipes in C — the well-known red book by Press et al. — also helped popularise this style. Its dmatrix/nrutil helpers use row indirection so algorithms can be written with [i][j] addressing, preserving mathematical notation and making transcriptions from Fortran more direct. That can be a reasonable interface choice; it is not, by itself, a performance win.
For the interested reader, the benchmark code contains three implementations of a matrix class: flat_matrix (access is done via multiplication, contiguous data) nr_matrix (access is done via row-pointer dereferencing, contiguous data) scattered_matrix (the same as nr_matrix, except the data is not stored contiguously: some junk is allocated between the rows) nr_matrix and scattered_matrix define operator[] returning a float *. Both of them store an array of pointers - pointing to the row of a matrix, the operator[] then returns the indexed row pointer. Benchmarking We run two kernels over these matrices: a row-major sum and a column-major sum. The main result is not “multiplication is free” or “row pointers are always bad”; it is that layout and traversal order dominate. The contiguous flat and Numerical Recipes-style layouts are close to one another. The deliberately scattered layout falls apart, especially once the working set is large. BenchmarkTime (400 x 400)Time (4000 x 4000)flat_matrix row-major kernel6062 ns987614 nsnr_matrix row-major kernel6065 ns987632 nsscattered_matrix row-major kernel6171 ns2323394 nsflat_matrix column-major kernel33148 ns11258036 nsnr_matrix column-major kernel36418 ns11450827 nsscattered_matrix column-major kernel39054 ns14800609 ns Take-away Avoid indirection just because it looks clever or historically familiar. Prefer contiguous storage and traversal patterns that match it. If possible, avoid writing your own linear algebra kernels at all: Eigen, BLAS/LAPACK, GLM, or a vendor-tuned library will usually be a better starting point. const& everywhere vs forwarding intent Another habit many of us inherited is: “always pass by const&; copies are expensive”. That is still a good rule when the function merely observes its argument: double norm(std::vector<double> const& xs); But it is the wrong abstraction for wrapper code. If a function’s job is to pass arguments on to something else, const& destroys information. An rvalue becomes a const lvalue, move construction is disabled.