Что такое «дружественный к кешу» код?

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

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

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

И все, что нужно, чтобы испортить представление, это пойти от

// Cache-friendly version - processes pixels which are adjacent in memory
for(unsigned int y=0; y<height; ++y)
{
for(unsigned int x=0; x<width; ++x)
{
... image[y][x] ...
}
}

в

// Cache-unfriendly version - jumps around in memory for no good reason
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 все Valarrays), чтобы сделать поэлементное добавление этих массивов.

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

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

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

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

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

• Ложный обмен

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

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

2. В случае, если кто-нибудь задается вопросом, как valarray (разработанный специально для производительности) может быть очень ошибочным, сводится к одному: он действительно был разработан для машин, таких как старые Crays, которые использовали быструю оперативную память и не использовали кеш. Для них это действительно был почти идеальный дизайн.

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

Добро пожаловать в мир Data-Oriented Design. Основная мантра — Сортировка, Устранение Ветвей, Пакет, Устранение virtual звонки — все шаги к лучшей местности.

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

Просто накапливаем: классический пример недружественного к кешу и кеш-дружественного кода — это «блокировка кеша» умножения матрицы.

Наивная матрица умножения выглядит так

for(i=0;i<N;i++) {
for(j=0;j<N;j++) {
dest[i][j] = 0;
for( k==;k<N;i++) {
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==;k<N;i++) {
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) и т. Д.

Некоторые результаты поиска в Google «блокировки кеша»:

http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf

http://software.intel.com/en-us/articles/cache-blocking-techniques

Хорошая видео анимация оптимизированного алгоритма блокировки кэша.

http://www.youtube.com/watch?v=IFWgwGMMrh0

Циклическая черепица очень тесно связана:

http://en.wikipedia.org/wiki/Loop_tiling

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

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

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

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

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

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

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

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

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

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

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

Как отметил @Marc Claesen, одним из способов написания кода, удобного для кэша, является использование структуры, в которой хранятся наши данные. В дополнение к этому еще один способ написания кода, удобного для кэширования: изменить способ хранения наших данных; затем напишите новый код для доступа к данным, хранящимся в этой новой структуре.

Это имеет смысл в случае, когда системы баз данных линеаризуют кортежи таблицы и сохраняют их. Существует два основных способа хранения кортежей таблицы: хранилище строк и столбцов. В хранилище строк, как следует из названия, кортежи хранятся по строкам. Предположим, что таблица с именем Product хранится имеет 3 атрибута, т.е. int32_t key, char name[56] а также int32_t priceТаким образом, общий размер кортежа 64 байт.

Мы можем смоделировать очень простое выполнение запроса хранилища строк в основной памяти, создав массив Product структуры с размером N, где N — количество строк в таблице. Такая схема памяти также называется массивом структур. Таким образом, структура для Product может быть такой:

struct Product
{
int32_t key;
char name[56];
int32_t price'
}

/* create an array of structs */
Product* table = new Product[N];
/* now load this array of structs, from a file etc. */

Точно так же мы можем смоделировать очень простое выполнение запроса хранилища столбцов в основной памяти, создав 3 массива размера N, один массив для каждого атрибута Product Таблица. Такое расположение памяти также называется структурой массивов. Таким образом, 3 массива для каждого атрибута Product могут выглядеть так:

/* create separate arrays for each attribute */
int32_t* key = new int32_t[N];
char* name = new char[56*N];
int32_t* price = new int32_t[N];
/* now load these arrays, from a file etc. */

Теперь после загрузки как массива структур (Row Layout), так и 3 отдельных массивов (Column Layout), мы имеем хранилище строк и столбцов в нашей таблице Product присутствует в нашей памяти.

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

SELECT SUM(price)
FROM PRODUCT

Для хранилища строк мы можем преобразовать вышеуказанный SQL-запрос в

int sum = 0;
for (int i=0; i<N; i++)
sum = sum + table[i].price;

Для хранилища столбцов мы можем преобразовать вышеуказанный SQL-запрос в

int sum = 0;
for (int i=0; i<N; i++)
sum = sum + price[i];

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

Предположим, что размер строки кэша 64 байт.

В случае разметки строк при чтении строки кэша значение цены составляет только 1 (cacheline_size/product_struct_size = 64/64 = 1) кортеж читается, потому что размер нашей структуры составляет 64 байта, и он заполняет всю нашу строку кэша, поэтому для каждого кортежа происходит промах кэша в случае расположения строки.

В случае расположения столбца при чтении строки кэша значение цены равно 16 (cacheline_size/price_int_size = 64/4 = 16) кортежи считываются, потому что 16 смежных ценовых значений, хранящихся в памяти, заносятся в кеш, поэтому для каждого шестнадцатого кортежа пропадание кеша происходит в случае расположения столбцов.

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

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