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

cresta



> "Моя процедура быстрее, если.."

> "Твоя процедура быстрее, если.."

> "Мне кажется есть смысл для разных образцов по разным смещениям получить время в тиках на байт и вывести среднюю скорость. Надо попробовать собрать статистику."



Прежде чем набирать статистику думаю стоит разобраться с закономерностями

Положение в файле влияет только косвенно, а основная зависимомость сидит в статистике символов в файле и положении наиболее вероятных символов в образцовой строке. Т.к. в windows.inc наиболее частый символ - пробел, то можно получить такую зависимость: берем строку из невероятных символов, например "ъ", вставляем по одному пробелу и смотрим результаты в зависимости от положения пробела. Вот результаты для P4, цифры загрублены и отброшены младшие разряды (т.е. это тысячи при размере поиска 300000):

Код (Text):

1. ------  ------------ положение пробела в строке match="ъъъъъъъъъъъъъъъъ" ------------------
2. метод   нет   1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16
3. ------  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---
4. BMH     130   [b]<=[/b]   =    =    =    =    =  [b]~800-850[/b]   =    =    =    =    =    =  [b]=>[/b]   280
5. fts     260  270  290  290  310  300  330  325  345  330  370  380  420  430  490  580  [b]900[/b]
6. scan2   220  250  250  250  250  290  290  290  290  370  370  370  370  220  220  220  220

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

Как видим мой вариант dw_scan2 дает предсказуемые результаты, т.к. прыжки идут с дискретом на 4 и лучшие результаты ес-но получаются когда bad-сивол расположен в первом или последнем дворде (прыжок на 12 или 16).



Твой вариант fts в целом тоже ведет себя как положено - задержка монотонно нарастает, т.к. величина прыжка уменьшается. Но ты видишь как "катастрофически" возрастает задержка, если пробел расположен в конце. Почему ? Если бы пробелы были разбросаны поодиночке случайным образом как в обычном тексте, то такого бы не было. А тут мы имеем длинные серии пробелов. Натыкаясь на такую серию твой алгоритм начинает "глупо" переберать каждый пробел (или каждый второй или третий) и соответсвенно затыкается почти на каждой серии. Кстати такая же ситуация может встретиться и в бинарных файлах с длинными сериями нулей если образец заканчивается нулем. Тебя это не смущает ?



Еще одно явное различие между алгоритмами - в твоем варианте ищется начало строки, а в моем - конец. Соответсвенно вероятность ложных захватов должна зависеть насколько частое сочетание символов стоит в начале строки или в конце. Думал, щас попробую продемонстрировать и обломс - никакой заметной разницы при совпадении 4 символов не видно:

Код (Text):

1.   образец строки     fts   scan2
2. -----------------    ---   ---
3. " equъъъъъъъъъъъъ"   295   255
4. "equ ъъъъъъъъъъъъ"   320   260
5. "ъъъъъъъъъъъъ equ"   500   225
6. "ъъъъъъъъъъъъequ "   950   240

Практически те же цифры, что и без совпадения - предсказатель переходов, что ли настраивается ...

 

То, что последний символ для fts - это его слабое место, понятно. У меня есть 3 мысли в эту сторону:

1. Если после проверки байта [esi+16] прыжок вперед слишком мал (часто повторяющийся символ в конце образца), то проверить дворд [esi+12]. Возможно это даст доп. инфу, и можно будет увеличить минимальный прыжок с 1 до 5 байт.

2. Если после проверки байта [esi+16] прыжок вперед слишком мал, попытаться быстро определить наличие в куске esi+прыжок - esi+15 символа, не входящего в образец.

3. Попробовать использовать пустой старший ворд ячейки, и за счёт усложнения заполнения таблицы, впихнуть в него доп. информацию о взаимоположении символов в строке.



Основная сложность в этих трех возможных вариантах - свести к минимуму количество jcc, в идеале вообще без них обойтись, как это сделано на данный момент.

Ты остановился на самой границе Стоило продолжить и там такая картина: Зависимость времени от количества частых символов в конце строки, начинающейся с несуществующего символа.

