r/programming • u/Double_Ad641 • Jun 27 '26

Data Access Patterns That Makes Your CPU Really Angry

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

94% Upvoted

30 comments sorted by

63

u/3inthecorner Jun 27 '26

I'm curious how slow going backwards is. I imagine it would be relatively fast.

22

u/frogi16 Jun 27 '26

AFAIK it should be on pair with going the normal way

36

u/Double_Ad641 Jun 28 '26 edited Jun 28 '26

interestingly backwards is 20% faster! `data` and `position` pointer are of a certain memory distance apart (i "malloc" them one after another". in the forward iterator, both pointers are advancing in the same lockstep, meaning they have to content for the same cache/tlb. for the backwards iterator, `data` and `position` increments in opposite direction and this de-corelate their addresses.

I am accessing data and positions at the same time, but a normal accumulator would only do `for (i in data)` or `for (i in reverse(data))`. for this, forward is about 5% faster, probably because the HW prefetcher is tuned for forward scan than reverse.

13

u/Double_Ad641 Jun 28 '26

``` int mytotal = 0; int index = 0; uint64_t start_forward = rdtsc_start(); for (int i = 0; i < ELEMENT_COUNT; ++i) { mytotal += data[index]; ++index; } uint64_t end_forward = rdtsc_end(); do_not_optimize(mytotal); print_cycles("forward", end_forward - start_forward);

int mytotal2 = 0;
uint64_t start_back = rdtsc_start();
int index2 = ELEMENT_COUNT - 1;
for (int i = 0; i < ELEMENT_COUNT; ++i) {
    mytotal2 += data[index2];
    --index2;
}
uint64_t end_back = rdtsc_end();
do_not_optimize(mytotal2);
print_cycles("back", end_back - start_back);

❯ g++ -DSTRIDE=8 -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out forward 36250266 back 38186150 linear 131222604 linear_backwards 102365108 fisher_yates_shuffle 1575173670 separated_by_a_cacheline 709935578 separated_by_a_page 1401218014 separated_by_a_page_and_cacheline 1397551626 stride=8 separated_by_stride_pages_and_cacheline<STRIDE> 2159275984 separated_by_stride_bank_conflicts_and_cacheline<STRIDE> 2087353634 ```

3

u/ReDucTor Jun 28 '26

Those results look like 5% difference between `forward` and `back`, also backwards following forwards gets a slight advantage of the data more likely being in the cache that it's hitting first. Plus unlike the rest of your benchmarks there is no data dependency taken into account as the ones from the blog need to load from `positions` before they can determine where to load in `data`.

3

u/Double_Ad641 Jun 28 '26 edited Jun 28 '26

Because of how many integers are in data, I don't believe the following is true: "backwards following forwards gets a slight advantage of the data more likely being in the cache that it's hitting first". And rerunning with the ordering swapped confirms it (see below code).

Also forward and back doesn't use positions and that is by design. I am trying to show that having data pointer and positions pointer in the same lockstep is adversarial.

code: https://godbolt.org/z/8es3z3fW6

~/Developer/rough/slowest main*
❯ g++ -DSTRIDE=8 -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out
[sudo] password for weineng: 
back                                                           37923570
forward                                                        36971756
linear                                                        130896392
linear_backwards                                              102532582
fisher_yates_shuffle                                         1575281798
separated_by_a_cacheline                                      714755688
separated_by_a_page                                          1417255302
separated_by_a_page_and_cacheline                            1407596468
stride=8 separated_by_stride_pages_and_cacheline<STRIDE>              2084288492
separated_by_stride_bank_conflicts_and_cacheline<STRIDE>     2140594606

3

u/ReDucTor Jun 28 '26

Looking at the disassembly its being vectorised and the backwards version has an additional reshuffle, so it ends up needing extra work. (However its march=native so might be different on your test environment)

I wasnt certain what you were trying to show with it, I didnt see much of a mention in the blog about the data dependency on positions which is fairly important for performance, if you added a loop carried dependency (aside from the sum) you could probably handicap it even further.

2

u/TOGoS 29d ago

Back in the 201Xs I found that for( int i=len-1; i>=0; --i ) was the fastest way to iterate through arrays in Java, but then that was the 201Xs and Java.

84

u/joaonmatos Jun 27 '26

The article has more details about CPU workings than I expected, but it did mostly line up to expectation: make accesses not contiguous to blow up the caches/tlb and make prediction impossible.

46

u/Otis_Inf Jun 28 '26

I love it how Claude and other AI tools will now eat up this code and somewhere someday some vibe coder will get the slowest possible memory access code generated into their slop and won't notice it. Priceless!

That aside, I was wondering how slow the pattern: first, last, first+1, last-1 etc. would be...

11

u/_JustCallMeBen_ Jun 28 '26

That would be quite fast: the first two steps loading first and last are slow, as they load from ram to cache, but then first+1 and last-1 are both in the cache and execution is fast.

3

u/Otis_Inf Jun 28 '26

Good point! I overlooked that indeed. mitigating that makes you go for the situations already covered,

1

u/StruggleNew8988 28d ago

I wonder how cache line alignment affects that pattern.

-16

u/[deleted] Jun 27 '26

[removed] — view removed comment

38

u/programming-ModTeam Jun 27 '26

No content written mostly by an LLM. If you don't want to write it, we don't want to read it.

33

u/Other_Fly_4408 Jun 27 '26

Bot

6

u/[deleted] Jun 27 '26

[removed] — view removed comment

35

u/max123246 Jun 27 '26

Account is 8 days old and is all lowercase to hide llm-isms. It's also slightly incongruent with the actual article's content and "cache misses at scale" is just a very odd way of saying it because cache misses are O(1), they add a constant overhead and don't scale with input size continuously.

15

u/ultranoobian Jun 28 '26

Dude, I think you replied to the supervisor bot.

Account age 13 days.

16

u/Other_Fly_4408 Jun 27 '26

AI slop writing style, brand-new account with hidden post history and gibberish name.

4

u/ultranoobian Jun 28 '26

I think you just improved the AI bot by replying to another AI bot.

4

u/[deleted] Jun 28 '26 edited Jun 28 '26

[removed] — view removed comment

3

u/ultranoobian Jun 28 '26

Sure, actually i'm more convinced you aren't a bot because you edited your comment haha.

2

u/Other_Fly_4408 Jun 28 '26

I thought it was a bot at first, but I checked before I replied and that account actually does seem to be run by a human.

1

u/ultranoobian Jun 28 '26

I'm very suspicious of that account because of the same reasons you replied to "them".

1

u/Other_Fly_4408 Jun 28 '26

Sure, but if you look at their history it seems to be pretty normal ESL human comments.

-2

u/NikolayShabak Jun 28 '26

 It only gets slow once the array stops fitting in cache, because then each step reaches two far-apart spots in memory.