ugrep indexer
v1.0.0
Утилита ugrep-indexer рекурсивно индексирует файлы, чтобы ускорить рекурсивный поиск.
Также содержимое архивов и сжатых файлов индексируется, если указано в параметре командной строки. Это исключает их поиск, когда ни одно из их содержимого не соответствует указанным шаблонам.
ugrep — это быстрый поиск файлов, совместимый с grep, который поддерживает поиск на основе индекса. Поиск по индексу может быть значительно быстрее на медленных файловых системах и когда кэширование файловой системы неэффективно: если файловая система на искомом диске не кэшируется в оперативной памяти, т.е. она «холодная», то индексирование ускорит поиск. Он ищет только те файлы, которые могут соответствовать указанному шаблону регулярного выражения, используя индекс файла. Этот индекс позволяет быстро проверить наличие потенциального совпадения, поэтому мы избегаем поиска по всем файлам.
Индексированный поиск с помощью Ugrep безопасен и никогда не пропускает обновленные файлы, которые теперь могут совпадать. Если какие-либо файлы и каталоги добавляются или изменяются после индексирования, то поиск всегда будет выполнять поиск этих добавлений и изменений, внесенных в файловую систему, путем сравнения меток времени файлов и каталогов с отметкой времени индексации.
Если после индексирования добавляется или изменяется много файлов, мы можем захотеть выполнить повторную индексацию, чтобы обновить индексы. Повторная индексация является инкрементальной, поэтому она не займет столько времени, сколько первоначальный процесс индексации.
Типичный, но небольшой пример поиска по индексу, например в репозитории ugrep v3.12.6, размещенном на отдельном диске:
$ cd drive/ugrep
$ ugrep-indexer -I
12247077 bytes scanned and indexed with 19% noise on average
1317 files indexed in 28 directories
28 new directories indexed
1317 new files indexed
0 modified files indexed
0 deleted files removed from indexes
128 binary files ignored with --ignore-binary
0 symbolic links skipped
0 devices skipped
5605227 bytes indexing storage increase at 4256 bytes/file
Обычный поиск в холодной файловой системе без индексации занимает 1,02 секунды после отключения drive и повторного монтирования, чтобы очистить кэш ФС и записать эффект индексации:
$ ugrep -I -l 'std::chrono' --stats
src/ugrep.cpp
Searched 1317 files in 28 directories in 1.02 seconds with 8 threads: 1 matching (0.07593%)
Ripgrep 13.0.0 занимает больше времени — 1,18 секунды для того же холодного поиска (ripgrep по умолчанию пропускает двоичные файлы, поэтому опция -I не указана):
$ time rg -l 'std::chrono'
src/ugrep.cpp
1.18 real 0.01 user 0.06 sys
Напротив, при индексировании поиск в холодной файловой системе с помощью ugrep занимает всего 0,0487 секунды, что в 21 раз быстрее, после отключения drive и повторного монтирования для очистки кэша FS для записи эффекта индексации:
$ ugrep --index -I -l 'std::chrono' --stats
src/ugrep.cpp
Searched 1317 files in 28 directories in 0.0487 seconds with 8 threads: 1 matching (0.07593%)
Skipped 1316 of 1317 files with non-matching indexes
Всегда существует некоторая разница в затраченном времени: 0,0487 секунды — лучшее время из четырех прогонов поиска, которые дали диапазон времени поиска от 0,0487 (ускорение в 21 раз) до 0,0983 секунды (ускорение в 10 раз).
В целом прирост скорости может быть значительно выше по сравнению с этой небольшой демонстрацией, в зависимости от нескольких факторов: размера индексируемых файлов, скорости чтения файловой системы и предположения, что большинство файлов являются холодными.
Алгоритм индексации, который я разработал, является доказуемо монотонным : более высокая точность гарантирует повышение производительности поиска за счет уменьшения количества ложных срабатываний, но также увеличивает накладные расходы на хранение индекса. Аналогичным образом, более низкая точность снижает производительность поиска, но также снижает накладные расходы на хранение индекса. Поэтому я назвал свой индексатор монотонным индексатором .
Если пространство для хранения файлов ограничено, мы можем снизить нагрузку на хранилище индекса, указав более низкую точность индексации.
Индексирование приведенного выше примера с уровнем 0 (опция -0 ) уменьшает накладные расходы на индексное хранилище в 8,6 раз, с 4256 байт на файл до жалких 490 байт на файл:
12247077 bytes scanned and indexed with 42% noise on average
1317 files indexed in 28 directories
0 new directories indexed
1317 new files indexed
0 modified files indexed
0 deleted files removed from indexes
128 binary files ignored with --ignore-binary
0 symbolic links skipped
0 devices skipped
646123 bytes indexing storage increase at 490 bytes/file
В этом примере индексированный поиск по-прежнему выполняется в 12 раз быстрее, чем неиндексированный: фактически было найдено 16 файлов (15 ложных срабатываний):
Searched 1317 files in 28 directories in 0.0722 seconds with 8 threads: 1 matching (0.07593%)
Skipped 1301 of 1317 files with non-matching indexes
Более сложные шаблоны регулярных выражений, чем в этом примере, естественным образом могут иметь более высокий уровень ложных срабатываний, то есть количество файлов, которые считаются возможно совпадающими, хотя это не так. Более высокий уровень ложных срабатываний может снизить скорость поиска, если этот показатель достаточно велик, чтобы оказать влияние.
В следующей таблице показано, как точность индексирования влияет на хранилище индексации и средний шум на индексируемый файл. Крайние правые столбцы показывают скорость поиска и частоту ложных срабатываний для ugrep --index -I -l 'std::chrono' :
| соотв. | индексное хранилище (КБ) | средний шум | ложные срабатывания | время поиска (с) |
|---|---|---|---|---|
-0 | 631 | 42% | 15 | 0,0722 |
-1 | 1276 | 39% | 1 | 0,0506 |
-2 | 1576 г. | 36% | 0 | 0,0487 |
-3 | 2692 | 31% | 0 | разблокировать |
-4 | 2966 | 28% | 0 | разблокировать |
-5 | 4953 | 23% | 0 | разблокировать |
-6 | 5474 | 19% | 0 | разблокировать |
-7 | 9513 | 15% | 0 | разблокировать |
-8 | 10889 | 11% | 0 | разблокировать |
-9 | 13388 | 7% | 0 | разблокировать |
Если указанное регулярное выражение соответствует гораздо большему количеству возможных шаблонов, например, с поиском ugrep --index -I -l '(todo|TODO)[: ]' , то мы можем наблюдать более высокий уровень ложных срабатываний среди 1317 найденных файлов, что приводит к немного большему времени поиска:
| соотв. | ложные срабатывания | время поиска (с) |
|---|---|---|
-0 | 189 | 0,292 |
-1 | 69 | 0,122 |
-2 | 43 | 0,103 |
-3 | 19 | 0,101 |
-4 | 16 | 0,097 |
-5 | 2 | 0,096 |
-6 | 1 | разблокировать |
-7 | 0 | разблокировать |
-8 | 0 | разблокировать |
-9 | 0 | разблокировать |
Точность -4 используется по умолчанию (ранее -5 в более старых версиях), что очень хорошо работает при поиске по шаблонам регулярных выражений умеренной сложности.
Одно слово предостережения. Всегда есть небольшие накладные расходы на проверку индексов. Это означает, что если все файлы уже кэшированы в оперативной памяти, поскольку файлы были найдены или прочитаны недавно, то индексирование, очевидно, не обязательно ускорит поиск. В этом случае неиндексированный поиск может быть быстрее. Кроме того, поиск на основе индекса имеет более длительное время запуска. Это время запуска увеличивается, когда используются классы символов Юникода и подстановочные знаки, которые необходимо преобразовать в хэш-таблицы.
Подводя итог, можно сказать, что поиск на основе индекса наиболее эффективен при поиске большого количества «холодных» файлов и когда шаблоны регулярных выражений не слишком совпадают, т. е. мы хотим ограничить использование неограниченного количества повторений * и + и ограничить использование классов символов Юникода, когда возможный. Это сокращает время запуска Ugrep и ограничивает количество ложных совпадений с шаблоном (см. также вопросы и ответы ниже).
Рекурсивно и постепенно индексируйте все недвоичные файлы, показывающие прогресс:
ugrep-indexer -I -v
Рекурсивно и постепенно индексировать все недвоичные файлы, включая недвоичные файлы, хранящиеся в архивах и в сжатых файлах, показывая прогресс:
ugrep-indexer -z -I -v
Инкрементно индексировать все небинарные файлы, включая архивы и сжатые файлы, показывать прогресс, переходить по символическим ссылкам на файлы (но не на каталоги), но не индексировать файлы и каталоги, соответствующие globs в .gitignore:
ugrep-indexer -z -I -v -S -X
Принудительно переиндексировать все недвоичные файлы, включая архивы и сжатые файлы, следовать символическим ссылкам на файлы (но не на каталоги), но не индексировать файлы и каталоги, соответствующие globs в .gitignore:
ugrep-indexer -f -z -I -v -S -X
То же самое, но уменьшите объем хранилища индексных файлов до минимума, уменьшив точность индексирования с 5 (по умолчанию) до 0:
ugrep-indexer -f -0 -z -I -v -S -X
Повысьте производительность поиска, увеличив точность индексации с 5 (по умолчанию) до 7 за счет увеличения индексных файлов:
ugrep-indexer -f7zIvSX
Рекурсивно удалите все скрытые индексные файлы ._UG#_Store чтобы восстановить неиндексированное дерево каталогов:
ugrep-indexer -d
Настройте и скомпилируйте с помощью:
./build.sh
Если желательно, но не обязательно, установите с помощью:
sudo make install
Добавьте опцию для создания одного индексного файла, например явно указанную в ugrep. Это может еще больше повысить скорость индексированного поиска, если индексный файл расположен в быстрой файловой системе. В противном случае не ждите значительного улучшения или даже возможного замедления, поскольку в одном индексном файле нельзя искать одновременно, и будет проверяться больше записей индекса, хотя на самом деле каталоги пропускаются (также пропуская их индексы). Эксперименты покажут. Важным предостережением этого подхода является то, что поиск по индексу с помощью ugrep --index больше не безопасен: новые и измененные файлы, которые еще не проиндексированы, не будут искаться.
Каждый N-граммный фильтр Блума имеет свой собственный «битовый уровень» в хеш-таблице, чтобы избежать конфликтов хеширования. Например, 2-граммы не имеют общих битов с 3-граммами. Это гарантирует, что у нас никогда не будет ложных срабатываний при ошибочном сопоставлении символов, которые на самом деле не являются частью шаблона. Однако битовое пространство в 1 грамм (один символ) невелико (не более 256 бит). Поэтому мы теряем некоторые биты, когда хэш-таблицы больше. Возможный подход к сокращению потерь — объединить 1 грамм с 2 граммами для совместного использования одного и того же битового пространства. Это легко сделать, если мы считаем, что 1-грамма равна 2-грамме со вторым символом, установленным на (NUL). Мы можем снизить уровень ложных срабатываний с помощью второго 2-граммового хеша, основанного на другом методе хеширования. Или мы можем расширить «битовые уровни» с 8 до 9, чтобы хранить 9 граммов. Это повысит точность индексации для более длинных шаблонов (9 и более) без дополнительных затрат. С другой стороны, это изменение может привести к увеличению числа ложных срабатываний при ошибочном сопоставлении символов, не являющихся частью шаблона; мы теряем преимущество идеальной точности в 1 грамм.
Индексирование добавляет скрытый индексный файл ._UG#_Store к каждому индексируемому каталогу. Индексированные файлы сканируются (никогда не изменяются!) с помощью ugrep-indexer для создания индексных файлов.
Размер индексных файлов зависит от заданной точности: -0 самый низкий (маленькие индексные файлы) и -9 самый высокий (большие индексные файлы). Точность по умолчанию равна -4 . Подробную информацию о влиянии точности на размер индексации и скорость поиска см. в следующем вопросе.
Индексирование никогда не следует за символическими ссылками на каталоги , поскольку символически связанные каталоги могут находиться где угодно в файловой системе или в другой файловой системе, куда мы не хотим добавлять индексные файлы. Вы по-прежнему можете индексировать символические ссылки на файлы с помощью опции ugrep-indexer -S .
Опция -v ( --verbose ) отображает ход индексирования и «шум» каждого проиндексированного файла. Шум — это мера энтропии или случайности входных данных. Более высокий уровень шума означает, что индексирование менее точно отображает содержимое файла. Например, большой файл со случайными данными трудно точно проиндексировать, и он будет иметь высокий уровень шума.
Сложность индексирования линейно зависит от размера индексируемого файла. На практике это не быстрый процесс, не такой быстрый поиск, и для завершения полного прохода индексации по большому дереву каталогов может потребоваться некоторое время. Когда индексирование завершится, ugrep-indexer отобразит результаты индексирования. Также сообщается общий размер добавленных индексов и средний шум индексации.
Сканирование файла для индексации приводит к получению хэш-таблицы индексации размером 64 КБ. Затем ugrep-индексатор делит таблицу пополам с побитовым сжатием, используя побитовое-и до тех пор, пока не будет превышена целевая точность. Уполовинивание становится возможным благодаря тому, что таблица кодирует хэши для 8 окон со смещениями от начала шаблона, что соответствует 8 битам на ячейку таблицы хеширования индекса. Объединение двух половин таблицы может привести к обращению некоторых битов из единицы в ноль, что может привести к ложноположительному совпадению. Это доказывает монотонность индексатора. Хэш-значение с нулевым битом указывает на возможное совпадение.
Индексатор ugrep обнаруживает «двоичные файлы», которые можно игнорировать и не индексировать с помощью опции индексатора ugrep -I ( --ignore-binary ). Это полезно при поиске с параметром ugrep -I ( --ignore-binary ), чтобы игнорировать двоичные файлы, что является типичным сценарием.
Индексатор ugrep подчиняется исключениям файлов .gitignore, если они указаны с помощью опции -X ( --ignore-files ). Игнорируемые файлы и каталоги не будут индексироваться для экономии места в файловой системе. Это хорошо работает при поиске файлов с параметром ugrep --ignore-files .
Индексирование можно прервать, например, нажав CTRL-C, что не приведет к потере возможности поиска с помощью ugrep, но оставит структуру каталогов индексированной лишь частично.
Опция -c проверяет индексы на наличие устаревших ссылок и неиндексированных файлов и каталогов.
Индексы удаляются с помощью опции ugrep-indexer -d .
Индексатор ugrep был тщательно протестирован путем сравнения результатов поиска ugrep --index с «медленными» неиндексированными результатами поиска ugrep по тысячам файлов с тысячами случайных шаблонов поиска.
Индексированный поиск работает со всеми параметрами ugrep, кроме параметра -v ( --invert-match ), --filter , -P ( --perl-regexp ) и -Z ( --fuzzy ). Опция -c ( --count ) с --index автоматически устанавливает --min-count=1 для пропуска всех файлов с нулевым совпадением.
Если какие-либо файлы или каталоги были обновлены, добавлены или удалены после индексирования, то ugrep --index всегда будет искать эти файлы и каталоги, когда они присутствуют в пути рекурсивного поиска. Вы можете снова запустить ugrep-indexer, чтобы постепенно обновить все индексы.
Шаблоны регулярных выражений преобразуются внутри Ugrep с опцией --index в форму хеш-таблиц для первых 16 байтов указанных шаблонов регулярных выражений, возможно, короче, чтобы сократить время построения, когда шаблоны регулярных выражений являются сложными. Таким образом, первые 8–16 символов шаблона регулярного выражения для поиска наиболее важны и не должны совпадать слишком сильно, чтобы ограничить так называемые ложноположительные совпадения, которые могут замедлить поиск.
В Ugrep шаблон регулярного выражения преобразуется в DFA. Конечный автомат индексирования хеширования (HFA) строится поверх DFA для компактного представления хеш-таблиц как переходов состояний с помеченными ребрами. Этот HFA состоит из восьми слоев, каждый из которых сдвинут на один байт для представления следующего 8-байтового окна в шаблоне. Каждый уровень HFA кодирует хэши индексов для этой части шаблона. Выбранная хеш-функция индекса является «аддитивной», то есть следующий байт добавляется при хешировании с предыдущим хэшем. Это очень важно, поскольку существенно снижает накладные расходы на строительство HFA. Теперь мы можем кодировать помеченные переходы HFA в состояния как несколько ребер с 16-битными диапазонами хэш-значений вместо набора отдельных ребер, каждое из которых имеет индивидуальное значение хеш-функции. С этой целью я использую свою библиотеку открытых диапазонов reflex::ORanges<T> полученную из std::set<T> .
Ниже приведена очень простая однострочная функция maybe_match() с хэш-функцией индекса Prime 61, чтобы продемонстрировать поиск одной строки на основе индекса:
// prime 61 hashing
uint16_t indexhash(uint16_t h, uint8_t b, size_t size)
{
return ((h << 6) - h - h - h + b) & (size - 1);
}
// return possible match of string given array of hashes of size <= 64K (power of two)
bool maybe_match(const char *string, uint8_t *hashes, size_t size)
{
size_t len = strlen(string); // practically we can and should limit len to e.g. 15 or 16
for (const char *window = string; len > 0; ++window, --len)
{
uint16_t h = window[0] & (size - 1);
if (hashes[h] & 0x01)
return false
size_t k, n = len < 8 ? len : 8;
for (k = 1; k < n; ++k)
{
h = indexhash(h, window[k], size);
if (hashes[h] & (1 << k))
return false;
}
}
return true;
}
Хэш Prime 61 был выбран среди многих других возможных функций хеширования с использованием реалистичной экспериментальной установки. Кандидатная хеш-функция была протестирована путем многократного поиска случайно выбранного слова в файле Википедии размером 100 МБ. Слово было мутировано одной, двумя или тремя случайными буквами. Эта мутация проверяется, чтобы убедиться, что она не соответствует действительному слову в файле Википедии. Затем регистрировалась частота ложных срабатываний всякий раз, когда мутированное слово соответствовало файлу. Хэш-функция с минимальным уровнем ложных срабатываний в целом должна быть хорошим кандидатом.
При использовании окна размером 8 (или меньше, в зависимости от длины шаблона) уровень ложных срабатываний ниже по сравнению со стандартными фильтрами Блума. Более конкретно, в фильтре Блума вместо N используются хэш-функции N² . Для более коротких шаблонов N часто слишком мало, чтобы ограничить ложные срабатывания. Следовательно, N² более эффективен. Он также отклоняет любой шаблон из совпадений, в котором символ в первых 8 байтах шаблона фактически не встречается нигде в индексированном файле, тогда как стандартный фильтр Блума может иметь ложноположительное совпадение. Более того, битовая адресация, используемая для индексации хэш-таблицы, обеспечивает эффективное сжатие таблицы.
Индексирование — это форма сжатия с потерями. Чем выше точность индексации, тем быстрее должна быть производительность поиска Ugrep за счет пропуска большего количества несовпадающих файлов. Более высокая точность снижает шум (меньше потерь). Высокий уровень шума приводит к тому, что ugrep иногда ищет несовпадающие индексированные файлы. Мы называем это «ложноположительными совпадениями». Для более высокой точности требуются индексные файлы большего размера. Обычно мы ожидаем, что в среднем на файл будет индексироваться 4 КБ или меньше. Минимальный размер индексного хранилища составляет 128 байт на файл, исключая имя файла и 4-байтовый индексный заголовок. Максимальный размер хранилища составляет 64 КБ на файл для очень больших файлов с шумом.
При поиске индексированных файлов с помощью ugrep --index --stats опция --stats показывает статистику поиска после завершения поиска на основе индексирования. Когда многие файлы не пропускаются из поиска из-за шума индексации (т.е. ложных срабатываний), то более высокая точность помогает повысить эффективность индексации, что может ускорить поиск.
Файлы UTF-16 и UTF-32 также индексируются. Индексатор обрабатывает их как UTF-8 после внутреннего преобразования в UTF-8 для индексации.
Дисковое пространство экономится за счет архивирования (zip/tar/pax/cpio) и сжатия файлов. С другой стороны, поиск в архивах и сжатых файлах происходит намного медленнее, чем поиск обычных файлов. Индексирование архивов и сжатых файлов с помощью ugrep-indexer -z -I и поиск по ним с помощью ugrep -z -I --index PATTERN ускоряет поиск, т.е. когда архивы и сжатые файлы пропускаются. С другой стороны, требования к дисковому хранилищу возрастут с добавлением записей индексных файлов для архивов и сжатых файлов. Обратите внимание: если архивы и сжатые файлы содержат двоичные файлы, опция -I игнорирует эти двоичные файлы.
Затраты на запуск ugrep --index для создания индексирующих хеш-таблиц зависят от шаблонов регулярных выражений. Если шаблон регулярного выражения очень «разрешительный», т.е. соответствует множеству возможных шаблонов, то время запуска ugrep --index значительно увеличивается для вычисления хэш-таблиц. Это может произойти при использовании больших классов символов Юникода и подстановочных знаков, особенно при неограниченном повторении * и + . Чтобы узнать, как увеличивается время запуска, используйте опцию ugrep --index -r PATTERN /dev/null --stats=vm для поиска /dev/null с вашим ШАБЛОНОМ.
Индексные файлы должны быть очень плотными по содержанию информации, и именно так обстоит дело с новым алгоритмом индексации для Ugrep, который я разработал и внедрил. Чем плотнее индексный файл, тем более компактным он точно представляет исходные данные файла. Это затрудняет или делает невозможным сжатие индексных файлов. Это также хороший показатель того, насколько эффективным будет индексный файл на практике.
