Сравнение чисел в ММХ

Привет всем!



Подскажите пожалуйста, как правильно пользоваться командами

сравнения MMX ? Вернее, что делать с результатом сравнения ?



У меня задача - необходимо проверить множество пар чисел на

попадание в диапазоны {min1, max1} {min2, max2} соответственно.

Все min и max - статичные.

Если оба числа попадают в свои диапазоны, то делать одно,

если хотя-бы одно из чисел не попало в свой диапазон, то другое.



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

результатом проверки ? Ведь команды сравнения ММХ не

модифицируют флаги. . . Только заполняют либо 0 либо 1 все разряды

соответствующей части . . .

Я ничего лучше не придумал, как помещать результат в EAX и уже

его анализировать . . .



Вот мой код:



Подготовка в начале цикла:

Код (Text):

1.  
2. WORD Bounds[4] = { min1, max1, min2, max2}; //64 битное число с границами
3. movq mm7,Bounds ; помещаем его в регистр mm7
4.  

Тело цикла: (числа - WORD'ы)

Код (Text):

1.  
2. movd    mm0,Num1    ;берем первое число
3. punpcklwd mm0,mm0   ;дублируем его в младшей части
4. psllq   mm0,32      ;сдвигаем в старшую часть
5. movd    mm1,Num2    ;берем второе число
6. punpcklwd mm1,mm1   ;дублируем его в младшей части
7. por mm0,mm1     ;скалываем и получаем в старшей части
8.             ;2 раза первое число, в младшей 2 раза второе
9. pcmpgtw mm0,mm7     ;сравниваем с границами
10.  
11. packsswb mm0,mm0    ;упаковываем результат сравнения
12. movd eax,mm0        ;помещаем его в EAX
13. cmp eax,0x00FF00FF  ;сравниваем EAX с 0x00FF00FF
14.             ;если EAX == 0x00FF00FF, то оба числа попали
15.             ;в свои диапазоны, иначе хотя-бы одно не попало
16. je  l1
17.  
18. ;Здесь делаем то, что надо если числа не попали
19. ;в диапазоны
20.  
21. l1:
22. ;Здесь делаем то, что надо если числа попали
23. ;в диапазоны
24.  

Может кто подскажет как лучше сделать . . .



И еще, я заметил, что само вычисления попадания чисел

в диапазоны делаеться в 2 раза быстрее чем 1 инструкция je l1 :-(((

Можно ли это как-то ускорить ? Почему переход такой медленный



Заранее благодарен!



С уважением, Василий.

 

попробуй выровнять сам je и метку - иногда помогает

 

> "Почему переход такой медленный"

А о каком процессоре идет речь ?

Во-первых, на пентиумах задержка непредсказанного перехода сравнима с длиной конвеера: на P2,P3 - это около 10 тактов, на P4 - около 20. Если код отрабатывает не однократно, а крутится в цикле, то все зависит от предсказуемости чередования переход\не переход. В этом случае могут возникать задержки и при отсутствии перехода по je: процессор на основании истории переходов считает что переход будет и заранее грузит код в конвейер, а перехода то и нет..

Во-вторых, masquer правильно говорит, что иногда помогает выравнивание je и метки перехода. Но если помогает, то редко и максимум на 1-2 такта и здесь, видимо, не тот случай. Редко и мало, потому что это связано с работой декодера: если байты первой-второй инструкции разбиваются границей выравнивания кэша инструкций, то приходится подгружать новую линию с соответствующей задержкой декодирования. На циклах в P4 это вообще мало сказывается, т.к. декодирование инструкций цикла осуществляется один раз и кэшируются декодированные микрооперации.



> "как лучше сделать...", "можно ли это как-то ускорить ?"

Ускорить само сравнение видимо можно на P4, если отказаться от ММХ и сравнивать на 32битных регистрах. Но на P2,P3 это точно ничего не даст. Тут главное как "бороться" с задержкой перехода и возможно ли это вообще ? Если в цикле, и данные коррелированы, то может и ничего страшного, если пеньку удастся многое угадать.

 

Тело цикла можно придумать и примерно таким

Код (Text):

1. ; ax  - Num1
2. ; ecx - min1:max1
3.  
4.   sub     cx,ax
5.   shld    eax,ecx,16
6.   cmp     ax,cx
7.   jnc     l1
8.  
9. l1: ;Здесь делаем то, что надо если числа попали в диапазоны

 

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

 

Проверка будет быстрее если использовать 32-х битные регистры

Код (Text):

1. ; eax - Num1    ; 0x00001500
2. ; ecx - min1    ; 0x00001000
3. ; edx - max1    ; 0x00002000
4.  
5. sub edx,eax
6. cmp ecx,edx
7. jc  l1  ; переход если не попало в диапазон

 

Всем спасибо за советы!

А зачем тогда есть команды сравнения ММХ? Приведите мне хоть один пример, где они будут полезны ?

Сделал как посоветовал bogrus, и получил довольно странные результаты . . .

Дело в том, что у меня код этот в виде ассеблерной вставке в C проекте используеться.

Откомпилировал компилятором Микрософта и сравнил со своим кодом на ММХ - разницы почти никакой (в 1-2%).



Откомпилировал то-же самое компилятором IntelCPP 8.0. Версия от bogrus'а стала быстрее на 30%. Моя ММХ версия стала медленнее на 40% !!!

Чем такое объяснить.



И вообще, я заметил, что подпрограммы на ММХ откомпилированные Интеловским компилятором выполняються медленнее, чем откомпилированные Микрософтовским компилятором.



Проверял на PIII 800 и PIV 2400.

 

А зачем тогда есть команды сравнения ММХ? Приведите мне хоть один пример, где они будут полезны ?



пример рендеринг в софте с прозрачностью.



по сравнению щитаются битовые маски, потом паралеьно щитаются цвета для z>z_buf и z<z_buf затем делаем на один pand а на другой pandn, затем por и запишем результат.

я так делал, у меня было 262 такта на 8 пикселей по шине, быстрее в память проц не стучался, и это помогало - 0 ветвлений.

 

В варианте bogrus "притаилась" ошибочка. Стоит взять min1 < max1-Num1 и получим неверный результат. Этот вариант можно использовать если вместо min1 хранить разность max1-min1.

 

SolarWarez > стала быстрее.., стала медленнее... Чем такое объяснить ?



1) возможно некорректными замерами: влиянием окружающего "оформления", огромными непредсказуемыми задержками при первом проходе (когда данные и код еще не в кэше) и т.д. и т.п.

2) разное выравнивание кода и данных; без специального выравнивания возможно "неудачное" положение начала цикла или Jcc относительно границы 16 байт (особенно заметно на PII,PIII), а с выравниванием - может влиять задержка на нопах или их "эквивалентах".

3) что касается MMX, то возможно Intel проявляет заботу и вставляет EMSS (6 тиков на P3 и 12 на P4) там где его не просят, а микрософту и борланду вроди бы до лампочки, что ты там в асм-вставках пишешь.



Чтобы разобраться с 2) и 3) надо бы сравнить реальные куски кода в отладчике или дизасме.

 

