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

Поклонникам Boyer-Moore Fast String Searching Algorithm'а



Алгоритм Бойера-Мура позволяет уменьшить среднее число просматриваемых (сравниваемых) символов при наличии ложных совпадений. Идея конечно здравая, но в классической реализации алгоритма есть несколько протеворечивых НО. Во-первых, не учитывается статистика распределения символов в тексте (если это осмысленный текст, а не случайный набор байтов). В режиме поиска идет сравнение с последним символом искомой строки. А что будет если мы захотим найти нечто вроде "Смирнофф" в русском тексте ? Правильно, этот хваленый алгоритм будет работать как обычный линейный просмотр. Получается некий парадокс - алгоритм дает выигрыш именно при наличии ложных совпадений, т.к. только в этом случае он может перескочить через N-е количество символов и дать какой-то выигрыш.

Тут приходим ко второму НО - возможно такой подход и давал выигрыш на древних ЭВМ 70-80х годов, когда переход по ветвлению практически ничего не стоил. Даже на i486 разница между taken и not-taken переходами была сравнительно небольшой (3 такта против 1). А что мы имеем на сегодняшний день: на P6 непредсказанный переход стоит > 10 тиков, на P4 Northwood > 20, на Prescott'ах аж за 30. И что будет если мы в соответствии с Бойером-Муром будем стремиться отлавливать ложные совпадения, чтобы уж затем скакнуть вперед сразу на 5-10 символов. Обяснять думаю не надо, что на штрафе за переход мы можем потерять больше чем за счет пропуска нескольких "жалких" символов.



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

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

 

cresta



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



А ты ничего не путаешь, может опять указатель lpFileData забыл выравнять Да и выравниванием метки цикла конечно пренебрегаешь

А проц у тебя какой, я подзабыл ?



Не удивляйся, но на PIII с выравненными на 16 циклами твой вариант дает 2400 тиков на сканирование 1000 несовпадающих байт, а мой вариант только 1500 (как и при побайтном сканировании). Это тебе не ~8%, а 60% !!! Вот тебе и практика ))

 

cresta



Кстати на P4 Northwood (CPUID = 15.2.7) ситуация аналогичная и цифры близкие: на сканирование 1000 байт (без совпадения) твой вариант дает 2270 тиков, а мой 1530 с hard-coded строками или 1550 с регистрами (включая загрузку регистров).

Но это ес-но чистое сканирование. А обработку совпадений нужно как-то отдельно смотреть.

 

leo



Ни фига не забыл А если и забыл, то VirtualAlloc его выровнял, нафига равнять ровное



