Пакетная оптимизация

Пакетная оптимизация

5 июня 2016 г.
Ключевые слова: оптимизация кода, пакетная обработка, предварительная выборка, NUMA.

Вам когда-нибудь приходилось обрабатывать множество значений, случайно выбранных в массиве? Если да, то этот пост может быть для вас. Давайте посмотрим на эксперимент, который я недавно провел, чтобы ускорить такую ​​операцию в системе БД. Но сначала оговорка.

Ваш пробег может отличаться

Я провел эксперимент, описанный в этом посте, на нескольких разных платформах, и ваш результат определенно различается, в частности, в зависимости от деталей иерархии кэша. Экспериментальная установка, используемая здесь, представлена ​​в нижней части этого блога (в основном довольно старая коробка Intel Xeon-5 NUMA под управлением Linux). Кроме того, этот эксперимент идеализирован. Реальная система будет более сложной и может иметь несколько потоков или процессов, конкурирующих за ресурсы (включая кеш). Здесь все упрощено, поэтому остерегайтесь обобщений.

Проблема

Теперь, когда вас предупредили, давайте опишем проблему. Вот базовая обработка, которую мы хотим ускорить (весь код, результаты, детали используемого оборудования и графики, представленные здесь, находятся в свободном доступе по адресу: https://github.com/ferd36/batching-optimization):

for (size_t i = 0; i < N; ++i) {
  size_t pos = fast_hash_64(i, N) % M;
  certificate += F(data[pos]);
}

Позволь мне объяснить. В одном потоке мы просто перебираем N раз значения, хранящиеся в (статически предварительно выделенном массиве) data. Массив data имеет размер M. Однако есть две интересные вещи. Сначала доступ к значениям осуществляется в случайном порядке, который контролируется функцией fast_hash_64 (заполненной i для разнообразия). Это стандартная функция быстрого хеширования, работающая с 64-битными значениями (через инструкции SSE). Во-вторых, мы применяем произвольную обработку, функцию F, к каждому значению, которое мы извлекаем из данных. «Сертификат» вычисляется и сообщается позже, просто потому, что если мы просто применим F к data[pos] и не используем результат нигде в программе, некоторые компиляторы достаточно умны, чтобы дать нам бесконечное ускорение. путем… полного удаления петли! Также обратите внимание, что мы не записываем обратно в данные. В этом эксперименте мы читаем только из памяти в одном потоке. Поскольку шаблон доступа равномерно случайен для M значений data, мы априори не можем извлечь выгоду из локальности данных и кэширования. Мы также установили M так, чтобы данные не помещались в кэше L3 (который на этой машине составляет 15 МБ, поэтому эксперимент проводился с 4 ГБ данных). Чем больше, тем лучше, чтобы свести к минимуму вероятность того, что 2 последовательных поиска будут оба в кеше. Для контекста приведенный выше код может быть частью соединения в базе данных. На самом деле, «пакетная» оптимизация, по-видимому, широко используется в этой области (я не эксперт по БД с большой натяжкой).

Оптимизация пакетной обработки

Без лишних слов давайте посмотрим на первую версию «пакетной оптимизации»:

size_t last = (N / batch_size) * batch_size;
for (size_t i = 0; i < last; i += batch_size) {
  for (size_t j = 0; j < batch_size; ++j) {
    size_t pos = fast_hash_64(i + j, N) % M;
    batch[j] = data[pos];
  }
  for (size_t j = 0; j < batch_size; ++j) {
    certificate += F(batch[j]);
  }
}
for (size_t i = last; i < N; ++i) {
  size_t pos = fast_hash_64(i, N) % M;
  certificate += F(data[pos]);
}

Что здесь происходит? Что ж, у нас тот же шаблон произвольного доступа к данным, и та же обработка F применяется к каждому значению (и значение сертификата остается прежним, важно убедиться в этом). Но на этот раз мы разделим итерацию на пакеты. И мы делаем эту любопытную вещь, когда мы сначала извлекаем все значения в пакет, а затем обрабатываем пакет отдельно. Мы извлекаем, затем обрабатываем точно значения «batch_size», затем переходим к следующему пакету. Это отдаленно связано с такими терминами, как «векторизация» и «собрать-рассеять», хотя и не совсем одно и то же. Насколько это хорошо? Получим ли мы ускорение с этим кодом? Вот где это становится немного сложно. Это зависит от «полезной нагрузки», то есть фактической обработки, происходящей в F, и от размера пакета. Это также зависит от вашего оборудования и конфигурации системы, как указано в заявлении об отказе от ответственности выше. Но да, это делает что-то интересное, и вот результаты:

Красная плоская линия — это задержка первого фрагмента кода, непакетной версии нашего цикла. Поскольку этот код не пакетный, он становится плоским, когда мы меняем размер пакета. Синяя кривая — это задержка для пакетной версии кода. Ярлыки «math», «id», «p1», «p4»… относятся к различным объемам и типам работы, которую F выполняет над каждым элементом данных. Мы видим, что «p4» показывает наилучшее ускорение, если вы выберете размер пакета около 16 или более (горизонтальная ось — это размер пакета в количестве элементов — умножьте на 4 для байтов, поскольку в эксперименте используются целые числа C++) . Обратите внимание, что я решил указать 50-й процентиль, а не среднее значение, потому что это более надежные оценки центральности и отклонения (менее чувствительные к выбросам). Глядя на эти результаты, мы видим, что для полезной нагрузки «идентификация» пакетная обработка фактически замедляет выполнение. Я не уверен, почему в этот момент. «Математическая» полезная нагрузка не получает большого улучшения от пакетной обработки, но и различные полезные нагрузки «p» выше 28. Вот как выглядит полезная нагрузка «p1» (помните, что это один из экземпляров функции «F» выше). ), в C++ и на ассемблере (скомпилировано с помощью gcc 4.8.2):

