Eight histograms are faster than one

01One loop, three-point-seven million pixels

Before the interpreter can find timing marks or bubbles, it has to decide which pixels are ink. Otsu's method picks that threshold from the page's luminance histogram: 256 bins, one increment per pixel, ~3.7 million increments per pass, up to two passes per page. The loop could hardly look more innocent:

let mut hist = [0u32; 256];
for &p in pixels {
    hist[p as usize] += 1;
}

It reads memory perfectly sequentially — the previous explainer's lesson, feed the cache, is already satisfied. And it was still the slowest thing in page preparation. The problem isn't where the loop reads; it's what the data makes it do.

02A run of blank paper is a traffic jam

A modern core happily executes four or more instructions per cycle — if they're independent. But hist[p] += 1 is a read-modify-write, and when the next pixel has the same value, the next increment must wait for this one's store to land before it can load the count back. Scanned ballots are almost nothing but long runs of identical pixels: blank paper, black border. One bin, one chain of increments, each waiting a few cycles for the last. The core idles.

Give each of eight consecutive pixels its own histogram, though, and a run becomes eight independent chains the out-of-order engine overlaps for free. Watch the same 24-pixel run of blank paper (value 230) flow through both versions — each bar is one increment on a cycle timeline:

03The fix: interleave, then sum

The change is exactly that picture, in 49 lines. Accumulate into eight shard histograms round-robin, then sum the shards. Addition commutes, so the merged histogram — and therefore Otsu's threshold — is identical to the single-histogram version:

const HISTOGRAM_SHARDS: usize = 8;

let mut shards = [[0u32; 256]; HISTOGRAM_SHARDS];
let chunks = pixels.chunks_exact(HISTOGRAM_SHARDS);
let remainder = chunks.remainder();
for chunk in chunks {
    for (shard, &p) in shards.iter_mut().zip(chunk.iter()) {
        shard[p as usize] += 1;   // pixel i goes to shard i % 8
    }
}
for &p in remainder {
    shards[0][p as usize] += 1;
}

let mut hist = [0u32; 256];
for shard in &shards {
    for (total, &count) in hist.iter_mut().zip(shard.iter()) {
        *total += count;          // counts commute: same histogram
    }
}

04The data decides

Here's the part that makes this an optimization for scanners rather than for loops in general. On run-heavy data the single histogram serializes and sharding wins big. On uniformly random pixels, consecutive increments almost never hit the same bin — the naive loop is already parallel by accident, and sharding's bookkeeping makes it slightly slower. Both loops below advance at their measured real-world rates:

05So… SIMD?

Reasonable guess — this is a hot pixel loop, and "make it parallel" usually means vector lanes. But a histogram increment can't be vectorized: the write address depends on the data (shard[p]), which is a scatter with possible lane conflicts, and AVX2 (the x86-64-v3 target our release builds use) has neither scatter stores nor conflict detection. The compiler agrees. Here's the hot loop it actually emits — scalar increments, one per shard base:

; the sharded hot loop: scalar, but eight independent chains
movzbl  (%r14,%rcx), %edx          ; p = pixel
incl    8(%rsp,%rdx,4)             ; shard 0's bin p
movzbl  1(%r14,%rcx), %edx
incl    1032(%rsp,%rdx,4)          ; shard 1 — 1 KiB away
; … through shard 7 at 7176(%rsp)

where SIMD does show up

; the shard merge: addresses no longer depend on the data,
; so LLVM vectorizes it — 8 counts per instruction
vmovdqu 8(%rsp), %ymm0
vpaddd  1032(%rsp), %ymm0, %ymm0
vpaddd  2056(%rsp), %ymm0, %ymm0
; … one vpaddd per shard, <1% of the runtime

That contrast is the whole story: the moment the addresses stop depending on the data (the merge), the optimizer happily vectorizes. Inside the hot loop it can't — and it also won't invent the sharding transform for you, because splitting one histogram into eight is a change to your data structures, not your instructions. The naive loop compiles to the same scalar shape (LLVM even unrolls it 8×), but all eight increments funnel into one array, so on run-heavy data they still execute single-file. The 2× is pure out-of-order execution being given eight things to do instead of one.

06Why the threshold can't change

Same integers, same answer. Every pixel still increments exactly one counter; the shards are summed bin-by-bin; integer addition commutes and can't overflow here (a full page has ~3.7M pixels; the counters hold 4.2 billion). A property test in the commit checks the sharded histogram against a naive one across arbitrary inputs, and since Otsu's threshold is a pure function of the histogram, an identical histogram means an identical threshold — and identical binarized pages, timing marks, and scores downstream. The result: page preparation, which runs on every sheet before any interpretation can start, takes about half the time it used to.

07Check your understanding

Six questions — half on the ideas, half on the code the PR actually changes. Pick an answer to see the explanation; your first try is what's scored.