в дополнение к ответу @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 bpp изображения на текущих машинах); по этой причине, если вам нужно сделать много вертикальных сканирований, часто лучше сначала повернуть изображение на 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 и повторяйте, пока мы не закончим.²

Обмен Строк

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

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

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

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

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

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

---

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

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

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

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

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

просто нагромождение: классический пример cache-unfriendly против Cache-friendly кода - это "блокировка кэша" матрицы multiply.

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

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) и т. д.

некоторые результаты поиска в гугле " кэш блокировка":

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 массива для каждого атрибута продукта могут быть такими:

/* 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. */

теперь после загрузки как массив структур (макет строки) , так и 3 отдельных массива (макет столбца), у нас есть хранилище строк и хранилище столбцов на нашем таблица 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 непрерывных значений цен, хранящихся в памяти, вносятся в кэш, поэтому для каждого шестнадцатого кортежа кэш пропускает ocurs в случае расположения столбцов.

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

имейте в виду, что кэши не просто кэшируют непрерывную память. Они имеют несколько строк (по крайней мере 4), поэтому прерывистая и перекрывающаяся память часто может храниться так же эффективно.

то, что отсутствует во всех приведенных выше примерах, измеряется контрольными показателями. Существует много мифов о производительности. Если вы его не знаете. Не усложнять код, если у вас нет измеряемые улучшение.