Где он, твой вариант? Готовый, а не четыре строки? Дай потестить, посмотреть. А то может я не так использовал твои наметки :-( И на какого рода файлах и строках смотрел, а то разница есть: какая строка, в начале или в конце файла, бинарный или текстовый файл, как часто повторяются начальные фрагменты строки и т.д.



P.S.

Я тут кстати гуёвый вариант тестилки на скорость сделал, мож поглядишь-подскажешь чего, правильно/неправильно? В формате masm-radasm. А то тестилка от bogrus'a фасмовая, а куда же пользователям masm'а податься?

Может кому и сгодится Или ты на masm не смотришь?

 

Сделал по-двордное сканирование файла.

"Файл" - псевдослучайная последовательность 300000 байт. 16 байт выбраны в середине.

На Athlon 2200+ получилось в тиках:

Код (Text):

1. -----------------------------------------
2.  dword match | repe cmpsd | dword file |
3.    637 280      848 006       568 761
4.    321 238      624 235       255 710  
5.    350 941      649 655       255 662  
6.    321 232      653 731       302 300  
7.    321 189      648 064       255 650  
8.    321 189      648 074       278 475  
9.    321 189      646 257       255 652  
10.    344 071      647 884       255 650  
11.    321 189      624 183       255 650  
12.    321 220      646 270       255 650
13. -----------------------------------------

Сами процедуры и тестилка в аттаче, если автору ещё интересно

60% тут конечно нет, устойчиво 25-27%, с небольшими вариациями ~1-2% для разного типа файлов и строк.



P.S.

Интересно было бы посмотреть рабочую реализацию алгоритма Бойера-Мура на асме, может есть у кого?

 

cresta



> "разница есть: какая строка, в начале или в конце файла, бинарный или текстовый файл, как часто повторяются начальные фрагменты строки и т.д."

> "Файл - псевдослучайная последовательность"



Ну вот сам себе противоречишь Псевдослучайный фай - это завершаюющая стадия, возможно и не нужная, т.к. не понятно как результаты сравнивать - только большую статистику набирать. Если уж брать то какой-нибудь общедоступный текст или бинарный файл, например exe-шник.

А по хорошему задачку нужно разбить на части:



1) Скорость сканирования при отсутствии любых совпадений - просто скорость перебора байтов (или двордов в расчете на байт). Я тебе именно результаты простого перебора и приводил (при этом "файл" заведомо содержит только несовпадающие символы, например 00 или FF). По результатам видим, что проверка двордов обеспечивает ту же (практически предельную) скорость сканирования ~1.5 тика на байт, что и побайтное сканирование. Но при проверке двордами вероятность ложного совпадения теоретически ниже. Хорошо это или плохо надо смотреть дальше - как мы будем обрабатывать эти совпадения (дают ли "быстрые" методы а ля Бойер-Мур какой-то выигрыш и при каких условиях).



2) Начинаем смотреть как обрабатываются ложные совпадения. Истинные совпадения ИМХО и смотреть нечего - нашли и слава богу. Поэтому при обработке совпадения приоритет должен отдаваться ложному совпадению, т.е. оно должно обрабатывться быстрее истинного, чтобы в случае промаха быстрее продолжить сканирование. С точки зрения алгоритма хорошо бы проверить простые варианты с обычным продолжением и продвинутые варианты с пропуском заведомо несовпадающих отрезков и сравнить их с классическими побайтными fast searching а ля Бойер-Мур и др. А для первоначального тестирования надо бы брать не случайные данные, а специально подобранные: чтобы с одной стороны было известно количество промахов, а с другой стороны чтобы процессор не сумел подстроить под них предсказатель переходов - иначе получим слишком хорошие результаты. Размер файла думаю тоже не должен (заметно) сказываться на скорости - только скорость сканирования + количество ложных совпадений. Поэтому наверное, проще брать небольшие куски ~ 1..10Кб.

 

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



С первой частью проще, а вторая часть - это уже начинается разработка алгоритма. Соперничать с товарисчами Бойером и Муром как-то не хочется. Не будем отбирать у них хлеб.



В общем, я уже задолбался оптимизировать Пока более чем 3-х кратного увеличения скорости от первоначального хватит.

Результат в аттаче (процедуры №1 и №2)



_1304664089__speed_tester.zip

 

cresta



> "Соперничать с товарисчами Бойером и Муром как-то не хочется. Не будем отбирать у них хлеб."



Соперничать и отбирать хлеб ес-но никто не собирается, но равняться ИМХО следует на них, а не на некий заведомо не лучший "первоначальный" вариант. Мысли свои насчет "быстрых" алгоритмов я уже излагал, поэтому есть надежда на то, что за счет уменьшения ложных совпадений двордовое сравнение и без всяких наворотов окажется по крайней мере не хуже "быстрых" посимвольных.

 

Стабильней - это точно. Нашел две реализации Бойера-Мура (прямо в пакете масма оказались). Впечатление весьма странное. Обе реализации рабочие, но результаты ....

Код (Text):

