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

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

 

The Svin >

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

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



>

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

И, кстати, под этот случай отлично подходит код captain cobalt (поскольку складываются не "любые" числа, а вполне конкретные, адреса которых мы знаем на момент компиляции)



>

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





Gray >

Это как правильно заметил bogrus

SSE2, так что актуально только для PIV



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

Код (Text):

1. Gray
2. (align мало влияет):  0000000393
3.  
4. The_Svin
5. align 8:    0000000387
6. align 16:   0000000363
7.  
8. leo
9. align 8:    0000000374 - 0000000322
10. align 16:   0000000397 - 0000000323

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



>

Нет, не противоречит. 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 >

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

 

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

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



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

Код (Text):

1.     sub esi,edi
2.     clc
3. @@:
4.     mov eax,[edi+esi]
5.     adc [edi],eax
6.     lea edi,[edi+4]
7.     dec ecx
8.     jnz @@

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



S_T_A_S_

>"У меня этих попугаев в 2-5 раз меньше получается, чем у Gray"

У меня тоже другие числа получались, но когда взял ту же методику тестирования (см.аттач Gray .._test.asm) стало практически один в один.



>"танцы с бубном - команду туда, эту - сюда"

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



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

 

leo



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



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



Забавно А на Р4 такое перемещение ничего не меняет.



На Р4 твой компромисный вариант leo2 у меня дает тоже самое быстродействие, что и исходный Gray.

 

S_T_A_S_



> "Я до сих пор не вижу постановку задачи, что оптимизировать-то? ... Как я понял, оптимизировать можно совершенно не те сложения, которые тестируются сейчас."



Похоже, что Вы пропустили мой ответ от Окт 7, 2004 15:30:53 (см. вторую страницу этого топика)



А оптимизируем мы самое то, что надо - операцию "+="



P.S. А один попугай равен одному тику

 

Gray >

А надо ли ?!

На всякий случай повторю свои мысли:

Код (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;



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

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



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

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

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





То есть, можно ли перейти к варианту:

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



или будем шаманить вокруг:

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

 

S_T_A_S_



1. В реальной задаче надо вычислять: y+=z; z+=d; где d - число большое - 500-1000 бит. т.е d в непосредственный операнд не целиком запихивается в команду... только в несколько (вариант развертки цикла). Но дело даже не в этом, а в том, что исключая N операций чтения данных мы получаем N+KN операций чтения кода (K байты опкодов). Так что выигрыш сомнителен.

2. Параллельное вычисление сразу "y+=z; z+=d;", конечно же интересно, но, увы, скорее только мне, чем читателям форума. А вот "+=" может быть полезно многим. Посему его и обсуждаем.

 

Помнится, во времена 8086, я обнаружил, что NOP выполняется дольше чем xchg ax,ax.



...при том, что athlon выполняет 9 NOP за такт

откуда вы это взяли ?

цитата из 22007.pdf про nop:

These instructions have an effective latency of that which is listed. They map to internal NOPs that can be executed at a rate of three per cycle and do not occupy execution resources.

Ребята, вы перегрелись

а поповоду оптимизации сложения - посмотрели бы сначала исходники gmp.

 

Shur



Gray> "Помнится, во времена 8086, я обнаружил, что NOP выполняется дольше чем xchg ax,ax. "



Shur >"...при том, что athlon выполняет 9 NOP за такт .... откуда вы это взяли ? "



Смеюсь. Батенька, какой уж там athlon. В то время 8086 только появился. На нем и пробовал. )



Shur >"а поповоду оптимизации сложения - посмотрели бы сначала исходники gmp"



Смотрел я GMP и PARI и по BigLib c отладчиком полазил. Наши варианты пошустрее будут

 

Я тут подумал (на тест пока времени нету)... Что если избавиться от использования CF тем же методом, что на SSE2? Правда, число сложений возрастет... и, наверное, даже не в 2, а в 4 раза, чтобы использовать al, ah.



Не стоит ли попробовать?

 

