|
Скорость поиска с нечувствительным регистром
|
|
| haav | Дата: Пятница, 27.12.2019, 22:06 | Сообщение # 1 |
 Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| В принципе для Linux уже давно была написана утилита для поиска строки в файлах рекурсивно по каталогам. В первую очередь она была нужна для поиска в текстовых файлах, но иногда бывает надо найти что-то и в бинарных. И тут в один из дней утилита вылетает. Ну думаю ладно потом посмотрю что там. Вчера решил глянуть. Причина нашлась сразу же и проявлялась на очень больших файлах. В общем исправил. Потом при тесте офигел ,сколько времени приходится ждать поиска при режиме "нечувствительный к регистру" , это когда регистр у обоих строк приходится приводить к нижнему или верхнему состоянию. В моем случае было 43 секунды на 750мб. Кстати, в режиме с чувствительным регистром поиск занимает 1 секунду. В общем поверетел , покрутил код, и сумел немного оптимизировать до 30 секунд. Алгоритм прост: READ_FROM_FILE -> LCASE -> INSTR . Я конечно жестко упрощаю , в реале LCASE использовать не получится , приходится велосипедить с функциями mbtowc+towlower . Да и большие файлы целиком в память не загрузить , приходится нарезать. Ну думаю , ладно 30 секунд, да и фиг с ним. И вот тут надо же мне было взять и попробовать поиск с помощью встроенной утилиты "grep". Я тут чуть с кресла не свалился: grep выполняет эту операцию 2-3 секунды  . Я долго смотрел ошарашенно , пытаясь понять: как такое возможно. Потом смотрю в свой код и пытаюсь понять где же лажа? Сегодня решил задать вопрос на оф. форуме, но там на данный момент никто не ответил. А потом полез в исходники grep и реально начал офигевать на такие названия функций как: compile , execute , kwsinit , kwsmusts , dfasyntax , dfacomp и прочие выражения вроде matchers... И сплошь напеханные макросы... Блин думаю, что за извращенный мозг мог такое придумать? Нет я понимаю , что юниксовые заголовки зачастую такое дерьмо , что хочется спросить у автора заголовков: ты точно человек? Но похоже в таком же стиле пишут и программы... В общем после исследования я понял , что grep использует библиотеку регулярных выражений и похоже именно она дает такой дикий прирост скорости, а grep получается просто умело сделанная "обертка" , хотя надо сказать весьма полезная. И вот тут я думаю , что делать дальше... Изучить PCRE , разобраться и наваять поиск , не уступающий grep? Или все таки попробовать еще хоть на капельку, хоть на капелюшечку оптимизировать свою программу , чтобы уменьшить такую дикую цифру в 30 секунд. Душа просит второе блюдо , а разум твердит о рациональности первого.
