RAM — не RAM

Как это ни прискорбно признавать, но то, что мы называем RAM (random-access memory) уже давно не является RAM. По сути это уже память с последовательным доступом. Как магнитная лента. Здесь я имею в виду RAM не в смысле физическое устройство, а в смысле подсистема памяти компьютера, которая состоит из собственно основной памяти и нескольких уровней кэша.

Приблизительные цифры скорости доступа к различным уровням памяти на современных архитектурах:
Кэш L1 — 1-3 такта
Кэш L2 — 10-20 тактов
Основная память — 200-250 тактов

Что это означает для нас, программистов? То, что RAM — не RAM и абстракция "прозрачного" кэша начинает серьёзно "просвечивать". В пределе, при максимально плохом стечении обстоятельств при доступе к памяти, процессор с частотой 2.5 GHz фактически будет работать на частоте 10 MHz. Как Вам? В реальности, конечно, такого не будет даже в самых плохих условиях. Но разницу производительности в ~10 раз получить можно легко.

Умножение матриц

Возьмём вот такую простенькую функцию перемножения матриц:

void multiply(T* X, T* Y, T* Z, int size)
{
    for (int i = 0; i != size; ++i)
        for (int j = 0; j != size; ++j)
            for (int k = 0; k != size; ++k)
                Z[i*size+j] += X[i*size+k] * Y[k*size+j];
}

Запускаю для матриц размера 512 — результат 16.9 секунды.
Запускаю для матриц размера 513... делайте ставки, господа! Результат 4.8 секунды!

Причина кроется в паттерне прохода по матрице Y во внутреннем цикле. При размере матрицы 512 размер строки матрицы составляет 4096 байт (8-байтовые элементы). Соответственно адреса элементов Y[0][0] и Y[1][0] имеют одинаковые младшие 12 бит. Это вызывает постоянные конфликты в кэше с вытеснением старых данных.

Теперь для размера матрицы 513 попробуем попереставлять циклы местами. Результаты следующие:
k, j, i — 6.8 сек (для размера 512 время 34.1 сек)
j, k, i — 6.8 сек
i, j, k — 4.8 сек
j, i, k — 3.6 сек
k, i, j — 2.5 сек
i, k, j — 2.4 сек
Занятно. Итого: индексы (k, j, i), размер 512, время — 34.1; индексы (i, k, j), размер 513, время — 2.4. Ускорение — 14.2 раза. А вроде как ничего и не делали.
(матрицы перемножать с помощью этого кода скорее всего не стоит — лучше воспользоваться оптимизированными библиотеками, тут я хотел показать только эффекты от различных паттернов обращения к памяти)

Вкратце рецепт такой — по массивам надо проходить последовательно; учитывать количесто ассоциативных входов в кэш (обычно это 2 или 4); учитывать значащие биты в адресе, которые определяют индекс в кэше. Более подробно здесь:
http://en.wikipedia.org/wiki/CPU_cache

Cache-Conscious Binary Search

