Сложение очень-очень длинных чисел

Тут много чего интересного, произошло в мое отсутствие, сразу не могу осмыслить - утро вечера мудренее...

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



Суть такова: мы тут "дурью маемся" - такты считаем, а пеньки живут своей жизнью. Возможно для S_T_A_S_ это очевидно, но оказывается в данной задаче главным тормозом на P3\P4 является инструкция ADC m32,r32, и можно получить существенный выигрыш при замене ADC на (казалось бы длинную) цепочку эквивалентных операций:

Код (Text):

1.     ...
2. @@loop:
3.     mov eax,[...]
4.     mov edx,[...]
5.     adс eax,edx
6.     mov [...],eax
7.     ...

Здесь вместо "..." можно использовать вариант Gray или TheSvin.

Вот усредненные результаты тестов для size = 4096 и RepCount = 10000 для P3 650MHz (1 реликтовый "штук") и P4 1800MHz Northwood (3 "штук" - разница +- 10 мс):

Код (Text):

1. P3 650  P4 1.8  Метод
2. ------  ------  ------------------
3. 625 230-250 1) [b]Gray[/b] (add2)
4. 615 295-320 2) [b]TheSvin[/b] (на P3 лучше, на P4 1.8 хуже, на других не знаю..)
5. 580 185-210 3) [b]TheSvin[/b] с раздельными mov, т.е. замена (adc m,r) на (mov r,m)+(adc r,r)+(mov m,r)
6. -?- 165-175 4) [b]Gray[/b] аналогично 3)
7.  

ПрОценты не трудно посчитать, но и без калькулятора видно, что ADC m32,r32 на пеньках - это тормоз. Может кто на атлоне проверит...



PS: 2TheSvin: насчет выравнивания метки @@loop хотя бы на 4, мысль крутилась, но приведенные результаты - без всякого контроля выравнивания.

 

S_T_A_S_

>"из-за умножения ecx на 4"

Да, это первое что мне пришло в голову и заставило затеять проверку. Но, по-видимому, дело как раз в неоптимальной реализации "отдельных" CISC-инструкций, о чем ты говорил раньше.

 

leo

Хе - это могло испортить все тесты - вдруг какой-то вариант был случайно алигненым а другой нет? Правда на П4 это влияет тока на 1й проход, а на П3 все время...

 

Gray >

Поправте меня, т.к. математике я не силён, но IMHO код должен быть такого вида:

Код (Text):

1.  
2.         funny_number    y=0, d=1;
3.     for(funny_number i=1; i<10000000000000000000000000; i++)
4.     {
5.         y+=d; d+=2;// вычисляем y=i^2 без умножений :))
6.         if(простой_и_быстрый_тест(n,y)))
7.         {
8.             сложный_и_долгий_тест(n,y) // чаще всего до этого теста дело не оходит
9.         }
10.     }

Т.о. задачу можно свести к параллельному вычислению:

y+=d; d+=2;

?

 

semen

"Хе - это могло испортить все тесты - вдруг какой-то вариант был случайно алигненым а другой нет? Правда на П4 это влияет тока на 1й проход, а на П3 все время..."



Эксперимент на Р4 показал, что align очень заметно влияет, надо бы програмку тестирования на эту тему скорректировать.

 

S_T_A_S_



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

y+=z; z+=d; где d - число большое - 500-1000 бит.

А параллельность вычислений было бы здорово организовать

 

Исключительно для очистки совести (и стараясь не слишком задумываться) я написал вариант MMX решения. mm0 используется для храненея CF. Это противоречит здравому смыслу даже утром, но работает почти столь же быстро как и другие варианты! Похоже, что пора задуматься о 127 битном формате

@@: movd mm1,[esi+4*ecx] ;16456 20292

movd mm2,[ebx+4*ecx]

paddq mm2,mm1 ; MMX_Gray

paddq mm2,mm0

movd [ebx+4*ecx],mm2

inc ecx

psrlq mm2,32

movq mm0,mm2

jnz @B



Результаты по двум машинам:



P4 2.6 DDR P4 2.2

MMX_Gray 16456 20292

