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

Объясняю свою позицию: я чайник.

Сижу, читаю этот топ, и до сих пор не пойму, что же нужно складывать (

 

S_T_A_S_

Во-во, а я так точно такой, ну незнаю я С, чтоб условие понять, и не знаю какими регистрами складывать числа, если их длина может быть и 1000 и 2000 бит

 

Так и в прямом коде можно ADC использовать.

Вобщем ладно оставляю топик в покое

Нездоровая атмосфера так и витает как doom над ним.

 

The Svin

Прочитал наконец!



Да нормальная атмосфера. Чего ж вы хотите?

Атмосфера амбиций - это так естественно



Спасибо за идеи!

 

Давайте попытаемся разобраться, чтобы небыло наполовину, как Владимир Семёнович завещал, как сделать из декларативного утверждения "je увеличит количество непредсказанных переходов" утверждение логически и математически обоснованное.

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

Вначале вспомогательный вопрос о вычислении.

Допустим у нас число занимает 256 двойных слов.

При сложении всех возможных пар чисел A и B, которые в свою очередь состоят из частей-двойных слов (a_0,a_1 ...a_255) сколько раз возникнет ситуация когда

1. a_?+cf даст CF

2. a_?+cf даст ZF

С удовольствием почитаю результат и обязательное к нему обоснование.



Ешё раз подчёркиваю - во всех возможных парах A и B.

Т.е в 2^2048 возможных парах.

 

Хочу поделиться одним неудачным вариантом, ибо он поучителен. Идея была в том, чтобы использовать способность процессора к массовым чтениям и записям в/из памяти, в частности popa.



macro gray_popall{

mov dword ptr sp_mem,esp

xchg esp,esi

xor edx,edx

@@loop2:

repeat 16

popad

adc edi,[esp+0x1E0]

mov [esp+0x1E0],edi

adc esi,[esp+0x1E4]

mov [esp+0x1E4],esi

adc ebp,[esp+0x1E8]

mov [esp+0x1E8],ebp



mov ebp,[esp-4*5]

adc [esp+0x1EC],ebp



adc ebx,[esp+0x1F0]

mov [esp+0x1F0],ebx

adc edx,[esp+0x1F4]

mov [esp+0x1F4],edx

adc ecx,[esp+0x1F8]

mov [esp+0x1F8],ecx

adc eax,[esp+0x1FC]

mov [esp+0x1FC],eax

end repeat

mov esp,dword ptr sp_mem

}



Увы, но даже такой безджамповый и развернутый вариант показал неважные результаты: 1624 против 1432 исходного варианта Gray.

 

Привожу последние результаты тестов:



;____________________Comp2

;Gray_SSE2;____________880

;gray_pop;____________1100

;svin_test2;__________1176

;leo_setc;____________1212

;leo;_________________1228

;leo_setc2;___________1272

;svin_test_gray;______1284

;svin_test;___________1292

;Gray;________________1400

;leo2;________________1400

;The_Svin;____________1420

;gray_popall;_________1624



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



975894600__test.asm



Правка по следам замечания leo:

;Comp2 - Processor= x86 Family 15 Model 2 Stepping 4 GenuineIntel ~2254 Mhz (Windows XP)

 

Gray

Мы вроде бы согласились, что один и тот же код может давать разные результаты на P3 и P4. Отсюда два замечания:

1. Когда приводишь результаты тестов надо бы указвать тип процессора (ОТСТАВИТЬ ! Извини, не заметил Comp2).

2. Если ты тестировал свой последний код на P4, то одним из объяснений неважных результатов может быть то, что ты заменил ADC m32,r32 на ADC r32,m32. Хотя в IA-32 Optimization сказано, что операции r32 <- m32 могут работать медленнее, чем c раздельным mov и операцией r32 <- r32. А вот в первоначальном варианте ADC m32, r32 такого ограничения для P4 нет. Впрочем, это только предположение.

3. Мне кажется, что главным тормозом в данной задаче является не чтение\запись, а учет переноса в ADC или SETC. Чтобы в этом убедиться можно сделать контрольный тест, заменив все ADC на ADD - получим оценку снизу (к чему можно стремиться в попытках избежать анализа CF).



TheSvin

Математические упражнения:

Если dword "пробегает" все значения от 0 до N-1, где N=2^32, то вероятность (или относительная частота, или "частость") появления любого конкретного значения равна 1/N. Какова вероятность того, что при сложении двух независимых dword возникнет перенос ? Если один из двордов принимает значение X, то перенос возникает в том случае, когда второе слагаемое будет больше или равно N-X когда нет переноса из предыдущего дворда, или N-X-1, когда есть. Обозначим условную вероятность возникновения переноса через P(CF=1|c=0), где "|c=0" означает: при условии, что перенос на входе с=0. Аналогично P(CF=0|c=0) - это вероятность отсутсвия переноса при отсутсвии переноса на входе и т.д. Тогда по формуле полной вероятности запишем:

P(CF=|с=0) = (1/N)*(0/N+1/N+...(N-1)/N) = (1/N)*(N-1)*N/2N = (N-1)/2N = 1/2-1/2N

и => P(CF=0|с=0) = 1-P(CF=1|с=0) = 1/2+1/2N



P(CF=|с=1) = (1/N)*(1/N+2/N+...N/N) = (1/N)*N*(N+1)/2N = (N+1)/2N = 1/2+1/2N

и => P(CF=0|с=1) = 1-P(CF=1|с=0) = 1/2-1/2N

Поскольку величина 1/2N = 2^(-33), то ес-но ей можно пренебречь и считать, что вероятность переноса = 0.5 независимо от того был перенос на входе или нет.

Тогда вероятность перехода по JC в одном конкретном дворде равна вероятности события (X=N-1)И(c=1)

P(JC) = (1/N)*(1/2) = 1/(2N).

Вероятность перехода по JZ в одном дворде равна вероятности события (X=N-1)И(с=1)ИЛИ(Х=0)И(с=0)

P(JZ) = (1/N)*(1/2)+(1/N)*(1/2) = 1/N (это выражение точное, т.к. +-1/(2N) уничтожаются)



Если мы имеем длинное число из n двордов и нас интересует как часто будут возникать JC и JZ когда число пробегает все возможные значения, то задача сводится к серии из n независимых испытаний, где каждое испытание - это JC или JZ в одном дворде. Независимыми мы их можем считать на основании того, что вероятность возникновения переноса практически не зависит от того был перенос на входе или нет (пренебрегаем поправкой 1/(2N) для JC). В таком случае можно использовать известные формулы теории вероятностей.

Например, вероятность хотя бы одного Jcc при сложении n двордов будет равна

Pn(k >= 1) = 1-(1-p)^n ~ 1-(1-n*p) = n*p, где далее для простоты p это P(Jcc) в одном дворде.

Вероятность возникновения одной фиксированной комбинации из k переходов будет равна

Pn(k) = p^k * (1-p)^(n-k)

Вероятность возникновения k переходов в любых местах будет определяться формулой Бернулли (биномиальный закон распределения величины k):

Pn(k) = C(n,k) * p^k * (1-p)^(n-k), где C(n,k) - число сочетаний из n по k.

Поскольку n достаточно велико, а p - малая величина, то биномиальное распределение должно неплохо аппроксимироваться распределением Пуассона (по крайней мере для малых k):

Pn(k) = (n*p)^k * exp(-n*p)/k!,

в частности отсюда получим Pn(k >= 1) = 1-Pn(k=0) = 1-exp(-n*p) ~ n*p

Соответственно при n -> oo (бесконечности), можно рассматривать появление переходов как "простейший поток событий" в теории массового обслуживания.

И т.д и т.п.



Вот только вопрос, что делать со всеми этими вероятностями ? Все эти величины при равновероятном подходе получаются мизерными. А в жизни все может быть не совсем так, если мы крутим цикл по возрастающим значениям второго слагаемого (назовем его z), как в исходной задаче Gray по вычислению квадратов. В этом случае все наши расчеты будут верны в среднем, когда мы прокрутим все значения. Но вот на локальных отрезках, когда у нас какой-то из старших dword z установлен в 0 или N-1 мы на протяжении б-а-а-льшого числа циклов будем с вероятностью 0.5 иметь Jcc в однои и том же месте. Это примерно то же самое, что по среднегодовым данным пытаться определять вероятность того, что в июле температура воздуха будет ниже 0°C (по научному - это нестационарный случайный процесс).



PS: Вот если мы будем сначала складывать дворды, а потом учитывать перенос от предыдущего сложения (т.е. перенесем Jcc после сложения), вот тогда действительно все будет более или менее случайно и вероятность прыжка видимо можно будет считать мизерной во всех случаях.

 

Y-e-e-s-s! Идея с перестановкой Jcc дает превосходные результаты при отсутствии переходов. Вот "суперрекорд" на P4, работающий быстрее Gray_SSE2:

Код (Text):

1.     ;leo_JZ
2.     add ecx,ecx ;умножение ecx на 4
3.     add ecx,ecx
4.     add edi,ecx
5.     add esi,ecx
6.     neg ecx
7.     xor edx,edx
8.     xor eax,eax
9. @@loop:
10.     mov dl,al
11.     mov eax,[esi+ecx]
12.     mov ebх,[edi+ecx]
13.     add ebx,eax
14.     setc al
15.     add ebx,edx
16.     mov [edi+ecx],ebx
17.     jz @@correct
18.     add ecx,4
19.     jnz @@loop
20.     @@correct:
21.     or eax,edx  ;учет возможного переноса при add ebx,edx
22.     add ecx,4
23.     jl @@loop

Вот цифирьки для P4-800 15.2.7 (все методы уж приводить не буду)

Gray______1400

leo_JZ_____818

Тут конечно некоторые перестановки несколько влияют, например, если поставить mov ebx перед mov eax, то получается хуже (853). Как поведет себя P3 на таком коде пока неизвестно (наверное не так хорошо, т.к. на P4 доп.выигрыш дают быстрые регистровые сложения за 0.5 такта).



Здесь действительно вероятность прыжка можно считать малой за исключением случая сложении старших нулевых двордов. При наличии лидирующих нулей в обоих слагаемых на P4 получается около 950-1100 тиков (при любом числе нулей: если все нули, то стабильно 986, иначе нестабильные значения в указанных пределах).



PS: Спасибо TheSvin за упражнение по математике, трезвый неспешный анализ действительно помогает найти интересное решение.

 

Вау!!! leo, потрясающий код! На другом процессоре P4 15.2.4 oн показал

;Gray_SSE2;____________880

;leo_JZ;_______________924

;gray_pop;____________1100

;Gray;________________1400



Это лучшее, что мне пока удалось добиться на этом процессоре. Код чуть-чуть переделал (так оказалось быстрее):

macro leo_JZ{

add ecx,ecx

add ecx,ecx

add edi,ecx

add esi,ecx

neg ecx

xor edx,edx

xor eax,eax

align 4

@@loop:

mov dl,al

mov ebx,[edi+ecx]

mov eax,[esi+ecx]

add ebx,eax

setc al

add ebx,edx

mov [edi+ecx],ebx

jz @@correct

add ecx,4

jnz @@loop

@@correct:

or eax,edx

add ebx,edx

add ecx,4

jl @@loop

}



Кстати, перестановка двух инструкций

mov ebx,[edi+ecx]

mov eax,[esi+ecx]

дала заметное ускорение.

Похоже, что еще немного и мы станем обгонять SSE2 на всех моделях P4.

 

leo >"Если ты тестировал свой последний код на P4, то одним из объяснений неважных результатов может быть то, что ты заменил ADC m32,r32 на ADC r32,m32. Хотя в IA-32 Optimization сказано, что операции r32 <- m32 могут работать медленнее, чем c раздельным mov и операцией r32 <- r32. А вот в первоначальном варианте ADC m32, r32 такого ограничения для P4 нет."

Я пробовал разные варианты, увы, все они оказались слишком медленными

 

leo, мне кажется, что в Вашем последнем варианте

or eax,edx можно заменить на mov eax,edx

Или это у меня глюки?

 

Gray

> "мне кажется, что в Вашем последнем варианте or eax,edx можно заменить на mov eax,edx"

(Слушай, кончай "выкать" - ухо режет, тут все "инкогнито" и на равных - в этом весь шарм).

В приведенном варианте с JZ нельзя, т.к. главный перенос фиксируется setc при первом сложении, а при add ebx,edx перенос возникает только при ebx=2^32-1 и edx=1, а при ebx=edx=0 его нет, хотя в AL он может уже "сидеть". Но вообще ты прав, т.к. я в очередной раз лопухнулся - вместо JZ нужно использовать JC, т.к. именно эта комбинация является "случайной" и маловероятной и не зависит ни от каких лидирующих нулей или единиц. Виноват. Однако ситуацию с JZ проще моделировать и я использовал ее в тестах по оценке влияния переходов. При замене JZ на JC действительно можно использовать mov.



Кстати, на P4-1800 15.2.4 у меня тоже получились результаты похуже чем на 15.2.7. Интересные эти интелы, то уменьшают число микроопов, то увеличивают - видать ребята в творческом поиске (см.последнюю табличку)



Ну что, проверил я как работает последний вариант на P3 и P4 без переходов и с переходами. Как и ранее, наличие переходов незначительно влияет на P4 и существенно на P3. Причем я теперь совершенно не понимаю, как работает предсказание в P3 (как-то уж слишком тупо получается). Вот для начала результаты на P3-650 6.8.2

Код (Text):

1. Gray______1198
2. leo_JZ_____688 - без переходов
3. __________1425 - лидирующие нули при i >= 64 (это так, для иллюстрации если JZ и числа фикс.формата)
4. один переход при "случайном" i=0..127:
5. i=_____14___19____25____32____37____43____60____65____93___99___105__111__123
6. тики__1374__1344__1308__1266__1236__1200__1098__1067__900__864__829__792__719

Мда, что это за предсказание ??? Один раз ошибся и продолжает ошибаться во всех последующих циклах ??? В P4 такого нет - при наличии перехода результат ухудшается, но слабо зависит от положения перехода.

Возникает вопрос, как вернуть зацикленный после прыжка P3 в нормальное русло ? Оказывается достаточно вставить после метки @@correct один цикл в стиле setc2 и P3 практически "забывает" о прыжке

Код (Text):

1.     ...
2. @@loop:
3.     ...
4.     jz @@correct
5.     ...
6. @@correct:
7.     or eax,edx
8.     add ecx,4
9.     ;jl @@loop - при таком варианте P3 "запоминает" прыжок
10.         ;-- этот вариант для обмана P3, чтобы он работал быстрее после прыжка ---
11.     jge @@end    
12.     mov dl,al
13.     mov eax,[esi+ecx]
14.     mov ebx,[edi+ecx]
15.     add ebx,eax
16.     setc al
17.     add ebx,edx
18.     mov [edi+ecx],ebx
19.     jz @@correct2
20.     xor edx,edx
21. @@correct2:
22.     or eax,edx
23.     add ecx,4
24.     jl @@loop
25. @end:

Вот результаты для приведенного выше варианта с "обманом" P3 для разных процев:

Код (Text):

1. Проц____Модель____Gray_____Без прыжков_____Один прыжок
2. P3- 650  6.8.2____1198______688 ([b]74%[/b])_______720-895
3. P4-1800 15.2.4____1374______910 ([b]51%[/b])_______~950
4. P4-1800 15.2.7____1382______809 ([b]71%[/b])_______850-930
5. P4-3000 15.3.4____1680_____1130 ([b]49%[/b])______1230-1245 ;че-то больно крутой и дубовый этот model 3 :)

