„Не дают покоя вопросы "квазиоптимизации", предлагаемые TheSwin“

1.Мой ник пишется The Svin. Протри очки.
2.Для вычисления адреса существует отдельный сумматор ещё с 486 DX. Уже с тех пор это не проблема, и не вопрос для знакомых с тех. документацией.
3.Во вторых я не предлогал ни каких вопросов о "квазиоптимизации". Я предложил уточнить модели камней и формат данных в частности выравнивание. И я не понимаю здесь использование слов "квазиоптимизация", реликтовые процы и т.п. тебе не приходит в голову, что используя такое же количество букв вместо мутных слов можно дать точную информацию? Обычно когда не понимают, предпологают худшее. Дай себе труд выражатся яснее, ясность в нашем деле на вес золота.
4. Вред от отсутсвия выравнивания на PIV подтверждается эмпирикой. Тоже что тебе кажется однозначным ответом не звучит однозначно на самом деле без рассмотрения техники доступа к кешу.
„ Результаты тестов на разных процах противоречивы (меньше\больше\равно) возможно из-за разной реализации индексирования, а может и предсказания, т.к в начале цикла нужно вычислить адрес до загрузки“

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

Тупишь ты дружок, тебе говорят - даёт ускорение на PIII.
Ты упорно "сомнительно", "реликтовые процы" и прочее.
Мутно это всё звучит.
тебе кто сказал то, что в данный момент актуальна оптимизация только для камней которые у тебя на работе стоят?

Определись по крайней мере о каких камнях ты говоришь и добавляй "для PIV верно то-то...".
Поверь, люди это оценят, и решат что ты пишешь не для себя а для них.
Повторяю для тех кто в танке.
Пока не сказали для каких процов оптимизация, нет никаких прав утверждать что будет лучше.
Нет тут просто "лучше", есть "лучше для".
Это двухместный предикат. Функция Лучший(код, проц).

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

Математически CF можно высчитать за менее чем 8 тактов.
Тогда если верить leo про 8и тактовость ADC на можно не использовать простые add для P4 и заменить inc на add.
Логика приблизительно такая.
Мы вычисляем CF в знаковый бит какого-то регистра потом сдвигаем его на 31 вправо.
Пусть Cf - значение предыдущего CF,
(т.е. не реальный флаг а значение в каком то регистре хранящем Cf например, начально в нём 0)
тогда
((a>>1)+(b>>1))+(((a&1)+(b&1)+Cf)>>1)
даст нам CF в знаковый бит. После чего регистр сдвигается на 31.
В процессе вычисления CF можно вычислить и само значение для сохранению.
Оно будет равно смещёному на 1 влево уже значению выражения + младший бит куска вышеприведённого вычисления (a&1)+(b&1)+Cf.
Код не писал, так на P4 проверить не могу, а потому не интересно. Но вышеизложенная математика явно меньше 8и тактов правда прийдётся поломать голову как это эффективно развалить на регистры.
"Пошёл на поводу" хотя не верю в в 8 тактов ADC :)
Чтобы хоть какой-то позитив внести в эту нашу муть.
Можно математику покороче сделать наверно, предлогайте, это первое что в голову пришло.

Ещё идея - поместить ESP на начало одного числа и извлекать POP, по окончанию вернуть ESP исходное значение.
ESP будет автоматом прибавлять 4, и POP наиболее быстрый способ загрузки из памяти (при условии выравнености).
Если второе слогаемое (не перезаписываемое) то будет просто POP если перезаписываемое (куда помещается результат) то загрузка в регистр для сложения POP, сохранение [esp-4].

TheSvin
1. Прошу прощения за W.
2. А в остальном ??? и !!!
В моем посте о "квазиоптимизации" не было ничего личного, и если ты его перечитаешь на свежую голову, а также ВСЕ замечания и результаты тестов ВСЕХ уважаемых собеседников, то поймешь, что наговорил здесь лишнего...
Иначе складывается неприятное впечатление о всемогущих,но грубых и необъективных ...

PS: если есть конкретные вопросы, то прошу изложить их конкретно без эмоций, а не в форме "а ты кто такой..."

PPS: TheSvin, я как всегда торможу ? вроде наметилось позитивное продолжение ?

Тема очень интересная - если кто сделает тест - могу потестить это дело на P2-300, P3-1000, P4-1700(400FSB) без HT и P4-2800(800FSB) с HT, Duron 700. А то у самого ща времени нету...