Это была разминка, теперь более интересные и нетривиальные вещи.
Как организовать быстрый бинарный поиск при большом объёме данных? Ответ теоретика — с помощью бинарного дерева. Ну ладно, простим ему это. Конечно, с помощью упорядоченного массива. На маленьком объеме данных это будет работать хорошо, но вот на большом — не очень. Что бы понять почему, надо рассмотреть как происходит перемещение "точки поиска" по массиву в вслучае бинарного поиска. Вначале точка устанавливается на середину (1/2), потом "скачет" либо на 1/4, либо на 3/4, потом — на 1/8, 3/8, 5/8, 7/8 и т.д. Т.е. вначале "скачки" очень большие и хаотические. При этом из каждой
загруженной кэш-линии используется в основном только один элемент, ближайшие к нему элементы не используются.
Попробуем исправить это, попробуем сделать т.ч. "скачки" были по-возможности маленькие, и при этом из каждой загруженной кэш-линии использовалось как можно больше элементов.
Упорядочиваем массив следующим образом. В первую кэш-линию (допустим в кэш-линию помещается 8 элементов) кладём серединный элемент 1/2, следом за ним кладём элементы, на которые мы можем перескачить с 1/2, т.е. 1/4 и 3/4. Далее кладём элементы, на которые мы можем перескачить с 1/4 и 3/4, т.е. 1/8, 3/8, 5/8, 7/8. Таким образом, используя элементы только из первой кэш-линии, мы можем сделать 3 "скачка", при этом из неё будет использовано 3 элемента, а не 1 как ранее.
Далее элементы пакуются аналогичным образом, т.е. в кэш линии лежит некий начальный элемент; элементы, на которые можно "перескачить" с него; и элементы, на которые можно перескачить с них и т.д.
На синтетических бенчмарках такой метод дают ускорение в 4-5 раз, в реальных приложениях есть сведения об ускорении на 25-40%.

Hot/Cold Data Splitting

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

struct X
{
  int key;
  unsigned char some_data [28];
};

При этом при поиске используется только поле key. Размер структуры 32 байта, т.е. массив будет большой и толстый, и при поиске в нем неминуемо в кэш будет загружаться и some_data, которая вобщем-то нам совершенно не нужна, пока мы не нашли один искомый элемент.
Что мы делаем — мы разбиваем нашу структуру на 2:

struct X_hot
{
  int key;
};
struct X_cold
{
  unsigned char some_data [28];
};

Кладём в массив, в котором мы производим поиск только X_hot, а X_cold выносим в отдельный параллельный массив, в котором элементы упорядочены так же, т.е. по номеру элемента X_hot без труда можно получить и элемент X_cold.
Теперь поисковый массив у нас маленький и тонкий, в данном случае меньше в 8 раз (возможно в таком виде он целиком уместится в кэш L2), поиск в нём идёт быстрее. А когда нашли индекс искомого элемента, то загружаем и один нужный X_cold со всеми остальными данными.

Управление кэшем

Кэш не полностью управляется процессором — можно попробовать поуправлять им вручную. Хотя обычно этого делать не стоит. Я вкраце опишу какие средства есть на современных процессорах Intel/AMD x86. В любом случае любое применение таких средств надо тщательно профилировать, т.к. априори предугадать все эффекты сложно.

prefetcht0 (t1, t2, nta)
В MSVC инструкцию prefetcht0 реализует следующий интринсик:

void _mm_prefetch(char * p , int hint ); // hint = _MM_HINT_T0, _MM_HINT_T1, _MM_HINT_T2, _MM_HINT_NTA

Команде передаётся адрес, данные по которому будут загружены в кэш (загружается, естественно вся кэш-линия — сейчас обычно 64 байта). Так же команде передаётся хинт относительно предполагаемого использования этих данных. _MM_HINT_T0, _MM_HINT_T1, _MM_HINT_T2 скорее всего не различаются и загружают данные в кэш L2. _MM_HINT_NTA более интересен, он говорит, что данные нужны на короткое время. При этом данные загружаются в кэш L1, и помечаются специальным тэгом, который говорит, что при вытеснении из L1 данные не надо перемещать в L2 — из просто надо "выкинуть". Т.о. не происходит т.н. "загрязнения" кэша. Очень полезно при потоковой обработке больших массивов.

movnti/movntq
В MSVC инструкцию movnti реализует следующий интринсик:

void _mm_stream_si32(int *p, int a)

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

clflush

void _mm_clflush(void const*p)

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

Почему не надо вручную управлять кэшем. Потому что процессор имеет аппаратный предвыборщик данных, который в большинстве случаев делает свою работу достаточно хорошо. Сделать лучше, чем он, можно. Но легче сделать хуже. Когда можно заниматься ручным управлением кэшем — при потоковой обработке больших массивов данных (в т.ч. и при просто копировании памяти). В общем случае данные подгружаются на 4-8 строк кэша вперёд с помощью инструкции prefetchnta, и сохраняются с помощью movnti/movntq. В таком случае можно получить ускорение в 10 раз и более.