(На разных моделях 15.2.7 было отклонение цифр ~ 1%, возможно из-за разных паразитов-резидентов, в частности первый раз я приводил соотношение 1400 к 818 = тоже 71%)



PS: Прыжок обеспечивался так: бралось random i в диапазоне 0..126 и полагалось x(i)=0,y(i)=1,x(i+1)=y(i+1)=0.

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

 

leo, в твоем замечательном коде leo_JZ не давало мне покоя одно место - mov dl,al. Хотелось обойтись без этой пересылки. А еще было желание использовать считывания pop-ом. Это дало ускорение, хоть и небольшое. Вот код:

macro leo_JZ_pop2{

xchg esp,esi

lea edi,[4*ecx-4]

xor ebx,ebx

xor edx,edx

align 2 ; for Comp2

; nothing for Comp1

@@loop:

pop eax

mov ebp,[esp+edi]

add ebp,eax

setc bl

add ebp,edx

mov [esp+edi],ebp

jz @@correct1

sub ecx,1

jcxz finish

pop eax

mov ebp,[esp+edi]

add ebp,eax

setc dl

add ebp,ebx

mov [esp+edi],ebp

jz @@correct2

sub ecx,1

jnz @@loop

jmp finish

@@correct1:

or ebx,edx

sub ecx,1

jg @@loop

@@correct2:

or edx,ebx

sub ecx,1

jg @@loop

finish:

xchg esp,esi

}



