Coalesced vs strided memory access

*worked out from first principles*

Here is a puzzle that breaks people's intuition. A bundle of 32 threads reads 32 numbers from memory. In one version they read 32 neighboring slots, in another they read 32 scattered slots. The total amount of data requested is identical, the same 128 bytes either way. And yet the scattered version can be ten times slower. Same bytes, same threads, tenfold difference. The answer to that puzzle is one of the most important performance ideas in all of GPU programming, and it comes down to how memory is physically delivered.

↳ Think of it as a delivery truck. The GPU cannot hand you a single spoonful of data; it only ships full crates. Where your data sits inside those crates is the entire story.

The 128-Byte Box

Start with the hardware fact everything hinges on. The GPU does not fetch memory one byte at a time. It moves memory in fixed-size boxes, a chunk of 128 bytes at a time. This is not a software choice, it's baked into how the memory hardware physically works.

Whenever any thread asks for even a single value, the memory controller fetches the entire 128-byte box that contains it. The truck only comes in one size, no matter how little you actually wanted from inside it.

The Good Case: Coalesced Access

Now watch what happens in the good case. A bundle of 32 threads, each reading a 4-byte number. Thirty-two times four is exactly 128 bytes.

If the threads read neighboring slots—thread 0 at the start, thread 1 right after, and so on—then all 32 of their values sit inside a single 128-byte box. The memory controller sees this, sends one truck, grabs the one crate, and hands each thread its own 4-byte slice out of it. One transaction feeds all 32 threads. Every byte fetched is used. This is called a coalesced access, and it's 100 percent efficient.

The Disaster: Scattered Access

Now the disaster. Suppose the threads read scattered slots, each one far from the next, with a big gap between them. Now thread 0's value is in one box, thread 1's value is in a completely different box, thread 2's in yet another.

So the memory controller has no choice but to send a separate truck for each one. Thirty-two threads, up to thirty-two separate crate deliveries. And here is the brutal part: each truck still hauls a full 128-byte crate, the thread takes its 4 bytes, and the other 124 bytes are thrown away. So you fetched thirty-two full crates, over four thousand bytes of traffic, to deliver the 128 bytes you actually wanted. Your useful bandwidth collapses to a few percent.

The True Bottleneck: Transactions

And this reveals the deeper truth that surprises everyone. The memory system is not choked by the total bytes you need, it's choked by the number of transactions you force.

The memory controller has a limit on how many separate fetches it can issue, not just how many bytes it can move. So firing 32 tiny transactions instead of one clogs its queue completely. The whole bundle of threads freezes for hundreds of cycles waiting for all 32 trucks to return, and worse, other bundles that also need memory get stuck behind them in the queue. One badly-arranged read can stall the whole unit. One transaction gets its data and moves on cleanly. It was never about the weight of the data, it was about how many times you made the conveyor belt run.

The Array of Structures Trap

So the practical question, how do you keep your reads coalesced? And this is where a subtle trap catches programmers coming from ordinary CPU code. Imagine you have a bunch of particles, each with a position and a mass, and you store them the natural way: one complete particle after another in memory. All of particle 0's fields together, then all of particle 1's fields, and so on. This feels clean and obvious.

But now when 32 threads each want just the x-position of their particle, those x-positions are not neighbors in memory. They are spaced far apart with each particle's other fields sitting between them. Every thread lands in a different box. Coalescing shattered.

The fix is to flip the layout. Instead of storing complete particles back to back, you store all the x-positions together in one array, all the masses together in another, and so on. Now when the 32 threads each grab their x-position, those values are neighbors, packed tight, and the whole bundle collapses into one transaction.

The reason CPU programmers get this backwards is that a CPU genuinely prefers the first layout, because a single CPU thread working on one particle wants all its fields sitting together in cache. But a GPU is the opposite, because 32 threads want the same one field at the same instant, so that field needs to be contiguous across particles, not bundled per particle.

Honest Refinements

A couple of honest refinements. The hardware is not brutally unforgiving about perfect alignment. If your 32 values are contiguous but sit slightly off the box boundary, straddling two boxes, you pay for two transactions instead of one—a mild 2x penalty, not the catastrophic 32x of true scattering. So what really matters is locality, keeping the accesses clustered together, not obsessing over perfect alignment.

And there are cases where scattering seems unavoidable, like transposing a matrix, where turning rows into columns forces one side of the access to jump across memory. The trick there is to not fight memory directly. You read from slow memory in the nice coalesced direction, stash the tile into the fast on-chip scratchpad (shared memory) where scattered access carries almost no penalty, rearrange it there, and write back out in the coalesced direction. You route the unavoidable scatter through the fast memory that doesn't care about it.