Более подробно здесь:
Intel® 64 and IA-32 Architectures Software Developer’s Manual: Instruction Set Reference
http://www.intel.com/design/processor/manuals/253666.pdf
http://www.intel.com/design/processor/manuals/253667.pdf


Факультативное чтение по поводу Cache-Conscious Data Structures. В т.ч. описаны и другие приёмы — Structure Field Reorder, Cache Colouring, Cache-Conscious Heap Allocation.

Cache-Conscious Data Placement:
http://citeseer.ist.psu.edu/cache/papers/cs/130/http:zSzzSzwww.cse.ucsd.eduzSz~calderzSzpaperszSzASPLOS-98-CCDP.pdf/calder98cacheconscious.pdf

Cache-Conscious Structure Definition:
http://research.microsoft.com/~trishulc/papers/definition_distr.ps
(занятно — люди из Microsoft Research занимаются Java)

Cache-Conscious Structure Layout:
http://research.microsoft.com/~trishulc/papers/layout_distr.ps

Cache-conscious Frequent Pattern Mining on a Modern Processor:
http://www.vldb2005.org/program/paper/thu/p577-ghoting.pdf

Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems:
http://www.vldb.org/conf/2001/P181.pdf

Cache-Conscious Allocation of Pointer-Based Data Structures Revisited with HW/SWPrefetching:
http://www.ece.wisc.edu/~wddd/2003/01_hallberg.pdf

Здравствуйте, remark, Вы писали:

Слушай, ты бы не ленился, а писал статьи, а? А то нам в журнале печатать нечего, а ты тут фонтанируешь

R>Упорядочиваем массив следующим образом. В первую кэш-линию (допустим в кэш-линию помещается 8 элементов) кладём серединный элемент 1/2, следом за ним кладём элементы, на которые мы можем перескачить с 1/2, т.е. 1/4 и 3/4. Далее кладём элементы, на которые мы можем перескачить с 1/4 и 3/4, т.е. 1/8, 3/8, 5/8, 7/8. Таким образом, используя элементы только из первой кэш-линии, мы можем сделать 3 "скачка", при этом из неё будет использовано 3 элемента, а не 1 как ранее.

И получаем бинарное дерево, о котором говорил теоретик Правда, без указателей, но тем не менее.

Здравствуйте, SergH, Вы писали:

SH>Здравствуйте, remark, Вы писали:

SH>Слушай, ты бы не ленился, а писал статьи, а? А то нам в журнале печатать нечего, а ты тут фонтанируешь


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


R>>Упорядочиваем массив следующим образом. В первую кэш-линию (допустим в кэш-линию помещается 8 элементов) кладём серединный элемент 1/2, следом за ним кладём элементы, на которые мы можем перескачить с 1/2, т.е. 1/4 и 3/4. Далее кладём элементы, на которые мы можем перескачить с 1/4 и 3/4, т.е. 1/8, 3/8, 5/8, 7/8. Таким образом, используя элементы только из первой кэш-линии, мы можем сделать 3 "скачка", при этом из неё будет использовано 3 элемента, а не 1 как ранее.

SH>И получаем бинарное дерево, о котором говорил теоретик Правда, без указателей, но тем не менее.


Упорядоченный массив сам по себе с определенной высоты — бинарное дерево...

SH>Слушай, ты бы не ленился, а писал статьи, а?

Во-во, у меня такая же мысль возникла — прогнать текст через спелчекер и в журнал какой-нибудь!

Здравствуйте, remark, Вы писали:

R>Я подозреваю, что на написание статей будет уходить значительно больше времени.

Да, скорее всего, именно поэтому я написал "не ленился" От статьи обычно требуется некоторая законченность, на которую уходит куча времени.