1.     | образец строки     | Boyer-1 | Boyer-2 | dw scan |
2.     |---------------------------------------------------
3.     |                  файл windows.inc
4.     | "1234567890ABCDEF" |  303577 |  303831 |  441199 | нет в файле
5.     | "Macro Assembler " | 4235046 | 4239911 |  440834 |
6.     | "Macro  Assembler" |  986271 |  983656 |  440834 |
7.     |---------------------------------------------------
8.     | "abcdefghigklmnop" |  105285 |  105247 |  219308 | есть
9.     | "equ COLOR_BTNHIG" |  645668 |  646861 |  352672 |
10.     | "test string 16 b" |  516253 |  516326 |  216859 |
11.     | "CTLCOLOR_MAX    " | 2562264 | 2560419 |  334774 |
12.     | "COLOR_BACKGROUND" |  171455 |  171607 |  332830 |
13.     |---------------------------------------------------
14.     |                    файл ml.exe
15.     | случайн набор 16b  |  432950 |  432940 |  321487 | offset 2B3F0
16.     | случайн набор 16b  |  244358 |  244489 |  321482 | offset 2B400
17.     | "GetFileAttribute" |  200171 |  200304 |  413338 | offset 43390

Пары строк 2,3 и 9,10 показательны. 2 и 3 различаются одним пробелом, а результат - в 6 раз! Или для ехе файла два случайных набора, следующие друг за другом...

В общем, Бойер может как выиграть в два раза, так и проиграть в 10 раз. Причем невозможно определиться, на какого рода данных как он поведет себя. Что самое неприятное.

 

cresta



Вопросы:

1) Что у тебя скрывается за Boyer-1,2 (BM, SBM или BMH)

2) Уточни с какой скоростью работает find_dword_scan на твоем атлоне. У меня предыдущий тест дает ~8800 на PIII и ~7500 на P4 (15.2.7), т.е. 1.75 и 1.5 тика на байт. При обработке ml.exe у тебя получается ~1.8 и ~1.5, а как в "чистом виде" ?

3) На какой длине проверялся windows.inc (наверное 256-300 кб ?), чтобы тоже можно было пересчитать в скорость.



> "В общем, Бойер может как выиграть в два раза, так и проиграть в 10 раз. Причем невозможно определиться, на какого рода данных как он поведет себя. Что самое неприятное"



Насчет выиграть и проиграть, ты прав. Это же чисто статистический выигрыш, основанный на соотношении статистики символов в тексте и искомой строке. Но вот в отношении непредсказемости ты не совсем прав. На чисто случайных двоичных данных - конечно ничего не скажешь. А вот в отношении текстовых файлов вполне предсказуемо.

Известно, что BM-алгоритмы:

1) ищут совпадение последнего символа искомой строки (паттерна)

2) в случае несовпадения проверяют по таблице наличие несовпадающего символа в паттерне: если нет (impossible или bad character), то сразу перескакивают на длину строки N, если есть (good suffix) то перескакивают на соответсвующее число символов x < N, чтобы эти символы в тексте и паттерне совпали. Кстати стратегия прыжков по good suffix на малые расстояния, как я уже отмечал в своем опусе для поклоников BM, в среднем не дает выигрыша на "современных" процах, т.к. затрудняет предсказание переходов и не компенсирует штрафы на непредсказанные переходы. Поэтому в алгоритме BMH прыжки по good suffix не используются.



