Микробенчмарк — обратная итерация приводит к меньшему количеству промахов в кэше ⇐ C++

[Anonymous]

У меня есть очень простой тест:

Код: Выделить всё

void BM_forward_iteration_carray(benchmark::State& state)
{
srand(1);
const unsigned int N = state.range(0);
unsigned long* v1 = (unsigned long*) malloc(sizeof(unsigned int) * N);
unsigned long* v2 = (unsigned long*) malloc(sizeof(unsigned int) * N);
volatile unsigned long* v3 = (unsigned long*) malloc(sizeof(unsigned int) * N);

for (size_t i = 0; i < N; i++)
{
v1[i] = rand();
v2[i] = rand();
}

for (auto _ : state)
{
for (int i = 5; i < N; ++i)
{
v3[i] = v1[i] + v2[i];
}
benchmark::ClobberMemory();
}

state.SetItemsProcessed(N*state.iterations());
}

void BM_backward_iteration_carray(benchmark::State& state)
{
srand(1);
const unsigned int N = state.range(0);
unsigned long* v1 = (unsigned long*) malloc(sizeof(unsigned int) * N);
unsigned long* v2 = (unsigned long*) malloc(sizeof(unsigned int) * N);
volatile unsigned long* v3 = (unsigned long*) malloc(sizeof(unsigned int) * N);

for (size_t i = 0; i < N; i++)
{
v1[i] = rand();
v2[i] = rand();
}

for (auto _ : state)
{
for (int i = N - 1; i > 4; --i)
{
v3[i] = v1[i] + v2[i];
}
benchmark::ClobberMemory();
}

state.SetItemsProcessed(N*state.iterations());
}

Как вы можете видеть, разница между этими двумя функциями состоит только в том, что одна выполняет итерацию назад, а другая вперед.
Результат следующий:
Результат следующий:
р>

Код: Выделить всё

    Benchmark                                     Time             CPU   Iterations UserCounters...
-----------------------------------------------------------------------------------------------
BM_forward_iteration_carray/4194304     1462585 ns      1443273 ns          498 items_per_second=2.90611G/s
BM_backward_iteration_carray/4194304    1318551 ns      1317771 ns          498 items_per_second=3.18288G/s

Таким образом, обратная итерация выполняется немного быстрее. Я собираю компиляцию с использованием последней версии MSVC, и инструкции по сборке выглядят почти так же.
Вперед:

Код: Выделить всё

$LN3@BM_forward:
mov     DWORD PTR i$1[rsp], 5
jmp     SHORT $LN7@BM_forward
$LN5@BM_forward:
mov     eax, DWORD PTR i$1[rsp]
inc     eax
mov     DWORD PTR i$1[rsp], eax
$LN7@BM_forward:
cmp     DWORD PTR i$1[rsp], 10000   ; 00002710H
jae     SHORT $LN6@BM_forward
movsxd  rax, DWORD PTR i$1[rsp]
movsxd  rcx, DWORD PTR i$1[rsp]
mov     rdx, QWORD PTR v1$[rsp]
mov     eax, DWORD PTR [rdx+rax*4]
mov     rdx, QWORD PTR v2$[rsp]
add     eax, DWORD PTR [rdx+rcx*4]
movsxd  rcx, DWORD PTR i$1[rsp]
mov     rdx, QWORD PTR v3$[rsp]
mov     DWORD PTR [rdx+rcx*4], eax
jmp     SHORT $LN5@BM_forward

Назад:

Код: Выделить всё

$LN3@BM_backwar:
mov     DWORD PTR i$1[rsp], 9999      ; 0000270fH
jmp     SHORT $LN7@BM_backwar
$LN5@BM_backwar:
mov     eax, DWORD PTR i$1[rsp]
dec     eax
mov     DWORD PTR i$1[rsp], eax
$LN7@BM_backwar:
cmp     DWORD PTR i$1[rsp], 4
jle     SHORT $LN6@BM_backwar
movsxd  rax, DWORD PTR i$1[rsp]
movsxd  rcx, DWORD PTR i$1[rsp]
mov     rdx, QWORD PTR v1$[rsp]
mov     eax, DWORD PTR [rdx+rax*4]
mov     rdx, QWORD PTR v2$[rsp]
add     eax, DWORD PTR [rdx+rcx*4]
movsxd  rcx, DWORD PTR i$1[rsp]
mov     rdx, QWORD PTR v3$[rsp]
mov     DWORD PTR [rdx+rcx*4], eax
jmp     SHORT $LN5@BM_backwar

Единственная разница, которую я вижу, — это прямое движение с использованием инструкции jae и обратное с использованием инструкции jle.
Согласно AMDuProf, прямая версия имеет более высокий процент промахов кэша. Это могло бы объяснить результат, однако я не уверен, почему.


Отсюда и вопрос: почему прямая итерация приводит к большему количеству промахов в кэше L1?

Подробнее здесь: https://stackoverflow.com/questions/793 ... che-misses