x86 Optimization Manuals

Всем привет.
Многие я думаю читали или читают Intel Code Optimization Manual или AMD Code Optimization Manual.
И думаю переодически возникают вопросы (по крайней мере у меня возникают ).
Предлагаю в данной теме задавать вопросы, и соответственно отвечать если знаете ответ.

Пожалуй я начну

1. В мануалах по оптимизации можно прочитать совет в духе "unroll small loops"
Вопрос кто такие "small loops"
Это циклы с маленьким телом, или с маленьким числом повторений?
Какие из них имеет смысл разворачивать, а какие нет?
К примеру есть цикл на 4 итерации с телом в 150 строк ассеблерного кода.
Это small loop или нет?

2. Может кто-нибудь объяснить на пальцах что такое throughput, overhead, latency и тому подобные термины относительно команд процессора?
На русский я перевести и сам могу - только помогает это слабо.
Насколько я понял, overhead - время предварительной инициализации, latency - время выполнения в тактах.
Throughput - вроди пропускная способность, но что это такое относительно команды как-то слабо представляю.

 

cppasm

Оба.

Если выигрыш от раскрутки есть будет small.

По Интел. там написано в Мануэле по этому поводу.
throughput задержка до тех пор пока в ALU не сможет выполнять следующую команду.
latency задержка до тех пор пока не будет результат команды.
Если команды не зависимые. То их можно одновременно исполнять на одном ALU. Задержка между посылками и будет throughput. Если команды зависят от результата, то нужно дождаться пока будет выполнена команда это будет latency.

У AMD там свои определения.

 

Допустим цикл

Код (Text):

1. a:array of byte;
2.  
3. For i:=0 to 1000000 do
4.  a[i]:=a[i]+5;

Его можно раскрутить вот таким вот образом.

Код (Text):

1.  i:=0;
2. while i<1000000 /4 do
3.  begin
4.  a[i+1]:=a[i+1]+5;
5.  a[i+2]:=a[i+2]+5;
6.  a[i+3]:=a[i+3]+5;
7.  a[i+4]:=a[i+4]+5;
8.  i:=i+4;
9.  end;

Код (Text):

1. Или цикл такой вот.
2. for i:=0 to 5 do
3.  s[i]:=Copy(s[i],1,100);

Его можно раскрутить до конца

Код (Text):

1.  s[0]:=Copy(s[0],1,100);
2.  s[1]:=Copy(s[1],1,100);
3.  s[2]:=Copy(s[2],1,100);
4.  s[3]:=Copy(s[3],1,100);
5.  s[4]:=Copy(s[4],1,100);
6.  s[5]:=Copy(s[5],1,100);

 

Спасибо, вроди разобрался.
С разворачиванием циклов как раз всё понятно.
Не понятно было какие из них стоит разворачивать.
Просто у меня циклы с маленьким числом итераций - до 4, но тело по 400-512 байт.
Вот и думал стоит разворачивать или нет.

 

cppasm

скорее с маленьким телом.

попробуйте посчитать время выполнения

 

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

 

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

Если учесть что у Athlon о котором я читаю кэш кода составляет 64Кб - то практически все циклы будут small.

 

cppasm
смысл разворачивая циклов в том, что бежать по прямой ровной дорожке удобнее чем петлять зигзагами, потому и стадионы овальными делают с прямыми участками а не круглые ) и rdtsс на разворот отзывается очень даже хорошо и стабильно, особенно если разворачиваешь тело в 5-10 команд, но после нескольких обычно 3-5 разворотов дальнейший смысл разворачивания утрачивается т.е. прирост скорости прекращается в тонкости теории предпочитаю не слишком углубляться, а на практике так

 

У Агнера Фога:
На Core 2 если цикл меньше 64 байт (вернее, меньше четырёх 16-байтовых линеек кэша), он будет предекодирован только один раз - на первой итерации
На Core i7 если цикл меньше 28 микроопераций, то он будет декодирован только один раз.

А т.к. предекодеры и декодеры часто оказываются "узким местом", то НЕ разворачивая такие циклы, можно увеличить производительность

 

Зачем разворачивать циклы понятно.
Как написано в мануале AMD - "переходы которых нет не могут быть неверно предсказаны".
А неверно предсказанный переход - минимум 10 тактов штрафа.
Вопрос в том какие разворачивать.
В том что для циклов с маленьким телом есть преимущество я не сомневаюсь.
Интересует как раз обратная ситуация.
Цикл реально здоровый, но на 4 итерации.
И вот к примеру мои тесты с интеловским компилятором.
Для одного и того же алгоритма (код идентичный) есть две реализации - fixed point (т.е. целочисленные вычисления) и floating point (fpu).
Цикл на 8 итераций.
Так вот Intel C++ 10.0.14 для целочисленных вычислений развернул все 8 итераций в последовательность, а для fpu кода не развернул совсем.
И по каким соображениям я не очень понимаю.
Причём соображения явно какие-то есть
Если я ему говорю /Qunroll-aggressive - он разворачивает и для fpu, но по замерам скорости это совсем не прибавляет.
Нафига мне всё это надо?
Надо тот же алгоритм переписать под 3DNow! - вот и изучаю мануалы.

 

cppasm

