Быстрый поиск в массиве

Да в своем примере я допустил ошибку.

Но вот новый - без лишних прибамбасов

Код (Text):

1.  
2.         mov     esi,offset tvoi-massiv
3.         mov     ecx,razmer_masiva+4
4. s1:
5.         sub     ecx,4
6.         jz      konetc_masiva
7.         mov     eax,dword ptr [esi]
8.         add     esi,4
9.         shr     eax,10h
10.         xor     eax,55aah
11.         jnz     s1
12. ;
13. ;
14. ; Инструкции по нахождению 55aah
15. ;
16.         jmp     s1 ; это если еще надо находить
17. konetc_masiva:
18.  

 

/Вроде бы нужно искать 55h, 0AAh. Но не это важно./



Никто не гарантирует, что искомый паттерн будет именно в 2х старших байтах DWORD'а !





Кстати, делать 2 одинаковые операции не обязательно, можно одну убрать:

Код (Text):

1.         mov     ecx,razmer_masiva+4
2. s1:
3.         sub     ecx,4
4.         jz      konetc_masiva
5.         mov     eax,dword ptr [esi+ecx]
6. ;        add     esi,4
7.         ......

ЗЫ

А вообще, MSVC (2k3) при включенной оптимизации вполне сносный код выдаёт:

Код (Text):

1.     char *source;
2.     long foo;                       // trick compiler to use register
3.  
4.     while( (char)(foo = *(unsigned short*)source++) )   // & movzx
5.     {
6.         if( 0xAA55 == foo )
7.             goto found;
8.     }

ЗЫЫ

Вот хороший документ по оптимизации. Английский, но всё понятно.

 

boozook >

Да, наверное лучше так.. Где-то на 2 линейки делать предвыборку.

Я как-то не подумал, что остальные могут и не понадобиться .

 

S_T_A_S_,

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

Agner Fog: On P1 and PMMX, misaligned data will take at least 3 clock cycles extra to access if a 4-

byte boundary is crossed. The penalty is higher when a cache line boundary is crossed. On

PPro, P2 and P3, misaligned data will cost 6-12 clocks extra when a cache line boundary is

crossed. Misaligned operands smaller than 16 bytes that do not cross a 32-byte boundary

give no penalty. On P4, there is little or no penalty for misaligned operands smaller than 16

bytes if reads do not occur shortly after writes to the same address. Unaligned 128 bit (16

bytes) operands can only be accessed with the MOVDQU instruction or with two separate 64-

bit operations.

 

Достаточно? успешно:

Мои замечание больше относилось к использованию ax - 16битные команды медленные (Fog вроде бы про это писАл).

Лучше для этих целей movzx использовать - размер команды такойже, но это полноценная 32разрядная команда.

 

misaligned data will cost 6-12 clocks extra when a cache line boundary is crossed

Ну, если мы делаем предвыборку, то заодно можно и это предусмотреть, а если нет то эти 6-12 тактов ничего не решают



16битные команды медленные

В каком смысле? С чем связаны задержки? С префиксом переопределения размера... Возможно, я точно не знаю, но вроде подобного рода потери возникают при последоватльном исполнении пар операций записи-чтения пересекающихся ячеек памяти/частей регистра.

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

 

Ладно, Fog может и авторитет, но

вот что говорит intel:

вот что говорит AMD:

По поводу префиксов же у меня откуда-то устойчивое мнение, что они тормозят.

Видимо из старых мануалов. Вот что нашёл в более-менее современых доках:

Аргументы довольно туманны - про короткие инструкции ничего не написАно, но говорят - не пользуйтесь :/



Пришлось, как всегда всё проверять самому =)

В общем, видно, что вся эта теория пишется для каких-то обобщённых случаев, в реале же рулит AMD CodeAnalyst

358623305__mov.PNG

 

Вот как сделать с scasb и стокой для поиска произвольной длинны. Работать должно еще быстрее, особенно если еще оптимизировать.

Код (Text):

1.     mov   ecx,1024*1024 //размер буфера
2.     mov   edi,mem //адрес буфера
3. @continue:
4.     mov   esi,sr //адрес строки для поиска
5.     mov   al,[esi]
6.     cld
7.     repnz scasb
8.     jnz   @notfound
9.  
10.     inc esi
11.     mov   edx,1 //длинна строки для поиска-1 (т.е. длнна==2)
12. @loop:
13.     mov   al,[edi]
14.     mov   bl,[esi]
15.     cmp   al,bl
16.     jnz   @continue
17.     inc   esi
18.     inc   edi
19.     dec   edx
20.     jnz   @loop
21.     sub   edi,2 //2==длинна строки для поиска
22.     //теперь в edi - адрес найденного вхождения
23.    
24. @notfound:
25.  

 

