Оптимизация работы с памятью

Как известно, внутри процессора имеется специальная быстродействующая область памяти − кэш. В кэше хранятся копии часто используемых данных из оперативной памяти. Если при обращении к ячейке памяти она обнаруживается в кэше, то операция будет выполнена многократно быстрее, чем при использовании более медленной основной памятью.

Важно понимать, что одним из принципов организации кэша является пространственная локальность: если произошло обращение к ячейке оперативной памяти, то с большой вероятностью будет произведено обращение к соседним ячейкам. Реализуется это обычно так. Вся память условно разбита на строки некоторого размера (например, по 64 байта). Когда происходит обращение к какой-то ячейке памяти, в кэш загружается вся строка (причём данная операция реализована аппаратным образом так, чтобы выполняться максимально быстро). Если следующее обращение программы происходит к соседней ячейке памяти, то чаще всего она будет принадлежать этой же строке, и потому с большой вероятностью будет уже присутствовать в кэше.

Из вышенаписанного можно сделать вывод: программа, которая обрабатывает данные в памяти последовательно, работает заметно эффективнее, чем программа, которая "прыгает" по памяти, даже если они выполняют одинаковое число операций. Рассмотрим простой пример. Имеется достаточно большой двухмерный массив размера n x m (например, n = m =1000). Требуется вычислить сумму элементов массива. Который из двух вариантов кода работает лучше?

 

// Пример 9.2.8 - особенности работы кэша

 

// сумма элементов матрицы - вариант 1

int sum = 0;

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

sum += a[i][j];

 

// сумма элементов матрицы - вариант 2

int sum = 0;

for (int j = 0; j < m; j++)

for (int i = 0; i < n; i++)

sum += a[i][j];

 

Первый вариант кода на машине автора работает в 4.5 раза быстрее. Причина в том, что в памяти элементы матрицы хранятся по строкам − a[0][0], в следующей ячейке − a[0][1], и так далее. Первый вариант кода обходит матрицу по строкам, при этом достигается большое число попаданий в кэш. Во второй варианте матрица обходится по столбцам, при этом попаданий в кэш оказывается значительно меньше.

Интересно, что первый вариант кода будет быстрее работать и в случае, когда матрица настолько велика, что не влезает целиком в оперативную память. В этом случае роль кэша будет выполнять оперативная память, а роль медленной памяти − жёсткий диск, на котором находится файл подкачки.

Эффективное использование кэша может являться причиной, почему некоторые алгоритмы работают быстрее других несмотря на то, что они выполняют примерно одинаковое число операций − например, быстрая сортировка Хоара (quicksort) работает заметно быстрее алгоритма сортировки пирамидой (heapsort).

 

Предсказание переходов

Современный процессор за счёт конвейера инструкций способен выполнять сразу несколько инструкций параллельно, а потом объединять их результаты. Однако, что делать процессору, если встретилась инструкция условного перехода? Ведь пока результат условного перехода неизвестен, непонятно, какую инструкцию нужно выполнять следующей.

Специально для такого случая в процессоре предусмотрен модуль предсказания переходов. Данный модуль позволяет сократить простой конвейера внутри процессора за счёт предварительной загрузки и исполнения инструкций, которые должны выполниться после перехода. Если впоследствии обнаруживается, что предсказание было выполнено неверно, то результаты неверного ветвления отменяются и в конвейер загружается правильное, что приводит к задержке.

Для динамического предсказания ветвлений используется история ветвлений − информация о том, как часто этот переход выполнялся несколько предыдущих раз. Программный код, при выполнении которого предсказатель переходов хорошо угадывает результат перехода, будет выполняться заметно более эффективно, чем код, в котором результат перехода сложно предугадать.

Для примера рассмотрим две реализации сортировки массива методом пузырька (пример взят из статьи https://habrahabr.ru/post/73726).

 

// Пример 9.2.9 - две сортировки методом пузырька

// Вариант 1

for (int i = 0; i < N; i++)

for (int j = 0; j < N-i-1; j++)

if (a[j] > a[j+1])

std::swap(a[j], a[j+1]);

}

 

// Вариант 2

void bubble2()

{

for (int i = 0; i < N-1; i++)

for (int j = i; j >= 0; j--)

if (a[j] > a[j+1])

std::swap(a[j], a[j+1]);

}

 

Второй код почти не отличается от первого, но работает примерно в три раза быстрее. Чтобы разобраться, почему так, посмотрим на условие a[j]>a[j+1]. В первом случае при небольших i внутренний цикл по j пробегает почти до конца массива, при этом условие a[j]>a[j+1] выполняется почти случайно. При увеличении i элементы немного упорядочиваются, но всё равно остаётся большая доля случайности.