R>В любом случае, права на публикацию я готов предоставить. Если у кого есть время всё это оформить, то пожалуйста.

Добрый такой Сделал всю интересную часть работы, а теперь "кто хочет, можете поисправлять баги в моём проекте"

Здравствуйте, SergH, Вы писали:

R>>Упорядочиваем массив следующим образом. В первую кэш-линию (допустим в кэш-линию помещается 8 элементов) кладём серединный элемент 1/2, следом за ним кладём элементы, на которые мы можем перескачить с 1/2, т.е. 1/4 и 3/4. Далее кладём элементы, на которые мы можем перескачить с 1/4 и 3/4, т.е. 1/8, 3/8, 5/8, 7/8. Таким образом, используя элементы только из первой кэш-линии, мы можем сделать 3 "скачка", при этом из неё будет использовано 3 элемента, а не 1 как ранее.

SH>И получаем бинарное дерево, о котором говорил теоретик Правда, без указателей, но тем не менее.

Получаем, действительно, бинарное дерево. А если еще точнее — heap в его классическом представлении.

Здравствуйте, Alex Alexandrov, Вы писали:

AA>Здравствуйте, SergH, Вы писали:

R>>>Упорядочиваем массив следующим образом. В первую кэш-линию (допустим в кэш-линию помещается 8 элементов) кладём серединный элемент 1/2, следом за ним кладём элементы, на которые мы можем перескачить с 1/2, т.е. 1/4 и 3/4. Далее кладём элементы, на которые мы можем перескачить с 1/4 и 3/4, т.е. 1/8, 3/8, 5/8, 7/8. Таким образом, используя элементы только из первой кэш-линии, мы можем сделать 3 "скачка", при этом из неё будет использовано 3 элемента, а не 1 как ранее.

SH>>И получаем бинарное дерево, о котором говорил теоретик Правда, без указателей, но тем не менее.

AA>Получаем, действительно, бинарное дерево. А если еще точнее — heap в его классическом представлении.

heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B)

http://en.wikipedia.org/wiki/Heap_%28data_structure%29

Тут ключи и убывают и возрастают, т.е. если первый элемент 64, то второй — 32, третьий — 96

Здравствуйте, remark, Вы писали:

R>Здравствуйте, Alex Alexandrov, Вы писали:

AA>>Здравствуйте, SergH, Вы писали:

R>>>>Упорядочиваем массив следующим образом. В первую кэш-линию (допустим в кэш-линию помещается 8 элементов) кладём серединный элемент 1/2, следом за ним кладём элементы, на которые мы можем перескачить с 1/2, т.е. 1/4 и 3/4. Далее кладём элементы, на которые мы можем перескачить с 1/4 и 3/4, т.е. 1/8, 3/8, 5/8, 7/8. Таким образом, используя элементы только из первой кэш-линии, мы можем сделать 3 "скачка", при этом из неё будет использовано 3 элемента, а не 1 как ранее.

SH>>>И получаем бинарное дерево, о котором говорил теоретик Правда, без указателей, но тем не менее.

AA>>Получаем, действительно, бинарное дерево. А если еще точнее — heap в его классическом представлении.

R>

R>heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B)

R>http://en.wikipedia.org/wiki/Heap_%28data_structure%29

R>Тут ключи и убывают и возрастают, т.е. если первый элемент 64, то второй — 32, третьий — 96
R>

Если совсем точно, то я имел в виду binary heap. В Википедии она упомянута здесь — http://en.wikipedia.org/wiki/Binary_heap. Картинка приведенная там в подразделе "Implementation" совпадает с описанием порядка, которые ты дал выше. Массив хранится в порядке обхода бинарного дерева в ширину.

R>Тут ключи и убывают и возрастают, т.е. если первый элемент 64, то второй — 32, третьий — 96

