Оптимизация с учетом кэша

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


Существует очень быстрая память, способная работать на одной или близкой частоте с процессором. К сожалению, много такой памяти использовать нельзя как по техническим, так и по экономическим соображениям. Кроме того, есть менее быстрая память, которая существенно дешевле, и, поэтому ее можно использовать в больших объемах. Наконец, есть жесткий диск, который совсем медленный, но который имеет совершенно гигантскую емкость, по сравнению с остальными видами памяти. Для наиболее эффективного использования всего этого многообразия, различные виды памяти соединяют каскадно, один за другим. При обращении процессора к определенной ячейке, сначала производится поиск в наиболее близкой к нему памяти (для большинства современных компьютеров это кэш первого уровня — L1). Если искомое значение там есть, начинается его обработка, если нет — происходит обращение к следующему уровню памяти и т. д. Найденное значение, по дороге к процессору, дублируется на всех уровнях, позволяя при повторном обращении, найти его сразу. Учитывая то, что для многих алгоритмов вероятность повторного обращения к одной и той же переменной в течении малого промежутка времени достаточно высока, такая иерархическая модель позволяет значительно улучшить производительность системы в целом.
Конечно, т. к. каждый более высокий уровень памяти меньше по объему, новые значения вынуждены вытеснять старые, что, естественно снижает эффективность кэширования.
Кэширование данных выполняется при помощи аппаратуры, поэтому является прозрачным для программиста. Но, несмотря на это, программист может использовать некоторые особенности кэша для повышения быстродействия собственных программ. При дальнейшем рассмотрении будем считать, что мы имеем дело с двухуровневой памятью, т. к. многоуровневые структуры всегда можно свести к такому варианту.
Одной из таких особенностей является то, что чтение участка памяти в последовательном порядке быстрее, чем в произвольном. Если в следующем фрагменте кода

for(int i = 0; i < N; ++i) {
   int j = rand() % N;
   s += a[i] + j;
}

a[i] заменить на a[j], на моей машине он будет выполняться где-то в 4 раза быстрее. Расчет суммы добавлен для того, чтобы не возникло мысли, что компилятор что-нибудь соптимизировал. Разница в быстродействии связана с тем, что данные из памяти в кэш читаются не по одной ячейке, а блоками. Так проще с точки зрения аппаратной реализации. Поэтому, когда мы читаем одну ячейку, очень вероятно, что следующая за ней (или несколько следующих, в зависимости от размера блока в кэше и размера читаемых данных) тоже окажется в кэше. Тогда последующее чтение приведет к обращению только в кэш, что значительно быстрее.
Этот факт приводит к некоторым неожиданным последствиям. Например, базовые знания об алгоритмах говорят нам, что временная сложность обхода матрицы M×N и по строкам, и по столбцам составляет O(M×N). Однако, если в коде

for (int i = 0; i < N; ++i) {
   for (int j = 0; j < M; ++j) {
        s += a[i][j];
   }
}

заменить a[i][j] на a[j][i], производительность упадет в 2 раза. Очевидно, что двумерная структура в памяти вытягивается в линейную строка за строкой.


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

class A {
public:
    int x, y, z, t;
};

Объявим достаточно большой массив экземпляров класса:

A a[N];

, а затем пройдем по его полю x:

int s = 0;
for (int i = 0; i < N; ++i) {
    s += a[i].x;
}

Т. к. члены класса хранятся последовательно, при чтении первого x в кэш попадет также y, возможно и z, но не второй x.


За счет разреженности x-ов, производительность такого обхода будет в 1,5 раза ниже (для моей машины), чем при хранении данных в виде отдельных массивов:

int x[N], y[N], z[N], t[N];

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