Ну и что мы имеем. В файле windows.inc суперпопулярным символом является пробел (причем не одиночный, а длинные серии пробелов). Поэтому наихудшие (ужасные результаты получаются если наш паттерн заканчивается на пробел и содержит еще пробелы. В этом случае, во-первых, сканирование постоянно натыкается на пробелы в тексте и код идет по ветке проверки следующего символа и ес-но обламывается. Стратегия перескока по bad-символу на пробелах не срабатывает, т.к. в паттерне есть еще пробелы (поэтому алгоритм BMH вообще отдыхает). Стратегия good suffix в BM и SBM смещает указатель чтобы текущий пробел текста совпал с пробелом в паттерне. И что ? А то что серии пробелов в windows.inc очень длинные (десятки пробелов) и алгоритм опять попадает в аналогичную ситуацию. Казалось бы хорошо - предсказатель переходов может подстроиться. Да нет серия пробелов заканчивается на втором-третьем прыжке и начинает рулить стратегия bad-символа. В результате сплошные штрафы на прыжках.

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

Ну а когда все таки получается выигрыш ? Ес-но основной выигрыш на "современных" процах получается за счет стратегии bad-символа. И обилие пробелов в файле этому только помогает, отсюда выигрыш на строках 1,4 и 8. А наилучшие результаты (относительно dw_scan) показывает 4-я строчка, т.к. она содержит только малые буквы, а windows.inc изобилует прописными буквами, поэтому чаще выполняется условие bad-символа и алгоритм лихо скачет сразу через 16 байт текста.



Поэтому все довольно хитро, и для гарантированного выигрыша от BM-алгоритма желательно все таки иметь представление о тексте, в котором осуществляется поиск. Иначе как видим можно нарваться не на выигрыш, а на огромные потери. Хотя к упрощенному BMH-алгоритму это относится в меньшей степени, но все же лучше, когда паттерн заканчивается не на самый популярный символ.

 

Boyer-1 - SBM, Boyer-2 - BMH. Файл .inc был ограничен до 300000, строки примерно в середине выбирал, в районе 147,4-148,8 кб (наиболее характерные), свои строки (4,6) вставлял в районе 149,1 кб.

Файл ml.exe не ограничивал, чтобы посмотреть, как будет с поиском имен api. (Они за 300 кб находятся).



find_dword_scan на строках 5,7,8 дает 2,2 тика/байт. На строках 4,6 - 1,5 тика/байт. Для ml.exe - 1,8, для случайного random-набора 1,2 тика/байт.

Примерно так и должно быть, строки 5,7,8 дают наибольшое кол-во ложных срабатываний, случайный набор - наименьшее.

find_dword_scan в случае "угаданного" символа не скачет так быстро, как SBM/BMH, но зато и промашки не оказывают на него такого катастрофического влияния.

 

cresta



Так значит получается, что на Атлоне BMH и SBM дают примерно одинаковые результаты. А как интересно на P4. Ты чего аттач то не прицепил, пожалел ? Можешь только ехе-шник выложить и путь к masm32 указать



> "find_dword_scan на строках 5,7,8 дает 2,2 тика/байт"



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



> "Бойер может как выиграть в два раза"



И dw_scan наверное тоже сможет, если прикрутить стратегию пропуска bad-символов.

Вроде бы и затраты небольшие - всего-то килобайтный массивчик заполнить



1) Нужно перейти от сканирования первого дворда к сканированию последнего. (Это кстати может дать и свои косвенные преимущества, если сочетания символов в конце паттерна менее вероятны чем в начале - в windows.inc это однозначно так: возьми хоть "equ ..", хоть "COLOR.." хоть еще чего). Обработка совпадения вроде бы существенно не изменяется, просто вместо плюсовых смещений будут минусовые.



2) При сканировании вместо add esi,4 делаем and eax,0FFh и add esi,[eax*4+shift_table]



3) Ну и массивчик shift_table из 256 двордов перед началом поиска заполнить. Сначала забивам все длиной искомой строки минус 4 = 12 (ПОПРАВИЛ: 12, а не 16, т.к. мы берем только первый bad-байт дворда, а искомая строка может начинаться уже со 2-го байта). Затем пробегаемся по символам строки и по простому забиваем в соответствующие ячейки четверку: mov al,[edx+i] и mov [eax*4+shift_table],4.

Можно чуть посложнее: для первого символа 12, для следующих 4-х 8, а для остальных 4 (понятно, что если мы записали 12 для первого символа, но такой же символ встретится ближе к концу строки, то значение в таблице перепишется на 4).



Ну как, дерзнешь посоревноваться с BM-уром

 