Твоя идея обмануть P3 очень заманчива. Господи, до чего мы дошли! Уже начинаем задумываться, как обхитрить процессор. Вспомнилась шутка: "Новый чипсет Intel обладает сообразительностью и отличается покладистым характером"



leo >"Интересные эти интелы, то уменьшают число микроопов, то увеличивают - видать ребята в творческом поиске" ....



А не кэш ли и задержки памяти нам тумана подпускают?

 

Привожу последние результаты тестов:



; Новые результаты тестирования после подгонки align и nop:

;____________________Data1_____Data1_____Data2____Data1____Data2____Da ta1____Data2____Data1____Data2

;____________________Comp1_____Comp2_____Comp2____Comp3____Comp3____Co mp4____Comp4____Comp5____Comp5

;Gray_SSE2;____________940_______880______880_________________________ ___________

;leo_JZ_pop2;__________824_______916_____1008______625_____958_______6 25_____1026

;leo_JZ_pop;___________948_______920_____1204_____1034____1432______10 34_____1432

;leo_JZ;_______________824_______924_____1064______657____1307_______6 57_____1432

;gray_pop;____________1092______1100_____1164_____1400____1414______14 00_____1415

;svin_test2;__________1216______1176_____1120_____1459____1473______14 59_____1473

;leo_setc;____________1224______1212_____1232_____1044____1044______10 44_____1044

