В дополнение к ответу @Marc Claesen, я бы хотел отметить классический пример кода, который не дружит с кэшом: это код, который сканирует двумерный массив в C (например, битмап изображение) по столбцам, а не по строкам.

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

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

И всё, что нужно, чтобы ухудшить производительность, — это перейти от

// Версия, дружелюбная к кэшу — обрабатывает пиксели, которые находятся рядом в памяти
for(unsigned int y=0; y<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

к

// Версия, не дружелюбная к кэшу — прыжки по памяти без серьезной причины
for(unsigned int x=0; x<width; ++x)
{
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }
}

Этот эффект может быть довольно драматичным (разница в скорости в несколько порядков) в системах с маленьким кешем и/или при работе с большими массивами (например, изображения 10+ мегапикселей с глубиной цвета 24 бита на пиксель на современных машинах). По этой причине, если вам нужно выполнить много вертикальных сканирований, зачастую лучше сначала повернуть изображение на 90 градусов, а затем провести различные анализы, ограничив неэффективный с точки зрения кэша код только операцией поворота.

Оптимизация использования кэша в значительной степени сводится к двум факторам.

Локальность ссылок

Первый фактор (на который уже указывали другие) — это локальность ссылок. Локальность ссылок действительно имеет две аспекта: пространственный и временной.

• Пространственный

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

Во-вторых, мы хотим, чтобы информация, обрабатываемая одновременно, также находилась рядом друг с другом. Типичный кэш работает с "строками", что означает, что когда вы обращаетесь к какой-либо информации, в кэш загружается другая информация, находящаяся по близким адресам. Например, если я обращаюсь к одному байту, кэш может загрузить 128 или 256 байт рядом с ним. Чтобы воспользоваться этим, вы обычно хотите организовать данные так, чтобы максимально повысить вероятность использования других данных, которые были загружены одновременно.

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

• Временной

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

Так как вы отметили этот вопрос как касающийся C++, я укажу на классический пример относительно неблагоприятного для кэша дизайна: std::valarray. valarray перегружает большинство арифметических операторов, поэтому я могу (например) написать a = b + c + d; (где a, b, c и d — все это valarray) для выполнения поэлементного сложения этих массивов.

Проблема в том, что он проходит через одну пару входных данных, помещает результаты во временный массив, проходит через другую пару входных данных и так далее. При большом количестве данных результат одного вычисления может исчезнуть из кэша до его использования в следующем вычислении, и в итоге нам придется многократно читать (и писать) данные, прежде чем получим окончательный результат. Если каждый элемент конечного результата будет таким, как (a[n] + b[n]) * (c[n] + d[n]);, нам бы в целом больше понравилось прочитать каждый из a[n], b[n], c[n] и d[n] один раз, провести вычисление, записать результат, увеличить n и повторить это до завершения.²

Совместное использование строк

Второй важный фактор — это избежание совместного использования строк. Чтобы понять это, нам необходимо немного отступить и взглянуть на то, как организованы кэши. Самая простая форма кэша — это прямая адресация. Это значит, что один адрес в основной памяти может храниться только в одном определенном месте в кэше. Если мы используем два элемента данных, которые соответствуют одному и тому же месту в кэше, это будет работать плохо: каждый раз, когда мы используем один элемент данных, другой должен быть устранен из кэша, чтобы освободить место для другого. Остальная часть кэша может быть пустой, но эти элементы не будут использовать другие части кэша.

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

Проблема, вероятно, довольно очевидна: для кэша с прямой адресацией два операнда, которые случайно соответствуют одному и тому же месту в кэше, могут привести к плохому поведению. N-ходовой набор ассоциативного кэша увеличивает число с 2 до N+1. Организация кэша с большим количеством "путей" требует дополнительной схемы и, как правило, работает медленнее, поэтому (например) 8192-ходовой ассоциативный кэш редко является хорошим решением.

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

• Ложное совместное использование

Существует еще один связанный аспект, называемый "ложным совместным использованием". Он возникает в многопроцессорных или многопоточных системах, когда два (или более) процессора/ядра имеют данные, которые отделены, но попадают в одну и ту же строку кэша. Это заставляет два процессора/ядра координировать доступ к данным, даже если у каждого из них есть свой собственный независимый элемент данных. Особенно если два модифицируют данные по очереди, это может привести к значительному замедлению, поскольку данные должны постоянно передаваться между процессорами. Это также не может быть легко исправлено путём организации кэша с большим количеством "путей" или чем-то подобным. Основной способ предотвратить это — убедиться, что два потока редко (а лучше никогда) не изменяют данные, которые могут находиться в одной и той же строке кэша (с теми же оговорками о трудностях контроля адресов, по которым выделяются данные).