"Безумная" идея RobinFood оказалась гениальной! Соряжение ее с вариантами решения Gray и The_Svin дало почти 50% ускорение. cmovc - хорошая щтука, но, увы, не для всех процессоров.



RobinFood - примите мое искреннее восхищение.



macro RobinFood_Gray{

xor edx,edx

inc edx

xor eax,eax

xor edi,edi

@@: add eax,[esi]

lea esi,[esi+4]

add [ebx],eax

lea ebx,[ebx+4]

mov eax,edi

cmovc eax,edx

sub ecx,1

jnz @B

}



macro RobinFood_The_Svin{

xor eax,eax

mov edx,1

lea ebx,[ebx+ecx*4]

lea esi,[esi+ecx*4]

neg ecx

@@: add eax,[esi+ecx*4]

add [ebx+ecx*4],eax

mov eax,0

cmovc eax,edx

add cx,1

jnz @B

}



Еще одна новость - результат использования prefetch



macro Gray_SSE2{

pxor mm0,mm0

lea ebx,[ebx+ecx*4]

lea esi,[esi+ecx*4]

neg ecx

prefetchnta [ebx+128]

prefetchnta [esi+128]

@@:

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

}



Результат тестирования:

;_________________Comp1___Comp2_____Comp3____Comp4

;Gray_SSE2;__________880_____876_____exeption__exeption

;Gray;______________1432____1420_______1159_____1159

;The_Svin;__________1432____1424_______1118_____1117

;leo;_______________1264____1248________742______768

;leo2_______________________1420

;RobinFood_Gray;____________1024

;RobinFood_The_Svin;_________968



Исходник:



_548674902__test.asm

 

Gray >

Я уже окончательно запутался.

В прошлый раз, в качестве "реальной задачи", был приведён код вычисляющий квадраты чисел натурального ряда.

Код содержал ошибку, которую я исправил (?), так и получился мой код выше.

Этот вариант IMHO поддаётся неплохой оптимизации, просто за счёт уменьшения количества операций с памятью.

Одно из слагаемых - 2 - свободно помещается в один операнд (причём байтовый).

Далее нужно только отслеживать перенос, т.е. больше никаких непосредственных операндов нет.

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



Теперь же оказывается, что квадраты (путём сложения) вычислять не нужно.

Или может быть - квадраты - это только частный случай, и я что-то упустил?



Теперь дальше: 1000 бит это "всего" 125 байт.

Тогда непонятно, зачем делается prefetchnta [ebx+128] ?





К чему всё это я пишу.

Я не знаю, что интересно остальным участникам форума, но лично мне интересно решать реальные задачи.

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

Если же решать "задачу вообще", то ни о какой оптимизации по скорости не может идти речи, так как

для больших объёмов данных используют одни методики, а для небольших (500 - 1000 бит) - совершенно другие, это как минимум.





Помимо вышесказанного, неизвестно:

- где данные хранятся - известен ли их адрес на момент компиляции или же память под них выделяется динамически;

- целевой процессор(ы);

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



И только после ответа хотя бы на часть этих вопросов, IMHO можно начинать писАть код, смотреть его под VTune / CodeAnalyst или же просто измерять тем же RDTSC (но оговорить детали измерения).





Shur >

Да, я это знаю, у меня и распечатка на столе. и CodeAnalyst показывает тоже самое. Эту информацию мне сообщил один человек, которому оснований не верить нет. А проверять мне лениво - всё равно нигде не использую





ЗЫ

Про

я только сейчас понял %))

 

S_T_A_S_



S_T_A_S_ >"Или может быть - квадраты - это только частный случай"



Именно, что частный случай

Общий случай:



y=j*D; z=k*D; d=m*D;

for(i=1; i<10000000000000000000000000; i++)

{

y+=z; z+=d;

....

}

При D=1 j=1 k=3 m=2 вычисляются квадраты...

При D=? j=1 k=3 m=2 вычисляются D*i^2... и т.д. ....



Вот только нужно ли было всему форуму головушки морочить этой общностью? Задачка быстрой реализации "+=" ведь все равно остается.