Код (Text):

1. ------  ------------ кол-во пробелов в конце строки match="ъъъъъъъъъ       " ---------
2. метод   нет   1    2    3    4    5    6    7    8    9   10   11   12   13   14   15
3. ------  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---   --
4. fts     244   <=   =    =    =    =    =  ~1140-1160   =    =    =    =    =  =  =  =>
5. scan2   <=   = 268   =  =>  350  869 1649  <=   =   =   = ~ 2509-2560 =  =   =   =  =>

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

Для моего случая - это байт. Один байт спасает, далее начинается тормоз. Тормоз для побайтного метода fts меньше чем для подвордного метода scan2.

Условная усредненная цена промаха, вызванного последними неудобными символами получается для fts - 1394 ед. для scan2 - 1671 ед.

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

похоже она тоже нервно реагирует, как и BMH на пробелы в windows.inc. На другом уровне (меньшем), но тоже ярко выражено. Ну собственно, от этого не уйти, хотя можно попытаться от одного метода что-то применить в другом.

Надо думать.

 

Да, более 4 повторяющихся символов в конце строки для недоделанного варианта dw_scan2 это плохо. А все из-за дурных прыжков внутрь цикла @r0..@r2. Они мне сразу не понравились, но отложил на потом. Вот теперь исправил и стало гораздо лучше (dw_scan3). А суть такая: если совпадение было со смещением 3 то возврат в конец цикла на @r3, т.к. больше вариантов нет. А если со смещением 0,1,2 то проверяем совпадение начала строки (возврат на @Fnd_0 с приращением edi - т.е. получается второй "ближний" цикл проверки). Как все проверили возврат всегда в одну точку @r3. Результаты на P4:

Код (Text):

1. ------  ------------ кол-во пробелов в конце строки match="ъъъъъъъъъ       " ---------
2. метод   нет   1    2    3    4    5    6    7    8    9   10   11   12   13   14   15
3. ------  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---   --
4. fts     255   <=   =    =    =    =    =    =    =    =   ~900  =    =    =    =   =>
5. scan2   220  220  220  220  350  900 1200  1200  <=   =  ~1500  =    =    =    =   =>
6. scan3   220  220  220  220  300   <=   =    =    =    =  ~ 570-620   =    =    =   =>

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

 

У меня наоборот, за счет перехода к двордам: был movzx eax,[из тбл]-> add esi,eax заменил на add esi,[из тбл]. прибавилось 7-9% скорости.

Далее перевернул цикл кверх ногами, освободил регистры и стал хранить в них дворды образца, ну в общем оптимизация кое-какая, итог очень даже, скорость возросла на 15-26% (!) только за счёт того, что причесал код. Причем макс. прибавка в самом неудобном случае - в конце строки пробелы. По-моему, код получился настолько компактный и организованный, что малейшая попытка улучшить оборачивается только потерями. Имхо дальше некуда придумывать, разве что ещё принципиально другой вариант придумывать.

В общем посмотри оптимизированный вариант.

Код (Text):

