Строка db '1F3D5B79',0 Делаю dword из строки: Код (Text): mov edx,[esp+4] xor eax,eax xor ecx,ecx _st: test byte ptr[edx],0FFh mov cl,[edx] jz _end sub cl,61h js _00 _0A: shl eax,4 inc edx lea eax,[eax+ecx+0Ah] jmp _st _00: add cl,20h jns _0A add cl,11h shl eax,4 inc edx add eax,ecx jmp _st _end: Можно ускорить? Если да, то как? Возможно без переходов?
Код (Text): Ascii2Hex proc uses ebx esi lpHexString:DWORD mov esi, lpHexString xor eax, eax xor ebx, ebx @@: mov al, BYTE PTR [esi] test al, al jz @exit shl ebx, 4 .IF al > 040h sub al, 007h .ENDIF xor al, 030h or ebx, eax inc esi jmp @B @exit: mov eax, ebx ret Ascii2Hex endp Код (Text): Ascii2Hex proc uses ebx esi lpHexString:DWORD mov esi, lpHexString xor eax, eax xor ebx, ebx @@: mov al, BYTE PTR [esi] test al, al jz @exit shl ebx, 4 cmp al, 'f'+1 sbb ecx, ecx cmp al, 'a' adc ecx, 0 and ecx, 'A'-'a' add al, cl cmp al, 'F'+1 sbb ecx, ecx cmp al, 'A' adc ecx, 0 and ecx, -007h add al, cl xor al, 030h or ebx, eax inc esi jmp @B @exit: mov eax, ebx ret Ascii2Hex endp
Asterix Второй вариант медленный, а первый чуть быстрее моего, если заменить esi на edx, а ebx на ecx и за счёт этого избавиться от push esi/ebx pop esi/ebx. Но тут одно НО: процедура не понимает маленькие буквы abcdef А тут есть хороший момент: Код (Text): mov al, BYTE PTR [esi] test al, al jz @exit чуть быстрее, чем мой Код (Text): test byte ptr[edx],0FFh mov cl,[edx] jz _end
Avoidik В asmpack нет быстрых процедур. Asterix Вторая процедура выполняет 20 инструкций за цикл, потому и медленно В моём варианте 10 или 11 (в зависимости от буква/цифра) 9/10 лишних инструкций выполняются медленней, чем пара js(вперед) и jns(назад).
cresta Есть варианты на MMX обрабатывающие сразу 8-и символьную строку, не мои, поэтому постить не буду, их можно найти на http://board.win32asmcommunity.net/ в теме String2Hex там вроде в условии строка с символами в верхнем регистре, причем только hex символы, т.е. A-F, 0-9, но это не страшно, на практике практически всегда можно выполнить это условие.
cresta Тебе не кажется, что "10 или 11" это только при многократных проходах, т.е при настроенном бранч-предикторе и соответственно без пенальти ? По идее при случайном сочетании буква/цифра каждый непредсказанный переход должен давать пенальти ~ длины конвейера. Вариант без переходов: Код (Text): mov edi,hexstr xor eax,eax xor ecx,ecx xor edx,edx @@: mov cl,[edi] and cl,5Fh ;"0".."9" -> 1Xh, "A".."F","a".."f" -> 4Xh mov dl,cl jz @end shl eax,4 add dl,50h ;"0".."9" -> 6Xh, "A".."F" -> 9Xh and dl,90h shr dl,4 ;= 0 или 9 and cl,0Fh add edi,1 add eax,ecx add eax,edx jmp @B @end: На P4 Northwood 68 тиков на 8 байт, от буква/цифра ес-но не зависит
Момент правда интересный, команда test al,al устанавливает флаг ZF=1 если AL==0. И правда, процедура неплохая: Просто в одном из моментов код обращается два раза к памяти, а эту операцию как раз и надо как можно больше исключить, т.е. меньше обращаться к памяти. А может правда надо знать какие-нибдуь SSE1/2/3 и всё будет ок?
leo Не кажется Потому и сделал строку db '1F3D5B79',0 чтобы случайно, и буквы и цифры пропорционально их общему кол-ву(10/6). Твой вариант 13 инструкций в цикле. Похоже, всё-таки переход рулит (вып. вперед, невып. назад) независимо от предсказателя переходов : Код (Text): ;----------------------------------------------------------- ; | 1F3D5B79 | 12345678 | ABCDEFAB | abcdefab | ;----------------------------------------------------------- ; Asterix* | 90 | 90 | 84 | 88 | ; leo | 86 | 86 | 86 | 86 | ; cresta | 82 | 76 | 86 | 61 | ;----------------------------------------------------------- ;--------------------------------------------------------------------- ------------ ; | 1AF2 | FA12 | A12F | 1234 | ABCD | abcd | 11 | F1 | f1 | 1;F;f | ;--------------------------------------------------------------------- ------------ ; Asterix* | 46 | 46 | 46 | 46 | 41 | 43 | 30 | 30 | 30 | 22 | ; leo | 44 | 44 | 44 | 44 | 44 | 44 | 29 | 29 | 29 | 24 | ; cresta | 39 | 39 | 39 | 36 | 40 | 27 | 22 | 23 | 20 | 16 | ;--------------------------------------------------------------------- ------------ Asterix* - первая процедура, с добавленным одним переходом, чтобы понимала и нижний регистр букв. Asterix Спасибо за ссылку, щас буду смотреть.
cresta > "Потому и сделал строку db '1F3D5B79',0 чтобы случайно" 1) Ты яснее скажи - ты с одной строкой один проход теста делаешь или несколько ? Если несколько, то все пенальти проявляются в первом-втором проходе, а затем предиктор настраивается и на следующих проходах не ошибается. По крайней мере у меня на P4 твой код дает ~80 тиков именно при многократных проходах. А чтобы увидеть полноценное пенальти нужно в каждом проходе использовать другую строку (хотя бы один символ менять, чтобы возник непредсказанный переход). 2) Надеюсь, ты понимаешь что для предиктора чередование буква-цифра как в '1F3D5B79' это не "случайная", а наоборот простейшая комбинация о которой только можно мечтать
leo Сделал ещё 1234ABCD (78,86,82 тика) и ABCD1234 (92,86,71) Тесты в один проход. Начало всех процедур на 16 ровно. Все процедуры сделал option prologue : none. Нигде нет разворотов цикла и т.п. Всё чисто И специально сделал разные комбинации и с разными длинами и разными регистрами букв (аж 16 штук Все возможные случаи. Тест чистый, комар хвост не засунет. У твоей процедуры есть одно место нехорошее - регистров много надо, поэтому автоматом push/pop edi добавляется Что на такой короткой процедуре сказывается негативно. Избавиться от этого нельзя? По ссылке, что давал Asterix есть процедура от buliaNaza (надеюсь за плагиат не посчитают: Код (Text): buliaNaza proc lpString:DWORD option prologue : none option epilogue : none mov ecx, [esp+4] xor eax, eax xor edx, edx ;jmp L_2 L_1: shl eax,4 and edx, 0Fh add eax,edx ;L_2: ;mov dl,[ecx] movzx edx,byte ptr [ecx] inc ecx cmp edx,40h sbb ebx,ebx sub edx,37h and ebx,7 add edx, ebx jns L_1 retn 4 option prologue : prologuedef option epilogue : epiloguedef buliaNaza endp На длинных (8 символов) работает быстро - 62, правда на коротких медленно (2 и 1 символ) - 26 и 20 соответственно. Я и на других алгоритмах замечал, что переход не так уж и страшен, если в нужную сторону. Порой с переходами получается даже быстрее чем тупо добавлять табличные данные по индексу (например при преобразовании регистра букв). Или это для атлона переходы по барабану?
cresta > "Всё чисто " > "Или это для атлона переходы по барабану?" Ой сомневаюсь и в том, что все чисто, и в том, что атлон такой чудесный Ставим такой эксперимент. Задаем 8 последовательных строк с разным чередованием цифр, строчных и прописных букв. Для чистоты эксперимента делаем предварительный префетч всех строк в кэш (test byte [hexstr],0 + test byte [hexstr+cacheline],0 + ..). Делаем 8 проходов теста в двух вариантах. В варианте 1 после теста восстанавливаем edi = hexstr (т.е. каждый раз первая строка), а в варианте 2 делаем inc edi чтобы в каждом проходе обрабатывались разные строки. И вот что мы получаем на P3 Coppermine (CPUID 6.8.6): Код (Text): строки cresta 1 cresta 2 leo 1 leo 2 ----------- -------- -------- ----- ----- '1F3D5B7',0 148 148 149 150 '1234567',0 128 142 132 132 '1234ABC',0 61 93 70 70 '123abcD',0 61 104 70 70 '12A3fDc',0 61 178 70 70 'AAAAcc4',0 61 160 70 70 '3ccD24c',0 61 161 70 70 'ab1cd1D',0 61 149 70 70 Результат имхо на лицо (или на лице Интересно, что будет на P4 (у P3 пенальти раза в два меньше, но зато предсказатель послабее) Вывод: либо твоему атлону силы небесные помогают угадывать ветвление, либо не все так чисто ) > "переход не так уж и страшен, если в нужную сторону" Нужная сторона влияет только на предсказанные переходы. Если jcc или jmp пройден один раз, то затем он сидит в BTB во главе конвейера и рулит префетчем и максимальные потери в случае верного предсказания = 0 (прыжок не совершается) или 1 такт (прыжок совершается и нужно фетчить другой блок инструкций из L1). Если jcc или jmp встречается впервые, то он обнаруживается только на выходе декодера и рулит статическое предсказание. Если предсказание верно, то в случае если прыжка нет, то и пенальти нет - продолжаем последовательно декодить и исполнять команды. А если прыжок (jmp или jcc назад), то извольте пенальти - т.к. декодер отстоит от префетчера на N-е кол-во стадий (в P3 на 4-5), которые работали впустую и их нужно повторить заново. А что происходит с непредсказанным переходом ? Правильно - он обнаруживается только в самом конце конвейера на стадии установки флагов и коррекции BTB, поэтому как правило весь конвейер надо грузить заново с нового адреса.
cresta Ну вот и на P4 проверил твои "чудесные" прыжки. Есн-но для гиперконвейера в 20 стадий они бесследно не проходят - в варианте 2 на "нехороших" комбинациях результат подпрыгивает до 240-280, хотя в варианте 1 с многократным проходом одной строки он составляет всего 76 А вариант buliaNaza выглядит довольно симпатично, хотя только для прописных букв.. Вот только мысля у меня вертится, что мой вариант хоть и дубоватый, но его вроде как проще всего приспособить к фиксированной длине строки в 4 или 8 байт, т.к. вычисление коррекции на 9 можно выполнять сразу для 4-х символов
Вот прямой (~16 на CPUID 6.8.6), к регистру не чуствителен, строку не проверяет Код (Text): ;================================================== buffer db 'f5cD4e2A' ;================================================== mov eax,buffer call HexToDword ;================================================== HexToDword: mov ecx,[eax] mov edx,[eax+4] and ecx,0x40404040 and edx,0x40404040 shr ecx,6 shr edx,6 lea ecx,[ecx*8+ecx] lea edx,[edx*8+edx] add ecx,[eax] and ecx,0x0F0F0F0F add edx,[eax+4] and edx,0x0F0F0F0F mov eax,ecx shl eax,12 or ecx,eax mov eax,edx shl eax,12 or edx,eax mov eax,ecx shr eax,24 and ecx,0x0000FF00 or eax,ecx mov ecx,0x0000FF00 and ecx,edx shr edx,24 shl eax,16 or ecx,edx or eax,ecx ret ;==================================================
bogrus Ну ты быстр однако Не успел я приписку сделать (пока думаю народ дремлет), а тут уж супервариант для фиксированной длины !
Ну да конечно, быстро шло до "and edx,0x0F0F0F0F" включительно, а потом 3 часа завис на "реверсе сдвигов"
Ну вот, сам подозревал, что делаю не один проход, а теперь восемь предлагаешь Если я правильно понял, то ты предлагаешь так делать: Код (Text): align 16 hstr_1 db '1F3D5B7',0 hstr_2 db '1234567',0 hstr_3 db '1234ABC',0 hstr_4 db '123abcD',0 hstr_5 db '12A3fDc',0 hstr_6 db 'AAAAcc4',0 hstr_7 db '3ccD24c',0 hstr_8 db 'ab1cd1D',0 mov edi,offset hstr_1 test byte ptr[edi],0 test byte ptr[edi+56],0 REPT 8 push edi call _proc add edi,8 ENDM Чтобы все данные сидели в кэше? И чтобы сбить с толку предсказатель переходов? Сбить с толку - согласен. Данные иметь готовые в кэше - нет. В реальной программе такое не гарантируется. Код (Text): mov edi,offset hstr_1 ;test byte ptr[edi],0 ;test byte ptr[edi+128],0 ;------------------------------------------------- REPT 8 ;<-кол-во повторений push edi call cr_strhextodw add edi,33344 ;строки с таким разносом ;чтобы не попадали в кэш ENDM Думаю, это более реальные условия. Тут ни твой вариант, ни мой не рулят: 580 vs. 644 на 8 проходов (по одному на каждую из восьми строк) Кстати, вариант buliaNaza прекрасно понимает и большие и маленькие буквы. И если кто и рулит, то именно этот вариант - ~450 тиков на 8 строк Так что мы с тобой пролетаем как фанеры bogrus А как быть с длиной, что она должна быть обязательно 8 символов Так оно быстро - 190 тиков, но длина... Может имеет смысл организовать буфер-маску, с '00000000' и накладывать на него строку имеющейся длины?
cresta Насчет buliaNaza ты прав. А вот насчет префетча - мягко говоря, не совсем. Во-первых, "теоретически". При таком подходе и оптимизировать алгоритмы вовсе незачем, т.к. несчастный десяток-другой тактов это капля в море по сравнению с сотнями тиков загрузки данных из ОЗУ. Поэтому за исключением особых случаев (когда проверяется именно работа с памятью), обычно при тестировании алгоритма предполагают что данные находятся в кеше или хотя бы рулит опережающий хардварный префетч данных. А в твоем случае (разнос на 33 кБ) данные могут быть не только не в кеше, но еще и в разных страницах памяти. Поэтому к аппаратным задержкам (ОЗУ, чипсет, FSB) еще могут замешиваться и задержки OS на инициализацию страниц памяти. В такой ситуации можно сравнивать рультаты только на одном конкретном компе (процессор,чипсет,FSB,ОЗУ) и для конкретной оси. Это, что касается теории и принципов. А во-вторых, практически. Я подозреваю что ты используешь свой speed_tester и выполняешь за сеанс работы программы по несколько тестов - а это уже повторное использование данных и кода и худо-бедно настроенного BTB процессора. Если я тебя правильно понял, ты приводишь суммарные цифры на 8 проходов. Тогда разделив их на 8 получаем опять те же прекрасные результаты, что и раньше. Не видно никаких ошибок предсказания, никаких загрузок из ОЗУ и уж тем более никаких инициализаций страниц памяти. Хотя если ты предварительно пишешь эти строки в память, то у тебя и страницы инициализированы и строки преспокойно сидят в кеше - и ты просто себя обманываешь ) "В реальной программе такое не гарантируется", но вполне вероятно, т.к. строки как-то должны попасть в память - если они попадают туда путем обычной записи через процессор (не DMA, movntq и т.п.) и не успевают вытесниться из кеша другими данными - то где ж им быть - по крайней мере на L2 можно вполне расчитывать
Однако buliaNaza на P4 не так хорош из-за тормознутой SBB. На P4 Northwood (CPUID = 15.2.7) дает 76 тиков на строке из 8 символов. (На Willamette CPUID = 15.1.x наверное будет заметно хуже, хотя вроде бы это уже редкость) Мой туповатый вариант можно чуть ускорить (на P4), если перейти от cl\dl к ecx\edx и переставить парочку add eax.. в начало цикла. Эти замены\перестановки на P4 дают 60 тиков на 8-символьной строке. Но имхо для практики это несущественно, поэтому buliaNaza все-таки рулит Вариант bogrus для фикс.длины строки дает на P4 36 тиков. Кто меньше ? Или ставок больше нет ?
