Оптимизация производительности сборки x86-64 - выравнивание и прогноз ветвления

Question

Оптимизация производительности сборки x86-64 - выравнивание и прогноз ветвления

В настоящее время я пишу высокооптимизированные версии некоторых строковых функций стандартной библиотеки C99, таких как strlen(), memset()и т. д. с использованием сборки x86-64 с инструкциями SSE-2.

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

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

Таким образом, я предполагаю, что есть некоторые проблемы с выравниванием кода и / или с ветвями, которые были ошибочно предсказаны.

Я знаю, что даже при одинаковой архитектуре (x86-64) разные процессоры имеют разные алгоритмы прогнозирования ветвлений.

Но есть ли какие-то общие советы при разработке для высокой производительности на x86-64, о выравнивании кода и предсказании ветвлений?

В частности, о выравнивании, я должен гарантировать, что все метки, используемые инструкциями перехода, выровнены по DWORD?

_func:
    ; ... Some code ...
    test rax, rax
    jz   .label
    ; ... Some code ...
    ret
    .label:
        ; ... Some code ...
        ret

В предыдущем коде я должен использовать директиву выравнивания перед .label:, лайк:

align 4
.label:

Если да, достаточно ли выравнивания по DWORD при использовании SSE-2?

А что касается предсказания ветвлений, существует ли "предпочтительный" способ организации меток, используемых инструкциями перехода, для того, чтобы помочь ЦП, или современные ЦП достаточно умны, чтобы определить это во время выполнения путем подсчета количества раз, которое берется ветвь?

РЕДАКТИРОВАТЬ

Хорошо, вот конкретный пример - вот начало strlen() с SSE-2:

_strlen64_sse2:
    mov         rsi,    rdi
    and         rdi,    -16
    pxor        xmm0,   xmm0
    pcmpeqb     xmm0,   [ rdi ]
    pmovmskb    rdx,    xmm0
    ; ...

Выполнение его 10000 000 раз с 1000-символьной строкой дает около 0,48 секунды, и это нормально.
Но он не проверяет наличие ввода строки NULL. Очевидно, я добавлю простую проверку:

_strlen64_sse2:
    test       rdi,    rdi
    jz          .null
    ; ...

Тот же тест, теперь он запускается за 0,59 секунды. Но если я выровняю код после этой проверки:

_strlen64_sse2:
    test       rdi,    rdi
    jz          .null
    align      8
    ; ...

Оригинальные спектакли вернулись. Я использовал 8 для выравнивания, так как 4 ничего не меняет.
Может кто-нибудь объяснить это и дать несколько советов о том, когда выравнивать или не выравнивать фрагменты кода?

РЕДАКТИРОВАТЬ 2

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

33

performance assembly x86-64 branch-prediction sse2

Источник

user182676 07 авг '13 в 21:18

4 ответа

Другие вопросы по тегам performance assembly x86-64 branch-prediction sse2

user319204 16 авг '13 в 18:10 2013-08-16 18:10 · Answer 1 · 2013-08-16 18:10

Оптимизация выравнивания

1. Используйте `.p2align <abs-expr> <abs-expr> <abs-expr>` вместо `align`,

Предоставляет мелкозернистый контроль, используя 3 параметра

param1 - выровнять по какой границе.
param2 - заполнить заполнение чем (нулями или NOP с).
param3 - НЕ выравнивать, если заполнение будет превышать указанное количество байтов.

2. Совместите начало часто используемых блоков кода с границами размера строки кэша.

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

3. Используйте многобайтовый `NOP` s для заполнения, чтобы уменьшить время, затрачиваемое на выполнение `NOP` с.

  /* nop */
  static const char nop_1[] = { 0x90 };

  /* xchg %ax,%ax */
  static const char nop_2[] = { 0x66, 0x90 };

  /* nopl (%[re]ax) */
  static const char nop_3[] = { 0x0f, 0x1f, 0x00 };

  /* nopl 0(%[re]ax) */
  static const char nop_4[] = { 0x0f, 0x1f, 0x40, 0x00 };

  /* nopl 0(%[re]ax,%[re]ax,1) */
  static const char nop_5[] = { 0x0f, 0x1f, 0x44, 0x00, 0x00 };

  /* nopw 0(%[re]ax,%[re]ax,1) */
  static const char nop_6[] = { 0x66, 0x0f, 0x1f, 0x44, 0x00, 0x00 };

  /* nopl 0L(%[re]ax) */
  static const char nop_7[] = { 0x0f, 0x1f, 0x80, 0x00, 0x00, 0x00, 0x00 };

  /* nopl 0L(%[re]ax,%[re]ax,1) */
  static const char nop_8[] =
    { 0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00};

  /* nopw 0L(%[re]ax,%[re]ax,1) */
  static const char nop_9[] =
    { 0x66, 0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00 };

  /* nopw %cs:0L(%[re]ax,%[re]ax,1) */
  static const char nop_10[] =
    { 0x66, 0x2e, 0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00 };

(до 10 байт NOPс для х86. Источник binutils-2.2.3.)

Оптимизация прогнозирования ветвлений

_{Много вариаций между микроархитектурами / поколениями x86_64.} _{Однако общий набор рекомендаций, применимых ко всем из них, можно резюмировать следующим образом.} _{Ссылка: Раздел 3 руководства по архитектуре x86 Агнера Фога.}

1. Придерживайтесь коротких прыжков.