inline int p1(int x) {
 const unsigned char *ptr = (const unsigned char *) &x;
 const uint32_t Prime = 0x01000193; // 16777619
 uint32_t hash = 0x811C9DC5; // 2166136261
 hash = (*ptr++ ^ hash) * Prime;
 hash = (*ptr++ ^ hash) * Prime;
 hash = (*ptr++ ^ hash) * Prime;
 return (*ptr ^ hash) * Prime;
}
 movzbl %dil, %eax
 pushq %rbx
 movl %edi, %ebx
 xorl $-2128831035, %eax
 movzbl %bh, %esi
 movl %edi, %ecx
 imull $16777619, %eax, %edx
 shrl $16, %ecx
 shrl $24, %edi
 movzbl %cl, %r9d
 popq %rbx
 xorl %esi, %edx
 imull $16777619, %edx, %r8d
 xorl %r9d, %r8d
 imull $16777619, %r8d, %r10d
 xorl %edi, %r10d
 imull $16777619, %r10d, %eax
 ret

Мы видим, что «p1» — это примерно 17 инструкций по сборке. Обратите также внимание на то, что «p1» включает в себя в основном операции между регистрами. Это означает, что это очень оптимистичная «полезная нагрузка». Конечно, в реальном приложении код, вероятно, был бы намного сложнее, но также включал бы просмотр других областей памяти, что плохо для кеша. Другие «pn» — это просто итерации «p1»:

template <size_t n>
inline int pn(int x) { 
  for (size_t i = 0; i < n; ++i) 
    x = p1(x); 
  return x; 
}
inline int id(int x) { return x; }
inline int math(int x) { 
  return (int) ((int) ((int) cos(x) + sin(x)) / (1+log(x)));  
}

Я также показал код для «id» («идентификация» на графике выше) и для «математической» полезной нагрузки для справки. «Математическая» полезная нагрузка очень глупая, единственный смысл заключался в использовании циклов ЦП. Обратите внимание, что для полезной нагрузки «pn» мы можем легко подсчитать количество инструкций ЦП: это 17 * n.

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

Пик кривой приходится на «4», что указывает на то, что «p4» — это место, где мы получаем наилучшее ускорение. После этого качество пакетной обработки быстро снижается, хотя долгое время остается выше 1,0 («p128» имеет 2176 инструкций).

Почему это работает?