Если бы было все понятно, то наверное и воросов бы не было
"Тонкие" циклы разворачивают для того, чтобы уменьшить относительный вклад накладных расходов на инремент счетчиков\указателей и на условный переход. Если эти расходы составляют 1-2 такта на цикл, то заметный выигрыш от разворота можно получить только в случае, когда само полезное тело выполняется также за единицы тактов.
Циклы с малым фиксированным числом повторений разворачивают для того, чтобы избежать штрафа за непредсказанный переход при выходе из цикла. Здесь также рулит критерий целесообразности: поскольку штраф на разных процах составляет от 10 до 30 тактов, то соотв-но имеет смысл разворачивать циклы, общее время выполнения которых составляет не более сотни тактов.
Т.е. в тонких циклах учитыается время одной итерации, а в коротких циклах общее время всех итераций, т.к. штраф за непредсказанный переход - только один на выходе из цикла. Вот и прикинь, сколько тактов у тебя крутится 4 итерации по по "400-512 байт" и не будет ли десяток тактов экономии на переходе "каплей в море"

PS: На Pentium-M и Core развороты коротких циклов при повторных проходах ничего не дают, т.к. в них рулит предсказание числа итераций цикла

 

leo

А разве на самом первом переходе в цикле не будет штрафа?

 

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

В моём случае и капли важны.
С одной стороны размер исполняемого модуля плюс/минус 1КБ это ерунда, а с другой платить таким размером за 10тактов прироста тоже как-то не ахти...
Вот замеры на 100000 итерациях:
обычный цикл: 45792505 тактов
развёрнутый: 44727215 тактов

разница 10.7 тактов

 

cppasm
В принципе я переспросил, потому что leo сам как-то говорил, что штраф будет: http://www.wasm.ru/forum/viewtopic.php?pid=134671#p134671 .

 

Ну я ж тоже написал "вроди"
Я всё-таки решил разворачивать.
У меня там просто ещё в цикле для чётных элементов массива надо коррекцию делать.
Т.е. получается дополнительное условие, которое выполняется через раз.
А поскольку для предсказания используется история - будет слишком много промахов.
А так сделал копи/паст кода 4 раза (4 итерации цикла), и в два из этих блоков добавил нужную коррекцию.

 

l_inc
Да, при "самом первом" проходе цикла тоже будет штраф на статическое предсказание. Но, во-первых, первый проход это вообще отдельная "пестня", т.к. при этом могут быть еще большие задержки, связанные с подгрузкой кода из ОЗУ в кэш (на всех процах), плюс доп.тормоза на атлонах и P4 на преддекодирование команд. Например, в P4 при первом проходе декодируется одна команда за такт, а при повторных проходах мопы извлекаются из T-кэша по 3 шт. за такт, поэтому при первом проходе разворот толстых циклов может не только не выиграть, а даже существенно проиграть из-за тормозов преддекодера.
Во-вторых, при желании можно учесть и штраф на статику просто взяв суммарный штраф ~1.5 длины конвеера

cppasm

Угу, и как ты собираешься потратить сэкономленные капли ? Надеешься "накапать стаканчик" ?

 

leo

В смысле одна длина на неверно предсказанный последний и половина на первый за счёт отсутствия информации о переходе в принципе. Ясно. Вообще всегда можно взять суммарный штраф за всё и учесть все потери сразу. Важно знать, из чего всё таки составлять этот штраф.
А можно поинтересоваться, будет ли такой половинный штраф при первом проходе по прыжку вида EB 00? Ну или любому другому: главное, чтобы адрес назначения был адресом следующей инструкции. По идее ведь вся половина конвейера с командами после прыжка - это всё верно выбранные команды. Или это не важно? Ну и тот же самый вопрос для call и ret.

 

l_inc

Не знаю. По идее это из разряда "implementation specific", но т.к. случай, прямо скажем - экзотический, то его могли просто не предусмотреть и сбрасывать конвеер независимо от того происходит реальный прыжок или нет.

 

Да
У меня за счёт неправильно предсказанных переходов получается потеря 50-60 тактов на процедуру.
А процедура это критическая.
Т.к. приложение мультимедиа, и эта процедура вызывается тысячи раз для обработки массивов данных.
В итоге 50-60 тактов вылазят в секунды при обработке файла.
Хотя можно конечно и подождать
Но зачем я его тогда вообще под 3DNow! переписываю, и fixed point работает с терпимой скоростью.
Хочется быстрее...

Есть такое дело.
Я когда замеры производительности делал (100000 циклов с замером по rdtsc) - это чётко видно.
Первый вызов функции выполняется дольше - причём ощутимо.
Хотя как для варианта с развёрнутыми циклами, так и с обычными разница примерно одинакова.

PS: Вопрос может и не в тему.
Тестирую свои реализации этого же алгоритма.
Проверял на Pentium 4 и AMD Duron - тактовые частоты разные, результаты сравнивал в тактах.
Код написан на Си и скомпилирован с оптимизацией под P4 без SIMD.
Так вот fixed point вариант (целочисленные вычисления) на обоих процессорах выполняется примерно одинаковое число тактов.
А вот вариант с fpu (float) на P4 проиграл практически в два раза тому же коду запущенному на AMD.
На AMD от целочисленной реализации отставание всего на ~15-20%
Собственно вопрос - это у AMD настолько fpu хороший, или есть какие-то другие причины?

 

leo
Понятно. Спасибо.
Ну для прыжка, видимо, действительно экзотический, но вот call на следующую инструкцию используется для получения дельта-смещения. Хотя, наверное, тоже не так часто, чтобы специально добавлять поддержку такого случая.