Gather and Scatter Instructions Explained
Gather and scatter let vector code load or store elements at non-contiguous indexed addresses. They expand what can be vectorized, but irregular memory remains expensive.
Vector hardware is happiest when data is contiguous. A single wide load can then fetch neighboring elements that map naturally to vector lanes. Real programs are not always so cooperative.
Gather and scatter instructions provide a vector form of indexed memory access. A gather loads multiple elements from addresses derived from a base plus per-lane indices. A scatter stores vector elements to multiple indexed addresses.
Contiguous load
for (int i = 0; i < 8; ++i)
x[i] = a[base + i];The addresses are adjacent. Hardware can often service this efficiently through one or a small number of cache-line accesses.
Gather
for (int i = 0; i < 8; ++i)
x[i] = a[index[i]];Each lane can point somewhere different. A vector gather expresses the set of indexed loads as one architectural vector operation.
Scatter
for (int i = 0; i < 8; ++i)
a[index[i]] = x[i];Scatter performs the inverse style of operation: multiple vector lanes write to indexed locations.
Why gather/scatter matters
Without vector indexed-memory support, irregular loops may require scalar extraction, many separate loads/stores or complicated rearrangement. Gather/scatter expands the set of algorithms that can remain in a vector programming model.
AVX2 introduced vector gather capabilities for x86. AVX-512 expands indexed memory operations and mask integration. Arm SVE and RISC-V Vector also provide indexed memory forms.
One instruction does not mean one memory transaction
This is the most important performance fact.
If eight gathered elements fall in eight unrelated cache lines, the memory system may still need to perform many independent accesses. The architectural gather instruction packages those requests, but it cannot make scattered data contiguous.
Latency, cache misses, TLB behavior and memory-level parallelism can dominate execution.
Locality decides whether gather is cheap
A gather whose indices mostly land in one or two nearby cache lines can behave very differently from one whose indices are random across a large data structure.
Always characterize the index distribution and working set, not just the source code.
Scatter adds ordering questions
With scatter, two lanes might compute the same destination address. The language semantics and ISA rules determine what behavior is legal and how collisions must be handled.
A compiler needs to prove that vectorizing stores preserves required ordering or use an instruction whose semantics match the source.
Masks make irregular memory safer
Predicated architectures can disable selected gather/scatter lanes. This is useful for tails and conditions and can avoid accessing invalid addresses for inactive elements when the instruction semantics guarantee the required fault suppression.
Details differ by ISA, so low-level code should consult the architecture manual rather than assuming all masked memory operations behave identically.
Can data layout remove the need for gather?
Sometimes. Reorganizing data into contiguous arrays, sorting work by index, using structure-of-arrays layouts or blocking computations can turn irregular access into streaming access.
But data-layout changes have costs elsewhere. They can increase preprocessing, memory footprint or complexity. Measure the whole application.
Compiler auto-vectorization
Modern vectorizers can generate gather/scatter for some indexed loops when the target supports it and the cost model considers it worthwhile. A loop may be legal to vectorize yet remain scalar because indexed memory is predicted to be too expensive.
This is another example of legality versus profitability.
Key takeaways
- Gather loads vector elements from indexed, non-contiguous addresses.
- Scatter stores vector elements to indexed addresses.
- They broaden vectorization but do not eliminate the cost of poor locality.
- One gather instruction may trigger many underlying cache/memory accesses.
- Data-layout changes can sometimes outperform sophisticated indexed instructions.
References and further reading
- RISC-V “V” Vector Extension, Version 1.0
- Arm: The Arm Scalable Vector Extension (SVE)
- Intel: Intel AVX-512 Instructions
- Intel Intrinsics Guide
- LLVM Auto-Vectorization Documentation
Continue learning
Understand the loop. Understand the machine.
QCEV Vector Inspector is designed to help developers reason about vectorization opportunities, dependencies and memory access in performance-critical loops.