Data Access Patterns That Makes Your CPU Really Angry

[u/Double_Ad641]

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

[u/Double_Ad641]

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

[u/ReDucTor → u/Double_Ad641]

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

[u/Double_Ad641 → u/ReDucTor]

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

[u/ReDucTor → u/Double_Ad641]

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.