Как работает эта оптимизация пакетной обработки? Почему это обеспечивает ускорение? Основная причина заключается в том, что, объединяя множество выборок из памяти при подготовке пакета, мы используем большую пропускную способность памяти. Если вы извлекаете одно значение, обрабатываете одно значение, извлекаете следующее, обрабатываете следующее… ЦП будет ждать загрузки каждого значения из памяти перед его обработкой. При пакетной обработке мы даем ЦП возможность выполнять множество загрузок из основной памяти параллельно. Мы максимизируем использование пропускной способности памяти, выполняя несколько параллельных загрузок. fast_hash_64 зажат между загрузками из памяти, да, но это не имеет значения, потому что fast_hash_64 не нуждается в зависимости от основной памяти. Он работает в основном с регистрами с заданными значениями i, j и N. Он не сильно мешает выдаче параллельных загрузок. Затем, по мере увеличения размера полезной нагрузки, преимущества параллельных нагрузок уменьшаются: система становится все более и более привязанной к ЦП, а не к нагрузкам на память. Для достижения наилучших результатов вы хотите, чтобы полезная нагрузка имела значительный размер (идентификатор немного отставал), но вам также не нужна слишком большая полезная нагрузка. Однако есть много интересных подробностей о том, как процессор и память взаимодействуют. Если интересно, рекомендую эту ссылку: https://people.freebsd.org/~lstewart/articles/cpumemory.pdf.

Можем ли мы сделать лучше?

История на этом не заканчивается. Есть еще. Мы можем сделать лучше. Я представлю 2 варианта пакетной оптимизации, один из которых неожиданно хорош для небольших партий, а другой немного лучше, чем «только пакетный» код, который мы видели до сих пор. Я покажу код, потом результаты. Во-первых, вот «неожиданно хороший» вариант. Я назову это «партией локаций»:

for (size_t i = 0; i < N; ++i) {
  locations[i] = fast_hash_64(i, N) % M;
}
size_t last = (N / batch_size) * batch_size;
for (size_t i = 0; i < last; i += batch_size) {
  for (size_t j = 0; j < batch_size; ++j) {
    batch[j] = data[locations[i+j]]; 
    if (i+j+batch_size < N) {
      __builtin_prefetch(data + locations[i+j+batch_size]);
    }
  }
  for (size_t j = 0; j < batch_size; ++j) {
    certificate += F(batch[j]);
  }
}
for (size_t i = last; i < N; ++i) {
  size_t pos = fast_hash_64(i, N) % M;
  certificate += F(data[pos]);
}

Что происходит в «пакете местоположений», так это то, что мы сначала вычисляем все местоположения, которые нам понадобятся, все N из них, и сохраняем их. Затем мы делаем наши обычные итерации пакетной обработки, уже зная местоположения, и на этот раз используя ручную предварительную выборку. Позвольте мне также показать код лучшего варианта, который у меня есть на данный момент, который я назову «пакетной предварительной выборкой»:

size_t last = (N / batch_size) * batch_size;
for (size_t i = 0; i < last; i += batch_size) {
  for (size_t j = 0; j < batch_size; ++j) {
    size_t pos = i > 0 ? hashes[j] : fast_hash_64(i + j, N) % M;
    batch[j] = data[pos];
  }
  for (size_t j = batch_size; j < 2*batch_size; ++j) {
    size_t pos = hashes[j-batch_size] = fast_hash_64(i + j, N) % M;
    __builtin_prefetch(data + pos, 0, 1);
  }
  for (size_t j = 0; j < batch_size; ++j) {
    certificate += F(batch[j]);
  }
}
for (size_t i = last; i < N; ++i) {
  size_t pos = fast_hash_64(i, N) % M;
  certificate += F(data[pos]);
}

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

Все три варианта в целом имеют сходное асимптотическое поведение: преимущества уменьшаются по мере увеличения размера пакета и/или размера полезной нагрузки. Опять же, «p4» кажется идеальным размером полезной нагрузки, и снова где-то между 10 и 20 кажется идеальным размером пакета. Давайте посмотрим на ускорение для всех трех вариантов, когда мы изменим полезную нагрузку:

Независимо от того, какой вариант мы используем, идеальный размер полезной нагрузки — «p4» (или близкий к нему), что составляет около 17*4 = 68 ассемблерных инструкций (включая регистры, но практически без передачи памяти). Мы также видим, что предварительная выборка помогает — ускорение для «пакетной предварительной выборки» намного лучше, чем для «только пакетной». Давайте рассмотрим это более подробно, вернувшись к абсолютным задержкам:

«Пакетная предварительная выборка» обеспечивает максимальное ускорение 4,1 при размере пакета 12 значений. В этом эксперименте каждое значение представляет собой целое число размером 4 байта, поэтому объем памяти, занимаемый пакетом размером 12, составляет ровно 48 байт. Обратите также внимание на то, как «группа местоположений» (желтая кривая) удивительно хороша при небольших размерах пакетов. К сожалению, его преимущества быстро исчезают по мере увеличения размера партии.

