Во время оптимизации части кода для Cortex-A53 (aarch64) я столкнулся со странным поведением кэша.
В уменьшенном случае (см. Ниже) я читаю числа из двумерного массива, строки по ряду. Странно то, что если я не перебираю всю строку, но короткая заключительная часть опускается, время обработки увеличивается. Более того, при переходе от последней строки к первой этот эффект не наблюдается.
Следующий код демонстрирует это поведение с использованием каркаса google-benchmark.
#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);
вывод на Raspberry PI 3B + выглядит следующим образом:
--------------------------------------------------------------------------------------------------------
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
Я попытался выполнить профилирование с помощью oprofile Я прикрепляю результаты для событий L1D_CACHE_REFILL и PREFETCH_LINEFIL:
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&)
Масштабирование процессора составляет отключен. Процесс был запущен в режиме реального времени во время профилирования. Код был скомпилирован с -O3. Я не наблюдал различий в коде сборки внутреннего l oop в разных экземплярах функции сравнения.
Я подозреваю, что это поведение связано с предварительным извлечением кеша L1, но я не эксперт в кешировании топи c. Кто-нибудь может объяснить причины такого снижения производительности, и почему оно наблюдается только при посещении строк в прямом порядке, а не в обратном?