Gray 16188 20032

The Svin 16188 20032

leo 16336 20440



Тестировалось с align 16

 

Если это сложение будет выполняться довольно часто , то почему бы не развернуть цикл , может даст прирост скорости в 1,5-2 раза ? Его размер для таких чисел будет не большой (меньше килобайта) , на крайний случай можно в памяти развернуть один раз и всё .

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

Примерно так (но только если числа кратны 32 битам) :

Код (Text):

1. ;==========================================================
2. maxlenght   =       1024            ; бит
3. ;==========================================================
4.             lea     eax,[ecx*8+ecx] ; умножаем
5.             lea     eax,[ecx*4+eax] ; на 14
6.             add     eax,ecx
7.             mov     ecx,endloop
8.             sub     ecx,eax         ; находим смещение
9.             call    ecx             ; вызов цикла
10.             invoke  ExitProcess,0
11. ;==========================================================
12. repeat      maxlenght/32            ; развёрнутый цикл
13.             mov     eax,[esi]
14.             mov     ecx,[edi]
15.             adc     eax,ecx
16.             mov     [edi],eax       ; 14 байт кода на дворд
17.             lea     esi,[esi+4]
18.             lea     edi,[edi+4]
19. end         repeat
20. endloop:    ret
21. ;==========================================================

adc r32,r32 т.к. c adc m32,r32 тормознее

 

Gray >

Пусть число 64 байта. На последовательное выполнение этих опереций DWORD регистрами уйдёт:

16*2*2 операций чтения из памяти и 16*2 операций записи.



Если же одно из чисел - константа, то оно будет представлено в качестве непосредственного операнда.

Таким образом мы исключаем 16 операций чтения.

Если же при этом "спараллелить" увеличение на 2 со сложением y и z, то мы исключаем ещё 16 операций чтения.



Может быть пока рано считать такты?

 

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



1. "использовать счётчик в качестве индекса чтобы полностью избежать команд на изменение источника и приемника"

А зачем их избегать то ? На P4 они выполняются (наверное на быстрых ALU0\ALU1) параллельно с тормозной 8-тактовой инструкцией ADC и по идее не занимают никаких штрафных тактов. А вот когда мы переходим к использованию масштабирования [base+ecx*4] сразу возникает вопрос, а не дольше ли вычисляется исполнительный адрес. Результаты тестов на разных процах противоречивы (меньше\больше\равно) возможно из-за разной реализации индексирования, а может и предсказания, т.к в начале цикла нужно вычислить адрес до загрузки. Но с учетом параллельного исполнения LEA возможное увеличение времени при переходе к индексированию выглядит вполне логично (как отметил S_T_А_S_ 7окт 11:56).

Поэтому, я поддерживаю Gray: "очень изящное решение, сэр", но добавляю - сомнительное в плане увеличения быстродействия (ес-но в данном конкретном случае).



2. "Начало цикла итераций ОБЯЗАТЕЛЬНО должно быть выравнено по границе 16 байт"

Возможно логично для реликтовых процев, но сомнительно для P4, который кэширует декодированные микрооперации. Как заметил semen, это может влиять только на первый проход цикла. В IA-32 optimization на этот счет есть четкий ответ: "Because the trace cache (TC) removes the decoding stage from the

pipeline for frequently executed code, optimizing code alignment for

decoding is not as important for Pentium 4 and Intel Xeon processors".



3. "P4 не любят inc \ dec"

Ес-но, это "нестандартные операции", но согласно тому же мануалу их latency составляет 1 такт вместо 0.5 для add\sub. А что такое разница 0.5 такта по сравнению c ADC (8 тактов) и тремя MOV с памятью ? Мелочь..



PS: Вот если бы найти альтернативу тормозной ADC.. Чтобы получить заметный выигрыш хотя бы статистически. А то с учетом CF какой-то абсурд получается: за 8 тактов можно выполнить до 16 операций add\sub\logical, но чтобы вытащить CF, например setc, выложи до 5 тактов.

 

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]



но оказывается, что две будут медленее.

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

 

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

Код (Text):

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

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



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