Поиск в содержимом файла

[ger_kar]

Ось этим вовсе не рулит. Ось предоставляет изумительные возможности этим рулить, но 99 процентов программистов ими не пользуется. Им редко приходится на скорость работать с огромными объёмами, так что они дразнятся тем, что их время стоит слишком дорого, чтобы они занимались такого рода оптимизацией. Но вот здесь как раз тот случай, когда этим нужно заниматься.

ger_kar писал(а):вряд ли это можно исправить простыми средствами

Можно.

А как? Если только простыми, средствами, почему бы и нет.

[ger_kar]

1. Работает неверно со строками короче 4 символов! Не находит просто их. Сам-то тестировал?

Тестировал, тестировал, да не до тестировал. Qwertiy Спасибо за найденный баг. Перезалил с исправлением. Поправил только баг, остальное трогать не стал, пусть будет примером как не надо писать код .

[Qwertiy]

Лучше, как говорит Хакер, по тому, как моем файле и моими условиями поиска строки короче 4 символов находились. Нужны одинаковые условия тестирования.

Одинаковые условия для всех программ - да, одинаковые условия у всех тестирующих - нет.

Ты ошибся, я написал не «текстовый», а «тестовый».

Невнимательно прочитал

Я же уже где-то писал, что DoEvents делает кучу лишнего, в частности, там есть Sleep, который вызывает задержку минимум на 20 мс, даже несмотря на то, что указан 0, потому что это в любом случае переключение потока.

Я же не говорю вызывать после каждого символа. Но всё-таки окно не должно виснуть во время поиска.

От вас требуется EXE-файл. Взаимодействие организовано следующим образом. Есть два файла: input.exe и output.txt.

Отличная идея. Только, вероятно, input.txt.

[ger_kar]

Я же не говорю вызывать после каждого символа. Но всё-таки окно не должно виснуть во время поиска.

Может Хакер другой путь подскажет вместо DoEvents.

[ger_kar]

Вобщем так. Решил я поискать в интернете информацию, по поводу алгоритмов поиска определенной байтовой последовательности в байтовом массиве и наткнулся на следующую статью
Честно сказать я даже про существование функции InStrB уже давным давно забыл, так как на практике ее ни разу не применял, а даже если бы и вспомнил, то использовать ее для поиска массива (байтовый массив строки поиска) в массиве, точно бы не догадался, но прочитав статью решил попробовать и результат себя оправдал. Если взять мой пример с одиночным поиском и переписать его с использованием InStrB, то в зависимости от условий поиска средняя скорость выросла в 5 !!! раз. Жаль эта функция непригодна для мультипоиска, точнее она конечно пригодна если искать каждую строку в новом проходе, но в поиске за один проход она точно не поможет.

[ger_kar]

Вот и еще один вариант мульти поиска сварганил, постарался учесть все замечания Хакера относительно кривизны моего кода, не знаю насколько это получилось, со стороны виднее. Кроме этого сам алгоритм поиска сделан в виде отдельной процедуры в dll, которую написал на ассемблере. Хотел добавить мульти поточность, но работало с глюками и я от этого варианта отказался. Листинг процедуре на асме и сама библиотека в архиве. Поисковые строки берутся из файла Input.txt, где в первой строке имя файла в котором производится поиск, если файла нет, то можно ввести поисковые строки в соответствующее поле. По сравнению с предыдущим вариантом скорость выросла примерно в 2,5 раз.
В принципе можно сделать, что-бы было без доп. библиотеки, в виде ассемблерной вставки прямо в проект.
Вот собственно и все.

[Хакер]

Нда, позор.

Во-первых, какого фига там делает графический интерфейс? Я же сказал: никакого граф. интерса, взаимодействие только через файлы. Нет, блин, это чудо читает входные параметры из файла и... показывает богомерзкую Form1.

Во-вторых, я открыл asm-файл, и это просто ужас. Я уже не говорю о неправильном использовании регистров, но вот это:

Код: Выделить всё

ADD [ebx][edi]+1,al   

Это, извините, не ассемблер. Нет, не было и не будет никогда такой инструкции.

[ger_kar]

Нда, позор.

Где

Во-первых, какого фига там делает графический интерфейс?

Ну программы для тестирования:

С моей (или не с моей, а просто со стороны) стороны — приложение, которое само генерирует тестовые файлы, тестовые фразы, само вызывает ваши exe-шники, передаёт им входные данные, проверяет правильность поиска, и самое главное, делает замер времени.

Пока нет, а тестировать постоянно открывая и правя файлы вручную не очень то удобно.

и... показывает богомерзкую Form1.

Интересно, чем тебе так не по нраву стандартные формы VB? Форма как форма.

Во-вторых, я открыл asm-файл, и это просто ужас. Я уже не говорю о неправильном использовании регистров, но вот это:

А что с регистрами не так? ECX/CX - юзается как счетчик, EBX/BX - как база (указатель на начало массивов) индексные регистры тоже вроде правильно, оставшиеся EAX и EDX универсальные, разница только если что-то умножать/делить, а так что в лоб, что по лбу

Это, извините, не ассемблер. Нет, не было и не будет никогда такой инструкции.

Ежели это не ассемблер, то тогда что? Твоя, моя не понимает. Зато моя, компилятор MASM прекрасно понял
А если серьезно, то вот цитата из справочника

Косвенная базовая индексная адресация со смещением:
Этот вид адресации является дополнением косвенной индексной адресации. Эффективный адрес формируется как сумма трех составляющих: cодержимого базового регистра, cодержимого индексного регистра и значения поля смещения в команде. К примеру, команда

mov eax,[esi+5][edx]
пересылает в регистр eax двойное слово по адресу: (esi) + 5 + (edx)

[Хакер]

Где

Всюду.

Пока нет, а тестировать постоянно открывая и правя файлы вручную не очень то удобно.

Вот напиши граф. обёртку над файловый интерфейсом. Граф обёртка над файловым интерфейсом будет проще, чем файловая обёртка над граф. интерфейсом. Понмаешь?

Интересно, чем тебе так не по нраву стандартные формы VB? Форма как форма.

Пожалуйста, смени имя в паспорте с «Германа» на «Имя1». Потом продолжим обсуждать.

А что с регистрами не так? ECX/CX - юзается как счетчик, EBX/BX - как база (указатель на начало массивов) индексные регистры тоже вроде правильно, оставшиеся EAX и EDX универсальные, разница только если что-то умножать/делить, а так что в лоб, что по лбу

Не это определяет правильность. Любой знает, что 386+ процессор быстро работает с регистрами, разрядность которых соответствует текущему режиму работы. 16-битные регистры в 32-битном режиме это плохо, а 8-битные — ещё хуже. В плане скорости, разумеется.

Ежели это не ассемблер, то тогда что?

Макрокод. И вообще меня поражает такой тон.

Зато моя, компилятор MASM прекрасно понял

\
Масм на то, и макроасм, чтобы можно было вообще писать что-то вроде [eax].SomeMemberOfStruct.

А если серьезно, то вот цитата из справочника

Теперь я понял, что это, и забавно, почему MASM проглатывает такую извращённую форму записи.

Вот это:
AND eax, [ebx][edi*4]+4
Правильно писать так:
AND eax, [ebx+edi*4+4]

[ger_kar]

Всюду.

Если не брать в расчет имена и графический интерфейс, в остальном я вроде все поправил, отступы между строк и все такое. Или сам алгоритм кривой?

Пожалуйста, смени имя в паспорте с «Германа» на «Имя1». Потом продолжим обсуждать.

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

Не это определяет правильность. Любой знает, что 386+ процессор быстро работает с регистрами, разрядность которых соответствует текущему режиму работы. 16-битные регистры в 32-битном режиме это плохо, а 8-битные — ещё хуже. В плане скорости, разумеется.

Понятно, приму к сведению.

Макрокод. И вообще меня поражает такой тон.

А что не так? Мне показалось, что предложение не окончено, точнее не предложение а мысль. И я задал вопрос. Пусть будет макрокод, буду называть его так.

Масм на то, и макроасм, чтобы можно было вообще писать что-то вроде [eax].SomeMemberOfStruct.

Вот я и пытался использовать то что облегчает процесс.

Теперь я понял, что это, и забавно, почему MASM проглатывает такую извращённую форму записи.

В справочнике по этому поводу написано буквально следующее:

Индексный оператор
Индексный оператор [ ]. Не удивляйтесь, но скобки тоже являются оператором, и транслятор их наличие воспринимает как указание сложить значение выражение_1 за этими скобками с выражение_2, заключенным в скобки. Например,
mov ax, mas[si] ; пересылка слова по адресу mas+(si) в регистр ax

И далее описываются все возможные варианты написания такой команды, в том числе
AND eax, [ebx][edi*4]+4 и AND eax, [ebx+edi*4+4], мне больше понравился тот вариант, который я использовал.
Тут вот в чем вопрос, при каждом выполнении команды каждый раз происходят умножение + сложение регистров и константы и на это расходуются лишние такты, может как-то по эффективней можно сделать?

[Qwertiy]

может как-то по эффективней можно сделать

Битовый сдвиг вместо умножения на 4?

[Хакер]

Индексный оператор [ ]. Не удивляйтесь, но скобки тоже являются оператором, и транслятор их наличие воспринимает как указание сложить значение выражение_1 за этими скобками с выражение_2, заключенным в скобки. Например,
mov ax, mas[si] ; пересылка слова по адресу mas+(si) в регистр ax

Вот такой фрагмент я написал в предыдущем посте, но потом всё-таки убрал его, потому что сперва мне показалось, что инструкция вообще невозможная (вроде mov [ecx], [edx]), но потом всё-таки оказалось, что инструкция возможная, правда форма записи извращенская.

Но теперь этот удалённый кусок получается как раз к месту. Он звучит вот так:

Меня удивляют люди, которые обращаются к каким-то сомнительным источникам вроде каких-то справочников, написанных непонятно кем, даже если это какие-то популярные в определённых кругах справочники.
Очевидно, что нет более авторитетного источника по x86-ассемблеру, чем создатель x86-ассемблера, x86-кода, x86-архитектуры, то есть чем Intel. Вот справочник Intel и нужно читать в данном случае.

И вот радость, там нет таких причудливых вещей, как индексный оператор, и каких-либо слов вроде «подразумевает сложение». Там вполне чётка написано, что выражение, X подразумевает значение X, а [X] — значение, лежащее по адресу X.

Соответственно, [eax+4] — это значение, лежащее по адресу EAX+4, а [eax]+4 — это значение, которое на 4 больше, чем значение, лежащее по адресу EAX. Хотя ни одна из инструкций не допускает операнд такого вида, какой использован в последнем примере.

[ger_kar]

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

Такие справочники, в отличии от интеловских написаны, на понятном русском языке, доступным для понимания языком. Был бы интеловский справочник на русском читал бы его. С другой стороны, систему команд придумала интел, но MASM придуман в MS и видимо там и придумали соответствующую запись, и MASM ее соответственно адекватно воспринимает. Значит так все и задумывалось. Опять же в том-же VB много недокументированных/слабодокументированных ф-ций. И спасибо пытливым умельцам и тебе в том числе, которые не только вытащили на свет божий для всеобщего использования оных, но и расширили ранее не доступный функционал. Интересно как бы в MS отреагировали увидев где нибудь в работающем коде, синтаксис твоих замечательных указателей на функции, представляю мимику на лице . И что-бы было если бы все читали по VB только официальную документацию? А так ...

[ger_kar]

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

Блин, я про выводимый формат совершенно забыл, вот лажа.
А по поводу регистров, нашел один баг. Дело в том, что я для счетчика отвел 1 байт и для работы с ним юзал аккумулятор, но если образец поиска найден больше чем 255 раз, получается облом.
И еще один не приятный момент. Более-менее приемлемая скорость получается если прогонять поиск второй и последующие разы, а первый раз поиск протекает намного медленнее. Видимо во второй раз используются кэшированные данные, а в первый раз все читается с диска. Поэтому на данный момент именно этот фактор является бутылочным горлышком. Здесь несколько исправить ситуацию можно лишь только так как предлагал Хакер, с пред заказом чтения страниц в память. Но я если честно совершенно не представляю, как такое сделать. Так что в этом вопросе я пас.

[Хакер]

Но я если честно совершенно не представляю, как такое сделать. Так что в этом вопросе я пас.

Что тут можно не представлять?

[ger_kar]

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

[Хакер]

как сделать так что-бы процесс знал, что нужно подгрузить очередную порцию данных