1. find_tbl_scan_1 proc lpFileData:DWORD, DataLen:DWORD
2. option prologue : none
3. option epilogue : none    
4.     push ebx
5.     push ebp
6.     push esi
7.     push edi
8.     sub esp,1024                    ;LOCAL forward_tbl[256]          :DWORD
9.    
10.     mov ecx,256
11.     mov edx,16
12.     dec ecx
13.    
14. fill:   ;-- забиваем 16 (длина строки) во все 256 двордов таблицы
15.     mov [esp+ecx*4],edx
16.     mov [esp+ecx*4-4],edx
17.     mov [esp+ecx*4-8],edx
18.     mov [esp+ecx*4-12],edx
19.     sub ecx,4
20.     jns fill
21.    
22.     xor ecx,ecx
23.     mov edi,offset match
24. put_offset:;-- заполняем таблицу значениями максимального скачка, на которое можно подвинуть esi
25.     movzx eax, byte ptr[edi+ecx]    ;байт из строки образца
26.     mov [esp+eax*4],ecx             ;запись его смещения в таблицу соответственно кода этого байта
27.     neg dword ptr[esp+eax*4]        ;будем прибавлять esi, поэтому neg
28.     add dword ptr[esp+eax*4],16     ;и +16 (длина строки)
29.     inc ecx
30.     cmp ecx,16
31.     jne put_offset
32. end_put:                            ;таблица заполнена такими значениями:
33.                                     ;если 16-й байт от esi (esi+16) не входит в образец,
34.                                     ;то максимальный скачок +16
35.                                    
36.                                     ;если 16-й байт от esi (esi+16) входит в образец
37.                                     ;со смещением  0 - макс.скачок = +16 (add esi,16)
38.                                     ;со смещением  1 - макс.скачок = +15 (add esi,15)
39.                                     ;...................................
40.                                     ;со смещением 14 - макс.скачок =  +2 (add esi,2)
41.                                     ;со смещением 15 - макс.скачок =  +1 (add esi,1)
42.    
43.     mov esi,dword ptr [esp+1044]    ;lpFileData
44.     mov edx,esi
45.     add edx,dword ptr [esp+1048]    ;DataLen
46.     sub edx,16
47.     mov eax,[esi]
48.     mov ecx,dword ptr[match]
49.     mov ebx,dword ptr[match+12]
50.     mov ebp,dword ptr[match+8]
51. align 4
52.  
53.  
54. start:
55.     cmp eax,ecx                     ;проверка первого дворда от текущего esi
56.     jne @F                          
57.     cmp [esi+12],ebx                ;если дворд совпал - проверка остальных
58.     jne @F
59.     cmp [esi+8],ebp
60.     jne @F
61.     mov eax,[esi+4]                 ;не хватило одного регистра для красоты :-(
62.     cmp eax,[edi+4]
63.     je found
64.  @@:
65.     movzx eax, byte ptr[esi+16]
66.     add esi,[esp+eax*4]
67.     cmp esi,edx
68.     mov eax,[esi]
69.     jle start
70.     ;-- тут особенностей нет.
71. no_match:
72.     or eax,-1
73.     jmp @Ret
74.    
75. found:        
76.     mov eax,esi
77.     sub eax,dword ptr [esp+1044]    ;lpFileData
78. @Ret:
79.     add esp,1024
80.     pop edi
81.     pop esi
82.     pop ebp
83.     pop ebx
84.     retn 8                      ;return file offset of substring or -1 if not found
85.  
86. find_tbl_scan_1 endp

А свою причесаную процедуру что не показываешь?

 

> "А свою причесаную процедуру что не показываешь?"



Торопился, да еще ляпу сделал и в итоге результаты чересчур преукрасил

В исправленном варианте при числе пробелов > 4 на P4 получается не ~600, а ~850-900 (примерно или чуть лучше, чем в твоем предыдущем варианте).



Насчет оптимизации. Это дело хорошее если только не под конкретный проц

Например на P3 все соотношения могут измениться в обратную сторону и т.к. тут одни мувы, сравнения и сложения, то и число тиков получается примерно вдвое больше чем на P4

Время будет - посмотрю что на P3 творится



В аттаче исправленный вариант dw_scan3



220120773__dw_scan3.rar

 

cresta



На P4 твой оптимизированный вариант fts1 дает выигрыш ~5-10% по сравнению с fts, причем особой зависимости выигрыша от положения пробела незаметно (похоже на случ.разброс или периодичность).

А вот на P3 выигрыш получается гораздо больше особенно при малых скачках. Вот некоторые результаты на P3 в зависимости от положения пробела в "ъ..ъ":

Код (Text):

1. метод   нет  ...   12    13    14    15    16
2. ------  ---  ---  ----  ----  ----  ----  ----
3. fts     975?      1100  1200  1220  1450  2050
4. fts1    960?       890   950   950  1050  1380 ;~49% !
5. scan2   945?       920   790   790   790   790
6. (? Что-то первый результат не бьет, надо бы перепроверить -
7. общий разброс довольно большой, прикидывать среднее или наиболее частое довольно трудно)

А как тебе число тиков - впечатляет ? Мало того, что частота в несколько раз ниже, так еще и число тиков в несколько раз больше ((



А с моим подправленным вариантом на P4 тоже фиг знает, что происходит - какая-то нестабильность при большом числе пробелов в конце строки: идут группы значений то 800-950, то от 1000 до 1500

Наверное global branch history все поганит - уж и не знаю чего тут еще можно сделать



Вроде как твой вариант в среднем предпочтительнее получается

 

fts1 можно ускорить ещё на ~3-4%, если нормально инициализировать таблицу: я её для отсутствующих в строке символов проинициализировал значением 16, а надо 17 (перестраховался и забыл об этом). Т.е. mov edx,16 в начале процедуры заменить на на mov edx,17 и после первого цикла вставить dec edx. Это положительно сказывается на неудобных строках.



Попробовал find_dword_scan3 как с байтовой, так и с двордовой таблицей: разницы на моем Атлоне нет. А вот три варианта возврата - тут третий вариант лучше (тот который раскомментирован). Первый - хуже всего. В тиках соотношение 170-154-139.



Надо теперь попробовать с минимальными потерями сделать вариант, не ограниченный размером 16 байт. В принципе он уже есть, и на снятии ограничения 16 байт теряется порядка 10-12%. Это если все проверки загнать в циклы, а не раскладывать на 4 подвордные проверки.

Можно оставить проверку первых 16-ти так как сейчас есть, а на метке found допроверить оставшуюся длину образца.

Для find_dword_scan3 похоже только допроверка может снять 16-ти байтное ограничение, или у тебя есть намётки, как можно организовать всю длину образца в цикл? Я честно говоря, запутался в твоей таблице

 

Artemy

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



http://www-igm.univ-mlv.fr/~lecroq/string/node1.html

 

SDragon, спасибо, хорошая ссылочка



Просмотрев кучу методов из указаной статьи, я прихожу к таким выводам:

1) Основных идей не так много и они либо давно известны либо лежат на поверхности, поэтому многие из приведенных вариантов являются лишь незначительными модификациями (либо упрощениями, либо усложнениями - ради науки или увековечивания своего имени - типа "а еще вот так можно" ) Из оригинальных подходов пожалуй можно отметить только метод Tuned Boyer-Moore

2) Как и следовало ожидать, быстродействие методов оценивается по количеству сравнений символов без учета реализации ветвления и доп.вычислений на современных компьютерах. В итоге метод с наименьшим числом сравнений может на практике оказаться и не самым быстрым.

3) Как и следовало ожидать Horspool не такой "тупой", как его реализовали в BMH.asm в masm32