Во втором случае внутренний цикл бежит по уже отсортированной части массива, в который вставляется новый элемент a[i+1] (фактически, это сортировка вставками). При этом, пока элемент не встал на свою позицию, условие a[j]>a[j+1] будет оказываться всё время истинным, а затем до конца цикла всё время ложным. После нескольких итераций цикла модуль предсказания переходов начинает правильно угадывать результат ветвления, что и приводит к трёхкратной разнице в скорости.

 

Ускорение ввода-вывода

Если в программе выполняется ввод/вывод значительных объёмов данных в файлы, то операции ввода/вывода легко могут стать узким местом. В связи с этим необходимо хорошо знать классы и функции для ввода/вывода в стандартной библиотеке C++, в том числе представлять себе их сравнительную эффективность.

Заметим, что время выполнения операций ввода складывается из двух составляющих. Во-первых, это собственно чтение данных из файла в буфер в оперативной памяти. Во-вторых, это преобразование прочитанных данных в значения нужного типа (многие стандартные функции выполняют сразу обе операции). При оптимизации стоит учитывать оба аспекта.

Рассмотрим следующую задачу. Дан текстовый файл input.txt. В первой его строке содержится натуральное число N, за ним идут N неотрицательных целых чисел. Требуется прочитать всё содержимое файла в вектор. Для эксперимента нами был создан сравнительно большой файл размером 64 мегабайта, содержащий 10 миллионов чисел.

Ниже приводится несколько вариантов решения данной задачи. В первом варианте для работы с классом используется стандартный класс std::ifstream из заголовочного файла fstream.

Во втором варианте работа с файлом проводится в стиле языка C − используются функции из заголовочного файла stdio.h. Для чтения очередного числа из файла используется функция fscanf.

В третьем варианте решения используется функция fread, которая позволяет за один раз прочитать всё содержимое файла в память. Затем полученная строка разбивается на лексемы с помощью функции strtok, а каждая лексема переводится в число стандартной функцией atoi.

Четвёртый вариант является модификацией третьего − вместо функция atoi написана собственная функция str_to_int для перевода строки в число.

Поскольку все функции писались лишь для проведения эксперимента, в них отсутствуют проверки существования файла и правильности его содержимого.

 

// Пример 9.2.10 - разные реализации файлового ввода

 

// Вариант 1 - используем std::ifstream

std::vector<int> read1()

{

std::ifstream fin("input.txt");

int n; fin >> n;

std::vector<int> a(n);

for (int i = 0; i < n; i++)

fin >> a[i];

return a;

}

 

// Вариант 2 - используем fscanf

std::vector<int> read2()

{

FILE *f = fopen("input.txt", "r");

int n; fscanf(f, "%d", &n);

std::vector<int> a(n);

for (int i = 0; i < n; i++)

fscanf(f, "%d", &a[i]);

fclose(f);

return a;

}

 

// Вариант 3 - используем fread + strtok + atoi

std::vector<int> read3()

{

FILE *f = fopen("input.txt", "rb");

// получим размер файла

fseek(f, 0, SEEK_END);

int size = ftell(f);

fseek(f, 0, SEEK_SET);

// прочитаем данные

char *s = new char[size + 1];

fread(s, 1, size, f);

char *p = strtok(s, " \r\n");

int n = atoi(p);

std::vector<int> a(n);

for (int i = 0; i < n; i++)

{

p = strtok(NULL, " \r\n");

a[i] = atoi(p);

}

fclose(f);

return a;

}

 

// Вариант 4 - своя функция для замены atoi в функции read3

inline int str_to_int(char s[])

{

int res = 0;

for (char *p = s; *p!= 0; p++)

res = res * 10 + *p - '0';

return res;

}

 

В следующей таблице приведено время работы программы.

Способ ввода	Результат, g++ 4.9.2 (mingw)	Результат, Visual C++ 2013
std::ifstream	6.5 сек.	6.7 сек.
fscanf	2.5 сек.	2.2 сек.
fread + strtok + atoi	1.1 сек.	1.2 сек.
fread + strtok + своя функция перевода строки в число	0.08 сек.	0.08 сек.

Результаты получились довольно интересными. Во-первых, видно, что объектно-ориентированный ввод в стиле C++ заметно проигрывает по скорости вводу в "старом" стиле языка C. Можно также отметить, что в некоторых компиляторах, как это ни странно, скорость ввода при использовании директивы #include <stdio.h> может оказаться выше, чем при использовании #include <cstdio>.

Во-вторых, заметное ускорение можно получить, считывая файл в память сразу крупными кусками с помощью функции fread (в нашем случае мы читаем вообще весь файл целиком).

И самый интересный результат: оказалось, что очень сильно влияет на производительность способ преобразования прочитанных данных в тип int. Замена библиотечной функции atoi на собственную функцию str_to_int повысила скорость работы более чем на порядок. Вероятно, это связано с тем, что в нашей функции str_to_int не делается никаких проверок − предполагается, что входная строка содержит корректную запись числа.

Заметим, что разница между самым быстрым и самым медленным способом ввода составила более 80 раз!