S_T_A_S_ > "Теперь дальше: 1000 бит это "всего" 125 байт. Тогда непонятно, зачем делается prefetchnta [ebx+128] ?"



Так ведь в процессе счета z и y растут (цикл как ни как), причем у растет квадратично. А ставить цифру меньше 128 бесполезно, ибо P4 и сам prefetch делает.



S_T_A_S_ > "- где данные хранятся - известен ли их адрес на момент компиляции или же память под них выделяется динамически; "

Адрес заранее не известен.



S_T_A_S_ > "- целевой процессор(ы); "



От P3 и выше



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



См. исходник теста.

 

Gray

>"Соряжение ее с вариантами решения Gray и The_Svin дало почти 50% ускорение. cmovc - хорошая щтука"



Не спеши радоваться. Я уже пытался рассматривать аналогичный подход с setc, но бросил. А потому, что в твоем коде не учтен случай, когда на входе eax = 1 и первый операнд = xFFFFFFFFh, тогда перенос возникает при первом add, а при втором его нет = ошибочка, нужны дополнительные навороты.

 

Вариация на тему cmovc на P4



Как и предполагалось cmovc - не быстрая операция. Согласно IA-32 setc на P4 = 5 тактов, cmovc - неизвестно - возможно чуть быстрее. Но использование в цикле двух cmovc на P4 приводит к ухудшению на 25% и более, по сравнению с исходным методом Gray.

Ничего интересного, кроме "статистического" метода я не придумал. Но как ни странно, использование одного условного перехода к "катастрофическим" потерям не приводит и в итоге на P4 работает быстрее метода Gray:

Код (Text):

1.     sub esi,edi
2.     xor edx,edx
3.     mov ebx,1
4. @@loop:
5.     mov eax,[edi+esi]
6.     add eax,edx
7.     jc @@carry  ;перенос возможен только при edx = 1 => обнулять не нужно
8.     xor edx,edx
9. @@carry:
10.     add [edi],eax
11.     cmovc edx,ebx
12.     add edi,4
13.     dec ecx
14.     jnz @@loop

Результаты на P4 1800 (15.2.7) по сравнению с Gray (size = 128):

если нет ни одного перехода - выигрыш 23%,

если все 127 переходов (y[j]:=-1) - ВЫИГРЫШ около 1.5%, т.е по крайней мере не хуже.

В жизни выигрыш будет зависить от вероятности сочетания edx = 1 и y[j] = -1.



Кстати, в данном случае add edi,4 заметно быстрее чем lea edi,[edi+4]; dec ecx действительно лучше sub, а вот разницы dec ecx и dec cx я не обнаружил.

А контрольная попытка также и cmovc заменить на jnc приводит к большим потерям.



Gray > "cmovc - хорошая щтука, но, увы, не для всех процессоров"

Согласно IA-32 инструкция CMOVcc введена в P2 и должна быть во всех более старших моделях. А как насчет атлонов ?

 

leo



Вы абсолютно правы. Ошибся я Вот что значит положиться

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



Оба варианта RobinFood_Gray и RobinFood_The_Svin ошибочны

 

> Согласно IA-32 инструкция CMOVcc введена в P2 и должна быть во всех более старших моделях. А как насчет атлонов ?

Код (Text):

1. INSTRUCTION SET REFERENCE, A-M
2. CMOVcc—Conditional Move (Continued)
3.  
4. The CMOVcc instructions were introduced in the [u]P6 family[/u] processors;
5. however, these instructions may not be supported by all IA-32 processors.

 

Вижу стараниями leo приоритетом всё таки выбрана оптимизация под P4 без учёта мнения автора вопроса.

Вот сумел же человек, поставить свои приоритеты в чужом монастыре. Одно можно сказать тролли как и мафия бессмертны. О чём бы не говорили сумел ведь повернуть так, что если для P4 не актуально, то не очень и важно.

В результате все усилия направлены на поиск оптимизации под эту маразматичную модель.

Интересно, существует ли на борде хоть один проффессионал низкоуровник, работа которого именно оптимизация библиотек под P4?

Другой вопрос, существует ли, либо появится в будущем аналог фидошного твита на борде.