Оптимизация программ для современных интеловских процессоров (2010 г, i386)
Когда вышли первые пентиумы, было довольно много текстов с рекомендациями по
их эффективному использованию ассемблер-программистами: о том как комбинировать
команды, как максимально загружать ядро, как избегать опустошения конвейеров.
Мне попадались даже обучающие программы, которые мультиками показывали
всё это в наглядном виде.
В современных процессорах (2010 г) ситуация несколько изменилась: с одной
стороны - архитектура процессоров солидно усложнилась, с другой стороны -
целью некоторых усложнений как раз и является желание разработчиков железа
свалить вопросы оптимизации кода на аппаратную сторону: это всевозможный
reorder-инг команд, динамическое предсказание переходов, распознавание циклов
и, наконец, апофеоз: hypertreading - попытка одного физического
процессора косить под два, чтобы иметь большую возможность выбора
команд для объединения/перемешивания.
Тем не менее, список интеловских рекомендаций по эффективному
использованию ЦП нисколько не уменьшается, но даже наоборот - распух до
нескольких листов мелким шрифтом - и это только список общих положений.
Полный же рассказ об оптимизации занимает почти шесть сотен страниц.
И это - только об оптимизации. Списки команд, их систематизация -
это отдельные фолианты на сотни страниц каждый. Каждый том.
Материал по системе команд относительно несложен и его вполне
можно читать и воспринимать с листа английского оригинала. Текст
по оптимизации, на мой взгляд, воспринимаются более сложно.
Имея давнее увлечение программированием на ассемблерах, я прошерстил
некоторую часть этих книг и составил для себя конспект, посвященный оптимизации,
который предлагаю вашему вниманию. Возможно, некоторые
положения я понял и/или перевёл не вполне правильно, но, думаю,
бОльшая часть будет полезна и верна.
Конспект касается группы основных команд и почти не затрагивает группы SIMD,
так как в программе, которой я собираюсь заниматься, они почти не используются
(а материала по ним - ещё два вагона с большой тележкой).
================================================================================
Стр 68, 69 (надо вернутся)
(Стр 97) Некоторые рекомендации одинаково подходят для всех архитектур, но некоторые из рекомендаций
более предназначены для одной архитектуры, нежели для другой:
- Плотный поток через декодер инструкций важен для процессоров, основанных на Core i7, Core
(Pentium M, Solo, Duo), но менее важен для NetBurst.
- Шаблон кода 4-1-1 важен для Pentium M.
Solo и Duo к этому менее чувствительны.
- Размер кода на NetBurst ограничен trace cache. На Pentuim M - кешем инструкций.
- Частичная модификация регистров существенно портит ситуацию на PentiumM
(CPUID: family=6, model=9). На P4, Xeon, P-M (CPUID: family=6, model=13)
"such penalties are relieved by artificial" зависимостью между каждой
частью регистровой записи. Solo и Duo имеет незначительные задержки
при частичной модификации регистров. Для предотвращения используйте
полные регистры или extended moves.
- Используйте разрушающие зависимости инструкции (PXOR, SUB, XOR).
Также разрушать зависимость может инструкция XORPS может на Solo/Duo.
- Инструкции обмена FPU-стека несколько более тяжелы на архитектуре NetBurst.
- Аппаратная предвыборка может уменьшать задержки, но требует индивидуальной
настройки для различных архитектур.
- Задержки исполнения некоторых инструкций на NetBurst довольно существенны
(включая сдвиги/вращения, целочисленное умножение, mov из памяти с расширением
знака). Будьте осторожны при использовании LEA.
- На NetBurst: инструкция с непосредственным аргументом, требующая больше, чем 16-битовое
знаковое представление, следует за другой инструкцией, которая использует
непосредственный аргумент - может быть тормозом.
Оптимизация ветвлений:
- Располагайте код и данные на отдельных страницах. Это очень важно !
- Ликвидируйте ветвления, где это возможно.
- Организуйте алгоритмы так, чтобы они соответствовали алгоритму предсказания ветвлений.
- Используйте инструкцию pause в spin-wait циклах.
- Inline functions and pair up calls and returns.
- Разворачивайте циклы, имеющие 16 или меньше итерраций (если код не распухнет).
- Разделяйте ветвления так, чтобы они происходили не чаще, чем каждые три микрооперации.
- Не забывайте про префиксы вероятности ветвлений (,pt ,pn).
В разных архитектурах различаются предсказания: Pentium-M, Duo и Solo считают
все условные ветвления не срабатывающими (они их не анализируют статически
и полагаются только на статистику срабатываний). Но NetBurst считает ветвления "назад"
срабатывающими (если других данных по данной части кода нет). Что до статистического
анализа - то он очень прост: что было в прошлый раз, то будет и сейчас.
Главные заветы оптимизации (
Расшифровка влияния оптимизации:
i - локальное влияние - на конкретный участок кода
g - реальное влияние, у учётом среднестатистического мелькания в коде обычных приложений
H, M, L - High, Medium, Low
001..499 - если можно явно влиять на asm-код (т.е. для АСМ-программистов и разработчиков компиляторов),
500..999 - если есть только язык высокого уровня (для остальных)
):
iMH, gM
001: Правильно скомпонованная программа имеет мало ветвлений.
Для Pentum-M каждое ветвление на счету. Даже правильно предсказанное.
А выполненные ветвления ещё и нагружают буфер предсказаний.
iM, gML
002: Используйте SETcc и CMOVcc как замену непредсказуемым ветвлениям.
Не используйте вместо предсказуемых ветвлений. Не используйте это вместо
всех непредсказуемых ветвлений (поскольку эти инструкции процу придётся
выполнять независимо от сложившейся ситуации). Мало того, эти инструкции
ещё и портят жизнь движку out-of-order. Не забывайте, что нынешние процы вообще
шустро предсказывают ветвления и редко ошибаются. Используйте SETcc и
CMOVcc только если явно видно, что они эффективны для вашего алгоритма
(по сравнению с коряво предсказываемым ветвлением).
Мощный пример: X = (A < B) ? CONST1 : CONST2;
с ветвлением:
cmp a, b
jbe L30
mov ebx const1
jmp L31
L30:
mov ebx, const2
L31:
с SETcc:
xor ebx, ebx
cmp A, B
setge bl
sub ebx, 1
and ebx, CONST1-CONST2
add ebx, CONST2
XXX: без номера: используйте PAUSE здесь:
lock: cmp eax, a
jne loop
; Code in critical section:
loop: pause
cmp eax, a
jne loop
jmp lock
iM, gH
003: Делайте код так, чтобы он соответствовал статическим предсказаниям:
более вероятный код целью перехода "назад", маловероятный - целью перехода "вперёд".
iMH, gMH
004: Ближние вызовы (call) должны соответствовать ближним возвратам,
и дальние вызовы должны соответствовать дальним возвратам. Запихивание
(push) адреса возврата на стек и прыжки (jump) на процедуры не рекомендуются,
поскольку сбивают с толку trace cache (механизм быстрого угадывания переходов call/ret,
может шустро прыгать при вложенности до 16 уровней процедур).
call/ret - вообще дорогое удовольствие. Используйте inline, если:
- можно обойтись без передачи параметров.
- компилятор может их лучше оптимизировать.
- процедура содержит ветвления - если повезёт - их лучше удастся угадывать.
- корявое угадывание переходов внутри функции сильно портит работу, по сравнению
с корявым угадыванием, но когда функция будет inline.
iMH, gMH
005: Встраивайте функции (inline), если это уменьшает размер кода
или функция мелкая и часто выполняется.
iH, gH
006: Не встраивайте функции, если код от этого распухнет так, что
не влезет в кеш трассировки (trace cache).
iML, gML
007: Если вы не сдержались и получили больше 16-и шустрых вложенных прыжков
call/ret - попробуйте где нибудь сделать inline, в противном случае ускоритель
доступа к стеку откажется вам помогать.
iML, gML
008: Старайтесь встраивать мелкие функции, которые содержат плохопредсказуемые
ветвления. Если криво предсказанное ветвление укажет на RETURN - это
отвратительно скажется на производительности.
iL, gL
009: Если последний оператор в функции есть вызов другой функции - попробуйте
заменить эту call и последний ret на jmp: call x ; ret -> jmp x
iM, gL
010: Не запихивайте больше 4 ветвлений в 16-байтный блок кода.
iM, gL
011: Не стоит делать больше двух end loop -ветвлений в 16-байтном куске кода.
iM, gH
012: Цели ветвлений хотелось бы 16-байт-align.
iM, gH
013: Если тело условия маловероятно к исполнению - засуньте его
в другую часть программы, чтобы оно не забивало кеш инструкций.
Если вы вообще не верите, что оно когда нибудь исполнится
(типа обработчиков ошибок) - оно должно быть в другой странице кода.
iM, gL
014: Когда присутствует неявное ветвление (косвенные jmp),
попробуйте положить более вероятный код продолжения сразу за этой командой.
Если вы предполагаете что аппаратура не может предсказать переход,
по крайней мере положите после команды перехода команду UD2,
чтобы конвейеры не пытались забивать кеши всякой фигней.
Аппаратура считает более вероятным последний случившийся
переход, либо не предсказывает ничего, если не помнит случая
исполнения этой команды здесь.
Возможно, имеет смысл какие-то из переходов заменить
на группы условных ветвлений: для них сохраняется
индивидуальная история - это может помочь, если
есть какая-то упорядоченность вероятности выбора
конечных точек.
iM, gL
501: Если неявное ветвление имеет один-два более вероятных
варианта - попробуйте заменить их групой/деревом вложенных If
и уже затем Switch.
iH, gM
015: Разворачивание малых циклов, за счёт исключения
переменных-счётчиков и ветвлений, экономит меньше чем 10%
времени.
iH, gM
016: Избегайте особенно активного разворачивания циклов,
т.к. это может замусоривать кеши команд и трассировки.
iM, gM
017: Разворачивайте часто исполняющиеся циклы с
известным числом итераций так, чтобы число итераций
не превышало 16. Но делайте это так, чтобы цикл ещё умещался в
кеши инструкций и трассировки. Если тело цикла содержит более чем
одно условное ветвление, разворачивайте цикл так, чтобы он
имел не более 16/число_условных_ветвлений итераций.
iML, gM
018: Для увеличения пропускной способности выбор/декодер
команд отдавайте предпочтение инструкциям типа память-регистр
вместо регистр-регистр, если это позволит использовать
объединения микрокода {имеется ввиду, что обычно р-р быстрее, но
в некоторых случаях р-п тоже может не очень тормозить}.
Например, могут хорошо объединятся:
- Любые команды сохранения значений в памяти, даже непосредственное
(mov x, 4).
- Чтение-модификация между регистром и памятью:
(xor rax, qword ptr [rbp+32])
- Любые инструкции вида "чтение и переход":
(rts, jmp [])
- cmp и test с непосредственным операндом и памятью
i64 с RIP-относительной адресацией не объединяются в следующих случах:
- Когда дополнительное непосредственное требуется:
cmp [rip+400], 27
mov [rip+3000], 142
- Когда RIP нужен для целей управления потоком:
jmp [rip+500000]
iM, gML
019: Используйте объединения макрокода (асм-инструкций) там,
где оно может произойти (в основном, это пары: команды
test/cmp + некоторые условные переходы, в зависимости от архитектуры).
Предпочитайте test вместо cmp. Используйте беззнаковые переменные
и беззнаковые переходы (ja/jb/jz...), где возможно (знаковые объединяются не всеми
ядрами). Страйтесь логически проверять, что переменные не будут отрицательными
во время сравнения. Избегайте CMP и TEST с комбинацией MEM-IMM. Но всё
же не добавляйте новых инструкций, чтобы предотвратить это.
iM, gML
020: Софт может позволить объединение макрокода, когда он
может логически (до или во время компиляции) определить, что переменная
не отрицательна в время сравнения. Используйте test, чтобы позволить
объединение, когда сравниваете с нулём (test ecx,ecx) {это будет верно
даже если вы используете затем не только jz/je/jnz/jne}.
iMH, gMH
021: Предпочитайте использовать непосредственные аргументы из
8 или 32 бит, но не 16.
Префиксы размера адреса и данных (0x66, 0x67) вынуждают предекодер
инструкций использовать более сложный алгоритм, который тяжелее в
шесть раз. Если это имеет место среди солидных FPUшных инструкций
- не страшно, но когда команду с префиксом окружают скромные
целочисленные операции - она становится весьма тормозной на фоне
коллег. Это всё не относится к благородному префиксу REX (0x4x).
Если вам очень хочется иметь 16-разрядный аргумент - просто
загрузите в регистр 32-бита и затем обращайтесь к его младшей части.
Инструкции, которые всё таки работают с префиксом, да ещё и
пересекают некоторые границы, могут притормозить ещё больше (стр. 116).
iM, gML
022: Постарайтесь убеждаться, что инструкции, начинающиеся с 0xF7
(not, neg, div, idiv, mul, imul), не начинаются по смещению 14
в строке предвыборки и избегайте использовать эти инструкции
с 16-битными данными.
Тут есть какая-то заморочка с тем, что предекодер команд, не найдя
кусок команды (т.к. она сидит на последних позициях в строке),
думает, что она какая-то неправильная и на всякий случай активирует
тот же самый длинный алгоритм декодирования.
Это настолько существенно, что, как пример, рекомендуется
заменять "neg word ptr a" на что-то вроде "movsx eax, word ptr a \\
neg eax \\ mov word ptr a, AX" - если она попала в неудачное место.
iMH, gMH
023: Разбивайте длинные тела циклов на отдельные циклы, так, чтобы
эти тела помещались в LSD (Loop Stream Detector).
Размер LSD: на архитектуре Core - <= 18 инструкций, на Nehalem - <= 28
микроопераций.
Другие условия, необходимые для реакции LSD:
- Тело цикла <= 4 x 16 байт (4-fetch строки).
- Не более 4 правильно угаданных ветвлений, среди них не должно быть RET.
- Больше 64 итераций.
iMH, gM
024: Избегайте разворачивания циклов, если развёрнутый кусок кода
содержит префиксы 0x66/0x67 (или если может сработать правило 022) и
не помещается в LSD.
iM, gM:
025: Избегайте использования прямых ссылок на ESP между стековыми
операциями pop, push, call, ret.
P-4 не требует соблюдения особых правил, но Pentium-M имеет какие-то
заморочки с декодированием команд. Я не понял как соотносится
этот факт с правилом 025, но они шли подряд в соседних абзацах.
iML, gL
026: Используйте простые инструкции, короче 8 байт.
Это уже вроде как общее правило. И дальше тоже.
iM, gMH
027: Избегайте использования префиксов изменения
смещений и непосредственных значений.
Вроде про это было уже??
В крайнем случае, перемешивайте такие инструкции
между другими, которые тоже будут иметь проблемы
с декодированием, но по другим причинам.
Похоже, это опять касается Pentium-M.
iM, gH
028: Предпочитайте инструкции из одной микрооперации.
Предпочитайте инструкции с небольшими задержками.
Хороший тон - порядок операций: инструкция из
одной микрооперации, затем простая инструкция
из не более 4 микроопераций, в конце - инструкция,
требующая ROM микросеквенсора.
iM, gL
029: Избегайте префиксов, особенно множества не-0x0F-префиксованных
кодов операций.
Не очень понял :( Но 0x0F - это первый байт некоторой группы операций,
т.н. "2-byte escape".
"Avoid prefixes, especially multiple non-0F-prefixed opcodes."
iM, gL
030: Не используйте много сегментных регистров.
On the Pentium M processor, there is only one level of renaming of segment registers.
iML, gM
031: Избегайте комплексных инструкций (enter, leave, loop...), которые имеют
больше четырёх микроопераций и требуют много циклов декодирования.
Используйте последовательность из простых инструкций вместо этого.
Такие инструкции могут сберегать регистры, но они совершенно неповоротливы,
особенно на NetBurst. Теоретически, можно пытаться сгонять поток
инструкций в шаблон 4-1-1-1, но работающие на фрон-энде блоки
реорганизации потока (out-of-order), вероятно, добавят
отсебятины и вы не выиграете ничего серьёзного.
Если вам очень хочется использовать длинные инструкции, попробуйте хотя отделить
какие-то их элементы в отдельные, одно-микро-операционные инструкции.
Например, эти инструкции относятся к длинным: ADC/SBB, CMOVcc, read-modify-write
(но они, по крайней мере, не обращаются к микросеквенсору).
If a series of multiple-MKop instructions cannot be separated, try breaking the
series into a different equivalent instruction sequence. Например, серия
read-mod-write может быть заменена на read-mod + store. Эта стратегия
может ускорить работу даже если общая длина команд (в байтах), будет больше исходной.
iM, gH
032: Инструкции inc и dec должны быть заменены на add и sub. Это
связано с тем, что add и sub честно переписывают все флаги, в то
время как inc и dec этого не делают, создавая нехорошие условия
для out-of-order-движка.
XXX: без номера: Инструкциям CWD и CDQ обычно предшествует операция
целочисленного деления. CWD и CDQ "have denser encoding than" (меньшее число байт в инструкции ?)
сдвиги и move, но генерируют такое же число микроопераций. Если известно,
что AX/EAX позитивно, замените эти инструкции на что-то вроде xor dx,dx.
Объяснение не очень понятно :(
iML, gL
033: Если инструкция LEA использует масштаб != 1, последовательность
с ADD может быть вкуснее. Однако если плотность кода и полоса trace cache
- более важный для вас фактор - тогда, конечно, LEA.
Тут объяснение тоже хромает, вероятно, от невозможности дать
чёткую рекомендацию на все случаи жизни. Но, в общем, статус не критический.
iML, gL
034: Избегайте ROTATE по регистру и с непосредственным значением
(имеется ввиду, видимо, cx - количество сдвигов или их непосредственное
указание). Если можно, заменяйте их на ROT на 1 (старый формат инструкции,
без указания счётчика сдвигов).
На некоторых версиях процессоров:
Дополнительная задерка для левых сдвигов будет раза в три короче, чем для правых
(The latency of a sequence of adds will be shorter for left shifts of three or less)
Варианты с fix и var -сдвиги имеют одинаковое время исполнения.
Вращения более накладны, чем сдвиги (в двухаргументном варианте).
Для одноаргументного варианта (на 1) - вращения идентичны сдвигам.
iM, gML
035: Используйте разрушающие-зависимости-идиомы для установки регистра
в 0. Или разрушайте неверные цепочки сами. В случае, когда цепочки
зависимостей должны быть сохранены, используйте mov XX, 0. Это требует
больше памяти, но "avoids setting the condition codes."
Частичная модификация регистров может вызывать некоторые задержки.
Чтобы этого избежать, некоторые инструкции, в основном варианты
xor и sub (на разных ядрах - разные наборы, но обычные целочисленные идиомы
поддерживаются всеми ядрами), специально оптимизированы так, чтобы конструкции вроде
xor ax, ax (идиома) исполнялись быстро и не тормозили код зависимостями
от предыдущих операций (очевидно, по нормальному бы надо было дождаться
вычисления значений ax на предыдущем шаге, но идиома потому и идиома, что это частный
случай - когда результат не зависит от исходных данных).
В пояснениях как-то не сказано - зачем сохранять цепочки зависимостей.
Да и пример как-то не прокомментирован. Т.е. как он работает-то
понятно, но зачем там было заморачиваться с xor - не ясно -
в примере используется не часть регистра, а целый xmm.
Чуть позже по тексту есть такой намёк: нехорошо смешивать операции
разных типов (плавающая точка, целые числа) на mmx-регистрах
(ну и, видимо, но xmm тоже). И именно чтобы быстро объяснить
ЦП, что дальше пойдёт другой тип данных, как раз рекомендуется
pxor/xorps всего регистра самого с собой (видимо, перед
дальнейшим использованием не полного регистра).
iM, gMH
036: Разрушайте зависимости, связанные частями регистров между инструкциями, использующими
полные 32 бита. Для mov это может быть полный mov32 или movzx.
На Pentium-M movzx и movsx - весьма шустры. На P-4 movsx тормознее,
чем movzx, но это всё равно лучше, чем последующий геморрой с
частями регистров.
iM, gM
037: Попробуйте movzx или работайте сразу с 32-битными, если
очень нужны знаковые операции. Это лучше чем movsx.
iML, gL
038: Избегайте расположения инструкций, которые используют
32-битные непосредственные значения, которые не могут быть
закодированы как знакорасширяемые 16-битные, рядом друг с другом.
Старайтесь распихивать инструкции так, чтобы микрооперации
с 32-imm не соседствовали с другими imm-аргументными инструкциями.
The trace cache can be packed more tightly when instructions with operands that can
only be represented as 32 bits are not adjacent.
iML, gM
039: Используйте test вместо and когда результат не нужен. Используйте
test сам с собой, если нужно cmp x,0. Избегайте сравнения константы
с памятью. Предпочтительнее загрузить память в регистр и сравнить регистр
с константой.
Че-то то это обязательно, то иногда желательно....
iML, gM
040: Избегайте ненужных сравнений с нулём, коль предыдущие операции
уже расставили флаги. Если нужно - хотя бы test, а не cmp. Будьте
внимательны, чтобы такая переделка не привела к проблеммам переполнения.
Последнее предложение - как-то странно выглядит.
XXX: без номера: NOPы бывают разные. Но есть среди них одна особенная:
XCHG EAX,EAX. Она имеет специальную аппаратную поддержку, которая приводит
к тому, что эта операция не имеет зависимостей от предыдущего значения
EAX и, следовательно, будет выполнятся всегда за самое минимальное время.
XXX: без номера: работая с SIMD-регистрами используйте какой нибудь однообразный
тип данных подряд. Т.е. если вы загрузили в регистр число, используя целочисленную
mov, то постарайтесь и другие операции над этим регистром выбирать именно целочисленные.
Или плавающая точка - от первой до последней mov. Если вам вообще безразличен тип
(например, для побитных операций) - используйте PS вместо PD. Просто коды
команд так будут покороче. Если ваш код особенно кривой (т.е. часто использует
то одни то другие команды) он может исполнятся на Intel Core даже медленнее,
чем на предыдущих архитектурах (которые допускали микширование инструкций).
iH, gMH
041: Для мелких циклов placing loop invariants in memory is better than
spilling loop-carried dependencies.
A possibly counter-intuitive result is that in such a situation it is better to put loop
invariants in memory than in registers, since loop invariants never have a load
blocked by store data that is not ready.
Честно: не понял.
XXX: без номера: Стр 127. ROB Read Port Stalls. Не понял, начиная отсюда:
Чтобы избежать неудачных комбинаций команд,
которые не могут долго протиснутся через исполнительное ядро, ожидая
своих зависимостей:
- Keep common register usage clustered together. Multiple references to the same
written-back register can be "folded" inside the out of order execution core.
- Keep dependency chains intact. This practice ensures that the registers will not
have been written back when the new micro-ops are written to the RS.
Но и это можно использовать не всегда и не везде.
XXX: без номера: Тормоз частичного использования регистров есть ситуация,
когда инструкция ссылается на регистр, часть которого была ранее модифицирована
другими инструкциями. Это было просто отвратительно на ядрах P6 и некоторых
версиях Pentium-M, но на других архитектурах (Solo, Duo, NetBurst) не так страшно.
Заметьте себе, что на i64 модификация нижних 32-х бит приводит к очистке верхних
32, поэтому никаких проблем не вызывает (кроме потери верхней части регистра).
Есть также ложные зависимости: add ah, bh ; add al, 3 - вторая инструкция будет
уверена, что зависит от первой. Хрен знает почему :)
Корявый код:
mov al, byte ptr a[2]
shl eax,16
mov ax, word ptr a
movd mm0, eax
ret
Некорявый код:
movzx eax, byte ptr a[2]
shl eax, 16
movzx ecx, word ptr a
or eax,ecx
movd mm0, eax
ret
С регистром флагов, кстати, ровно та же фигня, см мысль # 032.
И этим же объясняется мысль # 034. Смешной пример:
Корявый код:
xor eax, eax
mov ecx, a
sar ecx, 2
setz al
;No partial register stall,
;but flag stall as sar may
;change the flags
Некорявый код:
xor eax, eax
mov ecx, a
sar ecx, 2
test ecx, ecx
setz al
;No partial reg or flag stall,
; test always updates
; all the flags
iM, gML
042: Избегайте введения зависимостей с частями FPU-регистров,
например от команды movsd xmm1, xmm2. Используйте movapd xmm1, xmm2
вместо неё.
Вместо инструкций movsd (которая копирует 64 бита) используйте movapd.
Она хотя и гоняет 128 бит, тем не менее убивает двух кролей: и регистр назначения
станет полностью определённым и к тому же она использует другой
порт исполнения, который чаще свободен (несмотря на то, что микроопераций
в этой команде больше).
Вообще, заморочки эффективного использования SIMD (даже в плане
элементарной загрузки-выгрузки данных) - вообще отдельная песня.
iML, gL
043: Вместо использования movupd для невыровненной 128битной загрузки
используйте movsd + movsd + UNPCKLPD. Если лишних регистров нет,
используйте movsd + movhpd.
iM, gML
044: Вместо использования movupd для сохранения используйте movsd +
UNPCKHPD + movsd.
iH, mG
502: Используйте самые мелкие типы данных, чтобы компилятор эффективнее
паковал их в SIMD-аргументы.
iM, gML
503: Arrange the nesting of loops so that the innermost
nesting level is free of inter-iteration dependencies.
Упорядочивайте вложенные циклы так, чтобы внутренний уровень
был свободен от межитерационных зависимостей (?).
Особенно избегайте бреда, подобного следующему:
чтение данных лексически раньше, чем их сохранение (даже
если на самом деле, из-за цикличности, порядок операций будет вроде
бы логичным).
iM, gML
504: Избегайте ветвлений внутри циклов и смотрите на возможность
использования SSE инструкций вместо них.
Странно: вроде это для ассемблерщиков надо, а не для C-шных
программеров.
iM, gML
505: Старайтесь использовать простые переменные (или выражения?) цикла.
Keep induction (loop) variable expressions simple.
iH, gH
045: Выравнивайте данные по естественным границам адреса. Если обращение
к данным выполняется векторными (SIMD) командами - выбирайте границу
кратную 16 байт.
Выравнивания:
8 бит - как хотите
16 бит - должны содержатся внутри 32-битного выравнивания (0, 1, 2, но не 3)
32 бита- кратно 4 байтам
64 бита- кратно 8 байтам
80 бит - кратно 16 байтам
128 бит - кратно 16 байтам
Если структура приличного размера - начинать её лучше с кратного 64 байтам.
Выравнивание данных(?) наиболее важно для NetBurst. Выравнивание кода - не очень.
Выравнивание кода важно для Pentium M, Intel Core Duo and Intel Core 2
Duo processors.
iH, gM
046: Передавайте данные в регистрах везде, где возможно (вместо стека).
Хотя конструкции sta / lda оптимизированы аппаратно и проц попытается
(если ему что нибудь не помешает) перехватить их до передачи данных
в кеш, это всё равно вызывает задержки, особенно данные FPU регистров.
Попробуйте уговорить ваш компилятор делать это, он может уметь такое,
если полностью контролирует компиляцию всей программы.
Видимо, имеется ввиду, что если компилятор собирает всю программу
полностью, то в нём можно будет рулить форматом передачи параметров.
Последовательное сохранение цифры в памяти с последующем оттуда
извлечением может быть опознано процессором и слегка оптимизировано,
но только если соблюдаются некоторые ограничения (разные для
разных архитектур, но связанные с тем, что желательно писать и
читать один и тот же тип/размер данных с одним и тем же смещением).
Нарушение этих ограничений особенно неприятно процессорам
с архитектурой NetBurst.
iH, gM
047: Если вы расчитываете на load-from-store-оптимизацию - по крайней
мере делайте чтение из того же адреса (и, следовательно, с того же
выравнивания), что и запись.
Это не единственный возможный вариант попасть в load-from-store,
но самый простой, понятный и универсальный, особенно в сочетании
со следующим правилом.
iH, gM
048: Данные загрузки, которые пересылаются из последней записи,
должны полностью содержаться в записи.
Ну логично - иначе откуда их взять. Речь о том, что:
mov dword ptr adr, EAX
mov BL, byte ptr adr
- это правильно, а наоборот: mov byte ptr \\ mov dword ptr
- неправильно. Т.е. проц будет вынужден лезть за данными
в кеш или память и оптимизация не состоится.
iH, gML
049: Если нужно вытащить невыровненный кусок только что сохраненных данных
(имеется ввиду выравнивание одного адреса относительно другого),
читайте его мелкими выровненными дозами, а потом ORте, сдвигайте, ANDите
по вкусу. Это лучше, чем поиметь проблемы со сбоями store-forward-оптимизации.
Речь о том, что если вы попадаете в правильный режим store-forward
- всё тип-топ. Если не попадаете на только что сохраненные данные
вообще - кеш вам в помощь. Но если вы одной частью в одной команде
попадаете на неизвестные ЦП данные, а другой - на только что ушедшие
в запись - то он будет их собирать в кучу тихо матерясь. За вас счёт.
Т.е. так неправильно:
mov dword ptr 2, eax
mov ebx, dword ptr 0
Интел рекомендует сделать что-то вроде (если я правильно понял):
mov dword ptr 2, eax
movzx ebx, word ptr 0 ; эта полезет в кеш/память не дожидаясь завершения предыдущей команды
movzx ecx, word ptr 2 ; это наверняка попадает под s&f-оптимизацию, причём может быть одновременно с предыдущей
shl ecx, 16 ; а эти вообще не в счёт
or ebx, ecx
Только не забывайте глядеть в разрешенные комбинации s&f - они не всегда допускают такое простое
решение.
Тоже пример:
mov [EBP + 0], `a'
mov [EBP + 1], `b'
mov [EBP + 2], `c'
mov [EBP + 3], `d'
mov EAX, [EBP]
В нём лучше сначала объединить всё в один большой регистр, а потом сохранять.
iMH, gML
050: Избегайте множества мелких чтений из области, в которую только что
сделали одно большое сохранение. Предпочтительнее сделать одно большое чтение
и потом раскидывать отдельные части данных mov'ами между регистрами.
Это не будет выглядеть смешным, если вспомнить про наличие в последних
процах почти отдельной оперативки, в виде здоровенных SIMD регистров,
куда слона заначить можно (16 x 128 бит, в ia64, если не ошибаюсь).
XXX: без номера: Если вам очень хочется нарушить эти правила, постарайтесь,
по крайней мере, разделить неправильные запись-чтение группой других
команд. В этом случае запись хотя бы успеет полноценно завершится, пока проц будет
ковырять группу команд, предшествующих чтению.
Описываемые здесь процессоры имеют глубоко эшелонированную оборону
исполнительного ядра от всех внешних невзгод. Чтобы максимально обеспечить
его работой, очень многое выполняется до непосредственного исполнения команд:
предвыборки данных, попытки опознать характерные последовательности
команд, реорганизация порядка команд, разбивка
на микрокод, реорганизация микрокода и прочяя ерунда.
Сразу после исполнения микрокоманд результаты скармливаются очередному
конвееру, который пытается восстановить порядок выдачи результатов
(если считает это нужным). Важно, что этот блок работает тоже асинхронно
от исполнительного ядра.
Важно так же то, что загрузка данных, даже соответствующая правилам
s&f, будет зависеть от генерации этих данных и не может быть выполнена
до завершения всех операций, предшествующих (по смыслу) сохранению.
Это отличается от обычных mov между регистрами, когда пересылаться
может некая, ещё не вычисленная, абстракция.
iH, gMH
051: Там, где это возможно без лишних сложностей, попробуйте всё таки
использовать регистры для передачи параметров и прочего, чтобы
избежать ненужных сбоев s&f-оптимизации. Особенно, если результат,
который вы хотите сохранить, получается в результате исполнения
долгой команды: mul, div. Избегайте коротких дистанций между
сохранением-чтением. Избегайте сохранения-чтения результатов,
которые были получены длинными/сложными цепочками вычислений.
И, если жизнь дорога вам, бегите от использования таких
конструкций в циклах.
iM, gMH
052: Вычисляйте адреса сохранений так рано, как возможно, для
предотвращения stores block loads.
iH, gM
506: Ну тоже старайтесь выравнивать все структуры, чтобы
всё было в согласии с заветами. Если компилятор ваш туп
от рождения - помогите ему:
struct unpacked { /* Fits in 20 bytes due to padding */
int a;
char b;
int c;
char d;
int e;
};
struct packed { /* Fits in 16 bytes */
int a;
int c;
int e;
char b;
char d;
}
XXX: без номера: Помните, что строка кеша данных - 64 байта, да
и объём всего кеша - тоже конечный.
Если вы придумали дурацкий массив структур, причем перебираете
весь массив, но извлекаете только какое-то одно-два небольших поля структуры
- так не лучше ли именно для этих полей сделать уже отдельный массив,
компактно размещённый в памяти, и не забивать кеш остальными,
нафиг не нужными, элементами ?
iH, gM
053: Попробуйте так построить структуры данных, чтобы доступ
к ним был последовательным.
Ну это тоже чтобы не гонять постоянно данные между кешем
и памятью. Иначе зачем вы вообще кеш покупали ? :)
Тем более, если даже если шаг доступа у вас большой (больше
кеш-строки, но меньше 2-4 кб, в зависимости от модели ЦП),
но одинаковый - предзагрузчик данных может быть разгадает
вашу идею и будет делать предвыборку. Кстати, он
попробует это делать даже если вы обращаетесь
к нескольким массивам. До 8 штук.
iM, gL
507: Опасайтесь ложных обобщений внутри строки кеша (64 байта)
и в секторе (128 байт) на NetBurst.
Без комментарие, увы :(
Но, это, похоже, продолжение предыдущих правил, чьи достоинства
здесь оборачиваются недостатком.
iH, gM
054: Если 64-битные данные передаются как параметры или сохраняются
на стеке - следите за тем, чтобы указатель стека был выровнен по
8-байтной границе.
Странная рекомендация (странно, что только про 64-битные данные),
но, возможно, речь о том, что равнение по 4 байта и так будет выполнятся,
если изначально выставить правильный esp (а операционка и так это сделает).
iH, gM
055: Избегайте сохранения данных, за которым следует загрузка, если
их адреса отличаются на величину, кратную 4 Кб. Кроме того, подбирайте
расположение данных или порядок вычислений так, чтобы избегать появления
кеш-строк с разницами адресов, кратными 64 Кб. Избегайте также
возникновения более 4 строк с разницами адресов в 2 Кб в кеше L1
и больше 8 строк с разницами в 4 Кб.
Без комментариев. Тут что-то в политиках кэш-контроллер.
iH, gML
508: Старайтесь использовать специальную библиотеку, которая выделяет
память с учётом правила # 055.
iM, gM
509: Когда расставляете переменные в памяти с учётом антиалиасинга
(из предыдущих правил) наибольший профит получается от избегания
алиасинга кеша L2, смещением в 128 байт или больше.
"When padding variable declarations to avoid aliasing, the greatest
benefit comes from avoiding aliasing on second-level cache lines,
suggesting an offset of 128 bytes or more."
iM, gL
056: Если какие -то данные должны быть размещены в том же сегменте,
что и код - хотя бы не располагайте их сразу за неявным jmp [].
Лучше положите туда ветку более вероятного продолжения кода,
а данные вставьте куда нибудь после явного jmp.
Самомодифицирующийся код допустим и будет исполнятся в соответствии
с заветами предков, но хуже него только тёплое пиво. Так как
скорость работы при этом упадёт ниже плинтуса.
Помните также, что процессору трудно различить что именно вы
модифицируете - код или данные, если вы зафигарили данные
между командами. Поэтому такой подход, по производительности,
немного лучше самомодифицирующегося кода.
iH, gL
057: Всегда кладите код и данные в разные сегменты. Избегайте
самомодифицирующегося кода - до него опускаются только разработчики
защит от копирования. Если хотите модифицировать - сделайте это,
по крайней мере, за раз и следите, чтобы модификатор и модифицируемый
были на разных 4 Кб-страницах или на отдельно выровненных 1 Кб-субстраницах.
Учтите также, что если в системе есть несколько процессоров, следует
избегать ситуаций, когда процессор A может подумать, что
процессор B начал модифицировать код, который исполняется процессором A.
Процессор B, в этом случае, будет сбрасывать кеши - а это тоже,
понятное дело, работы не ускорит.
Если руки чешутся сделать что нибудь этакое - по крайней мере модицифицируйте
код где нибудь вдали от модификатора, а потом передавайте туда управление
по неявному jmp []. Проц хотя бы не начнёт набирать оттуда кеш
раньше времени.
iH, gL
058: Если внутренний цикл записывает больше чем четыре массива,
в четыре отдельных строки кеша - разделите такой цикл на несколько частей,
чтобы запись происходила не более чем в 4 отдельных строки.
Это связано с возможностью распараллеливать отдельные потоки данных,
после того как они покинули исполнительное ядро и собираются расположится
в кеше записи.
iH, gH
510: "Optimization techniques such as blocking, loop interchange, loop skewing,
and packing are best done by the compiler. Optimize data structures either
to fit in one-half of the first-level cache or in the second-level cache;
turn on loop optimizations in the compiler to enhance locality for nested loops."
Оптимизация для первой половины кеша первого уровня принесёт улучшения
в терминах стоимости доступа к данным на цикл ("in terms of cycle-cost
per data access").
Если этого объёма кеша мало для практических нужд, оптимизируйте код
для кеша второго уровня. Оптимизация для чего-то посередине, вероятно,
вообще не принесёт пользы.
iM, gML
511: Если у вас в коде постоянно чередуется запись и чтение - постарайтесь
сделать так, чтобы группа команд выполняла запись и другая группа - чтение.
Это лучше для внешней шины.
iH, gH
512: "To achieve effective amortization of bus latency, software
should favor data access patterns that result in higher concentrations
of cache miss patterns, with cache miss strides that are
significantly smaller than half the hardware prefetch trigger threshold."
iM, gM
513: Позвольте компилятору использовать SSE, SSE2, SSE3 соответствующими
ключами.
Такое утверждение требует слишком пространного комментария :)
iH, gML
514: Убедитесь, что ваше приложение не попадает в области денормализованных
значений, потери точности.
Речь об оптимизации работы с FPU и о его исключениях.
iM, gML
515: Не используйте двойную точность без необходимости, обходитесь
одинарной. На некоторых операциях это повысит скорость работы. Однако
будьте осторожны и старайтесь не использовать чередования более двух
разных значений слова управления FPU - это понизит скорость.
iH, gML
516: Используйте быстрые float-to-int процедуры, FISTTP или SSE2-инструкции.
Если создаёте такие процедуры, используйте FISTTP, если SSE3 доступны,
либо CVTTSS2SI и CVTTSD2SI - если только SSE2.
Эти инструкции могут конвертировать плавающее в разные варианты целых
без изменения слова состояния FPU, что мощно экономит такты.
iM, gML
517: Удаляйте зависимости данных, где возможно, чтобы out-of-order
имел поле деятельности ("to extract more ILP from the code"). Например,
суммируя элементы массива используйте частичные суммы вместо аккумулятора:
z = a + b + c + d неверно вычислять как x = a + b; x = x + c; z = x + d.
Правильно так: x = a + b; y = c + d; z = x + y.
В общем, это тоже про FPU
iM, gML
518: Обычно, матбиблиотеки используют трансцидентальные инструкции (типа FSIN),
когда вычисляют элементарные функции. Если нет большой нужды в таких наворотох
с 80-битной точностью, софт может использовать табличные приблизительные поиски
с привлечением интерполяционных алгоритмов, в которые можно пристроить инструкции
группы SSE/SSE2.
iH, gML
519: Денормализованные FPU-константы должны быть удалены из программы.
Если вам не важно соответствие стандартам IEEE в обработке плавающей
точки - предпочитайте команды группы SSEx. На архитектуре NetBurst
они сами работают шустрее и исключительные ситуации тоже
проходят легче.
iH, gM
059: Минимизуйте изменения бит 8-12 слова управления FPU.
Изменения более чем на два значения (каждое из которых
представляет собой комбинацию бит точности, округления, бесконечности
и других бит) приводит к задержкам на глубину конвейера.
Какого из них тьмы ?
iH, gL
060: Минимизуйте число изменений режима округления. Не
используйте смену режимов округления для реализации
"floor and ceiling functions" если речь идёт о более чем
двух комбинациях бит.... (далее по тексту правила # 059).
iH, gL
061: Минимизуйте число изменений режима точности.
iM, gM
062: Используйте FXCH только если необходимо увеличить эффективное
пространство имён (регистров не хватает, то есть).
Чем-то она мешает out-of-order. Ну или не помогает, во всяком
случае.
iM, gM
063: Используйте SSE2 или SSE вместо FPU. Они шустрее и к тому
же быстрее. Потому что быстрее и потому что не заморачиваются
на управление стеком FPU. И ещё - может обрабатывать несколько
чисел в параллель.
Но эффективность SSEx - по сравнению с FPU - сильно зависит от
модельки. Pentium-M, например - не очень чтобы уж.
iM, gL
064: Попробуйте использовать 32-битные операнды вместо 16-битных
для FILD. Однако не делайте этого, если опасаетесь проблем
s&f-оптимизации.
Но комментарий странный:
"For processors based on Intel NetBurst microarchitecture, splitting floating-point
operations (FIADD, FISUB, FIMUL, and FIDIV) that take 16-bit integer operands into
two instructions (FILD and a floating-point operation) is more efficient. However, for
floating-point operations with 32-bit integer operands, using FIADD, FISUB, FIMUL,
and FIDIV is equally efficient compared with using separate instructions."
Впрочем, может быть я просто систему команд плохо помню...
XXX: без номера: Для более эффективного использования полосы
PCIe придерживайтесь следующего:
- Выравнивайте начальный адрес большого числа запросов по границе 64 байт.
- Используйте запросы, размер которых кратен 64 байтам.
- Избегайте или предотвращайте последовательные или случайные
частичные (не 64 байта?) запросы на запись.
- Избегайте или предотвращайте конфликты чтения, включая
последовательные неполные чтения.
Не понял - кому рекомендации ? То ли разработчикам новых процессоров ;)
а то ли - драйверописателям (в смысле, чтобы они не запрашивали у подопечных
устройств неправильные группы данных).
Ну вот и подошел к концу увлекательный манускрипт: "Intel 64 and IA-32 Architectures.
Optimization Reference Manual". Третья глава под названием "GENERAL OPTIMIZATION GUIDELINES".
Следующие главы включают в себя рассказы об оптимизации SIMD-кода (это включает в себя
всевозможные MMX/SSEx/AExx), но их я читал уже по диагонали.
Дальше идёт "оптимизация для MultiCore & HyperThreading", "оптимизация для 64-mode",
"использование SSE для обработки текстовых строк", "оптимизация для уменьшения
энергопотребления" и "оптимизация для Atom". И в конце - приложения на темы
о том - как измерять эффективность работы программ. Там тоже много интересного.
Там, кстати, есть одна забавная штука: таблицы эффективности отдельных команд.
Т.е. сколько они требуют условных тактов и как могут параллелиться.
В общем - правильная бумага. Пусть и электронная.
================================================================================
А свою прогу я почти закончил. И по сравнению с предыдущей версией,
которая тоже писалась на асме (году в 1995-м), скорость выросла почти
в пять раз. Все правила, я, конечно, не соблюдал - их слишком много,
некоторые требуют оценки уже скомпилированного кода, некоторые противоречат
другим и не очень ясно - какой выбор предпочесть. Но всё же следующий
небольшой список прост и, полагаю, важен:
- Выравнивания кода и данных.
- Правильное взаимное расположение кода, следующего после условных ветвлений.
- Избегать не только последовательных call/ret, но и jmp, располагая процедуры подряд.
- Если всё равно в конце нужны 32 бита (например, для индексной адресации), то
и до этого предпочтительно работать с полным регистром.
- Inc/dec заменить на add/sub.
- Если сохраняем в память 32 бита, то и читать потом 32 (с этого адреса). Если 8 - то и 8.
- 16 бит в регистрах - только если очень удобно. В остальных случаях - или 8 или 32.
- Loop/enter/leave - вообще пролетают.
- Push/pop - только в самых неважных участках кода. Да и доступ к памяти в циклах ограничить.
Регистры рулят.
- Неявные call и jmp - только праздникам: если без них совсем плохо.
PS Не стоит присылать мне письма со сложными вопросами по программированию
8x86.. - я вряд ли когда нибудь научусь виртуозно управлятся с этим монстриком :)
В отличие от простых контроллеров, вроде 8051, ATmega... - мир современных
ia-32 и intel64 бесконечен для изучения. Чем и интересен, собственно :))
Владимир