Кэш, циклы и производительность

Question

Некоторое время назад я написал небольшой фрагмент кода, чтобы спросить его об интервью и посмотреть, как люди понимают понятия кеш-памяти и памяти:

#include "stdafx.h"
#include <stdlib.h>
#include <windows.h>
#include <iostream>

#define TOTAL 0x20000000

using namespace std;

__int64 count(int INNER, int OUTER)
{
    int a = 0;
    int* arr = (int*) HeapAlloc(GetProcessHeap(), 0, INNER * sizeof(int));
    if (!arr) {
        cerr << "HeapAlloc failed\n";
        return 1;
    }
    LARGE_INTEGER freq;
    LARGE_INTEGER startTime, endTime;
    __int64 elapsedTime, elapsedMilliseconds;
    QueryPerformanceFrequency(&freq);
    QueryPerformanceCounter(&startTime);

    /* Начало работы */

    for (int i = 0; i < OUTER; i++) {
        for (int j = 0; j < INNER; j++) {
            a |= i;
            arr[j] = a;
        }
    }

    /* Конец работы */

    QueryPerformanceCounter(&endTime);
    elapsedTime = endTime.QuadPart - startTime.QuadPart;
    elapsedMilliseconds = (1000 * elapsedTime) / freq.QuadPart;
    HeapFree(GetProcessHeap(), 0, arr);
    return elapsedMilliseconds;
}

int _tmain(int argc, _TCHAR* argv[])
{
    __int64 time;
    for (int INNER = 0x10; INNER <= 0x2000000; INNER <<= 1) {
        int OUTER = TOTAL / INNER;
        time = count(INNER, OUTER);
        cout << INNER << "\t" << OUTER << "\t" << time << "\n";
    }
}

Вот что он компилирует (сам цикл):

00401062  xor         ecx,ecx 
00401064  test        ebp,ebp 
00401066  jle         count+83h (401083h) 
00401068  xor         eax,eax 
0040106A  test        ebx,ebx 
0040106C  jle         count+7Ch (40107Ch) 
0040106E  mov         edi,edi 
00401070  or          esi,ecx 
00401072  mov         dword ptr [edi+eax*4],esi 
00401075  add         eax,1 
00401078  cmp         eax,ebx 
0040107A  jl          count+70h (401070h) 
0040107C  add         ecx,1 
0040107F  cmp         ecx,ebp 
00401081  jl          count+68h (401068h) 

Вот что программа выводит на мою машину:

---

LOG2(INNER) LOG2(OUTER)  Time, ms
4           25           523
5           24           569
6           23           441
7           22           400
8           21           367
9           20           358
10          19           349
11          18           364
12          17           378
13          16           384
14          15           357
15          14           377
16          13           379
17          12           390
18          11           386
19          10           419
20          9            995
21          8            1,015
22          7            1,038
23          6            1,071
24          5            1,082
25          4            1,119

---

Я прошу людей объяснить, что происходит. По мере роста внутреннего массива количество циклов уменьшается с течением времени. По мере того, как внутренний массив перерастает кэш, начинают происходить его пропадания и время увеличивается. Пока все в порядке.

НО : когда размер массива INNER равен 16 (что дает нам 64 байта данных), производительность снижается boost , несмотря на большее число jmps в коде , Это мало (523 против 569), но воспроизводимо.

Вопрос : почему это повышение?

Answer 1

Возможно, потому что 64 - это размер строки кэша на вашем компьютере, и вы в основном выполняете каждую итерацию полностью из одной строки кэша.

Answer 2

Я не уверен, что вы спрашиваете. Вы просто проверяете то, что мы знаем? Зачем беспокоиться? Или вы спрашиваете нас, потому что вы сами не можете объяснить увеличение на 64 байта? Или это выяснить, хороший ли это вопрос для интервью, или ...?

В любом случае, если целью является просто предоставить справочную информацию для вашего вопроса об интервью, вы должны удалить весь ненужный код. Важен ли HeapAlloc? Почему массив не может быть объявлен в стеке? Или с новым / malloc?

Зачем вам нужно обрабатывать ошибки в этой маленькой тестовой программе? Опять же, это просто отвлекает и добавляет больше шума. То же самое касается звонков QPC. И я даже не буду спрашивать, зачем вам нужен предварительно скомпилированный заголовок.

Чтобы спросить собеседника о 6-строчной петле, он должен просеять 16 строк ненужного шума. Почему?

И, как упоминалось в комментарии, выходная таблица в основном не читаема.

Я за то, чтобы посмотреть, может ли интервьюируемый читать код, но я не вижу смысла ставить вопрос о производительности и характеристиках кэша так сложно для чтения.

В любом случае, при 64-байтовом массиве INNER точно вписывается в большинство строк кэша ЦП. Это означает, что для каждой итерации OUTER должна быть прочитана ровно одна строка кэша.

Answer 3

Просто чтобы уточнить, некоторые пробелы в его таблице на самом деле должны быть, s. Вы все можете понять это.