HexToDword

Тема в разделе "WASM.A&O", создана пользователем cresta, 30 июн 2005.

  1. cresta

    cresta Active Member

    Публикаций:
    0
    Регистрация:
    13 июн 2004
    Сообщения:
    2.257
    Строка db '1F3D5B79',0

    Делаю dword из строки:


    Код (Text):
    1.     mov     edx,[esp+4]
    2.     xor     eax,eax
    3.     xor     ecx,ecx
    4. _st:    
    5.     test    byte ptr[edx],0FFh
    6.     mov     cl,[edx]
    7.     jz      _end
    8.     sub     cl,61h
    9.     js      _00
    10. _0A:
    11.     shl     eax,4
    12.     inc     edx
    13.     lea     eax,[eax+ecx+0Ah]
    14.     jmp     _st
    15. _00:
    16.     add     cl,20h
    17.     jns     _0A
    18.     add     cl,11h
    19.     shl     eax,4
    20.     inc     edx
    21.     add     eax,ecx
    22.     jmp     _st
    23. _end:




    Можно ускорить? Если да, то как? Возможно без переходов?
     
  2. Asterix

    Asterix New Member

    Публикаций:
    0
    Регистрация:
    25 фев 2003
    Сообщения:
    3.576
    Код (Text):
    1. Ascii2Hex proc uses ebx esi lpHexString:DWORD
    2.      mov esi, lpHexString
    3.      xor eax, eax
    4.      xor ebx, ebx
    5. @@:
    6.      mov al, BYTE PTR [esi]
    7.      test al, al
    8.      jz @exit
    9.      shl ebx, 4
    10.      .IF al > 040h
    11.          sub al, 007h
    12.      .ENDIF
    13.      xor al, 030h
    14.      or ebx, eax
    15.      inc esi
    16.      jmp @B
    17. @exit:
    18.      mov eax, ebx
    19.      ret
    20. Ascii2Hex endp



    Код (Text):
    1. Ascii2Hex proc uses ebx esi lpHexString:DWORD
    2.      mov esi, lpHexString
    3.      xor eax, eax
    4.      xor ebx, ebx
    5. @@:
    6.      mov al, BYTE PTR [esi]
    7.      test al, al
    8.      jz @exit
    9.      shl ebx, 4
    10.      cmp al, 'f'+1
    11.      sbb ecx, ecx
    12.      cmp al, 'a'
    13.      adc ecx, 0
    14.      and ecx, 'A'-'a'
    15.      add al, cl
    16.      cmp al, 'F'+1
    17.      sbb ecx, ecx
    18.      cmp al, 'A'
    19.      adc ecx, 0
    20.      and ecx, -007h
    21.      add al, cl
    22.      xor al, 030h
    23.      or ebx, eax
    24.      inc esi
    25.      jmp @B
    26. @exit:
    27.      mov eax, ebx
    28.      ret
    29. Ascii2Hex endp
     
  3. cresta

    cresta Active Member

    Публикаций:
    0
    Регистрация:
    13 июн 2004
    Сообщения:
    2.257
    Asterix



    Второй вариант медленный, а первый чуть быстрее моего, если заменить esi на edx, а ebx на ecx и за счёт этого избавиться от push esi/ebx pop esi/ebx.

    Но тут одно НО: процедура не понимает маленькие буквы abcdef :dntknw:



    А тут есть хороший момент:
    Код (Text):
    1. mov al, BYTE PTR [esi]
    2. test al, al
    3. jz @exit




    чуть быстрее, чем мой
    Код (Text):
    1. test    byte ptr[edx],0FFh
    2. mov     cl,[edx]
    3. jz      _end
     
  4. Asterix

    Asterix New Member

    Публикаций:
    0
    Регистрация:
    25 фев 2003
    Сообщения:
    3.576




    С чего ты решил? ведь jmp'ов в ней почти нет.



    хотя действительно медленнее :-(
     
  5. Avoidik

    Avoidik New Member

    Публикаций:
    0
    Регистрация:
    29 дек 2004
    Сообщения:
    288
    Адрес:
    Russia
    asmpack смотри
     
  6. cresta

    cresta Active Member

    Публикаций:
    0
    Регистрация:
    13 июн 2004
    Сообщения:
    2.257
    Avoidik

    В asmpack нет быстрых процедур.



    Asterix

    Вторая процедура выполняет 20 инструкций за цикл, потому и медленно :dntknw: В моём варианте 10 или 11 (в зависимости от буква/цифра)

    9/10 лишних инструкций выполняются медленней, чем пара js(вперед) и jns(назад).
     
  7. Asterix

    Asterix New Member

    Публикаций:
    0
    Регистрация:
    25 фев 2003
    Сообщения:
    3.576
    cresta

    Есть варианты на MMX обрабатывающие сразу 8-и символьную

    строку, не мои, поэтому постить не буду, их можно

    найти на http://board.win32asmcommunity.net/

    в теме String2Hex

    там вроде в условии строка с символами в верхнем регистре,

    причем только hex символы, т.е. A-F, 0-9, но это

    не страшно, на практике практически всегда можно

    выполнить это условие.
     
  8. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    cresta

    Тебе не кажется, что "10 или 11" это только при многократных проходах, т.е при настроенном бранч-предикторе и соответственно без пенальти ? По идее при случайном сочетании буква/цифра каждый непредсказанный переход должен давать пенальти ~ длины конвейера.



    Вариант без переходов:
    Код (Text):
    1.   mov edi,hexstr
    2.   xor eax,eax
    3.   xor ecx,ecx
    4.   xor edx,edx
    5. @@:
    6.   mov cl,[edi]
    7.   and cl,5Fh    ;"0".."9" -> 1Xh, "A".."F","a".."f" -> 4Xh
    8.   mov dl,cl
    9.   jz @end
    10.   shl eax,4
    11.   add dl,50h    ;"0".."9" -> 6Xh, "A".."F" -> 9Xh
    12.   and dl,90h    
    13.   shr dl,4      ;= 0 или 9
    14.   and cl,0Fh
    15.   add edi,1
    16.   add eax,ecx
    17.   add eax,edx
    18.   jmp @B
    19. @end:
    На P4 Northwood 68 тиков на 8 байт, от буква/цифра ес-но не зависит
     
  9. Bill_Prisoner

    Bill_Prisoner New Member

    Публикаций:
    0
    Регистрация:
    4 май 2005
    Сообщения:
    238




    Момент правда интересный, команда test al,al устанавливает флаг ZF=1 если AL==0.



    И правда, процедура неплохая:





    Просто в одном из моментов код обращается два раза к памяти, а эту операцию как раз и надо как можно больше исключить, т.е. меньше обращаться к памяти.



    А может правда надо знать какие-нибдуь SSE1/2/3 и всё будет ок?
     
  10. cresta

    cresta Active Member

    Публикаций:
    0
    Регистрация:
    13 июн 2004
    Сообщения:
    2.257
    leo



    Не кажется :)

    Потому и сделал строку db '1F3D5B79',0 чтобы случайно, и буквы и цифры пропорционально их общему кол-ву(10/6). Твой вариант 13 инструкций в цикле. Похоже, всё-таки переход рулит (вып. вперед, невып. назад) независимо от предсказателя переходов :


    Код (Text):
    1. ;-----------------------------------------------------------
    2. ;           | 1F3D5B79 | 12345678 | ABCDEFAB | abcdefab |
    3. ;-----------------------------------------------------------
    4. ; Asterix*  |    90    |    90    |    84    |    88    |
    5. ; leo       |    86    |    86    |    86    |    86    |
    6. ; cresta    |    82    |    76    |    86    |    61    |
    7. ;-----------------------------------------------------------
    8.  
    9. ;--------------------------------------------------------------------- ------------
    10. ;           | 1AF2 | FA12 | A12F | 1234 | ABCD | abcd |  11 |  F1  | f1  | 1;F;f |
    11. ;--------------------------------------------------------------------- ------------
    12. ; Asterix*  |  46  |  46  |  46  |  46  |  41  |  43  |  30 |  30  |  30 |   22  |
    13. ; leo       |  44  |  44  |  44  |  44  |  44  |  44  |  29 |  29  |  29 |   24  |
    14. ; cresta    |  39  |  39  |  39  |  36  |  40  |  27  |  22 |  23  |  20 |   16  |
    15. ;--------------------------------------------------------------------- ------------
    16. Asterix* - первая процедура, с добавленным одним переходом, чтобы
    17. понимала и нижний регистр букв.






    Asterix

    Спасибо за ссылку, щас буду смотреть.
     
  11. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    cresta

    > "Потому и сделал строку db '1F3D5B79',0 чтобы случайно"



    1) Ты яснее скажи - ты с одной строкой один проход теста делаешь или несколько ? Если несколько, то все пенальти проявляются в первом-втором проходе, а затем предиктор настраивается и на следующих проходах не ошибается.

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

    2) Надеюсь, ты понимаешь что для предиктора чередование буква-цифра как в '1F3D5B79' это не "случайная", а наоборот простейшая комбинация о которой только можно мечтать ;)
     
  12. cresta

    cresta Active Member

    Публикаций:
    0
    Регистрация:
    13 июн 2004
    Сообщения:
    2.257
    leo

    Сделал ещё 1234ABCD (78,86,82 тика) и ABCD1234 (92,86,71)

    Тесты в один проход. Начало всех процедур на 16 ровно. Все процедуры сделал option prologue : none. Нигде нет разворотов цикла и т.п. Всё чисто :)

    И специально сделал разные комбинации и с разными длинами и разными регистрами букв (аж 16 штук:) Все возможные случаи. Тест чистый, комар хвост не засунет.

    У твоей процедуры есть одно место нехорошее - регистров много надо, поэтому автоматом push/pop edi добавляется :dntknw: Что на такой короткой процедуре сказывается негативно. Избавиться от этого нельзя?



    По ссылке, что давал Asterix есть процедура от buliaNaza (надеюсь за плагиат не посчитают:):


    Код (Text):
    1. buliaNaza proc lpString:DWORD
    2.     option prologue : none
    3.     option epilogue : none
    4.    
    5.     mov  ecx, [esp+4]
    6.     xor  eax, eax
    7.     xor  edx, edx
    8.     ;jmp  L_2
    9. L_1:
    10.     shl  eax,4
    11.     and  edx, 0Fh
    12.     add  eax,edx
    13. ;L_2:
    14.     ;mov  dl,[ecx]
    15.     movzx edx,byte ptr [ecx]
    16.     inc  ecx
    17.     cmp  edx,40h
    18.     sbb  ebx,ebx
    19.     sub  edx,37h   
    20.     and  ebx,7
    21.     add  edx, ebx
    22.     jns  L_1
    23.     retn    4                        
    24.     option prologue : prologuedef
    25.     option epilogue : epiloguedef
    26. buliaNaza endp




    На длинных (8 символов) работает быстро - 62, правда на коротких медленно (2 и 1 символ) - 26 и 20 соответственно.



    Я и на других алгоритмах замечал, что переход не так уж и страшен, если в нужную сторону. Порой с переходами получается даже быстрее чем тупо добавлять табличные данные по индексу (например при преобразовании регистра букв). Или это для атлона переходы по барабану?
     
  13. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    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):
    1. строки       cresta 1  cresta 2  leo 1  leo 2
    2. -----------  --------  --------  -----  -----
    3. '1F3D5B7',0    148       148      149    150
    4. '1234567',0    128       142      132    132
    5. '1234ABC',0     61        93       70     70
    6. '123abcD',0     61       104       70     70
    7. '12A3fDc',0     61       178       70     70
    8. 'AAAAcc4',0     61       160       70     70
    9. '3ccD24c',0     61       161       70     70
    10. 'ab1cd1D',0     61       149       70     70


    Результат имхо на лицо (или на лице ;)

    Интересно, что будет на P4 (у P3 пенальти раза в два меньше, но зато предсказатель послабее)

    Вывод: либо твоему атлону силы небесные помогают угадывать ветвление, либо не все так чисто ;))



    > "переход не так уж и страшен, если в нужную сторону"

    Нужная сторона влияет только на предсказанные переходы. Если jcc или jmp пройден один раз, то затем он сидит в BTB во главе конвейера и рулит префетчем и максимальные потери в случае верного предсказания = 0 (прыжок не совершается) или 1 такт (прыжок совершается и нужно фетчить другой блок инструкций из L1). Если jcc или jmp встречается впервые, то он обнаруживается только на выходе декодера и рулит статическое предсказание. Если предсказание верно, то в случае если прыжка нет, то и пенальти нет - продолжаем последовательно декодить и исполнять команды. А если прыжок (jmp или jcc назад), то извольте пенальти - т.к. декодер отстоит от префетчера на N-е кол-во стадий (в P3 на 4-5), которые работали впустую и их нужно повторить заново. А что происходит с непредсказанным переходом ? Правильно - он обнаруживается только в самом конце конвейера на стадии установки флагов и коррекции BTB, поэтому как правило весь конвейер надо грузить заново с нового адреса.
     
  14. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    cresta

    Ну вот и на P4 проверил твои "чудесные" прыжки.

    Есн-но для гиперконвейера в 20 стадий они бесследно не проходят - в варианте 2 на "нехороших" комбинациях результат подпрыгивает до 240-280, хотя в варианте 1 с многократным проходом одной строки он составляет всего 76



    А вариант buliaNaza выглядит довольно симпатично, хотя только для прописных букв..



    Вот только мысля у меня вертится, что мой вариант хоть и дубоватый, но его вроде как проще всего приспособить к фиксированной длине строки в 4 или 8 байт, т.к. вычисление коррекции на 9 можно выполнять сразу для 4-х символов
     
  15. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    Вот прямой (~16 на CPUID 6.8.6), к регистру не чуствителен, строку не проверяет
    Код (Text):
    1. ;==================================================
    2. buffer      db     'f5cD4e2A'
    3. ;==================================================
    4.             mov    eax,buffer
    5.             call   HexToDword
    6. ;==================================================
    7. HexToDword: mov    ecx,[eax]
    8.             mov    edx,[eax+4]
    9.             and    ecx,0x40404040
    10.             and    edx,0x40404040
    11.             shr    ecx,6
    12.             shr    edx,6
    13.             lea    ecx,[ecx*8+ecx]
    14.             lea    edx,[edx*8+edx]
    15.             add    ecx,[eax]
    16.             and    ecx,0x0F0F0F0F
    17.             add    edx,[eax+4]
    18.             and    edx,0x0F0F0F0F
    19.             mov    eax,ecx
    20.             shl    eax,12
    21.             or     ecx,eax
    22.             mov    eax,edx
    23.             shl    eax,12
    24.             or     edx,eax
    25.             mov    eax,ecx
    26.             shr    eax,24
    27.             and    ecx,0x0000FF00
    28.             or     eax,ecx
    29.             mov    ecx,0x0000FF00
    30.             and    ecx,edx
    31.             shr    edx,24
    32.             shl    eax,16
    33.             or     ecx,edx
    34.             or     eax,ecx
    35.             ret
    36. ;==================================================
     
  16. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    bogrus

    Ну ты быстр однако ;)

    Не успел я приписку сделать (пока думаю народ дремлет), а тут уж супервариант для фиксированной длины !
     
  17. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    Ну да конечно, быстро шло до "and edx,0x0F0F0F0F" включительно, а потом 3 часа завис на "реверсе сдвигов" :)
     
  18. cresta

    cresta Active Member

    Публикаций:
    0
    Регистрация:
    13 июн 2004
    Сообщения:
    2.257
    Ну вот, сам подозревал, что делаю не один проход, а теперь восемь предлагаешь :)



    Если я правильно понял, то ты предлагаешь так делать:


    Код (Text):
    1. align 16    
    2.     hstr_1              db '1F3D5B7',0
    3.     hstr_2              db '1234567',0
    4.     hstr_3              db '1234ABC',0
    5.     hstr_4              db '123abcD',0
    6.     hstr_5              db '12A3fDc',0
    7.     hstr_6              db 'AAAAcc4',0
    8.     hstr_7              db '3ccD24c',0
    9.     hstr_8              db 'ab1cd1D',0
    10.  
    11.     mov     edi,offset hstr_1
    12.     test    byte ptr[edi],0
    13.     test    byte ptr[edi+56],0
    14.     REPT 8
    15.         push    edi
    16.         call    _proc
    17.         add     edi,8
    18.     ENDM






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


    Код (Text):
    1.             mov     edi,offset hstr_1
    2.             ;test    byte ptr[edi],0
    3.             ;test    byte ptr[edi+128],0
    4.         ;-------------------------------------------------        
    5.         REPT 8     ;<-кол-во повторений
    6.             push    edi
    7.             call    cr_strhextodw
    8.             add     edi,33344            ;строки с таким разносом
    9.                                          ;чтобы не попадали в кэш
    10.         ENDM




    Думаю, это более реальные условия. Тут ни твой вариант, ни мой не рулят: 580 vs. 644 на 8 проходов (по одному на каждую из восьми строк)



    Кстати, вариант buliaNaza прекрасно понимает и большие и маленькие буквы. И если кто и рулит, то именно этот вариант - ~450 тиков на 8 строк :)

    Так что мы с тобой пролетаем как фанеры:)



    bogrus

    А как быть с длиной, что она должна быть обязательно 8 символов :dntknw: Так оно быстро - 190 тиков, но длина...

    Может имеет смысл организовать буфер-маску, с '00000000' и накладывать на него строку имеющейся длины?
     
  19. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    cresta

    Насчет buliaNaza ты прав.



    А вот насчет префетча - мягко говоря, не совсем.

    Во-первых, "теоретически". При таком подходе и оптимизировать алгоритмы вовсе незачем, т.к. несчастный десяток-другой тактов это капля в море по сравнению с сотнями тиков загрузки данных из ОЗУ. Поэтому за исключением особых случаев (когда проверяется именно работа с памятью), обычно при тестировании алгоритма предполагают что данные находятся в кеше или хотя бы рулит опережающий хардварный префетч данных. А в твоем случае (разнос на 33 кБ) данные могут быть не только не в кеше, но еще и в разных страницах памяти. Поэтому к аппаратным задержкам (ОЗУ, чипсет, FSB) еще могут замешиваться и задержки OS на инициализацию страниц памяти. В такой ситуации можно сравнивать рультаты только на одном конкретном компе (процессор,чипсет,FSB,ОЗУ) и для конкретной оси. Это, что касается теории и принципов.

    А во-вторых, практически. Я подозреваю что ты используешь свой speed_tester и выполняешь за сеанс работы программы по несколько тестов - а это уже повторное использование данных и кода и худо-бедно настроенного BTB процессора. Если я тебя правильно понял, ты приводишь суммарные цифры на 8 проходов. Тогда разделив их на 8 получаем опять те же прекрасные результаты, что и раньше. Не видно никаких ошибок предсказания, никаких загрузок из ОЗУ и уж тем более никаких инициализаций страниц памяти. Хотя если ты предварительно пишешь эти строки в память, то у тебя и страницы инициализированы и строки преспокойно сидят в кеше - и ты просто себя обманываешь ;)) "В реальной программе такое не гарантируется", но вполне вероятно, т.к. строки как-то должны попасть в память - если они попадают туда путем обычной записи через процессор (не DMA, movntq и т.п.) и не успевают вытесниться из кеша другими данными - то где ж им быть - по крайней мере на L2 можно вполне расчитывать ;)
     
  20. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    Однако 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 тиков. Кто меньше ? Или ставок больше нет ? ;)