При тестировании на P4 желательно указывать model, т.к. согласно IA-32 optimization между моделями 0-2 и >2 есть существенная разница.
В частности, операции сдвига более чем на 1 бит на ранних моделях выполняются до 4 тактов, а на последних якобы за 1 такт. Поэтому Intel для ранних моделей рекомендует заменять shl r32,2 на операции сложения. Возможно такая же ситуация и с индексированием, поэтому на процессорах 15.2.7, на которых я проводил сравнение, [base+ecx*4] могло давать худший результат чем доп. инструкция LEA

bogrus

"... то почему бы не развернуть цикл ..."
"Цикл закончить к примеру ret-ом , а управление передавать на зависящее от длины складываемого числа смещение."

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

Получился, однако, у меня зело быстрый вариант на ММХ:

pxor mm0,mm0
lea ebx,[ebx+ecx*4]
lea esi,[esi+ecx*4]
neg ecx
align 4
@@:
movd mm1,[esi+4*ecx]
movd mm2,[ebx+4*ecx]
paddq mm0,mm1
paddq mm0,mm2
movd [ebx+4*ecx],mm0
inc cx
psrlq mm0,32
jnz @B

На P4 на 30%-50% быстрее.

________________Comp1___Comp2_____Comp3____Comp4
Gray_MMX;________896_____892_____exeption__exeption
Gray;___________1432____1420_______1159_____1159
The_Svin;_______1432____1424_______1118_____1117
leo;____________1264____1248________742______768

Comp1 - P4 2.6 DDR (Notebook Dell Lattitude 100, Windows XP)
Comp2 - Processor= x86 Family 15 Model 2 Stepping 4 GenuineIntel ~2254 Mhz (Windows XP)
Comp3 - Processor= x86 Family 6 Model 8 Stepping 3 GenuineIntel ~601 Mhz (Windows 2000)
Comp4 - Двухпроцессорный сервер 2*(x86 Family 6 Model 11 Stepping 1 GenuineIntel ~601 Mhz) (Windows 2000 Server)

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


_736400052__test.asm

Gray Раз ты мне, то я Агнеру Фогу скажу спасибо, т.к. я тестировал на слегка переделаной его проге ;) Gray_MMX протестировать не смогу , мой celeron не поддерживает SSE2 , а в остальном результат теста на нём в точности до такта , аналогичен твоему Comp3.

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

Вот Вам несколько примеров. Посмотрите на код для P4:

pxor mm0,mm0
lea ebx,[ebx+ecx*4]
lea esi,[esi+ecx*4]
neg ecx
align 4
@@:
movd mm1,[esi+4*ecx]
movd mm2,[ebx+4*ecx]
paddq mm0,mm1
paddq mm0,mm2
movd [ebx+4*ecx],mm0
inc cx
psrlq mm0,32
jnz @B

Видите align 4? Противоречит докам от Intel? Однако именно 4 в данном примере дает минимальное время исполнения. (См исходник теста в моем предыдущем посте).
Поглядите на адрес начала цикла под отладчиком. Забавно?

Теперь смотрим на inc cх. А почему не inc ecx, или add ecx,1 ? Да потому, что, вопреки докам и поверьям, так оказывается быстрее. Причем, подчеркиваю, именно в этом примере. В другой ситуации может быть иначе.
Лучшее место для inc cx - перед psrlq. С чего бы это?

Вместо четырех команд:

movd mm1,[esi+4*ecx]
movd mm2,[ebx+4*ecx]
paddq mm0,mm1
paddq mm0,mm2

можно было бы написать две

paddq mm0,[esi+4*ecx]
paddq mm0,[ebx+4*ecx]

но оказывается, что две будут медленее.
Не правда ли, поучительный примерчик получился :)

Я с вашего позволения тоже подкину кусок кода ;)

   clc
   mov ecx,-КОЛИЧЕСТВО_ЭЛЕМЕНТОВ
@@ mov eax,[АДРЕС_ЗА_КОНЦОМ_ВТОРОГО_МАССИВА + 4*ecx]
   adc [АДРЕС_ЗА_КОНЦОМ_ПЕРВОГО_МАССИВА + 4*ecx],eax
   inc ecx
   jnz @@ 

Здесь демонстрируется техника оптимизации, известная как "устранение индуктивной переменной".