4) Последний вариант cresta является усовершенствованным вариантом метода Quick Search (сравнение символов с начала строки и переход по shift_table по символу +MatchLen). Усовершенствование разумеется в использовании сравнения не одного символа, а сразу 4-х (dword).

5) Чего-то ничего о возможности сравнения двордов в этом обзоре не говорится - то ли ребята увлеклись посимвольным сравнением, то ли вынесли эту возможность за скобки, посчитав что это разумеется всегда в плюс. А в итоге получается, что для рассматриваемого в обзоре примера вариант cresta бъет все рекорды, т.к. требует всего 5 сравнений вместо 11 и более для прочих рассмотренных методов

 

Ссылка хорошая, да только что-то ни один алгоритм не хочет у меня нормально компилироваться Сделал как либу - vc++ компилит без ошибок, линкуется к масму тоже без ошибок, а работать - хрен Пробовал штук 5 разных алгоритмов - либо возвращают -1, либо вылетает программа.

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



Я пробовал что-то типа RAITA, только немного по другому: не сравнивать первый, средний и последний байт, а делал 1-й xor средний xor последний, и записывал это значение. Чтобы разом три байта проверить. Но что-то не понравилось, не помню что. Надо попробовать ещё раз.

Пока сделал полноценный вариант без ограничения 16 байт. Сравнить есть только с BMH. Имхо, масмовый BMH побыстрее будет, чем алгоритмы с си-шной memcmp.