S_T_A_S_

"в реале же рулит AMD CodeAnalyst"

Секундомер рулит ,хотя, конечно, можно довериться и системным часам.

В общем процессор Celeron-Willamette, мой первый вариант(без оптимизаций под кэш и прочего) работает в два раза быстрее одного "repne scasb", простая замена "cmp [edi+xx],ax" парой "movzx/cmp" ничего не дает...



"про короткие инструкции ничего не написАно, но говорят - не пользуйтесь"

Если префикс OS действительно дает задержку, наверное имеет смысл использовать cmp [edi],al

ЗЫ все-таки там "не написано" )

 

Tellur >

Дык можно же просто:

Код (Text):

1.  
2.     mov   al,[edi]
3.     cmp   [esi],al
4.     jnz   @continue

boozook >

Зачем 2мя? одного должно хватить, но то что это не даст выигрыша в ланном случае я уже понял (см. картинку)

Там видно, что и одиночный префикс задержки тоже не даёт..





IMHO самым быстрым будет всёже такой поиск:



xor eax, 55555555h

lea edx, [eax-01010101h]

......



Но для оптимальной оптимизации нужно знать вероятности появления байтов 055h, 0AAh по отдельности и вмете, чтобы знать какой искать первым и можно ли искать их сразу оба.

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



ЗЫ

Щас как раз пишу прогу которая в частности ищет всякие там 0A0Dh, дык никаких извращений не использую, т.к. для меня очевидно, что это будет занимать ~2% от общего времени работы .



ЗЫЫ

Да, написАно - это круто %)

 

S_T_A_S_

"IMHO самым быстрым будет всёже такой поиск"

Честно говоря, сомнительно - не вникая в подробности, сразу видно, что основной цикл будет выполняться как минимум 5 тактов(ибо зависимости), т.е. скорость поиска меньше байта за такт(со scasb'ом наверное 1байт/такт). Можно попробовать и здесь "распараллелить", но тут и с регистрами напряг будет, да и вообще стремно как-то... но хуже от этого точно не станет



Зачем 2мя? одного должно хватить

Имелось ввиду "одной парой команд"



(см. картинку)

CodeAnalyst. Качал как-то себе эту штуку... не найти, затерялась куда-то. А как она анализирует, только для АМД, основываясь на теории? или с любым процом может скорость меррить?

 

boozook >

Это медленная команда как на intel так и на AMD (latency 4 такта)

Вообще, в том моём варианте возможно и ошибки есть

Но это самый быстрый способ поиска байта в больших объёмах памяти (+ prefetch конечно) по моим опытам.





CodeAnalyst - это симулятор, так что возможно будет работать и на не-AMD процах, но я не проверял.

Прога полезная, в графике показывает состояние пайпа, видно какие команды от чего зависят и какие тормозят.

Кстати, порой расходится с теорией (или я просто что-то не так понимаю).

Для intel есть VTune - она и по объёму больше, и не бесплатная, но я не смотрел даже..

 

хм пока меня не было стока случилось

люди прежде чем что то выкладывать проверяете - некоторые коды не находят 55AAh например в таком масиве

some_array db 12,35,55,55,AA,34,0A,99

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

 

"Это медленная команда"

хм.. выходит строковые команды тормозят даже с префиксом повторения



"Но это самый быстрый способ поиска байта в больших объёмах памяти (+ prefetch конечно) по моим опытам"

Да, и по моим тоже быстрее выходит. Можно еще с MMX пробовать ускорить.



Same

Вообще-то тут люди не только код выкладывают... не мешало бы и комментарии к нему почитать

 

AFAIK на PIV строковое копирование ускоряется аппаратно - по-видимому осущствляетя без превлечения ядра (ALU и т.п.)

(на Athlon такого нет - там movs медленный, быстрее копировать просто "разложив эту команду на составляющие".)



scasb же влияет на флаги, поэтому тут без ядра не обойтись - приходится раскладывать команду на несколько микроопераций, и выполнять уже их.

Поэтому и получается, что "обычные" команды работают как правило быстрее.

Здесь под "обычными" я понимаю команды, которые состоят из 1-2 микроопераций и способны за счёт этого паралелиться с другими.

У AMD для таких команд применяется термин Direct Path (для первых Vector Path).

У intel подобного чёткого деления нет, но всё равно можно проследить деление команд на 2 подобные группы.



Всё идёт от того, что процессоры внутри имеют RISC архитектуру.

Direct Path команды - это похоже те, которые имеют непосредственные RISC аналоги,

а для выполнения Vector Path запускается "подпрограмма" в microcode ROM, таким образом все ресурсы процессора идут на выполнение этой одной команды, а остальные ждут.