Прыжки в длину не прогнозируются, т. Е. Конвейер всегда останавливается при условном прыжке в длину.

2. Разверните большие петли.

Логика обнаружения цикла гарантированно работает ТОЛЬКО для циклов с < 64 итерациями. Это связано с тем, что команда перехода распознается как имеющая циклическое поведение, если она идет в одну сторону n-1 раз, а затем идет в другую сторону 1 раз, для любого n до 64.

user182676 17 авг '13 в 10:41 2013-08-17 10:41 · Answer 2 · 2013-08-17 10:41

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

1 - выравнивание кода

Intel рекомендует выровнять цели кода и ветвления по 16-байтовым границам:

3.4.1.5 - Правило 12. Кодирование сборки / компилятора.
Все цели ветвления должны быть выровнены по 16 байтов.

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

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

В качестве обозначения, .p2align Директива недоступна в NASM или YASM.
Но они поддерживают выравнивание с другими инструкциями, кроме NOP со стандартом align директива:

align 16, xor rax, rax

2 Прогноз отрасли

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

Процессор пытается сохранить историю ветвления в BTB (Branch Target Buffer).
Но когда информация о ветвлении недоступна в BTB, ЦП будет использовать то, что они называют статическим предсказанием, которое подчиняется простым правилам, как указано в руководствах Intel:

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

Вот пример для первого случая:

test rax, rax
jz   .label

; Fallthrough - Most likely

.label:

    ; Forward branch - Most unlikely

Инструкции под .label это маловероятное условие, потому что .label объявляется после фактической ветки.

Для второго случая:

.label:

    ; Backward branch - Most likely

test rax, rax
jz   .label

; Fallthrough - Most unlikely

Здесь, инструкции под .label являются вероятным условием, так как .label объявляется перед фактической веткой.

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

Как я уже говорил, это была самая важная часть.

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

TheCodeArtist также упоминает о развертывании цикла в своем ответе.
Хотя это и не было проблемой, поскольку мои циклы были уже развернуты, я упоминаю об этом здесь, поскольку это действительно чрезвычайно важно и приносит существенный прирост производительности.

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

Начиная с Pentium Pro, процессоры x86 имеют инструкции по условному перемещению, которые могут помочь устранить ветвление и снизить риск неправильного прогнозирования:

test   rax, rax
cmovz  rbx, rcx

Так что на всякий случай приятно иметь в виду.

user224132 27 июл '15 в 00:18 2015-07-27 00:18 · Answer 3 · 2015-07-27 00:18

Чтобы лучше понять, почему и как важно выравнивание, посмотрите документацию по микроархитектуре Agner Fog, esp. раздел о командно-выборочном интерфейсе различных конструкций ЦП. Sandybridge представил кэш UOP, который сильно отличается от пропускной способности, особенно. в коде SSE, где длина инструкции часто слишком велика для 16B за цикл, чтобы покрыть 4 инструкции.

Правила заполнения строк кэша UOP сложны, но новый блок из 32B инструкций всегда запускает новую строку кэша, IIRC. Так что выравнивание точек входа горячей функции в 32B - хорошая идея. Такое большое заполнение в других случаях может повредить плотности больше, чем помочь. (Тем не менее, в L1 I$ все еще есть строки кэша 64B, поэтому некоторые вещи могут повредить плотности L1 I$, помогая увеличить плотность кэша.)

Буфер цикла также помогает, но взятые ветви нарушают 4 мопа за цикл. например, цикл из 3 моп выполняется следующим образом abc, abcне abca, bcda, Таким образом, цикл по 5 мегапикселей идет на одну итерацию за 2 цикла, а не один за 1.25. Это делает раскрутку еще более ценной.

user3255455 26 июл '15 в 23:28 2015-07-26 23:28 · Answer 4 · 2015-07-26 23:28

"Цели ветвления должны быть 16-байтовым правилом выравнивания" не является абсолютным. Причина этого правила заключается в том, что при 16-байтовом выравнивании 16 байтов инструкций можно прочитать за один цикл, а затем еще 16 байтов в следующем цикле. Если ваша цель со смещением 16n + 2, то процессор все еще может прочитать 14 байтов инструкций (остаток строки кэша) за один цикл, и это часто достаточно хорошо. Однако начинать цикл со смещения 16n + 15 - плохая идея, поскольку за один раз может быть прочитан только один байт инструкции. Более полезным является сохранение всего цикла в минимально возможном количестве строк кэша.

На некоторых процессорах предсказание ветвления имеет странное поведение, когда все ветви в пределах 8 или 4 байтов используют один и тот же предиктор ветвления. Переместите ветви так, чтобы каждая условная ветвь использовала свой собственный предиктор ветвления.

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

Оптимизация производительности сборки x86-64 - выравнивание и прогноз ветвления

4 ответа

Оптимизация выравнивания

1. Используйте .p2align <abs-expr> <abs-expr> <abs-expr> вместо align,

2. Совместите начало часто используемых блоков кода с границами размера строки кэша.

3. Используйте многобайтовый NOP s для заполнения, чтобы уменьшить время, затрачиваемое на выполнение NOP с.

Оптимизация прогнозирования ветвлений

1. Придерживайтесь коротких прыжков.

2. Разверните большие петли.

1. Используйте `.p2align <abs-expr> <abs-expr> <abs-expr>` вместо `align`,

3. Используйте многобайтовый `NOP` s для заполнения, чтобы уменьшить время, затрачиваемое на выполнение `NOP` с.