gather-scatter access

A vector load is happiest when the data it wants sits in one neat contiguous run — like grabbing eight books from one shelf in one sweep. But real programs often want elements scattered all over memory: every tenth row of a table, or the entries whose indices come from another list (A[index[0]], A[index[1]], and so on). Gather is the operation that reaches into many separate addresses and collects those scattered elements into one vector register; scatter is the reverse, taking the lanes of a vector and writing each one back to its own separate address.

Two patterns matter. Strided access reads elements a fixed distance apart — every 4th float, say, for the red channel of an RGBA image; the stride is the constant gap. Gather/scatter is the fully general case: you give the hardware a vector of indices, and it fetches A[i] for each index i in the vector, no matter how irregularly those addresses jump around. A gather instruction with index vector [0, 7, 3, 12] loads A[0], A[7], A[3], A[12] into the four lanes; a scatter does the mirror image on a store. This is what lets vector code handle sparse matrices, indirect lookups, and histogram-style updates.

Gather and scatter are powerful but they are the expensive corner of data-level parallelism, and beginners should respect that. A contiguous vector load fetches one cache line and feeds every lane; a gather may touch a different cache line for every lane, so it can be many times slower and it strains the memory system. Scatter has an extra hazard: if two lanes scatter to the same address (a collision), the hardware must define what happens, and parallel histogram updates are a classic trap. The rule of thumb is that vectorization loves contiguous, unit-stride data; the further you drift toward arbitrary gather/scatter, the more the memory system, not the arithmetic, becomes your bottleneck.