|
| Посл.отвђт | Сообщенiе |
|
|
Дата: Сен 8, 2004 22:33:01 Если использовать scasb, придется дополнительно проверять второй байт. |
|
|
Дата: Сен 8, 2004 23:12:34 придется дополнительно проверять второй байт Да и еще ecx на ноль, но это же лучше двух проходов ;) |
|
|
Дата: Сен 8, 2004 23:28:13 Если размер строки большой (мегабайты) нужно оптимизировать под кеш - сначала читать блок, скажем 128Кб, потом уже искать в нём каким нибудь хитрым способом. А тут же маленький пакет, просто тупо искать: mov esi, pointer_to_string
mov edx, 0AA55h
align 16
loop: movzx eax, word[esi] ; именно так
inc esi
cmp eax, edx
jz found
test al, al
jnz loop
zzzyab Оригинальный способ заполнения области памяти :). |
|
|
Дата: Сен 8, 2004 23:49:09 „скажем 128Кб“ Скорее байт - линейка обычно 64 байта. Пока просматриваем одну нужно делать prefetch на следующую, и т.д. Наверно так... ...Да и ecx на ноль после scasbа все-таки можно не проверять, если в конец строки записать например 0 |
|
|
Дата: Сен 9, 2004 00:36:19 · Поправил: S_T_A_S_ boozook > „должно быть быстрее в разы“ IMHO не будет оно быстрее, там куча 16-битных операций над невыровненными данными ( cmp [edi],ax ) Параллелить, это как-нибудь так (без учёта длины!): .1: mov eax, [esi]
.2: add esi, 4
xor eax, 55555555h
lea edx, [eax-01010101h]
not eax
and edx, 80808080h
and edx, eax
jz .1
lea ebx, [eax-01010101h]
not eax
and ebx, 80808080h
and ebx, eax
jnz доп_проверка ; DWORD содержит одновременно 55h и 0AAh
; нужно отдельно проверить, что это именно 55h,AAh, но мне лень :)
; вариант пересечения DWORD
test edx, edx
mov eax [esi]
jns .2
cmp al, 0AAh
jz .2
found: |
|
|
Дата: Сен 9, 2004 01:08:32 · Поправил: zzzyab Да в своем примере я допустил ошибку. Но вот новый - без лишних прибамбасов
mov esi,offset tvoi-massiv
mov ecx,razmer_masiva+4
s1:
sub ecx,4
jz konetc_masiva
mov eax,dword ptr [esi]
add esi,4
shr eax,10h
xor eax,55aah
jnz s1
;
;
; Инструкции по нахождению 55aah
;
jmp s1 ; это если еще надо находить
konetc_masiva:
|
|
|
Дата: Сен 9, 2004 02:33:57 · Поправил: S_T_A_S_ /Вроде бы нужно искать 55h, 0AAh. Но не это важно./ Никто не гарантирует, что искомый паттерн будет именно в 2х старших байтах DWORD'а ! Кстати, делать 2 одинаковые операции не обязательно, можно одну убрать: mov ecx,razmer_masiva+4
s1:
sub ecx,4
jz konetc_masiva
mov eax,dword ptr [esi+ecx]
; add esi,4
......
ЗЫ А вообще, MSVC (2k3) при включенной оптимизации вполне сносный код выдаёт: char *source;
long foo; // trick compiler to use register
while( (char)(foo = *(unsigned short*)source++) ) // & movzx
{
if( 0xAA55 == foo )
goto found;
}
ЗЫЫ Вот хороший документ по оптимизации. Английский, но всё понятно. |
|
|
Дата: Сен 9, 2004 03:03:18 boozook > „Скорее байт - линейка обычно 64 байта. Пока просматриваем одну нужно делать prefetch на следующую, и т.д. Наверно так...“ Да, наверное лучше так.. Где-то на 2 линейки делать предвыборку. Я как-то не подумал, что остальные могут и не понадобиться :). |
|
|
Дата: Сен 9, 2004 12:03:48 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. |
|
|
Дата: Сен 9, 2004 18:42:37 Достаточно? успешно: „misaligned data will cost 6-12 clocks extra when a cache line boundary is crossed.“ Мои замечание больше относилось к использованию ax - 16битные команды медленные (Fog вроде бы про это писАл). Лучше для этих целей movzx использовать - размер команды такойже, но это полноценная 32разрядная команда. |
|
|
Дата: Сен 9, 2004 21:19:13 misaligned data will cost 6-12 clocks extra when a cache line boundary is crossed Ну, если мы делаем предвыборку, то заодно можно и это предусмотреть, а если нет то эти 6-12 тактов ничего не решают ;) 16битные команды медленные В каком смысле? С чем связаны задержки? С префиксом переопределения размера... Возможно, я точно не знаю, но вроде подобного рода потери возникают при последоватльном исполнении пар операций записи-чтения пересекающихся ячеек памяти/частей регистра. Лучше испробовать различные варианты на разных процессорах, а из теории иметь ввиду только некоторые общие моменты оптимизации... А так сразу не скажешь что быстрее - нужно измерять |
|
|
Дата: Сен 10, 2004 00:59:13 Ладно, Fog может и авторитет, но вот что говорит intel: „Assembly/Compiler Coding Rule 17. (H impact, H generality) Align data on natural operand size address boundaries For best performance, align data as follows: • Align 8-bit data at any address. • Align 16-bit data to be contained within an aligned four byte word. • Align 32-bit data so that its base address is a multiple of four. • Align 64-bit data so that its base address is a multiple of eight. • Align 80-bit data so that its base address is a multiple of sixteen. • Align 128-bit data so that its base address is a multiple of sixteen.“ „Operand Sizes The Pentium 4 processor does not incur a penalty for partial register accesses as did the Pentium II and Pentium III processors, since every operation on a partial register updates the whole register. However, this does mean that there may be false dependencies between any references to partial registers.“ „Assembly/Compiler Coding Rule 48. (M impact, MH generality) Break dependences on portions of registers between instructions by operating on 32-bit registers instead of partial registers. For moves, this can be accomplished with 32-bit moves or by using movzx.“ вот что говорит AMD: „✩ Align Data Where Possible In general, avoid misaligned data references. All data whose size is a power of two is considered aligned if it is naturally aligned. For example: ■ Word accesses are aligned if they access an address divisible by two. ■ Doubleword accesses are aligned if they access an address divisible by four. ■ Quadword accesses are aligned if they access an address divisible by eight. ■ TBYTE accesses are aligned if they access an address divisible by eight. A misaligned store or load operation suffers a minimum onecycle penalty in the AMD Athlon processor load/store pipeline. In addition, using misaligned loads and stores increases the likelihood of encountering a store-to-load forwarding pitfall.“ По поводу префиксов же у меня откуда-то устойчивое мнение, что они тормозят. Видимо из старых мануалов. Вот что нашёл в более-менее современых доках: „Prefixed Opcodes On the Pentium II and Pentium III processors, avoid the following prefixes: • lock • segment override • address size • operand size On Pentium II and Pentium III processors, instructions longer than seven bytes limit the number of instructions decoded in each cycle. Prefixes add one to two bytes to the length of instruction, possibly limiting the decoder. Whenever possible, avoid prefixing instructions. Schedule them behind instructions that themselves stall the pipe for some other reason.“ Аргументы довольно туманны - про короткие инструкции ничего не написАно, но говорят - не пользуйтесь :/ Пришлось, как всегда всё проверять самому =) В общем, видно, что вся эта теория пишется для каких-то обобщённых случаев, в реале же рулит AMD CodeAnalyst :)  358623305__mov.PNG |
|
|
Дата: Сен 10, 2004 12:57:39 Вот как сделать с scasb и стокой для поиска произвольной длинны. Работать должно еще быстрее, особенно если еще оптимизировать. mov ecx,1024*1024 //размер буфера
mov edi,mem //адрес буфера
@continue:
mov esi,sr //адрес строки для поиска
mov al,[esi]
cld
repnz scasb
jnz @notfound
inc esi
mov edx,1 //длинна строки для поиска-1 (т.е. длнна==2)
@loop:
mov al,[edi]
mov bl,[esi]
cmp al,bl
jnz @continue
inc esi
inc edi
dec edx
jnz @loop
sub edi,2 //2==длинна строки для поиска
//теперь в edi - адрес найденного вхождения
@notfound:
|
|
|
Дата: Сен 10, 2004 14:49:40 S_T_A_S_ "в реале же рулит AMD CodeAnalyst" Секундомер рулит :) ,хотя, конечно, можно довериться и системным часам. В общем процессор Celeron-Willamette, мой первый вариант(без оптимизаций под кэш и прочего) работает в два раза быстрее одного "repne scasb", простая замена "cmp [edi+xx],ax" парой "movzx/cmp" ничего не дает... "про короткие инструкции ничего не написАно, но говорят - не пользуйтесь" Если префикс OS действительно дает задержку, наверное имеет смысл использовать cmp [edi],al ЗЫ все-таки там "не написано" :)) |
|
|
Дата: Сен 10, 2004 20:09:12 · Поправил: S_T_A_S_ Tellur > „ mov edx,1 //длинна строки для поиска-1 (т.е. длнна==2)
@loop:
mov al,[edi]
mov bl,[esi]
cmp al,bl
jnz @continue
inc esi
inc edi
dec edx
jnz @loop“
Дык можно же просто:
mov al,[edi]
cmp [esi],al
jnz @continue
boozook > „первый вариант(без оптимизаций под кэш и прочего) работает в два раза быстрее одного "repne scasb", простая замена "cmp [edi+xx],ax" парой "movzx/cmp" ничего не дает... “ Зачем 2мя? одного должно хватить, но то что это не даст выигрыша в ланном случае я уже понял (см. картинку) Там видно, что и одиночный префикс задержки тоже не даёт.. IMHO самым быстрым будет всёже такой поиск: xor eax, 55555555h lea edx, [eax-01010101h] ...... Но для оптимальной оптимизации :) нужно знать вероятности появления байтов 055h, 0AAh по отдельности и вмете, чтобы знать какой искать первым и можно ли искать их сразу оба. И самое главное - размер области поиска. Всего это в условии задачи нет, а измерять какой-то абстрактный код как-то лениво :( ЗЫ Щас как раз пишу прогу которая в частности ищет всякие там 0A0Dh, дык никаких извращений не использую, т.к. для меня очевидно, что это будет занимать ~2% от общего времени работы :). ЗЫЫ Да, написАно - это круто %) |