Ты здесь про свое описание говоришь, или про описание кучи? Еще раз, я упустил уточнение, что я имел в виду Binary Heap. Для бинарной кучи реализованной в виде массива действует правило

If the tree root item has index 0 (n tree elements are a[0] .. a[n−1]), then for each index i, element a[i] has children a[2i+1] and a[2i+2], and the parent a[floor((i−1)/2)]

Т.е. как раз и получается 1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8 вроде, нет?

Здравствуйте, remark, Вы писали:

R>RAM — не RAM

Есть такой проект Copenhagen STL, по оптимизации представления структур данных , в т.ч. и в плане Cache-Conscious'ness. http://www.cphstl.dk/
На сайте имеются интересные публикации и отчеты по теме:
http://www.cphstl.dk/WWW/papers.html
http://www.cphstl.dk/WWW/reports.html

Здравствуйте, remark, Вы писали:

R>Факультативное чтение по поводу Cache-Conscious Data Structures. В т.ч. описаны и другие приёмы — Structure Field Reorder, Cache Colouring, Cache-Conscious Heap Allocation.

Кеш памяти предугадывает действия софта, софт предугадывает поведение кеша... я один кто думает, что что-то тут не так?

Здравствуйте, Кодёнок, Вы писали:
Кё>Кеш памяти предугадывает действия софта, софт предугадывает поведение кеша... я один кто думает, что что-то тут не так?
Всё в порядке до тех пор, пока оба предугадывания направлены на достижение одной и той же цели. Характерный пример такой "кооперации без диалога" приведен в фильме "Место встречи изменить нельзя".

Кодёнок,

R>>Факультативное чтение по поводу Cache-Conscious Data Structures. В т.ч. описаны и другие приёмы — Structure Field Reorder, Cache Colouring, Cache-Conscious Heap Allocation.

Кё>Кеш памяти предугадывает действия софта, софт предугадывает поведение кеша... я один кто думает, что что-то тут не так?

Ещё одно подтверждение того, что уничтожение (или обход) слоя абстракции можно использовать для оптимизации.

Здравствуйте, Alex Alexandrov, Вы писали:


AA>Если совсем точно, то я имел в виду binary heap. В Википедии она упомянута здесь — http://en.wikipedia.org/wiki/Binary_heap. Картинка приведенная там в подразделе "Implementation" совпадает с описанием порядка, которые ты дал выше. Массив хранится в порядке обхода бинарного дерева в ширину.

R>>Тут ключи и убывают и возрастают, т.е. если первый элемент 64, то второй — 32, третьий — 96

AA>Ты здесь про свое описание говоришь, или про описание кучи? Еще раз, я упустил уточнение, что я имел в виду Binary Heap. Для бинарной кучи реализованной в виде массива действует правило

AA>

AA>If the tree root item has index 0 (n tree elements are a[0] .. a[n−1]), then for each index i, element a[i] has children a[2i+1] and a[2i+2], and the parent a[floor((i−1)/2)]

AA>Т.е. как раз и получается 1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8 вроде, нет?


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

Здравствуйте, remark, Вы писали:

А почему не использовать B-tree, столь хорошо зарекомендовавшие себя в СУБД?
Есть же целый класс структур и алгоритмов, которые оптимизированы с учетом заметной стоимости подкачки "страницы" в "кэш".

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, remark, Вы писали:

S>А почему не использовать B-tree, столь хорошо зарекомендовавшие себя в СУБД?
S>Есть же целый класс структур и алгоритмов, которые оптимизированы с учетом заметной стоимости подкачки "страницы" в "кэш".


Можно использовать B-tree. Реализация может быть разная. Но суть остаётся. Нельзя просто взять B-tree и получить требуемое поведение. Надо выбрать кол-во элементов в узле, исходя из того, сколько помещается в кэш-линию. Надо выравнивать узлы по кэш-линиям. Размер кэш-линии различается от платформы к платформе. Т.е. всё равно надо учитывать низкоуровневые детали кэша, это может быть достаточно непривычно для многих программистов.