Да не пожалел я ничего просто не подозревал, что у тебя нет масма и его файлов. Нашел ещё один BM (видимо классический) надо его тоже погонять. Все 4 процедуры в аттаче.

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

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



_728698848__attach.zip

 

cresta



> "просто не подозревал, что у тебя нет масма и его файлов..Все 4 процедуры в аттаче"



Ты меня не понял - это у меня все есть. Просто лень встраивать все это добро в твой speed_tester раз у тебя готовые тест.инки есть. Тем более, я в масме не силен, впрочем как и в прочих каламбурчик



> "Если делать таблицу по образу и подобию, то в конечном итоге придём туда же, куда пришли Бойер с Муром "



Туда же в смысле ускорения, но не ухудшения.

Я же предлагаю использовать таблицу только в случае несовпадения. В простом варианте мы увеличиваем esi на 4, а тут - если символа заведомо нет в строке, то можно сразу увеличить esi на 12 (не на 16, а на 12, т.к. мы проверяем только 1-й байт, а искомая строка может начинаться со второго). В худшем случае AND r,i и ADD r,m вместо ADD r,i прибавят 1-2 тика к времени сравнения 4 байт, т.е. в итоге 0.25-0.5 тика на байт если скачок на 4, но если скачок = 12, то сразу большой выигрыш. А на предсказание переходов это никак не влияет, т.к. никакого ветвления не происходит. Думаю такой вариант даже побыстрее BMH будет. Во-первых, за счет сравнения по 4 байта реже происходят совпадения и код реже скачет с ветки на ветку. Если искать не первый, а последний дворд строки, то возможно ложных совпадений будет еще меньше (конечно, не для всех случаев, но для "equ" и т.п. - точно). После совпадения переходим к проверке с противоположного конца строки - тоже возможный плюс в смысле вероятности сразу отсечь мусор. Во-вторых, BMH ИМХО тоже не идеал : в нем сомнительный переход jne Exit_Test сидит, а для P6 еще и нехорошая комбинация - запись в al и чтение eax (классический partial register stall). Одним словом, опасения напрасны - может быть только лучше (в среднем



> "Чтобы не потратить время впустую и не сорваться в повторение пройденного."



Ты же видишь сколько усовершенствованных вариантов классического BM расплодилось, т.к. идея в целом хорошая и правильная, но реализация для современных гиперконвейрных процев никуда не годится. Поэтому если прицепить к find_dword_scan табличку shift_table, да еще приспособить его под произвольную длину строки >= 4, то в итоге может родиться достойный современный вариант, типа BM4

 

В аттаче инклюды. 1-SBM, 2-find_dword_scan, 3-BM, 4-BMH.

Обрати внимание на 3-BM, он практически по всем тестовым строкам значительно превосходит свои "усовершенствованные" аналоги. И очень достойно ведет себя на текстах, как типа windows.inc, так и простых литературных. Имхо, если надо равняться, то на этот вариант, а не на усовершенствованные.

Возможно SBM и BMH были заточены под какие-то определенные цели, но под какие, я не смог определить.



1990619931__test_inc.zip

 

Ошибочка закралась в test_1.inc нужно строку

call BMHBinsearch заменить на

call SBMBinSearch

 

cresta



Что-то твой азарт поиссяк "Достойный" BM очаровал или времени нет ?

Ничего достойного я в нем не нашел и работает он на P4 в среднем хуже чем SBM, но много лучше чем BMH, насчет которого у меня сразу подозрения были.



А я вот нашел время поковыряться (методом тыка ес-но с масмом\радасмом и твоим спид_тестером и в итоге все таки получился супербыстрый вариант. Суть я уже излагал, но внес некоторые поправки. Суть такая:

1) сканируем последний дворд строки

2) если нет совпадения: делаем приращение esi по таблице по значению последнего (старшего) байта дворда:

movzx eax,[esi+3] ;esi еще не изменен

add esi,[eax*4+shift_table]

