Font: Spacing: Letters: Width:

Alignment, the Gather, and the Tail

27 minadvancedModule 3: Where It CostsContinues from simd-reduce

Why this matters

Everything so far was about a loop over consecutive elements, where a wide instruction is a straightforward win. This concept is about the three places that stops being true, and all three cost more per element than a 4-wide add does.

Start with the one everybody gets wrong, because it is the one the measurement refuses to confirm. The folklore is that unaligned vector loads are slow — that a misaligned 32-byte load costs you because it straddles a cache line. The artifact measures it at two working-set sizes:

$ ./simdbench | sed -n '/arm  /,/^      unaligned instruction/p'
   arm                                                               ns/iter  vs arm 1
   _mm256_load_pd   (DEMANDS 32B) on a 32-byte aligned address          7.58     1.00x
   _mm256_loadu_pd  (demands nothing) on a 32-byte aligned address       7.13     0.94x
   _mm256_loadu_pd  (demands nothing) on a +8 MISALIGNED address        7.58     1.00x

      unaligned instruction, aligned address / aligned instruction   0.94x
      MISALIGNED address / aligned address                           1.00x

All three are within 6% of each other, and the spread moves between runs — one of them even came out faster than the others. That is the signature of no effect rather than a small one: a real cost of alignment would be a consistent ordering. The same comparison at 2 MiB per stream, past the L2, came out at 0.92×, 1.29× and 1.00× on the three recorded runs — no consistent direction, which is what “no effect” looks like when the arm is bandwidth-bound and the run is noisy. On this machine an unaligned 32-byte vector load of memory is free.

So why does _mm256_load_pd exist? Because the requirement is a fault requirement, and the artifact measures that separately — by forking a child process and catching what comes back:

      _mm256_load_pd on a +8 address, in a child process: raised SIGSEGV (signal 11)

The two instructions differ in a way the table above cannot time: one of them is a legal program and the other is not. That is worth a whole paragraph, and it generalises: check whether the thing faults before you spend a benchmark on asking how slow it is. A duration table is the wrong instrument for a correctness requirement.

The model: a wide instruction is worth what the addresses allow

With the alignment surprise out of the way, the model that explains all three of this concept's findings is one sentence:

A WIDE INSTRUCTION IS WORTH WHAT THE ADDRESSES ALLOW. Four CONSECUTIVE addresses: the load unit fetches 32 bytes for the four lanes either way, one memory operation serves them all, and the width is pure win. This is the case every optimisation is written for. Four SCATTERED addresses: the four accesses are INDEPENDENT, and independent memory operations cannot be overlapped, because the memory system has no way to know they are unrelated. The width buys you arithmetic you could have had anyway and charges you for the independence you just lost. So: a permuted access is a SCATTER, a GATHER, a TRANSPOSE or a SHUFFLE, and on every one of those the width is a COST until measured otherwise.

And the gather is where the sentence is worth the most, because the instruction designed for the job is the slowest thing in the table:

$ ./simdbench | sed -n '/arm  /,/hand gather, four scalar/p'
   arm                                                                  ns/iter  vs arm 1
   four SEQUENTIAL addresses: 3 loads, 1 store, 1 fma per 4 elements          13.01     1.00x
   hand gather: FOUR SCALAR LOADS, then build the vector, then 1 fma          26.81     2.06x
   hardware gather: vpgatherdd, one instruction for the same four loads      74.54     5.73x

      the hand gather, against the SEQUENTIAL loop it replaces    2.06x
      vpgatherdd, against the same sequential loop                 5.73x
      vpgatherdd, against FOUR ORDINARY SCALAR LOADS                2.78x

The gather instruction is 2.78× slower than four ordinary scalar loads. Read that again, because it is the sentence the whole section exists for. vpgatherdd is not one instruction doing four things at once. It is one instruction doing four independent loads, and the memory system cannot overlap them. The instruction saves the register moves and charges a decode penalty for them.

This is not a compiler artefact — both arms are intrinsics in the same translation unit, with the same flags, in the same loop nest. And it is the same finding as the FMA row in the previous concept's table, with a bigger multiplier: an extra instruction you did not need costs a fetch and a decode slot, and on a loop that is not short of either, removing one buys nothing. Here the arithmetic runs the other way — the wide instruction is the extra one.

There is a genuine caveat, and the artifact states it: this is measured on gather. A segment load — a strided run rather than an arbitrary index list — is a different instruction with a different contract, and on some microarchitectures it is a genuine win. The three-architectures concept covers the one that exists for exactly this job.

The reality: the tail, and why the clever answer is the slow one