1. Тех, кто хорошо знает C++, может заинтересовать вопрос, можно ли оптимизировать это с помощью выраженческих шаблонов. Я почти уверен, что ответ — да, это можно сделать, и если бы это было сделано, вероятно, это было бы довольно значительным выигрышем. Однако мне не известно о том, чтобы кто-то это делал, и учитывая, как мало используется valarray, я бы был по крайней мере немного удивлён, если бы кто-то это сделал.
2. В случае если кто-то задается вопросом, как valarray (специально разработанный для производительности) может быть таким неудачным, всё сводится к одному: он действительно был разработан для машин, таких как старые Cray, которые использовали быструю основную память и не имели кэша. Для них это действительно был почти идеальный дизайн.
3. Да, я упрощаю: большинство кэшей на самом деле не измеряют наиболее недавно использованный элемент точно, но используют некоторую эвристику, которая предназначена для того, чтобы быть близкой к этому, не имея необходимости вести полный временной штамп для каждого доступа.

В ответ на ваш вопрос о сравнении кода, дружелюбного и недружелюбного к кэшу, классическим примером служит "блокировка кэша" при умножении матриц.

Наивное умножение матриц выглядит следующим образом:

for(i=0;i<N;i++) {
   for(j=0;j<N;j++) {
      dest[i][j] = 0;
      for( k=0;k<N;k++) {
         dest[i][j] += src1[i][k] * src2[k][j];
      }
   }
}

Если N велико, например, если N * sizeof(elemType) превышает размер кэша, то каждый доступ к элементам массива src2[k][j] приведет к промаху кэша.

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

int itemsPerCacheLine = CacheLineSize / sizeof(elemType);

for(i=0;i<N;i++) {
   for(j=0;j<N;j += itemsPerCacheLine ) {
      for(jj=0;jj<itemsPerCacheLine; jj++) {
         dest[i][j+jj] = 0;
      }
      for( k=0;k<N;k++) {
         for(jj=0;jj<itemsPerCacheLine; jj++) {
            dest[i][j+jj] += src1[i][k] * src2[k][j+jj];
         }
      }
   }
}

Если размер кэшной строки составляет 64 байта, и мы работаем с 32-битными (4-байтовыми) числами с плавающей запятой, то за одну кэшную строку мы получаем 16 элементов. И количество промахов кэша за счет этой простой трансформации сокращается примерно в 16 раз.

Более сложные трансформации работают с 2D-тайлами, оптимизируют для нескольких кэшей (L1, L2, TLB) и так далее.

Некоторые результаты поиска по запросу "cache blocking":

• Доклад о блокировке кэша
• Техники блокировки кэша от Intel
• Анимация алгоритма оптимизированной блокировки кэша на YouTube

Блокировка циклов очень closely связана с этим понятием:

• Блокировка циклов на Википедии

Современные процессоры работают с несколькими уровнями каскадной памяти. У центрального процессора (ЦП) есть собственная память на чипе, доступ к которой очень быстрый. Существуют разные уровни кэша, каждый из которых медленнее (но больше) предыдущего, пока не дойдём до системной памяти, которая находится вне ЦП и обладает относительно медленным доступом.

Логически, для набора команд ЦП вы обращаетесь к адресам памяти в гигантском виртуальном адресном пространстве. Когда вы обращаетесь к одному адресу памяти, ЦП извлекает данные. В прошлом он извлекал только запрашиваемый адрес, но сегодня процессор загружает сразу несколько адресов вокруг запрашиваемого, копируя их в кэш. Это делается на основании предположения, что если вы запросили определённый адрес, то, скорее всего, вы запросите ближайший адрес очень скоро. Например, если вы копируете буфер, вы будете считывать и записывать из последовательных адресов — один за другим.

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

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

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

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

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

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

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

Функция должна начинаться по адресу, удобному для выравнивания кэш-строк. Хотя существуют (gcc) переключатели компилятора для этого, имейте в виду, что если функции очень короткие, может быть нецелесообразно, чтобы каждая занимала целую кэш-строку. Например, если три из наиболее часто используемых функции помещаются в одну кэш-строку размером 64 байта, это менее расточительно, чем если у каждой была бы своя строка, что приводит к потере двух кэш-строк для других нужд. Типичное значение для выравнивания может быть 32 или 16.

Таким образом, стоит потратить немного времени, чтобы сделать код более плотным. Тестируйте разные конструкции, компилируйте и анализируйте полученный размер кода и его профилирование.