Why does reading every 16th value of a contiguous capture buffer take nearly as long as reading all of them?

## The wrong answer this aims at The instinctive reasoning is arithmetic: one sixteenth of the iterations, therefore roughly one sixteenth of the time. It is wrong because it counts *iterations* when the machine charges for *lines*. Interviewers like this scenario precisely because the wrong answer is so reasonable-sounding and the right answer forces you to say out loud what a memory system actually transfers. ## Counting lines instead of iterations Take a capture buffer of `n` contiguous 4-byte counters on hardware with 64-byte cache lines. Sixteen counters fit in one line. | Loop | Values read | Lines touched | Useful bytes per line | |---|---|---|---| | every value | n | n/16 | 64 of 64 | | every 16th value | n/16 | n/16 | 4 of 64 | | every 32nd value | n/32 | n/32 | 4 of 64 | The first two rows touch the *same number of lines*. If the loop body is a single add and the buffer is far larger than cache, the loop is bandwidth-bound: both versions move `n * 4` bytes across the memory bus, and the strided version simply wastes fifteen sixteenths of what it moved. The extra additions in the full scan are nearly free because they overlap with outstanding fetches, so the two loops land close together — often within a small percentage rather than the 16x the naive model predicts. The third row is where the picture changes. Once each step skips a whole line, lines are genuinely skipped and traffic falls proportionally. **The crossover is at exactly one cache line per step, not at one element per step.** ## Why very large strides can reverse the win Widening the stride does not improve things forever: - **Prefetch range.** Stride detectors work within a limited window and typically will not prefetch across a page boundary (commonly 4 KB). A stride of several kilobytes puts every access in a new page, so each one is an exposed miss. - **Address translation.** Every new page also needs a translation entry. Touching one value per page thrashes the translation cache, adding a second class of miss on top of the data miss. - **Bank and row behaviour.** Widely separated addresses lose the row-buffer reuse that sequential streams enjoy inside the memory devices themselves. So the cost curve as a function of stride is not monotonic in the way the naive model suggests: flat up to one line, falling for a while after that, then rising again per element once locality and prefetchability are gone. ## The generalisable rule For a memory-bound loop, estimate cost as **lines touched**, then sanity-check whether the address pattern is prefetchable. Two questions get you most of the way: 1. How many distinct cache lines does this loop touch? 2. What fraction of each fetched line does it actually use? A loop that touches few lines and uses all of each is as good as it gets. A loop that touches many lines and uses a sliver of each is paying full price for data it discards — and no amount of skipping iterations fixes it, because the skipping is happening at the wrong granularity. ## What this does not say It does not say the strided loop is *never* faster. When the loop body is expensive, cutting iterations by 16 cuts real work by 16 and dominates the memory story. It also does not say complexity changed: both loops are O(n) in the size of the buffer, and this is a constant-factor argument from start to finish. And it is a claim about a buffer much larger than cache — if the whole capture buffer fits in cache, there is no line traffic to argue about and the iteration count really does drive the time. ## Saying it well A strong answer names the transfer unit in the first sentence, does the sixteen-values-per-line arithmetic out loud, states the crossover at one line per step, and then adds the non-monotonic tail about pages and translation. A weak answer restates that "caches make sequential access fast" without ever computing how many lines each loop touches.