During optimization of a part of code for Cortex-A53 (aarch64), I encountered a strange cache behavior.
In a reduced case (see below) I'm reading numbers from a 2D array, row by row. The strange thing is, that if I don't iterate through whole row, but a short final part is omitted, the processing time increases. What's more, when going from the last row to the first, this effect is not observed.
The following code shows this behavior with the use of google-benchmark framework.
#include <iostream>
#include <benchmark/benchmark.h>
constexpr int CACHE_LINE_SIZE = 64;
using ElementType = int32_t;
constexpr int BUFFER_H = 1024;
constexpr int BUFFER_W = 4096; // in bytes
template <int X_END_BYTES> void BM_go_forward(benchmark::State& state)
{
static __attribute__((aligned(CACHE_LINE_SIZE)))
ElementType data[BUFFER_H][BUFFER_W / sizeof(ElementType)] = {5};
int X_END = X_END_BYTES / sizeof(ElementType);
for (auto _: state)
{
auto tmp = 0;
for (int yc = 0; yc < BUFFER_H; ++yc)
{
for (int x = 0; x < X_END; ++x)
{
tmp += data[yc][x];
tmp /= 2;
}
}
benchmark::DoNotOptimize(tmp);
}
}
template <int X_END_BYTES> void BM_go_backward(benchmark::State& state)
{
static __attribute__((aligned(CACHE_LINE_SIZE)))
ElementType data[BUFFER_H][BUFFER_W / sizeof(ElementType)] = {5};
int X_END = X_END_BYTES / sizeof(ElementType);
for (auto _: state)
{
auto tmp = 0;
int y = BUFFER_H-1;
for (int yc = 0; yc < BUFFER_H; ++yc, --y)
{
for (int x = 0; x < X_END; ++x)
{
tmp += data[y][x];
tmp /= 2;
}
}
benchmark::DoNotOptimize(tmp);
}
}
constexpr int ITERS = 100;
BENCHMARK_TEMPLATE(BM_go_forward, BUFFER_W)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_forward, BUFFER_W - CACHE_LINE_SIZE * 1)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_forward, BUFFER_W - CACHE_LINE_SIZE * 2)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_forward, BUFFER_W - CACHE_LINE_SIZE * 4)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_forward, BUFFER_W - CACHE_LINE_SIZE * 6)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_forward, BUFFER_W - CACHE_LINE_SIZE * 8)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_forward, BUFFER_W - CACHE_LINE_SIZE * 10)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_forward, BUFFER_W - CACHE_LINE_SIZE * 12)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_forward, BUFFER_W - CACHE_LINE_SIZE * 14)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_forward, BUFFER_W - CACHE_LINE_SIZE * 16)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_forward, BUFFER_W - CACHE_LINE_SIZE * 20)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_forward, BUFFER_W - CACHE_LINE_SIZE * 24)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_forward, BUFFER_W - CACHE_LINE_SIZE * 28)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_forward, BUFFER_W - CACHE_LINE_SIZE * 32)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_backward, BUFFER_W)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_backward, BUFFER_W - CACHE_LINE_SIZE * 1)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_backward, BUFFER_W - CACHE_LINE_SIZE * 2)->Iterations(ITERS);
BENCHMARK_TEMPLATE(BM_go_backward, BUFFER_W - CACHE_LINE_SIZE * 4)->Iterations(ITERS);
The output on Raspberry PI 3B+ is as follows:
--------------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------------------------------------------------
BM_go_forward<BUFFER_W>/iterations:100 5.67 ms 5.67 ms 100
BM_go_forward<BUFFER_W - CACHE_LINE_SIZE * 1>/iterations:100 6.53 ms 6.53 ms 100
BM_go_forward<BUFFER_W - CACHE_LINE_SIZE * 2>/iterations:100 6.46 ms 6.46 ms 100
BM_go_forward<BUFFER_W - CACHE_LINE_SIZE * 4>/iterations:100 7.22 ms 7.22 ms 100
BM_go_forward<BUFFER_W - CACHE_LINE_SIZE * 6>/iterations:100 7.02 ms 7.02 ms 100
BM_go_forward<BUFFER_W - CACHE_LINE_SIZE * 8>/iterations:100 6.77 ms 6.77 ms 100
BM_go_forward<BUFFER_W - CACHE_LINE_SIZE * 10>/iterations:100 6.51 ms 6.50 ms 100
BM_go_forward<BUFFER_W - CACHE_LINE_SIZE * 12>/iterations:100 5.94 ms 5.94 ms 100
BM_go_forward<BUFFER_W - CACHE_LINE_SIZE * 14>/iterations:100 4.69 ms 4.69 ms 100
BM_go_forward<BUFFER_W - CACHE_LINE_SIZE * 16>/iterations:100 4.50 ms 4.50 ms 100
BM_go_forward<BUFFER_W - CACHE_LINE_SIZE * 20>/iterations:100 4.17 ms 4.17 ms 100
BM_go_forward<BUFFER_W - CACHE_LINE_SIZE * 24>/iterations:100 3.84 ms 3.84 ms 100
BM_go_forward<BUFFER_W - CACHE_LINE_SIZE * 28>/iterations:100 3.48 ms 3.48 ms 100
BM_go_forward<BUFFER_W - CACHE_LINE_SIZE * 32>/iterations:100 3.14 ms 3.14 ms 100
BM_go_backward<BUFFER_W>/iterations:100 6.00 ms 6.00 ms 100
BM_go_backward<BUFFER_W - CACHE_LINE_SIZE * 1>/iterations:100 5.81 ms 5.81 ms 100
BM_go_backward<BUFFER_W - CACHE_LINE_SIZE * 2>/iterations:100 5.75 ms 5.75 ms 100
BM_go_backward<BUFFER_W - CACHE_LINE_SIZE * 4>/iterations:100 5.53 ms 5.53 ms 100
I tried profiling with oprofile I attach results for L1D_CACHE_REFILL and PREFETCH_LINEFIL events:
CPU: ARM Cortex-A53, speed 1400 MHz (estimated)
Counted L1D_CACHE_REFILL events (Level 1 data cache refill) with a unit mask of 0x00 (No unit mask) count 10007
Counted PREFETCH_LINEFILL events (Linefill because of prefetch) with a unit mask of 0x00 (No unit mask) count 10007
samples % samples % image name symbol name
31 1.6316 639 6.7214 all_benchmarks void BM_go_forward<4096>(benchmark::State&)
121 6.3684 545 5.7326 all_benchmarks void BM_go_forward<4032>(benchmark::State&)
123 6.4737 544 5.7221 all_benchmarks void BM_go_forward<3968>(benchmark::State&)
213 11.2105 454 4.7754 all_benchmarks void BM_go_forward<3840>(benchmark::State&)
207 10.8947 453 4.7649 all_benchmarks void BM_go_forward<3712>(benchmark::State&)
200 10.5263 456 4.7965 all_benchmarks void BM_go_forward<3584>(benchmark::State&)
193 10.1579 463 4.8701 all_benchmarks void BM_go_forward<3456>(benchmark::State&)
147 7.7368 491 5.1646 all_benchmarks void BM_go_forward<3328>(benchmark::State&)
48 2.5263 583 6.1323 all_benchmarks void BM_go_forward<3200>(benchmark::State&)
50 2.6316 557 5.8588 all_benchmarks void BM_go_forward<3072>(benchmark::State&)
46 2.4211 525 5.5222 all_benchmarks void BM_go_forward<2816>(benchmark::State&)
46 2.4211 484 5.0910 all_benchmarks void BM_go_forward<2560>(benchmark::State&)
39 2.0526 435 4.5756 all_benchmarks void BM_go_forward<2304>(benchmark::State&)
40 2.1053 403 4.2390 all_benchmarks void BM_go_forward<2048>(benchmark::State&)
61 3.2105 614 6.4584 all_benchmarks void BM_go_backward<4096>(benchmark::State&)
59 3.1053 612 6.4374 all_benchmarks void BM_go_backward<4032>(benchmark::State&)
60 3.1579 606 6.3743 all_benchmarks void BM_go_backward<3968>(benchmark::State&)
52 2.7368 615 6.4689 all_benchmarks void BM_go_backward<3840>(benchmark::State&)
Cpu scaling is disabled. Process was run as a realtime one during profiling. Code was compiled with -O3. I observed no differences in an assembly code of the inner loop in different instantations of the benchmark function.
I suspect this behavior is related to the prefetcher of L1 cache but I'm not an expert in caches topic. Can anyone explain reasons of such a performance drop, and why is it observed only when visiting rows in forward order and not in backward?