;leo;_________________1232______1228_____1228______738_____738_______7 66______766

;leo_setc2;___________1300______1272_____1412______796_____796_______7 96______796

;svin_test_gray;______1220______1284_____1280_____1401____1413______14 01_____1413

;svin_test;___________1220______1292_____1272_____1400____1412______14 04_____1412

;Gray;________________1428______1400_____1400_____1033____1033______10 33_____1033

;leo2;________________1428______1400_____1400_____1118____1118______11 18_____1118

;The_Svin;____________1432______1420_____1420_____1119____1119______11 19_____1119

;gray_popall;_________1588______1624_____1624______371_____371_______3 57______357

;

;

;Comp1 - Processor= x86 Family 15 Model 2 Stepping 9 GenuineIntel ~2664 Mhz (Windows XP) 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 - Processor= x86 Family 6 Model 11 Stepping 1 GenuineIntel ~601 Mhz) (Windows 2000 Server) Двухпроцессорный сервер.

;Comp5 - Processor= x86 Family 15 Model 2 Stepping 9 GenuineIntel ~2612 Mhz (Windows XP) Результаты имеют дикий разброс. Возможно проблема в железе компа.



Подробности в исходнике. Обратите внимание на gray_popall!

На младших моделях процессоров он оказался чуть ли не вдвое быстрее всех остальных. Понять бы еще почему Может мы не правильно тестируем?