Использование последнего байта позволяет скакать в случае несовпадения на 16 байт. Табличка заполняется так: сначала все = 16, затем для символов строки 1..4 забивается 12, для 5..8 -> 8, для 9..12 -> 4, а для 13..16 не изменяется (т.е. либо 16 если такого символа больше нет в строке, либо то что записалось для символов 1..12).

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

Вот некоторые результаты на P4 Northwood (CPUID=15.2.7) 1.8GHz на первых 300000 символах файла windows.inc:

Код (Text):

1.     | образец строки     |   BM    |   SBM   |   BMH   |dw_scan2 |
2.     |------------------------------------------------------------|
3.     |                  файл windows.inc                          |
4.     | "1234567890ABCDEF" |  263582 |  266498 |  291370 |  234644 | нет в файле
5.     | "Macro Assembler " |  433320 |  412672 | 1407702 |  288704 |
6.     | "Macro  Assembler" |  411512 |  276621 |  896299 |  289254 |
7.     | "STD LOCATED equ " | 1111896 | 1067087 | 1957946 |  503466 |<- частое совпадение окончания " equ "
8.     |------------------------------------------------------------|
9.     | "equ COLOR_BTNHIG" |  178088 |  129703 |  576734 |  130969 |есть в файле
10.     | "CTLCOLOR_MAX    " | 1098144 |  961722 | 1228542 |  193763 |

Как видим только лишь в некоторых "удачных" случаях SBM чуть-чуть опережает dw_scan2, но зато если уж проигрывает, то по крупному





PS: Парочка замечаний по speed_test:

1) После VirtualFree MEM_DECOMMIT надо бы еще делать MEM_RELEASE иначе адреса так и остаются занятыми

2) Подсчет тиков на оверхед надо бы вставлять в каждый тест и делать 4-5 проходов (без усреднения, просто брать последний отсчет), иначе вроде бы 0 не получается (не уверен, т.к. смотрел на своем измененном варианте).

3) Ну и если использовать ее для всякого тестирования на скорую руку, то ИМХО не очень удобно переписывать все окружение RDTSC - в глазах рябит . Я себе слепил вариант с переопределением макросов - весь служебный код сидит в speed_test.inc, а для тестов нужно только переопределить макросы test1_macro,test2_macro и т.п. Мне думается так удобнее, т.к. тест-инки проще и меньше получаются.



Вот процедурка find_dword_scan2 в аттаче:



273912567__dw_scan2.zip

 

leo

Ха-ха, мой азарт не иссяк Ты втихаря изобретал, я тоже времени не терял



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



Вариант получился быстрее чем BMH, проверял пока на windows.inc и текстовом файле литературного содержания.



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

Поэтому сравнения вел только с BMH, за которым грехов не заметил.



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



Пока в аттаче сама процедура.

Голая, без комментов (не успел ещё)





_1609732034__F_T_S.zip

 

Ну теперь подробней.



О SBM - BM - BMH: Первые два работают быстрее, но это лукавство, они допускают ошибки, что непозволительно в такого рода процедуре. Видимо в угоду скорости были сделаны некоторые упрощения, которые аукнулись глюками. Поэтому они не рассматриваются в принципе, как нерабочие.



Немного о своем методе:

Таблица двордов (256 штук по кол-ву возможных байт).

В таблицу заносится предварительно 16 в каждый дворд.

До сих пор было похоже, дальше мой метод: предрасчёт максимально допустимого скачка.

Берется байт из образца по смещению от 0 до 15 (до длины строки).

В ячейку, соответствующую байту, записывается значение, рассчитаное так:

[число в ячейке] = [длина строки] - [смещение байта от начала]

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

Дальше значения из таблицы просто добавляются к esi. Никаких условных переходов нет. Они устранены за счёт предрасчета скачка.

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



О тестере: я брал за образец структуру Фога, хотя может и правильней будет в макросах определить не счетчик, а тестируемые процедуры. На досуге переделаю.