Одно хорошо , что я понял где собака зарыта, а уж с определением дальнейших действий как нибудь справлюсь. 
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| haav | Дата: Суббота, 28.12.2019, 13:21 | Сообщение # 2 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| И так , с утра прямо свербило В битве душа vs разум победила первая. Открыл код своей утилиты и давай смотреть , что можно еще подкрутить. И тут меня осенило! А почему бы не заменить все символы нуля в буфере на... скажем пробелы? Ведь именно нули не дают использовать LCASE|UCASE . Сказано, сделано. Код стал проще, а скорость выросла аж в 4 раза. Теперь вместо 30 секунд результат равен 7,8 ! И это уже я считаю хорошим результатом. Да это все еще не 2-3 секунды как у grep , но такой результат значительно лучше чем скажем в поиске у:
double commander (~15 секунд)
krusader (~13 секунд)
tux commander (не дождался, похоже завис)
searchmonkey (вообще ничего не находит, похоже только для текстовых файлов)
okteta hex editor (не дождался, похоже завис)
bless hex editor (нет возможности искать с нечувствительным регистром , а с чувствительным регистром - 6 секунд, где у меня 0.75 секунды)
А вот этим уступаем:
wxHexEditor (3 секунды)
grep (2-3 секунды)
Пока с утилитой все. Надо попробовать погонять PCRE , никогда всерьез не пользовался регулярками.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| DarkDemon | Дата: Суббота, 28.12.2019, 17:19 | Сообщение # 3 |
|
Полковник
Группа: Друзья
Сообщений: 200
Статус: Offline
| Стас, а в какой кодировке у тебя идёт поиск? UTF-8 ? Добавлено (28.12.2019, 17:27)
---------------------------------------------
Цитата haav (  ) Я долго смотрел ошарашенно , пытаясь понять: как такое возможно.
Посмотри сколько оно жрёт ЦП. Уверен это "магия потоков". Халявных чудес не бывает.
Регулярки это же обычная работа со строками.
Тут алгоритм нужен. Стохастические методы должны работать эффективно.
Сообщение отредактировал DarkDemon - Суббота, 28.12.2019, 17:20 |
| |
| |
| haav | Дата: Суббота, 28.12.2019, 20:00 | Сообщение # 4 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Цитата DarkDemon ( ) Стас, а в какой кодировке у тебя идёт поиск? UTF-8 ?
Да UTF-8
Цитата DarkDemon ( ) Посмотри сколько оно жрёт ЦП. Уверен это "магия потоков". Халявных чудес не бывает.
Регулярки это же обычная работа со строками.
Тут алгоритм нужен. Стохастические методы должны работать эффективно.
В том и дело , что не особо grep жрет ресурсы. Да , там похоже многопоток , но на каждое ядро(у меня 4 ядра) где-то 15% - 20% . Самое интересное , что grep похоже пофиг: с учетом регистра или без учета , результат примерно одинаковый, особенно на огромных файлах. Так в каталоге с 20 гб (в нем файлы 8гб , 9гб и по мелочи) grep при худшем раскладе (когда нет того, чего ищешь) тратит 2 мин 25 секунд . У моей утилиты такой результат только без преобразования в нужный регистр. А с преобразованием... в общем рано я обрадовался. Если в файле много нулей , то моя утилита в глубоком анусе. Причем нулей в файлах под гигабайт часто бывает сотни миллионов. Ты представляешь , сколько времени тратится на поиск и замену такого кол-ва нулей ?
Весь блин сыр-бор из-за приравнивания строк к одному регистру. Функция INSTR великолепна , ищет быстро, но вот как обойти проблему с регистрами строк. Блин с ASCII все просто , а вот с UTF-8 просто угар. Приходится из utf-8 перегонять в unicode представление и только потом перегонять в регистр. И тут косяк! Если в буфере нули , то функции перегона в юникод обрезают буфер. Либо удаляй нули , либо используй побайтовую функцию перевода в unicode (а она раз в 10-20 медленнее). Теперь мне понятно решение многих разработчиков не предоставлять в Linux программах поиск с нечувствительным регистром. Пока получается у меня одна надежда на регулярки. Уж не знаю , как они там ищут , но это эффективно надо признать. Хотя тут тоже не буду зарекаться , может есть какая хитрость, которую я не знаю... Надо изучать и пробовать, вот тогда и будет понятно.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| DarkDemon | Дата: Воскресенье, 29.12.2019, 04:44 | Сообщение # 5 |
|
Полковник
Группа: Друзья
Сообщений: 200
Статус: Offline
| Цитата haav ( ) Да , там похоже многопоток , но на каждое ядро(у меня 4 ядра) где-то 15% - 20% .
Такой расклад может быть в не очень большом кол-ве случаев. Например, когда чтение с харда оставляет
процессору время.
Цитата haav ( ) Алгоритм прост: READ_FROM_FILE -> LCASE -> INSTR
Вроде народ где-то делал быстрый поиск по строкам. Вообще тема занимательная.
Досканально этот вопрос не изучал, но могу предположить, что если 8 бит кодировка
статическая и не "расплетается" в большее кол-во байт, то можно воспользоваться
асмовой инструкцией xlat для приведения строки к необх. регистру, при этом не используя
loop циклы(а через jmp условные), при этом держать основной кусок данных выровненным.
Дальше уже применять какой-нибудь продуктивный алгоритм поиска. Уж не знаю что там
в INSTR, но полагаю можно просуммировать все байты в требуемом выражении, а дальше
действовать по этой хеш-сумме, при перемещении на букву вычитая байт(первую букву выраж-я) и
плюсуя байт(новую букву из последовательности, идущую за последней буквой выр-я), далее
по совпадении хеша проверять слово как-нибудь хитрожопо:
Первый метод: Можно поочерёдно проверять буквы. Первая, последняя, вторая, предпоследняя и т.д
Или придумать более мозаичный и хитрожопый.
Второй метод: Сгенерировать 1000 кусков случайных чисел, для длин от 10-ти до тысячи. Т.е. поместить
в них сгенерированные случ. образом индексы элементов, по которым проверять куски соотв. длин.
Это примерно 1Мб данных(WORD-ы по 16 бит). И использовать эту последовательность для поиска совпадения.
Всё что за границами(<9 и >1000) проверять первым способом.
Считывать блок, делить его на 4 части(с перекрытием, чтобы не потерять результаты поиска в стыке блоков)
и проверять в разных потоках. Дожидаясь отработки всех потоков. Описанное должно работать очень быстро.
Если бы передо мной встала такая задача, действовал бы по описанному сценарию.
На счёт мультибайтовых кодировок ничего не могу сказать, это гемор и возможно в этом случае лучше взять
какую-нибудь библиотеку где это уже оптимизировано(перевод кодировок). Но и так в общем-то понятно,
что быстро оно работать не будет.
Кстати сказать, а что за текстовые файлы такого объёма, по 9 гигабайт? Базы данных?
Сообщение отредактировал DarkDemon - Воскресенье, 29.12.2019, 04:49 |
| |
| |
| haav | Дата: Воскресенье, 29.12.2019, 19:10 | Сообщение # 6 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Цитата DarkDemon ( ) Кстати сказать, а что за текстовые файлы такого объёма, по 9 гигабайт? Базы данных?
Леха, да я беру любой большой файл , это ведь не суть при тестах. Поиск может понадобится в будущем возможно для нерядовой задачи (скажем для прямого чтения харда). Понятно , что в бинарных файлах вероятность поиска строк крайне редко требуется.
Кстати, grep не PCRE использует , а regexp . И зря я гнал про то, что это простая обертка. Ты Леха был прав , регулярка - это просто более удобный поиск и ничего более. Как я в этом убедился? Да просто взял и подсунул две строки(шаблон и буфер) в библиотеку PCRE (в принципе regexp пашет по этой же схеме, просто менее удобна). Естественно , напрямую бинарный буфер запихал  с указанием , что это типа UTF-8. Ну и PCRE прислал код ошибки -10, что означает "что за хрень ты мне подсунул". Понятно , что он прочитал первый попавшийся байт FF и дал отказ. Если отключить опцию UTF-8 , то даже в потенциале никогда нужную строку не найдет . Получается я вернулся к тому месту где был: либо резать нули и использовать свою поделку, либо как-то резать все что не входит в диапазон UTF-8 и использовать регулярки.
Пока регулярки отложу на запасной верстак. Буду пытаться сваять какой нибудь несложный алгоритм вырезки нулей , но надеюсь, что получится хоть немного побыстрее. Если честно , пока нет желания связываться с многопотоком, попробую все в одном потоке. Ну а если совсем толку не будет , тогда может быть и на потоки начну поглядывать...
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| haav | Дата: Понедельник, 30.12.2019, 07:56 | Сообщение # 7 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Нарукоблудил примитивный алгоритм замены нулей. В итоге маленький профит есть. У меня сейчас что-то вроде:
1) Ищем ноль
2) Если нашли , то:
--------2a) пишем в integer значение c этой позиции и если оно равно нулю, то заменяем на пробелы (&h2020202020202020) и сдвигаем указатель следующего поиска на 8
--------2b) пишем в long значение c этой позиции и если оно равно нулю, то заменяем на пробелы (&h20202020) и сдвигаем указатель следующего поиска на 4
--------2c) пишем в short значение c этой позиции и если оно равно нулю, то заменяем на пробелы (&h2020) и сдвигаем указатель следующего поиска на 2
--------2d) заменяем на пробел (&h20) и сдвигаем указатель следующего поиска на 1
Была мысля еще промежутки проверять между
integer и long (то есть кол-во нулей подряд: 7 , 6 , 5 , 3 )
short и Long
но не знаю даст ли это профит. Был бы математиком, враз бы вычислил
Сейчас время работы тратится примерно так:
1) замена пробелов ~30%
2) преобразование в юникод и в нижний регистр ~55%
3) поиск вместе с чтением файла ~15%
Как я писал, на каталоге в 20гб если без преобразования в нужный регистр время примерно 2 минуты и 25 секунд . С преобразованием в регистр как раз в 2 раза дольше. Теперь посчитаем, сколько придется ждать при сканировании скажем терабайтника (~931гб). grep справится примерно за 1 час 45 минут , а моя утиль примерно за 3.5 часа. ЖЕСТЬ!!!
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| DarkDemon | Дата: Понедельник, 30.12.2019, 18:37 | Сообщение # 8 |
|
Полковник
Группа: Друзья
Сообщений: 200
Статус: Offline
| Цитата haav ( ) grep справится примерно за 1 час 45 минут , а моя утиль примерно за 3.5 часа.
Его тоже писали обычные люди. Нет ничего невозможного. Алгоритм задачи это 80-90% производительности,
остальное оптимизация.
Если речь о терабайтнике то скорость обычного механич. диска что-то начиная от 80Мб/с и до примерно 200
в самом лучшем случае, какого-нть недешёвого диска. Допустим в среднем 100Мб/с, т.е. проге надо отлопатить
100Мб данных за секунду. Чисто теоретически это возможно.
|
| |
| |
| haav | Дата: Понедельник, 30.12.2019, 21:42 | Сообщение # 9 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Цитата DarkDemon ( ) Если речь о терабайтнике то скорость обычного механич. диска что-то начиная от 80Мб/с и до примерно 200
в самом лучшем случае, какого-нть недешёвого диска. Допустим в среднем 100Мб/с, т.е. проге надо отлопатить
100Мб данных за секунду. Чисто теоретически это возможно.
Да я везде вижу цифры по скорости HDD , ограниченные в 200 мб. Я нисколько не хочу подвергать это сомнению. Получается моя утилита сейчас для HDD в принципе хороша 76 мб\сек в среднем и это при обработке регистра букв, а без обработки регистра скорость как минимум в два раза больше. А теперь вопрос: каким образом на моем компе с механическим HDD читается файл в 760 мб менее чем за секунду? Да не только читается , но и поиск полностью за это время проходит... Я не разбираюсь в схемотехнике ЖД , но видно что данное "колдовство" только до определенного момента. Как я и писал при 20гб время примерно 2 минуты и 25 секунд , а это уже ~150 мб\сек.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| DarkDemon | Дата: Понедельник, 30.12.2019, 22:41 | Сообщение # 10 |
|
Полковник
Группа: Друзья
Сообщений: 200
Статус: Offline
| Цитата haav ( ) А теперь вопрос: каким образом на моем компе с механическим HDD читается файл в 760 мб менее чем за секунду?
Он закешировался системой. После перезагрузки всё встанет на свои места.
Таких скоростей HDD не имеют, даже не всякий SSD так сможет.
А вообще да, по UTF-8 - это дичь:
http://i.voenmeh.ru/kafi5/Kam.loc/inform/UTF-8.htm
Этот парсинг простым не кажется. Особо срезать то и негде, как в случае с ASCII.
|
| |
| |
| WQ | Дата: Вторник, 31.12.2019, 03:07 | Сообщение # 11 |
|
Полковник
Группа: Проверенные
Сообщений: 215
Статус: Offline
| PCRE так не особо быстро работает, по ощущениям, но во многих случаях без нее никак, хоть и добавляет несколько сот килобайт
Когда-то искал на github небольшие библиотеки регулярных выражений на C, добавлял во Freebasic... все не то, да еще и практически все медленнее PCRE
По скорости - на оф форуме есть ветка про разбиение строки\текста на подстроки, в зависимости от заданного разделителя
Там разница между некоторыми вариантами много раз, естественно, алгоритм, которым я до этого обычно пользовался, оказался самым медленным)
Сообщение отредактировал WQ - Вторник, 31.12.2019, 03:21 |
| |
| |
| haav | Дата: Вторник, 31.12.2019, 06:32 | Сообщение # 12 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Цитата DarkDemon ( ) Он закешировался системой. После перезагрузки всё встанет на свои места.
Таких скоростей HDD не имеют, даже не всякий SSD так сможет.
Значит Linux вырос в этом плане , поскольку и после перезагрузки скорость не падает.
Цитата WQ ( ) По скорости - на оф форуме есть ветка про разбиение строки\текста на подстроки, в зависимости от заданного разделителя
Да, помнится где-то была такая тема , натыкался. Однако в то время меня этот вопрос никак не беспокоил и я прошел мимо.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
|
