The previous concept ended by naming the exception: a horizontal add is the one common instruction that reads across lanes rather than within them, and it is the only place in this course where a 4-wide loop loses to a scalar one. This concept is that place, and the number is worse than most people expect.
$ ./simdbench | sed -n '/arm /,/scalar loop, no vector at all/p' arm ns per 4 elem vs arm A value produced 4-wide accumulate, reduce ONCE at the very end 1.341 1.00x 1.644919 4-wide accumulate, TREE horizontal add every group 1.946 1.45x 26948.077729 4-wide accumulate, EXTRACT 4 lanes every group 1.984 1.48x 26948.077729 4-wide accumulate, VHADDPD every group 1.929 1.44x 26948.077729 scalar loop, no vector at all 5.349 3.99x 1.644919
Read that carefully. The first row and the last row compute the same number — both 1.644919 — and the 4-wide one is 3.99× faster. That is the shape to write, and it is the good news.
The bad news is the three middle rows, and what they say is this: folding the accumulator back into a scalar on every iteration costs about as much as the vector operation that produced it. The vector multiply-add is 1.341 ns per four elements; adding a tree horizontal add to every iteration takes it to 1.946, and extracting the four lanes into a scalar takes it to 1.984. The fold costs 45% on top of the work it is folding.
And there is a detail in that table that is worth more than the timings. The three middle rows do not compute the same number as the first and last. They produce 26948.077729. They are not broken; they are computing a sum of running totals, which is a different quantity. This is printed in the artifact deliberately, and it is the subject of a retraction later in this concept, because the first version of this section compared four arms that were each summing something different and reported the ratios as though they were costs of the same computation.
Given a register holding a = (a0, a1, a2, a3), there are three ways to get a0+a1+a2+a3 out of it, and they differ in what they cost and in what they assume.
And here is the fact that cost this course two bugs and is worth a paragraph on its own, because it is the most dangerous kind of error there is: an error that is perfectly stable.
Why that is dangerous, and it is the point of printing it: a wrong answer that is approximately wrong announces itself — the test fails, the number looks wrong, somebody investigates. An answer that is exactly twice the right one looks like a plausible sum of a different set of numbers, and it is stable across every re-run. You cannot detect this class of error by measuring more carefully. You can only detect it by looking at the answer.
And there was a second bug hiding behind the first, which is worth stating because they had the same symptom. The first version's tree reduction added the two 128-bit halves of an already-paired register, so both 64-bit lanes already held the total and it was added to itself. Also exactly twice. Two different bugs, one symptom, one line of output — and the checksum on that line is the only reason either was found.
Now the useful part. The three middle rows of the table differ in how they fold, and they cost almost the same — 1.45, 1.48 and 1.44 of the fold-once arm — which is itself a result. On four lanes the shape barely matters. It matters enormously on a million, and the reason is that a reduction is a dependency chain.
And the caveat, which is a correctness statement and not a performance one: a tree reduction reassociates the additions, and in floating point that gives a different answer. Summing a million doubles left to right and summing them pairwise do not produce the same number, and neither is “wrong”. If your answer must be bit-identical to the sequential one — because a test asserts an exact value, or because a downstream consumer hashes it — you cannot have a tree, and the chain is the price of the answer.
It also reassociates the additions, which changes the result in floating point -- so a tree reduction is a DIFFERENT SUM, and if your answer must be bit-identical to the sequential one you cannot have it.
Three rules fall out of the table, and they are the whole concept.
sum += v[i] over a vector. That is the EXTRACT row, and it is 1.48× — the worst of the three, because every lane is moved across to the scalar side individually. If you have written that, the fix is to accumulate into a vector and fold at the end.vhaddpd was the fastest-looking of the three and it is the one that means something else. The measured cost is nearly identical to the correct tree fold, so no timing would ever have told you; only the value did.And the general form, which is why this concept is in the course at all: a horizontal add of four doubles costs about as much as the vector operation that produced them. There is no formulation of a reduction that avoids paying for the fold — the fold is the operation. What there is, and what you choose, is how many times you pay it. Once at the end, or once per iteration, and the ratio between those two is the 1.45× in the table.
All five arms sum the squares of the same 65536 doubles. What differs is when the lanes are folded and how. Laid out so the arithmetic is checkable:
Arms 2, 3 and 4 are the same algorithm with three different folds, and they produce the same number as each other — 26948.077729 — because they are all summing running totals. Arm 1 and arm 5 produce 1.644919, the actual sum of squares. That is the retraction, printed in the artifact: the first version of this section compared all four as though they were four costs of one computation, and three of the four ratios were ratios between different quantities.
And one more worked case, because the interesting mistake is not in the code but in the question. A max reduction — the largest element of an array — looks like the same problem and is not. Two differences worth knowing before you write it:
vhaddpd(v,v) and check what it does. A four-line program: set a register to (1,2,3,4), call the intrinsic, print the lanes. (Expect (2,4,6,8) — it doubled. Then swap the halves with permute2f128 first and expect the pairs. This is thirty seconds of work and it is the single most useful half hour in the course, because the failure mode is a stable wrong answer rather than a crash.)sum += v[i] in code you did not write.(Expect to find one, usually in a hand-written inner loop where somebody started from scalar code and added intrinsics one instruction at a time. The fix is a vector accumulator and a single fold at the end, and the measurement above says it is worth about a third. Write down the before and after — a change with no number attached is a change nobody will keep.)Backwards, the shapes concept set this up by naming the horizontal add as the one instruction that is not elementwise, and by measuring that four independent accumulators are 4.00× one. Those four accumulators are the subject of this concept — the whole table above is about what happens after you have them, and the answer is that the fold costs as much as the work and therefore happens once. The compiler concept is the other parent: a compiler that cannot prove independence will not produce those four accumulators, and this concept is what it is trying to avoid.
Forward, the boundaries concept asks about the load and the store, which the four-body table in the previous concept showed is the real cost of a vector loop — and the tail it handles there is the same shape as the fold handled here. A tail and a reduction are the same problem: a small number of elements left over after a wide operation, and in both cases the answer on a machine with no mask register is to do them one at a time, which this concept measures as free and that one measures as free independently.
Outward, the connection to the execution course's dependency concept is the deepest in the course. That concept's central claim — that a chain is bounded by latency and independent work by throughput — is exactly the tree-versus-sequential argument above, and this course is the same lesson in a register where the latency is four times shorter. The multiprocessor course's atomic concept is the other connection worth making and it is a warning: it measured a lock prefix that promises ordering whether you asked for it or not, and the moral was that a guarantee you did not ask for is a cost you pay anyway. A floating-point sum has the same property. Reassociation is a freedom the language grants you and that most code silently uses, and the day the order matters — a test constant, a hash, a bit-for-bit comparison — the cost of the chain appears with no warning and no diagnostic.
Outward again, and it is the one that will matter to a code generator: any code that emits a horizontal reduction has to decide the fold order, and the decision changes the answer. That is not a performance knob. The execution course's harness is where the general rule for checking a compiler's choice lives — a claim about what a compiler did is a claim about bytes — and this course's own harness applies it to exactly one thing: the disassembly of the four loop forms.