Точно, прошу прощения, кстати у SolarWarez случаем не должно быть cmp eax,0xFF00FF00 ?

 

Вот максимум, что мне удалось накрутить (9 тактов на моем celeron 667MHz)

Код (Text):

1. ;===================================================================== ==
2. xmin        dd      min1             ; word
3. xmax        dd      max1-min1        ; word
4. ymin        dd      min2             ; word
5. ymax        dd      max2-min2        ; word
6. ;===================================================================== ==
7. ; esi       dw      множество пар чисел num1,num2,num1,num2 ...
8. ; edi       =       ($-esi)/4        ; для dec edi/jnz след. пара
9. ;===================================================================== ==
10.         movzx   eax,word [esi]
11.         sub     eax,[xmin]
12.         cmp     [xmax],eax
13.         sbb     ecx,ecx
14.         movzx   eax,word [esi+2]
15.         add     esi,4        ; для следующей пары
16.         sub     eax,[ymin]
17.         cmp     [ymax],eax
18.         adc     ecx,ecx
19.         jz      _inbound         ; если пара попала в свои диапазоны
20. ;=======================================================================

 

Можно сделать неветвящийся код :

после каждого сравнения собирать

бит очередного признака сравнения в маску.

После 4-х сравнений получим

4 битный код - далее таблица с 16-ю

адресами перехода. Возможно конечно,

что такой переход тоже долго будет выполняться.

Более сложный вариант : делаем только

сравнение и строим массив индексов чисел

для "первой" и "второй" обработки.

Потом быстренько обрабатываем

сначала все "первые" числа, потом "вторые",

если конечно они не завязаны друг на друга.

 

А если по 2 word сравнивать обычными регистрами ?

http://www.wasm.ru/forum//index.php?action=vthread&forum=17&topic=4854

 

.

 

bogrus > "Вот максимум, что мне удалось накрутить"

Да у меня на P3-800 (модель 6.8.6) тоже твой вариант дает 9 тиков без выравнивания и 8 тиков с выравниванием начала цикла.