Не процесс, а ОС. Очень просто сделать: прочитать что-нибудь из этой страницы.

как это осуществить асинхронно, не мешая основному поиску и т.д.

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

[ger_kar]

Если я правильно понял, то примерно так:
Берем адресное пространство с мап. файлом и делим это пространство на куски по 4 кб (а может и не 4).
Потом перебираем их по очереди и из каждого читаем по 1 или 4 байта, что заставляет Ось погрузить соответствующие страницы с диска, и к моменту, когда поиск до них добредет, они уже будут в памяти. Так?
И второй поток нужно организовывать в ассемблерной процедуре?

[Хакер]

Берем адресное пространство с мап. файлом и делим это пространство на куски по 4 кб (а может и не 4).

Оно и так поделено.

Потом перебираем их по очереди и из каждого читаем по 1 или 4 байта, что заставляет Ось погрузить соответствующие страницы с диска, и к моменту, когда поиск до них добредет, они уже будут в памяти. Так?

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

И второй поток нужно организовывать в ассемблерной процедуре?

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

[ger_kar]

Оно и так поделено.

Оно то конечно поделено, просто я неправильно выразился, а хотел я сказать что нужно определить страницу с которой начинается мап. файл и на которой заканчивается и соответственно потом эти страницы перебирать в цикле. Т.е. поделить адресное пространство мапа на участки перебираемые в цикле.

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

Но кроме GetMem4 еще и цикл нужен будет, да и и при вызове самой GetMem4 в другом потоке могут возникнуть проблемы с рантаймом, да и сама GetMem4 часть этого рантайма. А если все обсчитать при все данные приготовить в VB создав соответствующие структуры, а потом из подпрограммы на асме, в которой происходит поиск порождать новый поток и он просто будет использовать эти данные и в цикле перебирать страницы.

[Хакер]

Но кроме GetMem4 еще и цикл нужен будет

Ни в коем случае. Хотя, конечно, есть вариант, когда цикл нужен, но и в этом случае ничего страшного нет.

да и и при вызове самой GetMem4 в другом потоке могут возникнуть проблемы с рантаймом,

Не могут. GetMem-ы сами по себе рантаймонезависимы.

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

Ты судя по всему не понял. Если ты думаешь, что нужно создать доп. поток, в котором циклом пробежаться по всем страницам с помощью GetMem — то ты точно ничего не понял.

[ger_kar]

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

Ну я так и подумал, что просто пробежаться, а если нет то тогда я вообще не въехал с ситуацию.
Я пробовал делать по другому. Для начала я просто делил мап на 2 участка, со смежной областью по длине самого длинного слова (что-бы оно нашлось таки если окажется на разных участках). И в двух разных потоках пытался вызывать свою ассемблерную подпрограмму для поиска... И все благополучно рушилось Я так и сяк попробовал, да и бросил эту затею. Может падало из-за рантайма, при вызове самой подпрограммы на асме, может потому, что я неправильно подпрограмму написал и для многопоточного режима она по другому пишется. Я даже не в курсе, можно ли обращаться к одним и тем-же переменным одновременно из разных потоков т.е. система сама все обработает или надо самому делать хитрую синхронизацию. Вобщем в этих вопросах я полный чайник .

[Хакер]

Ну я так и подумал, что просто пробежаться, а если нет то тогда я вообще не въехал с ситуацию.

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

[ger_kar]

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

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

[ger_kar]

Других вариантов поиска от других участников как видимо уже не будет. То что касается моего последнего варианта, а точнее замечаний по его реализации тоже все понятно, но все замечания по сути относятся к вопросу культуры программирования и если даже полностью устранить отмеченные недостатки, то скорости поиска это не прибавит. Что касается самого поискового алгоритма, то сам поиск получился довольно быстрым, но остается узкое горлышко, тормозит подгрузка данных. Эту проблему у меня решить не получается. Имеет ли смысл дальше совершенствовать сам поиск и будет ли от этого, хоть какой-то эффект. Например, можно было бы задействовать регистры MMX, сделать отдельную процедуру для поиска одного слова и если слово будет одно, то использовать эту процедуру с максимальной эффективностью. Или это будет бесполезная трата времени?

[Хакер]

Нет, надо работать над рабочим набором и запросами на подгрузку.