How to explain poor performance on Xeon processors for a loop with both sequential copy and a scattered store?

Question

I stumbled upon a peculiar performance issue when running the following c++ code on some Intel Xeon processors:

// array_a contains permutation of [0, n - 1]
// array_b and inverse are initialized arrays
for (int i = 0; i < n; ++i) {
  array_b[i] = array_a[i];
  inverse[array_b[i]] = i;
}

The first line of the loop sequentially copies array_a into array_b (very few cache misses expected). The second line computes the inverse of array_b (many cache misses expected since array_b is a random permutation). We may also split the code into two separate loops:

for (int i = 0; i < n; ++i)
  array_b[i] = array_a[i];
for (int i = 0; i < n; ++i)
  inverse[array_b[i]] = i;

I would have expected the two versions (single vs. dual loop) to perform almost identically on relatively modern hardware. However, it appears that some Xeon processors are incredibly slow when executing the single loop version.

Below you can see the wall time in nano-seconds divided by n when running the snippet on a range of different processors. For the purpose of testing, the code was compiled using GCC 7.5.0 with flags -O3 -funroll-loops -march=native on a system with a Xeon E5-4620v4. Then, the same binary was used on all systems, using numactl -m 0 -N 0 on systems with multiple NUMA domains.

The used code is available on github. The interesting stuff is in the file runner.cpp.

[EDIT:] The assembly is provided here.

[EDIT:] New results including AMD EPYC.

On the various i7 models, the results are mostly as expected. Using the single loop is only slightly slower than the dual loops. This also holds for the Xeon E3-1271v3, which is basically the same hardware as an i7-4790. The AMC EPYC 7452 performed best by far, with almost no difference between the single and dual loop implementation. However, on the Xeon E5-2690v4 and E5-4620v4 systems using the single loop is incredibly slow.

In previous tests I also observed this strange performance issue on Xeon E5-2640 and E5-2640v4 systems. In contrast to that, there was no performance issue on several AMD EPYC and Opteron systems, and also no issues on Intel i5 and i7 mobile processors.

My question to the CPU experts thus is: Why does Intel's most high-end product-line perform so poorly compared to other CPUs? I am by far no expert in CPU architectures, so your knowledge and thoughts are much appreciated!

Answer 1

After playing with a minimized example shown below I'm concluding that the root cause is a variant of the 2017 question by Travis Downs titled Unexpectedly poor and weirdly bimodal performance for store loop on Intel Skylake, for which he provided further specu^Wdiscussion in his 2019 blog post What Has Your Microcode Done for You Lately? and 2020 post to RWT. I think the graphs shown in the question show how the effect is exacerbated on multi-socket systems, where responses to RFOs take longer, making RFO serialization more visible.

In my test program, a PRNG is used instead of an extra array with permuted indices, and the effect is still visible. The PRNG has latency 4 cycles, and you can see that when the working set fits in L1 cache, each iteration takes a bit more that 4 * (1 << log_sz) cycles. When there are L1 misses, a great slowdown is observed, with apparently-useless prefetches recovering a lot of performance. Sticking the same magic prefetch in the original program also improves performance.

#include <stddef.h>
#include <stdio.h>
#include <stdint.h>

#include <sys/mman.h>

static uint64_t prng(int bits)
{
    static uint64_t state = 0;
    uint64_t ret = state >> (64 - bits);
    state = state * 6364136223846793005 + 1;
    return ret;
}

typedef uint64_t T;

typedef void fn(volatile T *, int, int);

static void no_prefetch(volatile T *buf, int log_n, int chunk)
{
    size_t n = (size_t)1 << log_n;
    for (size_t i, k = 0; k < n; k = i) {
        for (i = k; i < k + chunk; i++) {
            buf[i] = 0;
        }
        for (i = k; i < k + chunk; i++) {
            size_t j = prng(log_n);
            buf[j] = 0;
        }
    }
}

static void do_prefetch(volatile T *buf, int log_n, int chunk)
{
    size_t n = (size_t)1 << log_n;
    for (size_t i, k = 0; k < n; k = i) {
        for (i = k; i < k + chunk; i++) {
            buf[i] = 0;
        }
        for (i = k; i < k + chunk; i++) {
            size_t j = prng(log_n);
            __builtin_prefetch((T*)buf+j, 1);
            buf[j] = 0;
        }
    }
}

static fn *const fns[] = { no_prefetch, do_prefetch };

int main(int argc, char **argv)
{
    unsigned with_prefetch, chunk, log_sz, reps;
    if (argc < 2 || sscanf(argv[1], "%u", &with_prefetch) != 1)
        with_prefetch = 0;
    if (argc < 3 || sscanf(argv[2], "%u", &chunk) != 1)
        chunk = 1;
    if (argc < 4 || sscanf(argv[3], "%u", &log_sz) != 1)
        log_sz = 13;
    if (argc < 5 || sscanf(argv[4], "%u", &reps) != 1)
        reps = 10000;
    size_t sz = sizeof(T) << log_sz;
    void *m;

    if ((m = mmap(0, sz, PROT_READ | PROT_WRITE,
              MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)) == MAP_FAILED)
        return 1;

    for (; reps; reps--)
        fns[with_prefetch](m, log_sz, chunk);
}

Answer 2

Maybe this is related to avx-512 frequendy throttling on Intel processors. These instructions generate a lot of heat, and if used on some circunstances the processor reduces the working frequency.

Here are some benchmarks for OpenSSL that show the effect. There is a rant from Linus Torvalds on this topic.

If avx-512 instructions are generated with "-march=native" you may be suffering this effect. Try disabling avx-512 with:

gcc -mno-avx512f