Что интересно, на P4 этот вариант дает те же 9 тиков на цикл. Несмотря на тормозные adc\sbb (латентность 8 тиков) все видимо прекрасно перекрывается за счет отсутствия зависимости по данным. Хотя возможно при наличии перехода задержка на adc и проявится.



Те же результаты получаются и без adc\sbb при использовании классической проверки: inbound:=((x-min) < 0) xor ((x-max) < 0):

Код (Text):

1.     movzx eax,word [esi]
2.     movzx edx,word [esi+2]
3.     mov   ecx,eax
4.     add   esi,4
5.     sub   ecx,[xmin]  
6.     sub   eax,[xmax]  
7.     xor   eax,ecx      ;знаковый бит, если внутри диапазона
8.  
9.     mov   ecx,edx
10.     sub   ecx,[ymin]
11.     sub   edx,[ymax]
12.     xor   edx,ecx
13.     and   edx,eax     ;оба результата со знаком
14.     js    _inbound    ;если пара попала в свои диапазоны

На P3 с выравниванием 8 тиков, на P4 - 9 тиков независимо от выравнивания.

<font color="gray]<font size=2>Хотя на P4 заметил такую хитрость: если закомментировать переход js и вместо dec edi использовать sub edi,1 (декремент счетчика), то получаем сразу экономию в два такта (7 тиков). Спрашивается почему, если регистровая логика выполняется за 0.5 такта, а предсказанный переход - 0 ? Не может же процессор пропускать "ненужные" операции..</font><!--size--></font><!--color-->



PS: Всетаки мне думается оптимизация сравнения в данном случае мало что дает, т.к. главным тормозом будут переходы и возможно сами действия, которые нужно выполнить по результатам сравнения. Если бы задача стояла конкретнее, то можно было бы что-то анализировать, как уменьшить влияние переходов, а так, в общем, могут быть только одни фантазии...

 

leo

Да, смысла нет, т.к. не ясно какие действия будут выполнятся по переходу, и зная диапазоны (если учитывать пары случайными числами), то возможно сыграть на переходах, т.е. попадание чисел в оба диапазона, может быть очень маловероятным. Но черт, инструкции MMX довольно шустрые, хотя заметил (объяснить не могу), что первая MMX инструкция, не всегда, но часто отбирает за 5000 тиков

 

Или может я чего с кешем намутил, но первый проход в mmx.exe почти всегда за 5000

_157749874__test.zip

 

bogrus > "не всегда, но часто отбирает за 5000 тиков"



На P4 твои тесты, что "eax", что "mmx" съедают более 4500 тиков на всех проходах !!! Это на цикл из 16 без переходов по условию => до 300 тиков вместо 9-12 на цикл !!!



Какая-то хрень с кэшированием, но не могу понять в чем дело. Попробовал два варианта, которые ставят все на место и дают "нормальный" результат (~280 тиков для "mmx", ~220 для "eax" и ~190 для "xor" при отсутствии переходов по Jcc):

1) разнести данные и код по секциям (4 кб)

2) сдвинуть start на границу >= 1 кб (вставкой align 0400h или фиктивных данных).



Но чем это объяснить не знаю.

Данные+код+импорт в сумме около 1 кБ, т.е. все адреса должны быть в одном ассоциативном множестве и не должны вытеснять друг друга. Чтобы код не попадал в одну строку кэша с данными достаточно разнести их на 64 байта, а тут приходится на 512 и более. Что за чертовщина ?

 

Ого, у меня (6.8.6) была такая картина:

Код (Text):

1. --------------------------- ---------------------------
2. MMX 70 bytes , 10 passes    EAX 77 bytes , 10 passes
3. --------------------------- ---------------------------
4. 000000[b]5[/b]844                  0000000863
5. 0000000176                  0000000190
6. 0000000146                  0000000162
7. 0000000146                  0000000162
8. 0000000146                  0000000162
9. 0000000146                  0000000162
10. 0000000146                  0000000162
11. 0000000146                  0000000162
12. 0000000146                  0000000162
13. 0000000146                  0000000162
14. --------------------------- ---------------------------
15. OK                          OK
16. --------------------------- ---------------------------

Причем стабильно 162 на 16 пар если выбрать все пары "попадающими" или наоборот "не попадающими" в диапазоны (или если распределить попадания поровну), а если например выбрать 13 пар непопадающими, а 3 попадающими, то кол-во тиков увеличивается до 230.

А разброс по разным секциям и другие варианты выравнивания только ухудшают ситуацию (не намного, 2-12 тиков). Вечером попробую P4 найти потестить