Почему эти 2 варианта работают лучше, чем исходный, «только пакетный» код? Для «пакета местоположений», помимо ручной предварительной выборки, я интерпретирую, что мы выигрываем от локальности данных для массива locations. Но в то же время наличие этого массива в иерархии кеша означает, что для пакетов доступно меньше кеша. Однако в настоящее время у меня нет хорошего объяснения, почему производительность этого варианта быстро ухудшается. Если у вас есть какие-либо идеи по этому поводу, пожалуйста, напишите мне сообщение ниже. Что касается варианта «пакетной предварительной выборки», мы явно пожинаем плоды ручной предварительной выборки. Но обратите внимание, как зеленая кривая возвращается вверх (ускорение уменьшается), в то время как синяя кривая («только партия») остается плоской (плоскостность синей кривой лучше всего видна на первом графике). Похоже, что ручное принудительное выполнение слишком большого количества предварительных выборок становится контрпродуктивным. Существует оптимальное значение для предварительной выборки вручную, что лежит в основе оптимального размера пакета.

Возможны дальнейшие оптимизации. Я пробовал сортировать местоположения в варианте партии местоположений, чтобы максимизировать локальность данных внутри пакетов, но сортировка всегда была слишком медленной. Еще одна оптимизация, которую я не пробовал, но я слышал, что она очень многообещающая, заключается в уменьшении количества промахов TLB за счет использования огромных страниц памяти. Вот ссылка на это: https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt. Это вновь ввело бы своего рода локальность данных, по крайней мере, с точки зрения TLB.

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

На этом графике показано множество запусков для различных размеров пакетов и различных процентилей ускорения для полезной нагрузки «p4» и кода «пакетной предварительной выборки». Медиана убедительно составляет 4,1X при лучшем размере пакета из 12 значений, что означает, что да, результаты довольно хорошо сохраняются во многих запусках. 95% прогонов достигают ускорения 3,89X или около того, и только 5% прогонов работают лучше, чем 4,21X. Точечные артефакты под кривыми могут быть связаны с тем, что регулятор частоты ЦП замедляет ЦП, чтобы дать ему остыть, но пытается обеспечить максимально возможную скорость в противном случае.

Вывод

«Пакетная оптимизация» с предварительной выборкой обеспечивает хорошее ускорение, хотя эти результаты трудно обобщать. Как упоминалось выше, детали системы, в которой вы применяете эту оптимизацию, будут иметь решающее значение. Например, я провел тот же эксперимент на MacBook, а не на машине с Xeon-5/NUMA/Linux, и результаты были очень разными (я подозреваю, что тип кеша и политики замены записей в кеше разные). Если вы хотите использовать этот метод, я бы порекомендовал вам сначала загрузить код для этого теста с git и попробовать его на вашей целевой платформе. Кроме того, еще раз обратите внимание, что этот эксперимент сильно идеализирован. Например, Linux-машина в этом эксперименте мало что делала, кроме запуска тестовой программы, чего не будет в реальной жизни, где кеш почти наверняка будет использоваться совместно с другими процессами.

Информация о настройке

CPU:                   Intel Xeon-5 2620 v2 
OS:                    linux 6.6 
Compiler:              gcc 4.8.3.4 
Language:              c++ 11 
Compilation flags:     -std=c++11 -DNDEBUG -O3 -funroll-all-loops 
Memory alignment:      valloc 
Threads:               only 1 process, 1 thread
lscpu:
Architecture:          x86_64 
CPU op-mode(s):        32-bit, 64-bit 
Byte Order:            Little Endian 
CPU(s):                12 On-line 
CPU(s) list:           0–11 
Thread(s) per core:    2 
Core(s) per socket:    6 
Socket(s):             1 
NUMA node(s):          1 
Vendor ID:             GenuineIntel 
CPU family:            6 
Model:                 62 
Stepping:              4 
CPU MHz:               1200.000 
BogoMIPS:              4190.02 
Virtualization:        VT-x 
L1d cache:             32K 
L1i cache:             32K 
L2 cache:              256K 
L3 cache:              15360K 
NUMA node0 CPU(s):     0–11
All runs with taskset -c 7 (pinned to CPU 7)
Full details at: https://github.com/ferd36/batching-optimization