Now the third cost, and the one that has a mask register's entire reason for existing. A 66-element loop with a 4-wide instruction leaves two elements over, and this machine has no AVX-512, so there is no k register to say “only two of these four lanes”. Three strategies, and two of them are wrong:

$ ./simdbench | sed -n '/64 elements/,/CONTROL: a PART/p'
   64 elements, 4-wide, NO TAIL at all                (the reference)      12.71     1.00x
   66 elements, 4-wide + a SCALAR remainder of 2                         12.94     1.02x
   66 elements, 4-wide + one OVERLAPPING iteration, 2 valid lanes stored      22.50     1.77x
   68 elements, plain 4-wide: WRITES 2 ELEMENTS PAST THE END OF THE ARRAY      13.91     1.09x
   CONTROL: a FULL 32-byte overlap (load exactly what was stored)        13.95     1.10x
   CONTROL: a PARTIAL overlap load, only 1 lane stored back              16.62     1.31x

Four findings, in order of how surprising they are.

The scalar remainder is free: 1.02×. Two elements out of 66 is 3% of the work and it costs 2%. This is the right answer and it is not a trick — it is a for loop with a scalar body.
The overlapping last iteration is 1.77× — the worst arm in the table, and it is the one that is supposed to be the clever one. On a machine with no mask, the textbook trick is to run one more 4-wide iteration starting at element 62 and store only the two lanes that exist.
The two controls say why, which the overlapping arm on its own does not. A full 32-byte overlap is 1.10× and a partial overlap load is 1.31×. So the cost is not “doing the tail” — it is the load at +62, which overlaps the 32-byte store at +60 by half. A load that overlaps a recent store only partly cannot be forwarded from the store buffer; it has to wait for the store to reach the cache. The overlapping trick reads back the very line it has just written, half-aligned, and that is the slowest thing in the table.
The arm that writes past the end is cheap (1.09×) and it is a bug. It writes two elements into memory the array does not own. The array in the artifact is declared with eight spare doubles, which is why it does not crash and why it is a bug rather than an accident. A vector loop that over-reads and over-writes its tail is a portable program that gets faster by writing to memory it does not have.

And the mechanism in point 3 is marked INFERRED in the artifact, not measured, because there is no PMU on this machine and nothing above is a count of anything. It is a mechanism with two controls supporting it, which is the strongest kind of claim this hardware can support. The controls are the point: a single measurement of “the overlapping trick is slow” would have been a story, and two controls that separate the full overlap from the partial one make it an argument.

THE ORDERING, which is the thing to remember: on a machine WITHOUT a mask register, WRITE THE TAIL SCALAR. It is free, it is correct, and the clever alternative is the most expensive row in the table. And this is exactly what a mask register is for. A masked store uses a bit per lane to say which lanes to KEEP, so the last iteration of a 66-element loop is the same instruction as every other iteration with two lanes switched off -- no epilogue, no branch, no partial-overlap load, and nothing written past the end. SVE calls this PREDICATION and RISC-V V does it with vl (the vector length register). AArch64 NEON and x86-64 without AVX-512 do not have it, and both arrive at the same answer this table measured: peel it.

Worked: the three rules, and the two that are not what they look like

Collecting this concept into something a code generator can use:

1. ALIGNMENT IS A CORRECTNESS REQUIREMENT HERE, NOT A SPEED ONE. _mm256_load_pd demands 32-byte alignment and FAULTS without it (measured, in a forked child: SIGSEGV). _mm256_loadu_pd demands nothing and costs the same (measured, twice, at L1 and past the L2; the L1 arms agree within 6% and the 2 MiB arm has no consistent direction across three runs, which is what no effect looks like when the loop is bandwidth-bound anyway). So emit the aligned form when you KNOW the address is aligned -- it is a smaller decoder case and it is one fewer thing to have to be right about -- and do not expect it to be faster on this machine. On some other microarchitecture it is. 2. A GATHER IS NOT A WIDE INSTRUCTION. vpgatherdd 2.78x four ordinary scalar loads hand gather 2.06x a sequential 4-wide load sequential 1.00x If you have an indirect access, the default on this machine is FOUR SCALAR LOADS and a vector built from them. A segment load for a regular stride is the case where a wide instruction may still win. 3. THE TAIL IS FREE IF YOU DO IT SCALAR AND EXPENSIVE IF YOU DO IT CLEVERLY. scalar remainder 1.02x overlapping iteration 1.77x <- the clever one writing past the end 1.09x <- and a bug

Two of these deserve a note about what they are not, because both are commonly over-generalised.