_695453674__test.asm

 

Gray

> macro leo_JZ_pop2

Тут у тебя "опечатка" закралась: по метке @@correct1 должно стоять or edx,ebx а не or ebx,edx иначе ты теряешь перенос.



> По поводу разных степпингов P4: "А не кэш ли и задержки памяти нам тумана подпускают?"

Память навряд ли, т.к. мы используем несколько проходов и все данные должны быть в кэше. Кэш возможно влияет, но видимо не напрямую, а как-то хитро. Все-таки результаты повторяющиеся, и на 15.2.4 часть методов работает хуже, а часть лучше, чем на 15.2.7 или 15.2.9. И опять же раз есть процы одной модели с одинаковой частотой, но разным степпингом, значит они чем-то различаются (или только микронными технологиями ?)



> "Твоя идея обмануть P3 очень заманчива. Господи, до чего мы дошли!"

Самому не нравится, это было скорее так в плане исследования. А для рабочего метода, как-то некрасиво.

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

Код (Text):

1.     jz @@correct ;в рабочем варианте jc
2.     xor edx,edx
3. @@correct:
4.     or ...

Все равно остается выигрыш до 45-50%, зато менее чувствительно к переходам.



> "Обратите внимание на gray_popall! На младших моделях процессоров он оказался чуть ли не вдвое быстрее всех остальных. Понять бы еще почему Может мы не правильно тестируем?"