_1103497728__FJT.zip

 

cresta



Масмовские варианты BM, SBM и BMH это какие-то урезаные обгрызки настоящих алгоритмов

Попробовал я реализовать классический BM, да запутался в заполнении suffix_table поэтому попробовал частный случай для одной серии символов в конце строки (под наши тесты, когда match содержит серию пробелов в конце). Хорошие результаты получаются, однако !

Недостаток наших и масмовских вариантов в том что они не используют good suffix table. Ведь что получается если использовать только shift_table. Пусть строка имеет два пробела в конце, тогда если встречается пробел, то shift_table дает нам сдвиг всего на 1. Но это же глупо, т.к. после сдвига этот пробел попадает внутрь окна просмотра и заведомо не даст никакого совпадения:

Код (Text):

1. "ъъъъъъъъъъъъъъ  "
2. >"ъъъъъъъъъъъъъъ  "                ;+1 по shift_table
3. >>>>>>>>>>>>>>>>"ъъъъъъъъъъъъъъ  " ;+16 по suffix_table

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

Поэтому настоящий BM работает так:

1) проверяется совпадение последнего символа

2) если нет, то скачок по shift_table

3) если да, то ведется сравнение строки от конца к началу с подсчетом числа совпадений (длины суфикса)

4) при несовпадении по длине суфикса берется скачок из suffix_table и возврат к 1)



Вот прикидочные рез-ты на P4 для windows.inc и строки "ъъъ.. " в зависимости от числа пробелов в конце строки:

Код (Text):

1. Метод       нет   1    2    3    4    5    6    7    8    9   10   11
2. tbl_scan_1  225  845  845  845  845  850  850  850  850  850  850  850 < 850 >
3. dw_scan3    210  210  210  210  405 1000 1000 1000 1000 1000 1000 1000 <~1000>
4. BMS         210  255  300  350  390  490  540  600  650  810  870  870 < 920-1000 >

Т.е. классический BM всетаки рулит и надо бы разобраться с заполнением таблицы суфиксов для общего случая ...



Вариант реализации для частного упрощенного случая suffix_table (под одну серию повторяющихся символов в конце строки):



839917904__BMS.inc

 

Результат хороший, вот только таблица суффиксов заточена под одну единственную строку ъъъъъъъъъъъъъ____, на других образцах процедура даёт сбои (проскакивает мимо образца, не замечая его). На строках более 16 такое происходит оч. часто, на 64 байтных строках она вообще ни одной строки не нашла Получается, что процедура делает недопустимые предположения и скачет слишком оптимистично. Такого рода вариант уже есть - масмовый SBM.



Если реализовать полноценную процедуру, то может получиться, что появятся разного рода коллизии, на разрешение которых уйдёт недопустимо много времени.

Вообще, на мой взгляд, две таблицы умозрительно должны были дать лучший результат, тем более для фиксированной строки.



А пока я у себя немного подправил хвост строки в варианте с неограниченной длиной образца.



1416769734__FJT.inc

 

Насчет длинных строк - забыл предупредить. Это пробный вариант, поэтому длину массива suffix_table я на шару взял фиксированной = 32. А по уму конечно надо делать через sub esp,lpSubLen.



А насчет одной единственной строки - странно, я тоже на одной строке проверял - неужели на этой же ?! Да вроде бы для хвостов и логика заполнения suffix_table элементарная Надо проверить...



Насчет разного рода коллизий - не знаю где они могут появиться. Таблицы одинаковые по смыслу, но разные по назначению. Shift_table работает в случае несовпадения и показывает есть ли в строке такой символ и насколько надо сместиться, чтобы подставить esi под этот символ. Suffix_table делает примерно тоже самое, но в случае совпадения L символов с конца. Т.е. есть ли еще такая серия длиной L в строке и если есть насколько нужно изменить esi, чтобы эта серия в строке совместилась с текущей серией в тексте. Поэтому думаю, если не наделать ошибок при заполнении suffix_table, то все должно работать

 