Как видим, здесь используется та же идея, что и в коде The Svin, но адреса массивов пробиты в коде (то есть предполагается, что они статические), и адресация происходит с использованием лишь регистра ecx. Освободилось целых два регистра, которые окружающий код теперь может использовать, и за счёт этого тоже может произойти оптимизация...

Резонно, если только возможно использовать непосредсвенный дисплейсмент. Иногда приходится вычислять, в таком случае прийдётся вставлять его модификацией кода.

The Svin > „Для вычисления адреса существует отдельный сумматор ещё с 486 DX. Уже с тех пор это не проблема, и не вопрос для знакомых с тех. документацией.“

Да я больше на догадках основываюсь, ибо документация IMHO "мутновато" написана (а проверить на практике нет возможности):

„The lea instruction is not always as fast on the Pentium 4 processor as it is on the
Pentium II and Pentium III processors. This is primarily due to the fact that the lea
instruction can produce a shift µop. If the lea instruction uses a shift by a constant
amount then the latency of the sequence of µops is shorter if adds are used instead of a
shift, and the lea instruction is replaced with the appropriate sequence of µops.“

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

> „Мы вычисляем CF в знаковый бит какого-то регистра потом сдвигаем его на 31 вправо. “

Идея интересная, если задачу можно будет всё же свести к параллельному вычислению y+=d и d+=2, то для 2го сложения (с константой) можно заметно упростить арифметику.
И, кстати, под этот случай отлично подходит код captain cobalt (поскольку складываются не "любые" числа, а вполне конкретные, адреса которых мы знаем на момент компиляции)

> „поместить ESP на начало одного числа и извлекать POP, по окончанию вернуть ESP исходное значение.
ESP будет автоматом прибавлять 4, и POP наиболее быстрый способ загрузки из памяти (при условии выравнености).“