Здравствуйте, remark, Вы писали:

R>Можно использовать B-tree. Реализация может быть разная. Но суть остаётся. Нельзя просто взять B-tree и получить требуемое поведение. Надо выбрать кол-во элементов в узле, исходя из того, сколько помещается в кэш-линию. Надо выравнивать узлы по кэш-линиям. Размер кэш-линии различается от платформы к платформе. Т.е. всё равно надо учитывать низкоуровневые детали кэша, это может быть достаточно непривычно для многих программистов.
А как можно програмно узнать размер кеш линии?
А то у меня есть пара алгоритмов которым от этого знания может полегчать.

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, remark, Вы писали:

R>>Можно использовать B-tree. Реализация может быть разная. Но суть остаётся. Нельзя просто взять B-tree и получить требуемое поведение. Надо выбрать кол-во элементов в узле, исходя из того, сколько помещается в кэш-линию. Надо выравнивать узлы по кэш-линиям. Размер кэш-линии различается от платформы к платформе. Т.е. всё равно надо учитывать низкоуровневые детали кэша, это может быть достаточно непривычно для многих программистов.

WH>А как можно програмно узнать размер кеш линии?
WH>А то у меня есть пара алгоритмов которым от этого знания может полегчать.


Это платформенно-зависимо. Обычно процессор предоставляет такую информацию.
Например на x86 смотри инструкцию cpuid, с аргументом eax=4 можно получить всю информацию по кэшу. Так же там есть упрощенный вариант при eax=1 — в ebx биты 15-8. В MSVC смотри интринсик __cpuid(), в Intel C++ тоже есть что-то аналогичное.

На Windows (начиная с Server2003) есть функция GetLogicalProcessorInformation(), с помощью которой можно получить размер кэшей.

Здравствуйте, remark, Вы писали:

R>Здравствуйте, WolfHound, Вы писали:

WH>>Здравствуйте, remark, Вы писали:

R>>>Можно использовать B-tree. Реализация может быть разная. Но суть остаётся. Нельзя просто взять B-tree и получить требуемое поведение. Надо выбрать кол-во элементов в узле, исходя из того, сколько помещается в кэш-линию. Надо выравнивать узлы по кэш-линиям. Размер кэш-линии различается от платформы к платформе. Т.е. всё равно надо учитывать низкоуровневые детали кэша, это может быть достаточно непривычно для многих программистов.

WH>>А как можно програмно узнать размер кеш линии?
WH>>А то у меня есть пара алгоритмов которым от этого знания может полегчать.


R>Это платформенно-зависимо. Обычно процессор предоставляет такую информацию.
R>Например на x86 смотри инструкцию cpuid, с аргументом eax=4 можно получить всю информацию по кэшу. Так же там есть упрощенный вариант при eax=1 — в ebx биты 15-8. В MSVC смотри интринсик __cpuid(), в Intel C++ тоже есть что-то аналогичное.

R>На Windows (начиная с Server2003) есть функция GetLogicalProcessorInformation(), с помощью которой можно получить размер кэшей.


Да, обычно сейчас на большинстве x86 это 64 байта.


R>

Здравствуйте, remark, Вы писали:

R>Это платформенно-зависимо. Обычно процессор предоставляет такую информацию.
Печально все это. Возьня того не стоит.
Вот еслиб ктонибудь сделал кросплатформенную библиотечку с простым сишным интерфейсом.
Думаю народ был бы благодарен.

Здравствуйте, remark, Вы писали:

R>Возьмём вот такую простенькую функцию перемножения матриц:
R>[. . .]

Большие матрицы, например, текстуры в видеопамяти, хранятся кусочками типа 16x16. Называется глупым словом Texture Swizzling. За счет этого, в среднем в 255 из 256 случаев получаем быстрый доступ, в 1 из 256 — медленный.

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