- Published on
Does Code Alignment Change the Speed of the Same Code?
- Authors
- Name
- Mehdi Akiki
Investigation · Part 15 of 20 · When the benchmark lies
Eleven instructions, always the same bytes. At 63 positions in memory they take about 0.45 nanoseconds per element. At one position they take 0.52. In the part about interleaving I wrote that interleaving can not help when two builds differ only in how their code is placed in memory. Here I wanted to know if placement alone can change the speed on this laptop, and how much.
The loop, at 64 positions
The loop reads an array of 1,024 long values and updates four sums. I first wrote it in plain C with gcc 15.2.1 -O2, and I put a padding of N bytes of nop before it, so that the loop would start N bytes later. It did not work. gcc wrote .p2align 6 just before the loop, even with -fno-align-loops (the fixture keeps this output, in p15-gcc-loop-alignment.txt), so every copy of the loop started again at the beginning of a 64-byte block, and my padding was only moving the empty space. The compiler aligns loops by itself, which already says something: compilers think that the position of a loop matters.
So I wrote the loop body in inline assembly, with the padding inside the same asm statement, where the compiler can not insert anything:
2652: mov (%rdi),%rax
2655: add $0x8,%rdi
2659: lea (%rax,%rax,2),%r9
265d: add %rax,%rdx
2660: sub %rax,%rsi
2663: xor %r9,%r10
2666: mov %rax,%r9
2669: sar $0x2,%r9
266d: add %r9,%r8
2670: cmp %rdi,%rcx
2673: jne 2652 <a3+0x12>
This is the copy with 3 bytes of padding, as objdump shows it. The loop is 35 bytes long. The program has 128 functions: for each padding from 0 to 63 bytes, two copies, a and b, each function aligned to 64 bytes. objdump confirms where each loop really starts, modulo 64:
pad 0: 15 15 pad 1: 16 16 pad 2: 17 17 pad 3: 18 18 pad 4: 19 19 pad 5: 20 20 pad 6: 21 21 pad 7: 22 22
pad 8: 23 23 pad 9: 24 24 pad 10: 25 25 pad 11: 26 26 pad 12: 27 27 pad 13: 28 28 pad 14: 29 29 pad 15: 30 30
pad 16: 31 31 pad 17: 32 32 pad 18: 33 33 pad 19: 34 34 pad 20: 35 35 pad 21: 36 36 pad 22: 37 37 pad 23: 38 38
...
One byte of padding moves the loop by one byte, and the two copies are at the same position. OK, now it works. So the 64 paddings cover every position of the loop inside a cache line, and the two copies of each padding are an A/A test: same code, same alignment, different addresses.
The program measures each function with 200 calls of 1,024 elements, and repeats this for 21 rounds. In every round the order of the 128 functions is shuffled again, so a slow moment of the machine hits random functions, not always the same ones. The result for each function is its median over the 21 rounds.
One position is slow
This is a part of the second run, pinned to CPU 2:
12 0.4224 0.4505 0x55db01defec0 0x55db01deff40
13 0.4317 0.4318 0x55db01deffc0 0x55db01df0040
14 0.4316 0.4221 0x55db01df00c0 0x55db01df0140
15 0.4290 0.4321 0x55db01df01c0 0x55db01df0240
16 0.5342 0.5051 0x55db01df02c0 0x55db01df0340
17 0.4310 0.4497 0x55db01df03c0 0x55db01df0440
18 0.4531 0.4398 0x55db01df04c0 0x55db01df0540
The columns are the padding, the median time per element of copy a and copy b, and the addresses of the two functions. Padding 16 is slower in both copies: 0.534 and 0.505 ns, against about 0.43 for its neighbors. The summary of the three runs (the third one on CPU 6, another performance core):
p15_run1.txt: median of the 64 paddings 0.4854 ns per element
copy a against copy b of the same padding: mean difference 3.0%, max 14.4%
fastest padding 57 (0.4622), slowest padding 16 (0.5864), slowest / median 1.208
paddings more than 10% above the median: 16 (loop at offset 31 of 64, 0.5864, +21%)
p15_run2.txt: median of the 64 paddings 0.4498 ns per element
copy a against copy b of the same padding: mean difference 3.4%, max 10.0%
fastest padding 56 (0.4248), slowest padding 16 (0.5196), slowest / median 1.155
paddings more than 10% above the median: 16 (loop at offset 31 of 64, 0.5196, +16%)
p15_run3.txt: median of the 64 paddings 0.4625 ns per element
copy a against copy b of the same padding: mean difference 3.1%, max 17.0%
fastest padding 62 (0.4303), slowest padding 16 (0.5513), slowest / median 1.192
paddings more than 10% above the median: 16 (loop at offset 31 of 64, 0.5513, +19%)
In all three runs, the slowest padding is 16, and it is the only one more than 10 percent above the median: +21, +16 and +19 percent. That is the loop starting at byte 31 of a 64-byte block. When I ran this part a second time, padding 16 was again the slowest in all three runs, by 21, 13 and 14 percent. In the third of these runs two other paddings were just above 10 percent too, 31 and 45, so the line of 10 percent is not a sharp border (p15-code-alignment.txt).
Is it bigger than the noise? The A/A test says that two copies of the same padding differ by about 3 percent on average. The largest A/A difference is big, up to 17 percent, because this laptop was busy during the runs, but it happened at a different padding in each run (paddings 16, 36 and 21 in the first run, 60, 50 and 4 in the second, 62, 15 and 0 in the third). Padding 16 is slow in both copies, in all runs, on two different cores. Noise does not do that. I had to look twice at this: I expected either no effect or a messy one, not one sharp position.
Why offset 31?
I do not know, and I want to be careful here. I can describe the addresses: at offset 31, the first instruction of the loop (3 bytes) crosses a 32-byte boundary, and the last one, the jne, starts exactly on the next 64-byte boundary. As far as I know, the front end of a modern core fetches and decodes instructions in blocks of fixed size, and it keeps decoded instructions by such blocks, so it is easy to imagine that one particular way of cutting a small loop into blocks is worse. But "easy to imagine" is not evidence. To show it, I would need the performance counters of the front end, and perf is not available on this laptop. So: a real, repeatable effect of placement, and a cause that I can only guess.
Interesting also: other positions where the loop crosses a 64-byte boundary (any start from offset 30 to 63) are not slow. So it is not simply "crossing a cache line is slow".
What this means for a benchmark
The same instructions changed speed by up to 21 percent because of their address. In a real program, the address of a hot loop depends on everything around it: the functions before it in the binary, the compiler version, an unrelated change in another file. So a change that seems to make a program 10 percent faster or slower can be, in part or completely, a change of layout. A benchmark that measures one binary, like everything I did since the first part, measures one layout.
Curtsinger and Berger describe this problem in "STABILIZER: Statistically Sound Performance Evaluation" (ASPLOS 2013): "A single binary constitutes just one sample from the space of program layouts, regardless of the number of runs." Their tool re-randomizes the layout of code, stack and heap while the program runs, so that many layouts are measured instead of one, and with it they found that the impact of -O3 over -O2 in their benchmarks was "indistinguishable from random noise". I did not use the tool here, but the idea is what I did by hand: measure many placements of the same code, and compare the difference you care about with the spread of placements.
So when a small change moves a number, I now look at three things. First, the A/A noise, as in the previous parts. Second, the addresses of the hot loop in both builds, with objdump: if they moved, layout is a possible explanation. Third, a placement test like this one: add some padding before the hot code, or change the order of the functions, and see if the "improvement" survives. If a 5 percent win disappears when I add 16 bytes of nop somewhere, it was not a win of the code.
The generated program, the assembly, the offsets and the three runs are in the fixture, in p15-code-alignment.txt.