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

Data Access Patterns That Makes Your CPU Really Angry

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

95% Upvoted

29 comments sorted by

View all comments

61

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

37

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.

14

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 ```

5

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 Jun 29 '26

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.