RAM - не RAM, или Cache-Conscious Data Structures
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:
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: