Используя SIMD на amd64, когда лучше использовать больше инструкций, чем загружать из памяти?

Таблицы поиска редко обеспечивают выигрыш в производительности в реальном коде, особенно когда они достигают размера 4 КБ. Современные процессоры могут выполнять вычисления так быстро, что почти всегда быстрее просто выполнять вычисления по мере необходимости, а не пытаться кэшировать их в справочной таблице. Единственным исключением из этого являются случаи, когда вычисления чрезмерно дороги. Это явно не тот случай, когда вы говорите о разнице в 30 и 8 инструкций.

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

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

Другая скрытая стоимость (больших) LUT заключается в том, что они рискуют вытеснить код из кэша, поскольку большинство современных процессоров имеют унифицированные кэши данных и инструкций. Таким образом, даже если реализация на основе LUT немного быстрее, она очень сильно рискует замедлить все остальное. Микротест этого не покажет. (Но на самом деле бенчмаркинг вашего реального кода будет, так что это всегда хорошо, когда это возможно. Если нет, читайте дальше.)

Мое эмпирическое правило таково: если подход на основе LUT не дает явного выигрыша в производительности по сравнению с другим подходом в реальных тестах, я его не использую. Похоже, здесь именно так. Если результаты тестов слишком близки, чтобы их можно было назвать, это не имеет значения, поэтому выберите реализацию, которая не увеличивает ваш код на 4 КБ.

Коди Грей уже рассмотрел большую часть баз выше, так что я просто добавлю несколько своих мыслей. Обратите внимание, что я не так негативно отношусь к LUT, как Коди: вместо того, чтобы давать им общее «большой палец вниз», я думаю, вам нужно тщательно проанализировать недостатки. В частности, чем меньше LUT, тем больше вероятность того, что его можно будет сравнить по принципу «яблоки за яблоками» с вычислительным подходом.

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

SIMD

Большая часть обсуждения, следующего за этим разделом, не относится конкретно к SIMD — оно относится как к скалярным, так и к SIMD-кодам. Прежде чем мы дойдем до этого, давайте немного поговорим о LUT, поскольку они относятся конкретно к SIMD.

Для SIMD-кода LUT имеют некоторые преимущества, а также дополнительные недостатки. Главный недостаток заключается в том, что, помимо обсуждаемого ниже обмана типа PSHUFB, не существует хорошего SIMD-эквивалента скалярному LUT-коду. То есть, хотя вы можете выполнять N (где N — ширина SIMD) параллельных независимых вычислений для каждой инструкции с использованием SIMD, обычно вы не можете выполнять N операций поиска. Обычно вы ограничены тем же количеством операций поиска за цикл в коде SIMD, что и в коде LUT, причем 2/цикл является обычным числом для современного оборудования.

Это ограничение является не просто некоторым упущением в SIMD ISA — это довольно фундаментальный результат того, как устроены кэши L1: у них очень мало портов чтения (как указано выше, обычно 2), и каждый добавленный порт значительно увеличивает Размер L1, энергопотребление, задержка и т. д. Таким образом, вы просто не увидите процессоры общего назначения, предлагающие 16-стороннюю загрузку из памяти в ближайшее время. Вы часто видите доступную инструкцию gather, но она не позволяет обойти это фундаментальное ограничение: вы по-прежнему будете ограничены ограничением в 2 загрузки за цикл. Лучшее, на что вы можете надеяться в gather, это то, что он может заметить, когда две нагрузки находятся по одному и тому же адресу (или, по крайней мере, "достаточно близко"), так что они могут быть удовлетворены одной и той же нагрузкой⁶.

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

С другой стороны, LUT часто находят новую нишу в коде SIMD, потому что:

1. Тот факт, что вы векторизовали код, означает, что вы, вероятно, ожидаете среднего или большого размера задачи, что помогает амортизировать затраты на кэширование LUT.

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

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

4. Наборы инструкций SIMD часто содержат инструкции по тасовке/перестановке, которые можно переназначить в функции «поиска в регистре», как описано ниже.

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

Проблема поэтапного решения

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

Если вы принимаете серию решений по оптимизации на основе контрольных показателей, каждый раз выбирая «лучший» подход на основе реальных контрольных показателей, более поздние решения могут сделать более ранние недействительными. Например, допустим, вы рассматриваете возможность использования LUT или вычислений для функции A. Вы можете обнаружить, что в реальном тесте LUT несколько быстрее, поэтому вы реализуете это. На следующий день вы тестируете новые реализации функции B, опять же с подходом сравнения LUT и вычислений. Вы можете снова обнаружить, что LUT лучше, чем вычисления, поэтому реализуете это, но если вы вернулся и протестировал A, результаты могут быть другими! Теперь A может быть лучше с вычислительным подходом, поскольку добавление LUT для функции B вызвало усиление конкуренции за кэш. Если бы вы оптимизировали функции в обратном порядке, проблема не возникла бы².

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

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

Приблизительные оценки LUT

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

Например, возьмите какое-то контрольное число для промаха кеша в DRAM, например 200 циклов, а затем вы можете оценить производительность LUT в наихудшем случае для различных размеров итераций вашего алгоритма. Например, если подход LUT занимает 10 циклов при попадании в кэш, по сравнению с 20 циклами для подхода вычислений, и имеет таблицу размером 640 байт (10 строк кэша), то вы можете заплатить стоимость 10 * 200 = 2000. циклов, чтобы получить всю LUT, поэтому вам нужно выполнить итерацию не менее 200 раз, чтобы окупить эту стоимость. Вы также можете удвоить стоимость промаха кеша, поскольку перенос LUT в кеш, по-видимому, часто также вызывает промах в нисходящем направлении для любой строки, которая была вытеснена.

Таким образом, вы иногда можете сказать: «Да, LUT имеет стоимость X циклов в худшем случае из-за эффектов кэширования, но мы почти всегда окупаем это, потому что мы обычно вызываем метод Y раз с экономией Z циклов на вызов. ".

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

Промахи I-кэша

Одна вещь, которая не часто упоминается в дебатах между LUT и вычислениями, - это влияние на I$. Некоторые программы, особенно большие объектно-ориентированные или разветвленные⁴, более чувствительны к перегрузке кэша инструкций, чем к перегрузке кэша данных. Если подход, основанный на вычислениях, требует значительно больше статических инструкций (т. е. количество невыполненных инструкций на стороне кода), он может в некоторой степени отдать предпочтение LUT. Тот же самый аргумент можно привести, например, при решении разворачивать или агрессивно векторизовать циклы или нет.

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

Гибридные подходы

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

Это вычисление может предшествовать поиску, когда вы сопоставляете входной домен с индексом с меньшим доменом, так что все входы, сопоставленные с одним и тем же индексом, имеют одинаковый ответ. Простым примером может быть вычисление четности: вы можете сделать это «быстро» (в смысле микротеста!) с таблицей поиска 65 КБ, но вы также можете просто выполнить xor-fold входных данных, например input ^ (input >> 8), а затем использовать нижний байт для индексации в таблица на 256 записей. Таким образом, вы уменьшите размер таблицы в 256 раз за счет еще пары инструкций (но все же немного быстрее, чем метод полных вычислений).

Иногда вычисление происходит после поиска. Это часто принимает форму хранения таблицы в несколько более «сжатом» формате и распаковки вывода. Представьте, например, некоторую функцию, которая отображает байт в логическое значение. Любая такая функция может быть реализована с помощью lut bool[256] за счет 256 байт. Однако каждой записи действительно нужен только один бит (всего 32 байта), а не один байт - если вы хотите «распаковать» после поиска, например return bitwise_lut[value] & (1 << (value & 7)).

Совершенно другой гибридный подход заключается в выборе между LUT и вычислительными подходами во время выполнения, в зависимости от размера задачи. Например, у вас может быть подход на основе LUT для декодирования некоторых данных, закодированных в base64, который, как вы знаете, работает быстро, но накладывает нетривиальные затраты на кеш и может страдать от промахов прогрева, и у вас может быть подход на основе вычислений, который медленнее в долгосрочной перспективе, но не имеет таких проблем. Поскольку вы заранее знаете размер данных, почему бы просто не выбрать лучший алгоритм на основе некоторой точки пересечения, которую вы вычисляете или получаете в ходе тестирования?

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

Сокращение промахов кэша

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

Расположение LUT рядом с кодом

В принципе вроде как для очень маленьких LUT можно просто поместить LUT в ту же строку кэша, что и код. Это работает лучше всего, если ваш LUT немного меньше, чем строка кэша; в частности, он работает лучше всего, если добавление его к размеру функции не меняет общее количество строк кэша для комбинированного кода LUT +, но все же может иметь небольшие преимущества, даже если это не так^5.

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

LUT в регистрах GP и SIMD

Крайняя версия подхода «поместить LUT рядом с кодом» заключается в том, чтобы найти LUT в коде. В скалярном коде вы можете сделать это, загрузив константу в регистр, а затем выполнив что-то вроде сдвига и маски переменной, чтобы выбрать элемент в регистре. Например, вы можете использовать регистр как 16-элементную логическую LUT для вычисления четности< /а>.

В мире x86-64 SIMD вы можете довести эту идею до крайности с помощью PSHUFB (впервые доступна в SSSE3). В своем 128-битном воплощении SSE он эффективно позволяет выполнять 16 параллельных операций поиска от 4 до 8 бит за один цикл. Версия AVX2 позволяет выполнять 32 таких поиска параллельно. Таким образом, вы можете выполнять поиск на стероидах без большинства недостатков настоящего LUT (т. е. таблица хранится в регистре — хотя вам может потребоваться одна загрузка, чтобы получить ее туда в первую очередь).

Это работает только для небольших (16-элементных таблиц) - хотя вы можете расширить это до 32, 64 и т. д., таблиц элементов с 2, 4, ..., PSHUFB операциями и аналогичным количеством операций смешивания, но это все еще подходит только для довольно маленьких таблиц.

¹ Возможно, вы могли бы также назвать это проблемой "зависимой от пути оптимизации" или "неаддитивной оптимизации".

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

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

⁴ На ум приходят компиляторы, браузеры и все виды JIT-кода.

⁵ Например, используя строку кэша, полученную в результате последовательной предварительной выборки, которая в противном случае могла бы быть потрачена впустую, или, по крайней мере, разместив код и LUT на одной и той же странице размером 4 КБ, возможно, избегая промаха TLB. .

⁶ Стоит отметить, что на Intel, несмотря на наличие по крайней мере 4 новых выпусков чипов, gather по-прежнему не делает этого: он ограничен в лучшем случае 2 загрузками за цикл, даже если есть дублирование в загруженных индексах.