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

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

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

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

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

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

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

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

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

В предыдущем коде следует использовать директиву align перед .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
    ; ...

Запуск его 10'000'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

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

Ответ 1

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

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

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

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

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

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

3. Используйте многобайтовый `NOP` для заполнения, чтобы уменьшить время, затрачиваемое на выполнение `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 для x86. Исходный binutils-2.2.3.)

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

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

1. Разверните циклы, чтобы избежать слишком большого количества итераций.

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

Это на самом деле не относится к предикторам в Haswell и более поздних версиях, которые используют предиктор TAGE и не имеют специальной логики обнаружения петель для определенных ветвей. Число итераций ~ 23 может быть наихудшим случаем для внутреннего цикла внутри узкого внешнего цикла без какого-либо другого ветвления на Skylake: выход из внутреннего цикла в большинстве случаев ошибочен, но счетчик срабатываний настолько мал, что это происходит часто. Развертывание может помочь, укорачивая шаблон, но при очень высоких значениях числа циклов отключения один ошибочный прогноз в конце амортизируется во многих поездках, и для этого потребуется неоправданное количество развертываний.

2. Придерживайтесь ближних/коротких прыжков.

Дальний переход не прогнозируется, т.е. Конвейер всегда останавливается при переходе к новому сегменту кода (CS: RIP). В принципе, в любом случае нет причин использовать дальний прыжок, так что это в основном не актуально.

Косвенные переходы с произвольным 64-битным абсолютным адресом обычно прогнозируются на большинстве процессоров.

Но Silvermont (процессоры Intel с низким энергопотреблением) имеют некоторые ограничения в прогнозировании косвенных переходов, когда цель находится на расстоянии более 4 ГБ, поэтому избегайте того, чтобы при загрузке/отображении исполняемых файлов и общих библиотек в низком 32-битном виртуальном адресном пространстве это могло быть выигрышем., например, в GNU/Linux путем установки переменной среды LD_PREFER_MAP_32BIT_EXEC. См. Руководство по оптимизации Intel для получения дополнительной информации.

Ответ 2

Чтобы продолжить ответ 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 (буфере целевых буферов).
Но когда информация о филиале недоступна в BTB, CPU будет использовать то, что они называют статическим предсказанием, которые подчиняются простым правилам, как указано в руководствах 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

Так что на всякий случай, хорошая вещь, чтобы иметь в виду.

Ответ 3

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

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

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

Ответ 4

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

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

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