Сейчас перепроверил на длине 32 байта (с оффсета 50000) - в двух случаях из 20-ти промах



Мне не очень понятна сама задача оптимизации под случай, когда образец имеет несколько совпадающих символов в конце. Имхо, такие образцы на практике не встречаются вообще. Трудно представить случай, когда нужно было бы найти строки, заканчивающиеся на несколько пробелов (или других символов). Если даже таковая гипотетически появится, то её логичней решать как поиск чистых нескольких пробелов. Мы решаем задачу, которая никогда не будет востребована.

Самая типичная задача для файлов, подобных windows.inc - это парсинг на предмет разного рода констант. И образцы в подавляющем большинстве случаев имеют совершенно противоположную структуру: несколько частовстречающихся символов в начале образца: WM_, ERROR_ и т.п.

Что думаешь по этому поводу ?

 

Я тоже перепроверил (правда на 16). Для того случая что задумана - вроде работает нормально. А случай это частный только для проверки того что может дать suffix_table. Должна работать для строк удовлетворяющих условию: если Х - последний символ строки (любой), то в строке допускается только неразрывная серия из таких символов в конце строки и нигде больше, т.е. match = {любые символы != X}+{N символов X, где N = 1,2 ..} и общая длина < 32. А cделал я эту фигню, только потому что таблица получается элементарная, а с настоящей пытаюсь разобраться - но возни уж больно много



> Имхо, такие образцы на практике не встречаются вообще

> Мы решаем задачу, которая никогда не будет востребована



Помнится не так давно ты говорил нечто совсем другое

 

Есть такое, обратил внимание на неудобные символы в строке Только что-то мы на них только и зациклились.

Идея с помощью второй таблицы увеличить минимальный сдвиг в принципе хорошая, только если образец большой, то не станут накладные расходы на таблицу чрезмерными?

не пробовал воспользоваться теми готовыми алгоритмами (которые по ссылке были)?

 

Кто то еще следит за форумом? Я решаю похожую задачу.
http://forum.sysfaq.ru/index.php?showtopic=22536

 

Не знаю поможет ли, но поиск подстроки в строке можно выполнять за линейное время (в худшем случае, если искомая подстрока находится в конце строки). Идея простая:
1) заводим 2 счетчика: 1 - индекс элемента в строке, 2 - в подстроке
2) на каждой итерации сравниваем элемент, на который указывает счетчик в строке и элемент, на который указывает уже 2 счетчик (указатель, если "по русски") в подстроке (сравниваем 2 байта или символа)
3) если элементы совпали, то делаем инкремент обоим счетчикам. Если не совпали - делаем +1 счетчику строки, а счетчик для подстроки снова на 1 позицию устанавливаем
4) если счетчик в подстроке указывает на последний её элемент, то в любом случае делаем inc счетчику строки, и , так как подстрока найдена, выходим из цикла и возвращаем "ТЕКУЩИЙ счетчик в строке - длина подстроки".

 

Примерчик

Код (Text):

1. var Str, subStr:String;
2.     i, j, subStrLen : integer;
3. begin
4.  Str := 'dkfjgjksdkgjhdfksjghkjdfshgjhdksfhruieotiourisetuojkl,mnb';
5.  subStr := 'iou';
6.  i := 1;
7.  j := 1;
8.  subStrLen := length(subStr);
9. repeat
10. if SubStr[j] = Str[i] then inc(j)
11.                       else j := 1;
12. inc(i);
13. until j = subStrLen + 1;
14. writeln( 'Index of SubString: ', i - j ); //напечатает 40, как и должно быть :)

 

Как способ оптимизации этого метода: вести поиск "с двух концов сразу", только " с конца" искать подстроку в обратном порядке. Тогда худшее время будет N/2. Когда подстрока встречается 1 раз и посередине строки, в которой производится поиск.