Оптимизация работы с памятью
Как известно, внутри процессора имеется специальная быстродействующая область памяти − кэш. В кэше хранятся копии часто используемых данных из оперативной памяти. Если при обращении к ячейке памяти она обнаруживается в кэше, то операция будет выполнена многократно быстрее, чем при использовании более медленной основной памятью.
Важно понимать, что одним из принципов организации кэша является пространственная локальность: если произошло обращение к ячейке оперативной памяти, то с большой вероятностью будет произведено обращение к соседним ячейкам. Реализуется это обычно так. Вся память условно разбита на строки некоторого размера (например, по 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 раз!