Да действительно интересный результат. Но тестируем мы наверное нормально, по крайней мере для относительных сравнений при не слишком малом числе тиков. Это что же получается: даже если брать по максимуму (357..371) / 16 = 22..23 такта на цикл, делим на 8 получаем меньше 3 тактов на сложение без учета POPAD. Фантастика ! А откуда тогда берутся задержки в других методах - за счет переходов или зависимостей ? Может попробовать обычный macro leo развернуть до 8 и использовать разные регистры (может я чего напутал с независимостью, может это только для P4 не зависит).

 

leo > "Тут у тебя "опечатка" закралась: по метке @@correct1 должно стоять or edx,ebx а не or ebx,edx иначе ты теряешь перенос."

Согласен. Спасибо!



А идея обмана процессора мне как раз нравится. Начинаешь относиться к нему не как к тупой и исполнительной железке...



"Может попробовать обычный macro leo развернуть до 8 и использовать разные регистры"



Проверяю. Предварительные результаты по развертке (_flat)

На модели 15.2.4

Gray_flat 1048 (без развертки Gray 1400)

Gray_SSE2_flat 844 (без развертки Gray_SSE2 880)



На модели 6.8.3

Gray_flat 528 (без развертки Gray 1033)



Эвристический вывод - развертка цикла для SSE2 кода дает значительно меньше чем для обычного кода.



leo > "Может попробовать обычный macro leo развернуть до 8 и использовать разные регистры"



На тех же моделях попытка использования разных регистров в варианте leo ничего не дала. Результаты не меняются.

Разворачивать leo еще не пробовал.



Кстати, о варианте gray_popall.

На модели 15.2.4

adc edi,[esp+0x1E0]

mov [esp+0x1E0],edi

немного медленнее чем

adc [esp+0x1E0],edi

, а для модели 6.8.3 ситуация инверсная.

 

Gray

А вот меня заинтриговали фантастические результаты с POPAD на P3. Решил попробовать развернуть цикл macro leo с разными регистрами и в результате вышло, что и без POPAD получаются те же результаты при обычном разворачивании цикла до 32 сложений с использованием 4 регистров.

Код (Text):

1.     shr ecx,2+dd       ;dd=0..3, nn=2^dd = 1,2,4,8 - число повторений блока из 4-х сложений
2.     clc
3. @@loop:
4.     mov eax,[ebx]       ;здесь группировка mov в одном месте дает лучшие рез-ты
5.     mov edx,[ebx+4]  
6.     mov ebp,[ebx+8]
7.     mov esi,[ebx+12]
8.  
9.     adc eax,[edi]       ;adc r32,m32 и mov на P3 быстрее чем adc m32,r32
10.     mov [edi],eax       ;mov лучше сразу после adc, чем несколько adc подряд
11.     adc edx,[edi+4]
12.     mov [edi+4],edx
13.     adc ebp,[edi+8]
14.     mov [edi+8],ebp
15.     adc esi,[edi+12]
16.     mov [edi+12],esi
17.  
18.     ... дальше (nn-1) раз тоже самое с увеличением смещений на 16
19.  
20.     lea ebx,[ebx+16*nn]
21.     lea edi,[edi+16*nn]
22.     dec ecx
23.     jnz @@loop

