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 > „А оптимизируем мы самое то, что надо - операцию "+=" “

А надо ли ?!
На всякий случай повторю свои мысли:

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

Т.о. задачу можно свести к параллельному вычислению:
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 > „В реальной задаче надо вычислять: y+=z; z+=d; где d - число большое - 500-1000 бит.“

Я уже окончательно запутался.
В прошлый раз, в качестве "реальной задачи", был приведён код вычисляющий квадраты чисел натурального ряда.
Код содержал ошибку, которую я исправил (?), так и получился мой код выше.
Этот вариант IMHO поддаётся неплохой оптимизации, просто за счёт уменьшения количества операций с памятью.
Одно из слагаемых - 2 - свободно помещается в один операнд (причём байтовый).
Далее нужно только отслеживать перенос, т.е. больше никаких непосредственных операндов нет.
При этом оба сложения можно будет производить параллельно, что так же должно увеличить скорость, поскольку мы избегаем хранения промежуточного результата в памяти.

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

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


К чему всё это я пишу.
Я не знаю, что интересно остальным участникам форума, но лично мне интересно решать реальные задачи.
Поскольку только в этом случае можно использовать свойства обрабатываемых данных.
Если же решать "задачу вообще", то ни о какой оптимизации по скорости не может идти речи, так как
для больших объёмов данных используют одни методики, а для небольших (500 - 1000 бит) - совершенно другие, это как минимум.


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

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


Shur > „цитата из 22007.pdf про nop:“

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


ЗЫ
Про „ NOP выполняется дольше чем xchg ax,ax на 86м“ я только сейчас понял %))

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:

	sub esi,edi
	xor edx,edx
	mov ebx,1
@@loop:
	mov eax,[edi+esi]
	add eax,edx
	jc @@carry	;перенос возможен только при edx = 1 => обнулять не нужно
	xor edx,edx
@@carry:
	add [edi],eax
	cmovc edx,ebx
	add edi,4
	dec ecx
	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 и должна быть во всех более старших моделях. А как насчет атлонов ?

INSTRUCTION SET REFERENCE, A-M
CMOVcc—Conditional Move (Continued)

The CMOVcc instructions were introduced in the P6 family processors;
however, these instructions may not be supported by all IA-32 processors.

Вижу стараниями leo приоритетом всё таки выбрана оптимизация под P4 без учёта мнения автора вопроса.
Вот сумел же человек, поставить свои приоритеты в чужом монастыре. Одно можно сказать тролли как и мафия бессмертны. О чём бы не говорили сумел ведь повернуть так, что если для P4 не актуально, то не очень и важно.
В результате все усилия направлены на поиск оптимизации под эту маразматичную модель.
Интересно, существует ли на борде хоть один проффессионал низкоуровник, работа которого именно оптимизация библиотек под P4?
Другой вопрос, существует ли, либо появится в будущем аналог фидошного твита на борде.