Why does this function run so much faster when it makes an extra read of memory?

I'm currently trying to understand the performance properties of certain loops on x86_64 (specifically, my Intel(R) Core(TM) i3-8145U CPU @ 2.10GHz processor). Specifically, adding an extra instruction to read memory inside the body of the loop almost doubles the performance, with the details not being particularly important.

I've been using a test program that consists of two main parts: a testing loop, and a function under test. The testing loop runs the function under test 2³² times, once with each signed 32-bit integer as argument (in order from INT_MIN to INT_MAX). The function under test (named body) is a small function that checks to see if it was called with the expected arguments, and records the error in a global variable otherwise. The test program touches a sufficiently small amount of memory that everything is likely to fit in the L1 cache.

In order to eliminate any speed differences that might be caused by the behaviour of a compiler, I wrote both of the functions in question in assembly language (I'm using clang as the assembler), and have been forced to start at fixed addresses (the performance of this sort of test loop often gets dominated by effects relating to alignment or caching, so using fixed addresses will eliminate any alignment effects or cache effects unrelated to the change).

Here's the test loop, disassembled (it takes the address of the function to loop over in %rdi):

  401300:       53                      push   %rbx
  401301:       55                      push   %rbp
  401302:       51                      push   %rcx
  401303:       48 89 fd                mov    %rdi,%rbp
  401306:       bb 00 00 00 80          mov    $0x80000000,%ebx
loop:
  40130b:       89 df                   mov    %ebx,%edi
  40130d:       ff d5                   callq  *%rbp
  40130f:       83 c3 01                add    $0x1,%ebx
  401312:       71 f7                   jno    40130b <loop>
  401314:       59                      pop    %rcx
  401315:       5d                      pop    %rbp
  401316:       5b                      pop    %rbx
  401317:       c3                      retq   

and here's the simplest version of body, the function under test:

  401200:       33 3d 3a 3e 00 00       xor    0x3e3a(%rip),%edi        # 405040 <next_expected>
  401206:       09 3d 30 3e 00 00       or     %edi,0x3e30(%rip)        # 40503c <any_errors>
  40120c:       ff 05 2e 3e 00 00       incl   0x3e2e(%rip)        # 405040 <next_expected>
  401212:       c3                      retq

(The basic idea is that body checks to see if its argument %edi is equal to next_expected, and sets any_errors to a nonzero value if it isn't, otherwise leaving it unchanged. Then it increments next_expected.)

The test loop, with this version of body as %rdi, takes approximately 11 seconds to run on my processor. However, adding in an extra read of memory causes it to run in under 6 seconds (a difference much too large to be explained by random variation):

  401200:       33 3d 3a 3e 00 00       xor    0x3e3a(%rip),%edi        # 405040 <next_expected>
  401206:       09 3d 30 3e 00 00       or     %edi,0x3e30(%rip)        # 40503c <any_errors>
  40120c:       33 3d 2e 3e 00 00       xor    0x3e2e(%rip),%edi        # 405040 <next_expected>
  401212:       ff 05 28 3e 00 00       incl   0x3e28(%rip)        # 405040 <next_expected>
  401218:       c3                      retq

I've tried lots of different variants of this code to see what specific properties of the additional statement (labelled 401212 above) give the "fast" behaviour. The common pattern seems to be that the statement needs to read from memory. The various statements I've tried there (note: each of these is a single statement that's exactly 6 bytes long, so there are no alignment considerations to worry about):

These statements run quickly (~6 seconds):

• It doesn't seem to matter what operation we read the memory with:
  • xor 0x3e2e(%rip),%edi # 405040 <next_expected>
  • and 0x3e2e(%rip),%edi # 405040 <next_expected>
  • mov 0x3e2e(%rip),%edi # 405040 <next_expected>
• or what register we read into:
  • and 0x3e2e(%rip),%eax # 405040 <next_expected>
• or (in most cases) what we're reading:
  • xor 0x11c7(%rip),%edi # 4023d9 <main>
  • or -0x12(%rip),%edi # 401200 <body>
• or whether we're writing to memory in addition to reading it:
  • xor %edi,0x3e2a(%rip) # 40503c <junk>
• Additionally, adding xor 0x11c7(%rip),%edi # 4023d9 <main>, but after rather than before the incl command, also gave fast performance.

These statements run slowly (~11 seconds):

• It isn't sufficient to use an instruction that's 6 bytes long but doesn't read memory:
  • nopw %cs:(%rax,%rax,1)
  • lea 0x3e2e(%rip),%edi # 405040 <next_expected>
• It isn't sufficient to write memory without reading it:
  • mov %edi,0x3e2a(%rip) # 40503c <junk>

Additionally, I tried writing the read value back to next_expected rather than incrementing it in place:

  401200:       33 3d 3a 3e 00 00       xor    0x3e3a(%rip),%edi        # 405040 <next_expected>
  401206:       09 3d 30 3e 00 00       or     %edi,0x3e30(%rip)        # 40503c <any_errors>
  40120c:       8b 3d 2e 3e 00 00       mov    0x3e2e(%rip),%edi        # 405040 <next_expected>
  401212:       ff c7                   inc    %edi
  401214:       89 3d 26 3e 00 00       mov    %edi,0x3e26(%rip)        # 405040 <next_expected>
  40121a:       c3                      retq

This had a performance very close to the original 11-second program.

One anomaly is the statement xor 0x3e2a(%rip),%edi # 40503c <any_errors>; adding that as the 401212 statement consistently gave a performance of 7.3 seconds, not matching either of the other two performances. I suspect that what's happening here is that the read of memory is sufficient to send the function onto the "fast path", but the statement itself is slow (because we just wrote any_errors in the preceding line; writing and immediately reading the same memory address is something that processors can struggle with), and thus we're getting fast-path performance + a slowdown from the use of a slow statement. Something similar happens if I add a read of next_expected (rather than main after rather than before the incl statement (again, we're reading a memory address that was just written, so the similar behaviour is not surprising).

Another experiment was adding xor next_expected(%rip), %eax earlier in the function (before the write to %edi or right at the start, before the read of next_expected). These gave a performance of around 8.5 seconds.

Anyway, at this point it seems fairly clear what is causing the fast behaviour (adding an additional read from memory is making the function run faster, at least when it's combined with the specific test loop shown here; it wouldn't surprise me if the details of the test loop were relevant). What I don't understand, though, is why the processor would behave like this. In particular, is there a general rule that can be used to work out when adding an extra read to a program will make it run (this much) faster?

If you want to experiment with this yourself

Here's a minimal version of the program that can be compiled and run, and exhibits this problem (this is C with gcc/clang extensions, and specific to x86_64 processors):

#include <limits.h>

unsigned any_errors = 0;
unsigned next_expected = INT_MIN;

extern void body(signed);
extern void loop_over_all_ints(void (*f)(signed));

asm (
    ".p2align 8\n"
    "body:\n"
    "   xor next_expected(%rip), %edi\n"
    "   or %edi, any_errors(%rip)\n"
//    " xor next_expected(%rip), %edi\n"
    "   addl $2, next_expected(%rip)\n"
    "   retq\n"

    ".p2align 8\n"
    "loop_over_all_ints:\n"
    "   push %rbx\n"
    "   push %rbp\n"
    "   push %rcx\n"
    "   mov %rdi, %rbp\n"
    "   mov $0x80000000, %ebx\n"
    "loop:\n"
    "   mov %ebx, %edi\n"
    "   call *%rbp\n"
    "   inc %ebx\n"
    "   jno loop\n"
    "   pop %rcx\n"
    "   pop %rbp\n"
    "   pop %rbx\n"
    "   retq\n"
    );

int
main(void)
{
    loop_over_all_ints(&body);
    return 0;
}

(The commented-out line is an example of an extra memory read that makes the program run faster.)

Further experiments

After posting the question, I tried some further experiments in which the testing loop was unrolled to depth 2, and modified so that the two calls to the function under test could now be made to go to two different functions. When calling the loop with body as both functions, there was still a clear performance difference between the versions of the code with and without the extra memory read (6-7 seconds with, >11 seconds without), giving a clearer platform to look at the differences.

Here are the results of the tests with two separate body functions:

• Same any_errors/next_expected variables for both, no extra read: ~11 seconds
• Same any_errors/next_expected variables for both, extra read for both: 6-7 seconds
• Same any_errors/next_expected variables for both, extra read in one but not the other: 6-7 seconds
• Same next_expected variable but different any_errors variables, no extra reads: ~11 seconds
• Same any_errors variable but different next_expected variables (thus an error is reported), no extra reads: 5-5½ seconds (noticeably faster than any case so far)
• Same any_errors variable but different next_expected variables, addl $2 rather than incl on next_expected (so that no error is reported), no extra reads: 5-5½ seconds
• Same as previous case, but with the extra reads: 5-5½ seconds (and an almost identical cycle count: it's different by only tens of millions compared to the billions of iterations, so the number of cycles per iteration must be the same)

It looks a lot like whatever is going on here is somehow related to the dependency chain on next_expected, because breaking that chain gives faster performance than anything that's possible with the chain present.

Further experiments #2

I've been trying a lot more variations of the program to try to eliminate possibilities. I've now managed to shrink a test case reproducing this behaviour down to the following asm file (built with gas via assembling with as test.s -o test.o; ld test.o; this isn't linking against libc, thus is Linux-specific):

    .bss
    .align 256
a:
    .zero   4
b:
    .zero   4
c:
    .zero   4

        .text
    .p2align 8, 0
    .globl _start
_start:
    mov $0x80000000, %ebx
1:
//  .byte 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x90
//  .byte 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x90, 0x66, 0x90
    mov a(%rip), %esi
    or %esi, b(%rip)
    or $1, a(%rip)
    mov c(%rip), %eax
    add $1, %ebx
    jno 1b

    mov $60, %rax
    mov $0, %rdi
    syscall

There are three versions of the program to compare: the version as written, the version which has 12 single-byte NOP instructions, and the version which has 11 NOP instructions (I made one of them two-byte to get the same alignment as in the 12-NOP case, but it doesn't matter).

When running the program with no NOPs, or with 11 NOPs, it runs in 11 seconds. When 12 single-byte NOPs are used, it runs in 7 seconds.

At this point, I think that it's obvious that something is going wrong when the loop in question runs "too fast", and fixes itself when the loop was artificially slowed down. The original version of the program was presumably bottlenecked on the bandwidth for reading memory from L1 cache; so the problem fixed itself when we added an extra read. This version of the program speeds up when it is (artificially) bottlenecked on the front end; the only difference between "12 single-byte NOPs" and "10 single-byte NOPs and a 2-byte NOP" is how quickly the NOP instructions can get through the front end of the processor. So it seems that the loop runs faster if it's artificially slowed down, and it doesn't seem to matter what mechanism is used to slow it down.

Some performance counter information to exclude possibilities: the loop is running out of the loop stream decoder (lsd.cycles_active over 25 billion, idq.dsb_cycles and idq.mite_cycles less than 10 million, in both the 11-NOP and 12-NOP cases), which eliminates the possibility that the huge number of NOPs added here are overloading the instruction caching mechanisms; and ld_blocks.store_forward is a single digit (I thought store-forwarding might be involved, and it still might be, but this is the only performance counter related to it so we won't get any more information about it this way).

The specific pattern of reads and writes used above is:

• read memory into a register;
• read-modify-write a different address, using the same register;
• read-modify-write the original address;
• read another address (in the original example, the pop of the instruction pointer served as the unrelated read).

This seems to be the simplest pattern that reproduces the behaviour; I haven't found any further simplifications which cause the behaviour to reproduce.

I still have no idea what's going on here, but hopefully this information will be useful to anyone who wants to try to figure it out.