Вот результаты на P3-650 6.8.1 в зависимости от числа сложений в цикле

Сложений_______4_______8________16_____32__ __Gray__

Циклов________32______16_________8______4__ ___128__

Тиков________582____471;445____420____355__ __1119__

Замечание: При 8 сложениях (двух блоках по 4) получается, что выравнивание на 16 работает несколько хуже (471), чем со смещением на 2 байта (445). (Я и раньше такую фигню наблюдал и пришел к выводу, что потери возникают, когда какая-то критичная команда разбивается следующей границей 16 байт, поэтому бывает лучше сдвинуть начало цикла. Однако похоже тут все хитрее, т.к. и в других случаях происходит разбивка, а вот заметных потерь нет).



Что же получается ? На P3 инструкция ADC работает достаточно быстро, по крайней мере в потоке команд ? На P4 этот код тоже дает улучшение, но не столь значительное (на 15.2.4 и 15.2.7 получилось одинаково 1146 против ~1380 Gray). Как-то все хитро и довольно запутанно с этими кэшами, предвыборками и предсказаниями.

 

leo

>"здесь группировка mov в одном месте дает лучшие рез-ты"



Вот и у меня есть ощущение (вопреки логике), что массовые чтения из памяти часто оказываются быстрее чем чтение по частям, потому и стал экспериментировать с popa. Вот поглядываю на CMPXCHG8B, может выйдет из этого прок



leo >"Я и раньше такую фигню наблюдал и пришел к выводу, что потери возникают, когда какая-то критичная команда разбивается следующей границей 16 байт, поэтому бывает лучше сдвинуть начало цикла."



Очень похоже на правду, добавлю еще свое подозрение, что джамп назад на четное (или кратное четырем?) число байт быстрее чем джамп назад на нечетное число байт.

 

О развороте цикла.



Если разложить все по полочкам, как учит TheSvin, то выдающиеся результаты по развертке цикла на P3 станут более или менее понятными.

Что мы имеем: метод Gray дает на P4 (model 2) ~1400 тиков / 128 = 11 тиков на цикл. Это вполне соответствует IA-32: 2 тика на загрузку 2 чисел из памяти + 8 тиков ADC + 1 на общие расходы с учетом возможностей параллельного исполнения LEA и DEC во время ADC и сохранения рез-та. Предсказанный переход для P4 вообще не имеет задержки. На P3 тот же код дает около 9 тиков на цикл. Значит инструкция ADC работает быстрее и занимает 4-5 тактов. При элементарном развороте цикла по первому методу leo имеем ~740/32 = 23 такта на 4 сложения. Видимо задержки на загрузку\выгрузку "съедаются" за счет совмещения с ADC, но сами ADC по прежнему выполняются последовательно (уж не знаю почему). При разворачивании цикла с использованием 4 регистров и группировкой загрузки удается "убедить" процессор начинать следующую ADC не дожидаясь завершения предыдущей и задержка уменьшается до 355/32 = 11 тактов на 4 сложения. При этом 8 тактов "вынь да положь" на загрузку 4*2 чисел + 3 такта на прочие нераспаралеленные микроопы. Если порисовать диаграммы, то все нормально умещается да еще с запасом (если учесть, что сохранение идет в буфер записи параллельно с загрузкой).



В таком случае, какие возможности мы имеем для P4. Согласно IA-32 ADC имеет задержку 8 тактов и максимальный темп поступления 3 такта. В этом случае для 4 чисел получается предел 3*4=12 тактов (т.е. в сумме 384), при условии, что все ADC выполняются с перекрытием и параллельно с MOV.

Интересный вопрос - как это сделать ? Как "уговорить" P4 грузить данные во время вычислений (это наверное не проблема) и начинать следующую ADC не позднее 3-4 тактов после начала предыдущей ?