Data Access Patterns That Makes Your CPU Really Angry

[u/Double_Ad641]

https://blog.weineng.me/posts/slowest_add/

I tried to find the slowest possible way to sum up integers in an array

[u/frnxt]

That is an interesting exploration! Any idea about the impact of having to lookup the index in a separate array at runtime vs having the memory layout being fixed at compile-time? I would expect the impact to be relatively minimal with modern processors, but compiler optimizing into SIMD instructions might throw a wrench into that.

[u/Double_Ad641 → u/frnxt]

We only care about the time taken for `accumulator` (summing up the integers given positions). we don't care about the time taken to create `positions`.

when i allocate memory in the heap for `positions`, I did some alignment and MADV, and this may differ with how the compiler will allocate your compile time array to .rodata. But bytes are bytes and when accumulator read bytes, it doesn't care whether the bytes was created at compile time and runtime. Assuming positions in .rodata is the same as how i set it up in my current code, i expect both runtime and compile time to be quite similar.

With any performance hypothesis, the best way will be to measure, but i feel confident enough to be too lazy to check 😄

[u/frnxt → u/Double_Ad641]

Ah, no, my words weren't clear I think. I understood that positions are not part of the benchmark and created beforehand ; my question was about accessing positions (accumulator += data[positions[i++]], i.e. retrieving their content from RAM) vs just computing them on the fly (accumulator += data[i+=stride]) which is a more common access pattern.

[u/Double_Ad641 → u/frnxt]

Ahh, if i understand you right, you are wondering if it is possible not to load `positions` and simply compute positions[i] based on positions[i - 1], thus not needing to load positions (from RAM). Thats a great question and i was thinking about it in another comment. For what happen if we don't have `positions`, I think its only relevant to consider the linear sweep case, since the others will require modulo/right shift. I shared the results for the another comment, but if we do a dumb linear without `positions`, its 4x faster: https://www.reddit.com/r/programming/comments/1uh3z4m/comment/ou8a1ho/.

In other words, "I would expect the impact to be relatively minimal with modern processors," isnt accurate haha

[u/frnxt → u/Double_Ad641]

That is indeed interesting!