Например, на K7 это медленная инструкция - VectorPath, 4 такта :-(


Gray > „Получился, однако, у меня зело быстрый вариант на ММХ: “

Это как правильно заметил bogrus
SSE2, так что актуально только для PIV

Результаты теста для AthlonXP@1667MHz (брал лучшие числа, но в случае с кодом leo наблюдается стабильная нестабильность, поэтому 2 значения)

Gray
(align мало влияет):	0000000393

The_Svin
align 8:	0000000387
align 16:	0000000363

leo
align 8:	0000000374 - 0000000322
align 16:	0000000397 - 0000000323

Главным образом - для иллюстрации важности выравнивания кода.

> „Видите align 4? Противоречит докам от Intel?“

Нет, не противоречит. NetBurst кеширует не инструкции, а µops, но для остальных процев это критично.

Gray
"Посмотрите внимательно на табличку. Не шокирует ли то, что старые и медленные процессоры обставляют новые и шустрые. Может мы не то измеряем?"
Если ты имеешь ввиду цифры, то rdtsc дает нам не абсолютное время выполнения, а число тиков процессора, и чтобы получить время нужно разделить эти тики на тактовую частоту проца. А то, что в "новых и шустрых" (по крайней мере в P4) число тиков на одну операцию в среднем больше, чем в старых это известный факт. По крайней мере в i486 инструкция adc выполняется за 1 такт, а в P4 за 8.

"Вот Вам несколько примеров"
Могу подбросить еще пример: если в твоем исходном варианте просто переместить вторую инструкцию lea после dec ecx, то на P3 (6.8.1) получим выигрыш на 11-12% (вместо 3.6%, которые дает метод TheSvin).

"Вместо четырех команд movd ... можно было бы написать две paddq... но оказывается, что две будут медленее"
Что касается операций типа xxx r,m то это один из немногих случаев документированных в IA-32 optimization - тут ребята из интел честно признаются, что две операции mov r,m и xxx r,r в NetBurst работают быстрее.

А примерчики действительно поучительные.

S_T_A_S_
"Главным образом - для иллюстрации важности выравнивания кода"
"NetBurst кеширует не инструкции, а µops, но для остальных процев это критично"
Боюсь навлечь на себя очередную волну критики о пренебрежительном отношении к выравниванию, но по-видимому для P3, модель 6.8.1 это тоже не критично (во внутреннем цикле). Вставкой нопов перед меткой цикла я прошелся по всему диапазону смещений 0..15 и разницы более, чем в 3 тика не обнаружил ни для метода Gray ~ 1198 тиков, ни для метода TheSvin ~ 1158 тиков (алгоритм проверки типа bogrus\Gray, число - 128 двордов, внешниий цикл - 8 повторов, выравнен на 16).
А что собственно нам известно про кэш инструкций P3 кроме общих слов и "мутноватых" описаний (согласно твоему меткому определению) ?

И еще филосовско-риторический вопрос: вставить в нужное место кода align 16 труда не составляет, но если в результате этого у нас появится цепочка из 15 нопов, то как это повлияет на общее время выполнения на тех процах, на которых это критично (уж о размере кода говорить не приходится).

PS: Для доказательства действительной важности выравнивания начала цикла нужно получить устойчивую и значимую разницу для случая выравнивания кода хотя бы на одну из магических цифр x0h,x4h,x8h, по сравнению с любым другим "плохим" офсетом. Говоря о выравнивании, мы видимо имеем ввиду, что на загрузку невыравненных данных может понадобиться по крайней мере один дополнительный такт (ну хотя бы 1/2) на каждый цикл независимо от реализации тела цикла. => во-первых, это должно быть заметно для любого из рассматриваемых методов и во-вторых, при использовании rdtsc разница в тиках должна составлять более 0.5-1 от числа проходов (для теста Gray это 64-128 тиков). Если мы получаем меньшую разницу или она "скачет" от метода к методу, то это скорее всего очередной примерчик "фокусов" конкретной модели проца.

Эх.. что-то мне всё это напоминает танцы с бубном - команду туда, эту - сюда.
Я до сих пор не вижу постановку задачи, что оптимизировать-то?

Как я понял, оптимизировать можно совершенно не те сложения, которые тестируются сейчас.
(но это только догадка ;)

Пока же, мне кажется, мы говорим о чём-то абстрактном, измеренном в каких-то попугаях.
У меня этих попугаев в 2-5 раз меньше получается, чем у Gray.
Почему? Вероятно, из-за того, что я откидываю первых 2 значения, которые заведомо большие, т.к. инструкции ещё не кешированы, переходы не предсказаны, остальные числа примрно одинаковы.
А Gray похоже считает среднее арифметическое ВСЕХ чисел.
Ну и как в таком случае сравнивать-то? Сколько ещё нужно сделать допущений..


leo > „И еще филосовско-риторический вопрос: вставить в нужное место кода align 16 труда не составляет, но если в результате этого у нас появится цепочка из 15 нопов“

Например, AMD отводит отдельнуый параграф на описание команд, которыми можно делать выравнивание. (и это при том, что athlon выполняет 9 NOP за такт)ю У intel по этому поводу тоже что-то написано.

The Svin > „Для вычисления адреса существует отдельный сумматор ещё с 486 DX. Уже с тех пор это не проблема, и не вопрос для знакомых с тех. документацией.“
Так-то оно так, но хотя это и специальный и, видимо, оптимизированный сумматор, но ведь не волшебный. И даже не знакомым с тех.документацией ясно, что адрес [base+const] должен вычисляться быстрее, чем [base+r32*4] (тем более если результат в r32 еще не готов). Кстати, в отличие от общих слов IA-32 в двухтомной книжке "i486™ микропроцессор" есть отдельный раздел, посвященный этой теме, где расписаны некоторые штрафы при использовании индекса и масштаба.

Кстати, "можно подбросить" компромиссный вариант, который исключает одну инструкцию LEA в методе Gray и не не использует масштабирования как в методе TheSvin. Для этого можно сразу вычислить разность esi-edi и использовать ее в качестве постоянного смещения:

	sub esi,edi
	clc
@@:
	mov eax,[edi+esi]
	adc [edi],eax
	lea edi,[edi+4]
	dec ecx
	jnz @@

(На P4 работает без ухудшения, на P3 еще не проверял)

S_T_A_S_
>"У меня этих попугаев в 2-5 раз меньше получается, чем у Gray"
У меня тоже другие числа получались, но когда взял ту же методику тестирования (см.аттач Gray .._test.asm) стало практически один в один.

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

По поводу NOP. Если атлон выполняет 9 NOP за такт, значит он "умный", а тогда у него и кэш инструкций видимо сделан по уму - вроде бы логично кэшировать декодированные инструкции, а не исходные. Я риторический вопрос задавал в отношении неких "других" процев, у которых по нашим предположениям офсет в кэше совпадает или связан с офсетом в памяти. Или я туплю..