Rule 1 does not survive a page boundary. A 32-byte load whose last bytes are in the next 4 KiB page is a different case, and the artifact says so in its limits block: it has no PMU, it did not measure a page-crossing vector load, and it does not claim anything about one. The measured “free” is free within a page, and that is the only claim being made.

Rule 2 is about an arbitrary index list. A gather whose four addresses happen to be adjacent is a sequential load wearing a gather's clothes, and the microarchitecture may detect that. What was measured is a permutation — index[j] = (j * 7) & 63 — which is the realistic case for indirect array access and which the compiler cannot fold back into a load.

And the general form of all three, which is the sentence the section is built on: the width is a property of the register, and whether it is a benefit is a property of the addresses. Everything in this concept is that sentence in three costumes, and every one of them cost more than the 4-wide add does. Optimise for the shape of the access, not for the size of the register.

Apply it

Reproduce all three tables and read the surprising one first.(Expect the alignment arms to be indistinguishable, expect vpgatherdd to be several times the hand gather, and expect the overlapping tail to be the worst row. If the alignment arms differ sharply, you are on a microarchitecture where the folklore is true — check the disassembly for a vmovupd that became two operations, and treat your result as a fact about that machine and not a contradiction of this one.)
Do the fault experiment yourself, because it is thirty seconds. Write a two-line program that calls _mm256_load_pd on ptr + 1 and run it. (Expect SIGSEGV, immediately, with no output. Then add __attribute__((aligned(32))) to a local array and do it again, and note that the compiler now knows the address is aligned and will not let you make the mistake. That is the real reason aligned loads exist in a compiler: they are an assertion the compiler can check and you cannot get wrong accidentally.)
Replace a gather with four scalar loads in real code and measure. Find an indirect access — a sparse lookup, a particle gather, a pixels[i * stride] where stride is a variable. (Expect a win of around 2–3× over the hardware gather and roughly parity with whatever the compiler was doing. If the win is larger, check whether the compiler was emitting a gather at all — most do not, and the baseline you are comparing against may be something else entirely.)
Take a vectorised loop with a runtime length and add the tail three ways. Scalar remainder, overlapping iteration, and padded array. (Expect the scalar remainder to cost nothing, the overlap to be the most expensive, and the padding to be fastest and wrong. The padding case is the dangerous one — it is a buffer overflow that works until it does not, and the exercise is worth doing precisely so you can recognise it in code you did not write. If you do pad, the padding is not an optimisation: it is a precondition, and it belongs in a comment and in a bounds check.)
Find an indirect access that is actually a strided run and ask whether a segment load exists for your target.(Expect the answer to be yes on RISC-V V and SVE, and no on x86-64 — which is why x86 gather instructions exist at all and why they cost what they do. This is the clearest place in the course where an ISA feature is a direct consequence of another ISA not having one, and it is a good bridge to the three-architectures concept.)

Connect

Backwards, the shapes concept is where the load and the store were identified as the real cost of a vector loop — the four-body table showed an add and a multiply costing the same because they hide inside the memory operations. This concept is that cost's price list. And the reduction concept is the structural twin: a tail and a fold are the same problem — a few elements left over after a wide operation — and both arrive at “do them one at a time, it is free” for the same reason and on the same machine without a mask register.

Forward, the three-architectures concept is the direct answer to two of this concept's findings. AArch64 NEON has no gather instruction at all, which sounds like a missing feature and is actually the reason the hand-written gather is not merely faster but the only option there; and SVE and RISC-V V both have predication, which is the answer to the tail table. The harness concept then explains why this section's mechanism is marked INFERRED and its checks assert shapes.

Outward, the two connections a compiler author needs most. The memory course's latency concept is where “where do the bytes come from” was made a measurement rather than an assumption, and it is the reason the alignment result could be checked at two working-set sizes instead of one: a claim about a load is a claim about a cache level, and the answer changes when the answer changes. Its writes concept is where the store side of every table in this concept was introduced. And The ISA course's length concept is where you can go to see whyvmovapd and vmovupd are two opcodes rather than one with a flag — the ISA course teaches the encoding, and this concept measures what the two encodings cost.

One outward-facing consequence, and it is the most practical thing in the concept. “Aligned” is a promise a declaration makes and a compiler can check.__attribute__((aligned(32))) on a local array does not just help the optimiser — it makes a whole class of misaligned access unrepresentable. That is the same shape as the trap in the multiprocessor course's sharing concept, where an attribute on a one-dimensional array aligned the array and not the elements and every “private line” row was a false-sharing row wearing a different label. Both are cases of a declaration promising alignment at the wrong granularity, and both are silent.

Keyboard Shortcuts