Same reads, different order

01Why we look for streaks

A speck of debris on a scanner's glass drags a dark vertical line down every page that passes over it. On a ballot, that line can cut through bubbles and read as phantom marks, so the interpreter checks every scanned page for them and rejects affected sheets. The rule of thumb: a streak is a column of pixels that is dark almost top-to-bottom, with no white gap large enough to suggest it's a printed feature.

02An image is one long row

A grayscale scan isn't stored as a grid — it's a single flat array of bytes, one row after another. Pixel (x, y) lives at raw[y * width + x]. The CPU never fetches one byte at a time; it pulls memory in 64-byte cache lines. Read a byte and its 63 neighbors arrive for free.

That makes traversal order the whole game. Walking a row touches consecutive bytes: one line fetch serves 64 pixels. Walking a column jumps a full row's width between reads — on a real scan that stride is ~1,700 bytes, so every single read lands on a different cache line.

03The change: count first, look later

The old detector walked the page column by column — the worst possible order — binarizing each full column just to count its black pixels: about 3.7 million strided reads per page. That made streak detection the single most expensive stage of interpretation, paid on every sheet, streak or not.

The fix keeps the arithmetic and flips the loop. One row-major pass accumulates all ~1,700 per-column counts simultaneously — like keeping a running tally per column while reading the page the way memory wants to be read. Only columns whose count clears the 25% gate — usually none — get the detailed two-column analysis, which is completely unchanged:

// for every column: walk the whole column (stride = width,
// a new cache line on every read)
for x in x_range {
    fill_column(&mut next_col, x + 1);   // `height` strided reads
    let black = next_col.iter().filter(|&&b| b).count();
    if score(black) >= MIN_ONE_COLUMN_STREAK_SCORE {
        // detailed two-column analysis …
    }
    mem::swap(&mut cur_col, &mut next_col);
}

// count black pixels in every column at once, in memory order
let mut counts = vec![0u32; width];
for row in raw.chunks_exact(width) {
    for (count, &p) in counts.iter_mut().zip(row) {
        *count += u32::from(p <= thresh);
    }
}
for x in x_range {
    if score(counts[x]) >= MIN_ONE_COLUMN_STREAK_SCORE {
        fill_column(&mut cur_col, x);      // rare: candidates only
        fill_column(&mut next_col, x + 1);
        // detailed two-column analysis (unchanged) …
    }
}

Simplified from image_utils.rs — the real diff is +18/−11 lines in detect_vertical_streaks.

04The race

Both detectors below run on the same toy page, and both panels advance at their measured real-world rates (2.8 ms vs 0.6 ms per page), slowed down about 2,500× so you can watch. The bars under each page are the per-column black counts — the same integers, arriving in a different order.

05Why the output can't change

This is a pure reordering. Addition commutes, so the row-major tally produces the same integers the column walk produced — not approximately, exactly. Same counts means the same columns clear the 25% gate, and the detailed two-column analysis that actually declares a streak wasn't touched: it still reads the candidate columns directly and applies the same 75% score and white-gap rules.

The commit backs that argument with data: all 2,472 real scans in the validation corpus produce identical detected streaks before and after — including the three pages with genuine scanner streaks — and the change survives the interpreter's full test suite. The result is a 29-line diff that removes the most expensive stage of ballot interpretation from the common path entirely: ~2.8 ms → ~0.6 ms per page.

06Check 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.