Поиск строки в файле (быстрее, ещё быстрее :))

Тема в разделе "WASM.ASSEMBLER", создана пользователем Barracuda, 23 май 2005.

  1. Barracuda

    Barracuda New Member

    Публикаций:
    0
    Регистрация:
    31 авг 2003
    Сообщения:
    19
    Пусть file_ptr - указатель, на данные из файла (получаем через MapViewOfFile), file_size - размер файла.

    И пусть нам надо найти строчку "abcdefghijklmnop" (т.е. вся строка известна заранее).


    Код (Text):
    1.  
    2. file_ptr dd ?
    3. file_size dd ?
    4. whole_str db "abcdefghijklmnop"
    5.  
    6.         mov     ebx, "dcba"
    7.         mov     esi, file_ptr
    8.         mov     edx, esi
    9.         add     edx, file_size
    10.         cld
    11.  
    12. @@first_try:
    13.         lodsd
    14.         cmp     eax, ebx
    15.         jnz     @@first_exit
    16.  
    17.         lea     edi, whole_str + 4
    18.         mov     ecx, 3
    19.         repe cmpsd
    20.         jnz     @@not_yet
    21.  
    22.         sub     esi, 16
    23.         jmp     @@found
    24.  
    25. @@not_yet:
    26.         lea     esi, [esi+ecx*4 - 16 + 4]
    27.  
    28. @@first_exit:
    29.         sub     esi, 3
    30.         cmp     esi, edx
    31.         jb      @@first_try
    32.  
    33. @@not_found:
    34.         xor     esi, esi
    35.         jmp     @@finish
    36.  
    37. @@found:
    38. ; some additional checks here
    39.  
    40. @@finish:
    41.         mov     eax, esi
    42.  




    Очень тормозной вариант, как мне кажется :) Кто-нибудь может предложить что-либо быстрее? (Здесь же полно гуру по оптимизации.. :))





    EDITED>> Мдя, только что обнаружил, что у меня ещё и бага:

    если строка не существует в файле и размер не кратен четырем, то заработаем эксепшн..
     
  2. Artemy

    Artemy New Member

    Публикаций:
    0
    Регистрация:
    18 май 2005
    Сообщения:
    48
    Адрес:
    Russia
    весь mapview - одна большая строка.

    есть оч. много алгоритмов поиска подстроки в строке.

    например Кнута и др. видел в Сети интерактивный учебник по этой теме с тонной описаний (на английском). ссылка где-то по-моему здесь появлялась
     
  3. Artemy

    Artemy New Member

    Публикаций:
    0
    Регистрация:
    18 май 2005
    Сообщения:
    48
    Адрес:
    Russia
  4. Artemy

    Artemy New Member

    Публикаций:
    0
    Регистрация:
    18 май 2005
    Сообщения:
    48
    Адрес:
    Russia
    и, наверно, сегодня напоследок:



    Boyer-Moore String Searching и т.д. и т.п.

    но где-то я видел целую кучу описаний в одном месте



    а какой-нить готовый routine нельзя заюзать - учебная задача?
     
  5. cresta

    cresta Active Member

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




    А длина строки известна? Примерно какого порядка? И каков примерно размер файла?
     
  6. Barracuda

    Barracuda New Member

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

    Длина известна - 16 байт ('\0' не считается, то есть это даже не строка, а просто последовательность байт). А размер файла.. хм.. в пределах 500кб, в среднем ~300кб.



    Artemy



    Да, очевидно, что это задача поиска подстроки в строке :) Только это некоторый частный случай, который очень хотелось бы ускорить (основываясь как раз на том, что известна длина строки и вся эта строка), так как операция будет выполняться много раз.
     
  7. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    IMHO мало смысла это оптимизировать - узким местом бедут медленное чтение с винта.
     
  8. Artemy

    Artemy New Member

    Публикаций:
    0
    Регистрация:
    18 май 2005
    Сообщения:
    48
    Адрес:
    Russia
    Barracuda

    самый короткий код в цикле не есть самое быстрое решение

    чем тебя не устраивают существующие алгоримы?

    например, very fast и др.

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



    товарищь S_T_A_S_ прав про винт

    время исполнения вообще критично?

    большая часть времени уйдет на обращение к диску
     
  9. Barracuda

    Barracuda New Member

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



    Прям так критично? :dntknw: Можно конечно и не оптимизировать, но очень интересно, что смогут предложить гуру в этой области :lol: Давно ещё как-то интересовался поиском сигнатур, а сейчас вот досталась задачка как раз в тему :)



    Artemy



    Да, гугл рулит, я не спорю :) Но только линки, которые были преведены выше - совсем не рулят. Первый ещё можно применить, хотя явно это не особо оптимально, так как длина строки кратна 4, поэтому хотелось бы по 4 байта обрабатывать. А второй линк вообще не в тему, потому что такой сложный алгоритм для такой маленькой подстроки использовать - явно нерационально.



    EDITED>>

    Да, 500кб - это не очень-то много, но если много раз по 500кб, то...

    "А пять старушек — это уже рубль" :)
     
  10. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    Barracuda



    По-моему, в коде ещё есть ошибка - предполагается, что строка выровняна по границе dword'а.

    А exception, возможно, и не стОит бояться, поставив SEH (хотя исклбчения довольно долго обрабатывабтся).



    Что до кода - lods лучше убрать, очень медленаая команда.

    как-нибудь так искать первой совпадение (синтаксис fasm)
    Код (Text):
    1.     mov   edx, [file_size]
    2. @@:
    3.     cmp   dword[esi+0+0], 'abcd'
    4.     jz    found_0               ; эти переходы должны быть вперёд
    5.     cmp   dword[esi+4+1], 'fghi'
    6.     jz    found_5
    7.     cmp   dword[esi+8+2], 'klmn'
    8.     jz    found_10
    9.     cmp   dword[esi+0+3], 'defg'
    10.     jnz   found_3
    11.     add   esi, 4
    12.     sub   edx, 4
    13.     ja    @b
    ну и оставшиеся части строки проверять подобным образом, сравнивая с hardcoded заначениями.
     
  11. EvilsInterrupt

    EvilsInterrupt Постигающий азы дзена

    Публикаций:
    0
    Регистрация:
    28 окт 2003
    Сообщения:
    2.428
    Адрес:
    Russia
    jnz found_3

    add esi, 4

    а почему на 4?
     
  12. yureckor

    yureckor New Member

    Публикаций:
    0
    Регистрация:
    25 фев 2004
    Сообщения:
    494
    Адрес:
    Russia
    >а почему на 4?

    cmp dword...



    Edited>хм, верно, нигде не сказано что файл-это массив из 16 байтных последовательностей.
     
  13. leo

    leo Active Member

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



    Видимо ты поспешил ;) Ты же знаешь, что работать с невыравненными двордами "нехорошо" - наверное лучше только смещать символы в сравниваемых частях строки: первый дворд с 'abcd' второй с 'defg' и т.п.

    А чтобы не вылететь за размер файла нужно сразу вычесть из edx 16.
     
  14. cresta

    cresta Active Member

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

    Имхо, mapview - не очень хорошая идея для таких размеров файла. Она начинает рулить только от 50-100 Мб и выше. До этого размера обычный ReadFile гораздо эффективней.

    Конструкции типа repe cmpsd не только медленней непосредственного сравнения в цикле, но и не позволяют сделать разворот цикла, за счет которого тоже можно заметно ускорить.

    Для затравки простая процедура:


    Код (Text):
    1. find_sub_string proc uses esi edi ebx lpFileData:DWORD, lpMatch:DWORD, DataLen:DWORD
    2.     align 16
    3.         mov esi,lpFileData
    4.         mov edi,lpMatch
    5.         mov eax,dword ptr[edi]    ;1-й дворд строки
    6.         mov ebx,dword ptr[edi+4]  ;2-й дворд строки
    7.         mov ecx,dword ptr[edi+8]  ;3-й дворд строки
    8.         mov edx,dword ptr[edi+12] ;4-й дворд строки
    9.         mov edi,esi
    10.         add edi,DataLen
    11.         sub edi,15
    12.         dec esi
    13.     @@:
    14.         inc esi
    15.         cmp esi,edi
    16.         je @No
    17.         cmp eax,dword ptr[esi]
    18.         je @Fnd
    19.         inc esi
    20.         cmp esi,edi
    21.         je @No
    22.         cmp eax,dword ptr[esi]
    23.         je @Fnd
    24.         inc esi
    25.         cmp esi,edi
    26.         je @No
    27.         cmp eax,dword ptr[esi]
    28.         je @Fnd
    29.         inc esi
    30.         cmp esi,edi
    31.         je @No
    32.         cmp eax,dword ptr[esi]
    33.         jne @B
    34.     @Fnd:
    35.         cmp edx,dword ptr[esi+12]
    36.         jne @B
    37.         cmp ecx,dword ptr[esi+8]
    38.         jne @B
    39.         mov ebx,dword ptr[esi+4]
    40.         jne @B
    41.        
    42.         mov eax,esi
    43.         ret
    44.     @No:or eax,-1
    45.         ret
    46. find_sub_string endp




    Проверял на файле 1Мб, искомая строка в самом конце файла, файл читался ReadFile'ом. Быстрее на 30% (2530/3280). Если не разворачивать цикл, то 20%.

    Если строка известна на стадии компиляции, то может сыграть на этом как-то?
     
  15. leo

    leo Active Member

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



    > "так как длина строки кратна 4, поэтому хотелось бы по 4 байта обрабатывать"



    Вот если бы еще позиция строки в файле была бы кратна 4-м, тогда да ;)

    А если нет, то в итоге в любом случае приходится просматривать все варианты побайтных сдвигов. Поэтому выигрыш от сравнения двордами в основном - ИМХО статистический, т.к. вероятность ложного совпадения одного символа теоретически выше, чем 4-х. Поэтому при побайтных сравнениях код будет чаще скакать на дополнительные проверки и впустую отъедать драгоценное время :)



    cresta



    Затравка у тебя ИМХО не из самых быстрых ;)

    1) Совершенно незачем каждый раз делать inc esi и проверять конец файла (тем более тормозной inc вместо add 1). Если сразу вычесть из размера файла длину искомой строки, то мы никогда не вылезем за размер => можно спокойно делать приращение на 4.

    2) Опять невыравненные дворды => пересечение границ кеш-линеек 3 раза из 32 чтений на P6 или из 64 на P4. Можно конечно пренебречь, но не следует удивляться если побайтное сравнение окажется быстрее (а оно действительно быстрее, если не брать в расчет ложные совпадения первого символа).
     
  16. Privalov

    Privalov New Member

    Публикаций:
    0
    Регистрация:
    16 апр 2004
    Сообщения:
    16
  17. cresta

    cresta Active Member

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



    Вариант №2:
    Код (Text):
    1. find_sub_string_1 proc uses esi edi ebx lpFileData:DWORD, lpMatch:DWORD, DataLen:DWORD
    2.     LOCAL off       :DWORD
    3.     LOCAL tmp       :DWORD
    4.        
    5.     align 16
    6.         mov esi,lpFileData
    7.         mov edi,lpMatch
    8.         mov eax,dword ptr[edi]
    9.         mov tmp,eax
    10.         mov ebx,dword ptr[edi+1]
    11.         mov ecx,dword ptr[edi+2]
    12.         mov edx,dword ptr[edi+3]
    13.  
    14.         add DataLen,esi
    15.         sub DataLen,15
    16.         sub esi,4
    17.        
    18.     @St:mov eax,tmp
    19.         mov off,12
    20.     @@:
    21.         add esi,4
    22.         cmp eax,dword ptr[esi]
    23.         je @Fnd_0
    24.         cmp ebx,dword ptr[esi+1]
    25.         je @Fnd_1
    26.         cmp ecx,dword ptr[esi+2]
    27.         je @Fnd_2
    28.         cmp edx,dword ptr[esi+3]
    29.         je @Fnd_3
    30.         cmp esi,DataLen
    31.         jle @B
    32.         jmp @No
    33.        
    34.  @Fnd_3:sub off,4
    35.  @Fnd_2:sub off,4
    36.  @Fnd_1:sub off,4
    37.  @Fnd_0:
    38.         mov eax,esi
    39.         add eax,off
    40.         mov eax,dword ptr[eax]
    41.         cmp eax,dword ptr[edi+12]
    42.         mov eax,3
    43.         jne @F
    44.         mov eax,esi
    45.         add eax,off
    46.         mov eax,dword ptr[eax-4]
    47.         cmp eax,dword ptr[edi+8]
    48.         mov eax,2
    49.         jne @F
    50.         mov eax,esi
    51.         add eax,off
    52.         mov eax,dword ptr[eax-8]
    53.         cmp eax,dword ptr[edi+4]
    54.         mov eax,1
    55.         jne @F
    56.         jmp @found
    57.         @@:
    58.         sub esi,eax
    59.         jmp @St
    60. @found:        
    61.         mov eax,esi
    62.         ret
    63.     @No:or eax,-1
    64.         ret
    65.  
    66. find_sub_string_1 endp




    Тоже неоптимально, регистров не хватает :dntknw: Хотя скорость подросла: время поиска - 60% от исходного варианта (by Barracuda). Или в 1.6 раза быстрее. Кому как больше нравится.



    А вообще,leo, критикуя - предлагай.
     
  18. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    leo >




    Это только на древних процах :). На современных получим пенальти только при пересечении строк кэша, то есть в 3х случаях из 16ти или 32х. Если очень критично, можно для граничных участков написать отдельный код со сдвигами.
     
  19. leo

    leo Active Member

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



    Может я не догоняю, но не понимаю зачем смещаться на байты. Преумущество задачки в том, что длина строки >= 8 и вместо смещения адреса "источника" мы можем смещать искомую подстроку. В случае hard-coded примерно так:
    Код (Text):
    1.     mov esi,lpFileData
    2.     mov ecx,DataLen
    3.     sub ecx,MatchLen ;вычитаем длину искомой строки
    4.     ;искомая строка 'abcdefgh...'
    5. align 16
    6. @@:
    7.     add esi,4
    8.     mov eax,[esi]
    9.     cmp eax,'efgh' ;второй дворд искомой строки
    10.     je @found0
    11. @ret0:
    12.     cmp eax,'defg' ;сдвинутый кусок искомой строки
    13.     je @found1
    14. @ret1:
    15.     cmp eax,'cdef'
    16.     je @found2
    17. @ret2:
    18.     cmp eax,'bcde'
    19.     je @found3
    20. @ret3:
    21.     sub ecx,4
    22.     jg @B
    23.     jmp @exit
    24.  
    25. @found0: ... ;проверка соответствия остальной части строки
    26. @found1: ...
    27. @found2: ...
    28. @found3: ...
    29. @exit:
     
  20. cresta

    cresta Active Member

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

    В теории всё это хорошо, а на практике может оказаться с точностью до наоборот. Надо эти теоретические посылы оформить в процедуру и посмотреть, как будет влиять (и в какую сторону) по-байтовость/по-двордность.



    К тому же когда по-двордно смещаться относительно строки, в случае если первый дворд совпал, а остальные-нет, думаю, что возвращаться к прежнему адресу сложнее, чем в побайтовом перемещении.


    Код (Text):
    1. ;------------------ поиск подстроки --------------------
    2.         mov esi,lpFileData
    3.         mov edi,lpMatch
    4.         mov eax,dword ptr[edi]
    5.         mov ebx,dword ptr[edi+4]
    6.         mov ecx,dword ptr[edi+8]
    7.         mov edx,dword ptr[edi+12]
    8.  
    9.         add DataLen,esi
    10.         sub DataLen,16
    11.         sub esi,4
    12.     @St:xor edi,edi
    13.     @@: add esi,4
    14.         cmp eax,dword ptr[esi]
    15.         je @Fnd_0
    16.         cmp eax,dword ptr[esi+1]
    17.         je @Fnd_1
    18.         cmp eax,dword ptr[esi+2]
    19.         je @Fnd_2
    20.         cmp eax,dword ptr[esi+3]
    21.         je @Fnd_3
    22.         cmp esi,DataLen
    23.         jle @B
    24.         jmp @No
    25.  @Fnd_3:inc edi
    26.  @Fnd_2:inc edi
    27.  @Fnd_1:inc edi
    28.  @Fnd_0:add esi,edi
    29.         cmp edx,dword ptr[esi+12]
    30.         jne @F
    31.         cmp ecx,dword ptr[esi+8]
    32.         jne @F
    33.         cmp ebx,dword ptr[esi+4]
    34.         je @found
    35.         @@:
    36.         sub esi,3
    37.         jmp @St
    38.  @found:mov eax,esi
    39.         ret
    40.     @No:or eax,-1
    41.         ret
    42. ;-------------------------------------------------------




    К тому же алго позволяет не привязываться жестко к 'abcdefgh...'. Строка может быть любая.



    P.S.

    Сейчас попробовал
    Код (Text):
    1. @@:add esi,4
    2.    mov eax,[esi]
    3.    cmp eax,'ELES'
    4.    je @Fnd_0
    5.    cmp eax,'CELE'
    6.    je @Fnd_1
    7.    cmp eax,'TCEL'
    8.    je @Fnd_2
    9.    cmp eax,'ITCE'
    10.    je @Fnd_3
    11.    cmp esi,DataLen          ;'SELECTIONWITHIN '
    12.    jle @B
    13.    jmp @No


    так получилось медленней, ~ на 8% ...