О компенсации времени на работу счетчика: после вычитания времени на сам счётчик (counterL/counterH) максимум погрешности - 2 тика, думаю на уровнях 200 - 300 тыс. тиков это пренебрежимо мало, чтобы усложнять расчёт, добиваясь чистого нуля.

VirtualFree попробовал с MEM_RELEASE, но всё равно, последующие получения памяти происходят по другим адресам (число hMemFind растет все равно).

Еще такое: я подумал, что если брать только специфичные "тяжелые" и "легкие" образцы строк, то они не дают полной картины о работе алгоритма. Поэтому добавил в тестер кнопочку, По её нажатию на место образца (match) копируется 16 байт со смещения от начала файла, увеличивающегося каждый раз на 255 байт. Смещение некратное 4, чтобы посмотреть и на строки, которые имеют разный align в файле. В итоге получилось достаточно удобно и просто меняются образцы. В число образцов попадают как неудобные строки, так и удобные и средние по удобству. Оффсет и сам образец выводятся в статике.



О процедурах:

Проверял на текстовых файлах.

Моя процедура быстрее, если образец в начале файла (где-то до 4 кб от начала), и она менее чувствительна к повторяющимся комбинациям в конце образца(типа пробела в windows.inc)

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

Обе процедуры заметно быстрее BMH.

Измененный тест в аттаче. 1 кнопка пустая, 2 - моя, 3 - твоя, 4 - BMH.



Попробуй, как работает find_tbl_scan.

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





_801996711__test.zip

 

В общем, прогнал две процедуры через windows.inc и ml.exe.

Бойера-Мура не стал писать, т.к. он проигрывает в самом оптимистичном случае ~30% (на ml.exe), а на windows.inc вообще в разы.



Двадцать замеров в начале файла, двадцать на 150 кБ. Образцы брались с прогрессирующим смещением 255 от первого.

min - самый благоприятный образец из 20-ти, max - неблагоприятный. Среднее - по результатам 20-ти замеров.



Результат в таблице:

Код (Text):

1.     |   процедура        |   FTS   |   LEO   |
2.     |-----------------------------------------
3.     |                    |     тик/байт      |
4.     |-----------------------------------------
5.     |        windows.inc начало файла        |
6.     | min                |  0,86   |  0,86   |
7.     | max                |  2,17   |  3,49   |
8.     | среднее            |  [b]1,58[/b]   |  [b]1,87[/b]   |
9.     |-----------------------------------------
10.     |    windows.inc середина файла (150 кБ) |
11.     | min                |  0,98   |  0,96   |
12.     | max                |  4,52   |  9,59   |
13.     | среднее            |  [b]3,24[/b]   |  [b]3,60[/b]   |
14.     |-----------------------------------------
15.     |     windows.inc строки нет (300 кБ)    |
16.     | min                |  1,09   |  1,18   |
17.     | max                |  2,44   |  6,22   |
18.     | среднее            |  [b]1,90[/b]   |  [b]3,06[/b]   |
19.     |-----------------------------------------
20.     |=========================================
21.     |           ml.exe начало файла          |
22.     | min                |  0,74   |  0,74   |
23.     | max                |  7,38   |  2,53   |
24.     | среднее            |  [b]2,12[/b]   |  [b]1,39[/b]   |
25.     |-----------------------------------------
26.     |       ml.exe середина файла (150 кБ)   |
27.     | min                |  0,92   |  0,93   |
28.     | max                |  1,30   |  1,27   |
29.     | среднее            |  [b]1,03[/b]   |  [b]1,02[/b]   |
30.     |-----------------------------------------
31.     |        ml.exe строки нет (300 кБ)      |
32.     | min                |  0,91   |  0,92   |
33.     | max                |  1,58   |  1,32   |
34.     | среднее            |  [b]1,14[/b]   |  [b]1,10[/b]   |
35.     |-----------------------------------------

Вот. Пока буду смотреть твою процедуру, чего там наверчено