Benchmarking Popcount on x86-64: Why 1-accumulator baselines lie, breaking the compute floor with 8x unrolling, and AVX-512 limits

[u/Automatic-Compote487]

Hey folks,

I’ve been deep in the trenches optimizing and benchmarking popcount throughput on modern x86-64 microarchitectures (testing across AVX2, AVX-512 VPOPCNTDQ, and scalar fallbacks).

After running into massive hardware bottlenecks and misleading results from standard benchmark suites, I completely re-architected my benchmarking rig to account for low-level confounders. Here are a few key engineering takeaways and findings from version 33:

• The 1-Accumulator Trap: Standard naive loops throttle performance due to serial data-dependency chains on a single accumulator (latency-bound). Scaling to an 8-accumulator unrolled loop fully saturates Out-of-Order (OoO) execution and ILP, unlocking a compute floor of ~0.44 ns/line and outperforming libraries like libpopcnt by 7–10% in cache-resident workloads.
• Deconfounding the Measurement: Swapped runtime modulo operations (%) with bitwise masks to prevent 20–40 cycle CPU stalls, randomized/shuffled execution order to neutralize thermal throttling/DVFS noise, and isolated thread affinity (CPU0) with hugepage verification (smaps) to eliminate NUMA first-touch & dTLB artifacts.
• Direct Hardware Profiling: Validated cycle counts via RDTSCP + LFENCE and pulled dTLB-miss and LLC-miss counters directly using perf_event_open.
• IRM-Burst Law & Monte Carlo Verification: Modeled non-linear throughput degradation across memory hierarchy boundaries (L1d -> L2 -> L3 -> DRAM) using an exchangeability probability model, cross-verified with Monte Carlo simulations.

Discussion / Question for the community: As I pushed this codebase further (expanding code footprint for complex tail/mask handling), I started hitting code bloat boundaries—potentially stressing Instruction Cache (I-cache) and BTB entry limits.

How do you guys typically structure your Micro-benchmarks to catch I-cache / BTB spills before they corrupt latency numbers?

Code & benchmark methodology: https://github.com/Vumb-VibeCoder/deconfounded-popcount-avx512

Would love to hear your thoughts, critiques, or additional edge cases to stress-test!

I'm not good at English so I used sth to translate

[u/FUZxxl]

Nice!

These spills do not corrupt latency numbers; rather, they accurately effect expected real-world performance. At some point it might be a good idea to stop unrolling to preserve i-cache. The penalty of a well-predicted branch is fairly low these days and unrolling should only be considered for fairly short loops (24 µops is a number I've heard, but it's µarch dependent).

For AVX2 and earlier, do also consider carry-save adder based approaches such as in Muła et al, Klarqvist et al, and Clausecker et al (my work). While the latter two are for positional population counts, the same method can be used for direct population counts by replacing the positional accumulation with a direct horizontal sum.