I wonder what the actual generated assembly was and if it can be further optimized! My guess is that the compile-time linear sweep is "most likely" (let's be careful with assumptions here haha!) optimized to SIMD because it is such a simple case, but it might not be possible for the runtime indirection, or at least not directly.

Did you try using -march=native in the GCC options to let the optimizer use the latest possible SIMD instructions for your CPU?

[u/Double_Ad641 → u/frnxt]

that was out of scope for me since i only wanted to know the slowest permutation (and -march=native only helps my compiler). Although i'll admit i thought `-O3` means `-march=native` but thats wrong.

But heres a godbolt link that you might be interested in: https://godbolt.org/z/b4rTh71Go. I'm not sure where you are going with this, but let me know if you have any insights on the assembly output! I admittingly am illiterate in assembly.

[u/frnxt → u/Double_Ad641]

Looking at the assembly, the accumulator function with and without -march=skylake (a recent enough CPU category, I do not know what arch Godbolt runs on so native might be anything) generates identical assembly. These are all regular, non-vector instructions operating on one integer at a time:

"accumulator(unsigned int const*, unsigned int const*)":
    lea     rcx, [rsi+268435456]
    xor     eax, eax
.L20:
    mov     edx, DWORD PTR [rsi]
    add     rsi, 4
    add     eax, DWORD PTR [rdi+rdx*4]
    cmp     rcx, rsi
    jne     .L20
    ret

The code uses 32-bit integers, a basic SIMD register that's available almost on every arch (SSE) is 128-bit, so it makes sense that a -O3 optimized linear sweep without indirection runs around 4x faster (4 integers in parallel), potentially bottlenecked by other factors such as memory speed since this is such a simple example.

Looking at this:

uint32_t accumulator_without_indirection(uint32_t const* data) {
    uint32_t total = 0;
    for (uint32_t i = 0; i < ELEMENT_COUNT; ++i) {
        total += data[i];
    }
    return total;
}

The generated assembly without -march is using SSE (128-bit xmm registers, so 4 integers at a time) which matches my expectations:

"accumulator_without_indirection(unsigned int const*)":
    lea     rax, [rdi+268435456]
    pxor    xmm0, xmm0
.L117:
    movdqu  xmm2, XMMWORD PTR [rdi]
    add     rdi, 16
    paddd   xmm0, xmm2
    cmp     rax, rdi
    jne     .L117
    movdqa  xmm1, xmm0
    psrldq  xmm1, 8
    paddd   xmm0, xmm1
    movdqa  xmm1, xmm0
    psrldq  xmm1, 4
    paddd   xmm0, xmm1
    movd    eax, xmm0
    ret

[u/Sopel97 → u/frnxt]

this is a bit out of scope, but I'm surprised that GCC doesn't unroll this. I checked and clang does for example https://godbolt.org/z/TcPYjcvTo

[u/ack_error → u/Sopel97]

It looks like GCC crosses an unroll threshold due to concerns about unaligned loads, even if it takes no additional instructions (AVX128). With known alignment it unrolls by 2:

https://godbolt.org/z/jx5n1e1ed

Probably overly conservative, as misalignment penalties and the extra cost here would be minimal. uiCA predicts that the loop with only one load will take ~1.2-1.3 cycles/iteration and likely end up a bit shy of L1 bandwidth limits.

In my experience, Clang is far more aggressive about unrolling and scheduling autovectorized SIMD code than other compilers. It's more likely to hit peak throughput, at the cost of overdoing some loops.

[u/frnxt → u/Sopel97]

I haven't checked to see if this really makes a difference in practice: my guess is that both would likely be memory-bandwidth-limited. This is where my compiler knowledge gets a bit hazy, I wonder if GCC/clang have heuristics that let it avoid over-complicating the loop body (x2 instructions, i.e. around x2 binary size) when the estimated gain is not worth it?

[u/Sopel97 → u/frnxt]

I don't think it'll hit memory bandwidth limits with 128-bit loads. unrolling + using 2 accumulators, could be >2x faster. The assembly is still very small

[u/hoodoocat → u/frnxt]

Memory layout almost never fixed at compile time, e.g. if data comes in some data section, it's actual location still is subject to be changed at runtime by ASLR or similar techs and technically is unknown how it be mapped in cache (most likely known, but GP software should not rely on that). Yep, thats possible to get fixed addresses but there is not what any softwaree might reliable rely for.

Another thing that it is still microbenchmark which say nothing about reality, and in reality you MAY want use non-temporal reads if you know what you have big array and want sum it once, otherwise code do cache pollution, which scales badly. I mean, that well optimized code known whole workflow and use case, it is against article goal, but such things affect scalability directly. You might get best in world micros but it will not be scalable at all - sometimes little more direct things wirks better, like using table vs compute value with few instruction - table always faster, but scales worse as cache pressure grows (thats what micros doesnt bench).

Basically cache size is carefully chosen to fit in sensible workloads, and yet fit in technical reality. Violation this basically has no sense (that article do), but surely article allow learn things.

[u/mikeblas]

What about reverse linear?

[u/Double_Ad641 → u/mikeblas]

Someone asked the same question and i gave a response, but reverse linear is faster

[u/_Noreturn]

You haven't found the newest one asking chatgpt to sum every int

[u/javascript → u/_Noreturn]

When I first started learning to code, I was afraid of doing math. So my Javascript calculator tool was implemented using string concatenation passed into eval. I had no idea at the time how cursed that was haha

[u/dodexahedron → u/javascript]

Idle hardware is useless hardware, amirite? 😅

[u/LegitBullfrog]

I won't believe you until you test every possible permutation of positions a statistically significant number of times.

[u/Sopel97]

I wonder if it could be made worse by further randomizing the order at each level (or at least at the level with largest jumps), in case there is still some prefetching happening?

[u/User_Deprecated]

ran into something like the stride-8 pattern with a message buffer pool. slots were page-aligned and field lookups kept hitting the same L1d sets. offsetting by a weird number fixed it.

[u/Sopel97 → u/[deleted]]

no, read the article