grab
1.0.0
Это моя собственная экспериментальная параллельная версия grep , позволяющая тестировать различные стратегии ускорения доступа к большим деревьям каталогов. На флэш-накопителях или твердотельных накопителях вы можете легко перехитрить обычные команды grep в 8 раз.
Параметры:
Usage: ./greppin [-rIOLlsSH] [-n <cores>] <regex> <path>
-2 -- use PCRE2 instead of PCRE
-O -- print file offset of match
-l -- do not print the matching line (Useful if you want
to see _all_ offsets; if you also print the line, only
the first match in the line counts)
-s -- single match; dont search file further after first match
(similar to grep on a binary)
-H -- use hyperscan lib for scanning
-S -- only for hyperscan: interpret pattern as string literal instead of regex
-L -- machine has low mem; half chunk-size (default 2GB)
may be used multiple times
-I -- enable highlighting of matches (useful)
-n -- Use multiple cores in parallel (omit for single core)
-r -- recurse on directory
Grab использует библиотеку pcre , поэтому по сути она эквивалентна grep -P -a . Параметр -P важен, поскольку Perl-совместимые регулярные выражения имеют характеристики, отличные от основных регулярных выражений.
Есть два филиала. master и greppin . Master — это «традиционный» захват , который должен компилироваться и работать в большинстве систем POSIX. greppin поставляется с собственной оптимизированной и распараллеленной версией nftw() и readdir() , которая снова удваивает скорость помимо ускорения, которое уже обеспечивает master ветка. Ветка greppin работает на Linux, BSD и OSX. greppin также поддерживает библиотеки гиперсканирования Intel, которые пытаются использовать инструкции SIMD процессора, если это возможно (AVX2, AVX512 и т. д.) при компиляции шаблона регулярного выражения в JIT-код.
Скорее всего, вам захочется создать ветку greppin :
$ git checkout greppin
[...]
$ cd src; make
[...]
Убедитесь, что у вас установлены пакеты библиотек pcre и pcre2 . В системах BSD вам нужен gmake вместо make . Если вы хотите использовать передовые технологии с помощью механизма множественных регулярных выражений greppin и поддержки гиперсканирования, вам сначала нужно получить и собрать это:
$ git clone https://github.com/intel/hyperscan
[...]
$ cd hyperscan
$ mkdir build; cd build
$ cmake -DFAT_RUNTIME=1 -DBUILD_STATIC_AND_SHARED=1 ..
[...]
$ make
[...]
Это создаст так называемую «толстую» среду выполнения библиотек гиперсканирования, которая поддерживает все семейства процессоров, чтобы выбрать правильный шаблон компиляции во время выполнения для достижения максимальной производительности. Как только сборка завершится, вы создадите greppin для этого:
(внутри захвата клонированного репо)
$ cd src
$ HYPERSCAN_BUILD=/path/to/hyperscan/build make -f Makefile.hs
[...]
Это создаст двоичный файл greppin , который позволит опции -H загружать другой движок во время выполнения, пытаясь использовать все возможные биты производительности.
Вы можете связать его с уже установленными библиотеками, но API совсем недавно добавил некоторые функции в версию 5.x, а большинство дистрибутивов поставляются с 4.x.
Grab использует mmap(2) и сопоставляет весь файловый объект без подсчета символов новой строки (что делает grep , даже если совпадений нет [согласно моей проверке кода grep в 2012 году; сегодня все может быть по-другому]), что очень много. быстрее, чем read(2) разбивая файл на небольшие куски и подсчитывая символы новой строки. Если доступно, Grab также использует функцию PCRE JIT. Однако ускорение можно измерить только на больших файловых деревьях или быстрых жестких или твердотельных накопителях. В последнем случае ускорение может быть очень значительным (до 3 раз), если выполнять сопоставление рекурсивно и параллельно. Поскольку хранилище является узким местом, распараллеливание поиска на жестких дисках не имеет смысла, поскольку поиск занимает больше времени, чем простое линейное выполнение операций.
Кроме того, захват пропускает файлы, которые слишком малы, чтобы содержать регулярное выражение. Для более крупных регулярных выражений в рекурсивном поиске это может пропустить довольно большое количество файлов, даже не открывая их.
Требуется совершенно новая библиотека pcre , в некоторых старых системах сборка может завершиться неудачно из-за отсутствия PCRE_INFO_MINLENGTH и pcre_study() .
Файлы отображаются в формате mmap и сопоставляются частями по 1 Гигабайту. Для файлов большего размера последние 4096 байт (1 страница) фрагмента перекрываются, поэтому можно найти совпадения на границе 1 Гигабайта. В этом случае вы увидите удвоенное совпадение (но с тем же смещением).
Если вы сравниваете grep и Grab , не забывайте удалять кэши dentry и page между каждым запуском: echo 3 > /proc/sys/vm/drop_caches
Обратите внимание, что grep выведет только «Соответствие двоичных файлов», если он обнаружит двоичные файлы, тогда как grep выведет все совпадения, если не указано -s . Итак, для теста скорости вам нужно найти выражение, которого нет в данных, чтобы обеспечить поиск по всем файлам.
Grab был создан для быстрого поиска по большим деревьям каталогов без индексации. Исходный grep имеет гораздо более полный набор опций. Ускорение при совпадении одного файла очень незначительно, если вообще измеримо.
Для твердотельных накопителей имеет смысл выбрать многоядерный вариант. Для жестких дисков это не так, поскольку головку приходится перемещать вперед и назад между потоками, что потенциально нарушает принцип локальности и снижает производительность.
Ветка greppin имеет собственную параллельную версию nftw() без блокировки, поэтому время простоя N - 1 ядер, когда 1-е ядро строит дерево каталогов, также можно использовать для работы.
Осталось отметить: Grab физически перемещается по каталогам, т. е. не следует по символическим ссылкам.
spot — это параллельная версия find . Он поддерживает наиболее часто используемые параметры, какими вы их знаете. Больше рассказывать об этом нечего, просто попробуйте.
Здесь показано ускорение на 4-ядерной машине с поиском на SSD:
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grep -r foobardoesnotexist /source/linux
real 0m34.811s
user 0m3.710s
sys 0m10.936s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -r foobardoesnotexist /source/linux
real 0m31.629s
user 0m4.984s
sys 0m8.690s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -n 2 -r foobardoesnotexist /source/linux
real 0m15.203s
user 0m3.689s
sys 0m4.665s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -n 4 -r foobardoesnotexist /source/linux
real 0m13.135s
user 0m4.023s
sys 0m5.581s
С веткой greppin :
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grep -a -P -r linus /source/linux/|wc -l
16918
real 1m12.470s
user 0m49.548s
sys 0m6.162s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time greppin -n 4 -r linus /source/linux/|wc -l
16918
real 0m8.773s
user 0m4.670s
sys 0m5.837s
root@linux:~#
Да! ~9с против ~72с! На 4-ядерной SSD-машине это в 8 раз быстрее, чем при использовании традиционного grep.
Просто чтобы доказать, что это привело к тому же результату:
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# greppin -n 4 -r linus /source/linux/|sort|md5sum
a1f9fe635bd22575a4cce851e79d26a0 -
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# grep -P -a -r linus /source/linux/|sort|md5sum
a1f9fe635bd22575a4cce851e79d26a0 -
root@linux:~#
При сравнении одного ядра ускорение также зависит от того, какой процессор ядро фактически планирует grep , поэтому захват может быть или не быть быстрее (в основном так и есть). Если нагрузка в одноядерных тестах одинакова, Grab увидит ускорение при поиске в больших деревьях файлов. В многоядерных конфигурациях захват может принести пользу.
Проект можно найти здесь.
Основное ускорение в их таблицах тестов связано с тем, что ripgrep игнорирует множество файлов (особенно точечные файлы) при вызове без специальных опций, а также рассматривает двоичные файлы как цель с одним совпадением (аналогично grep ). Чтобы получить сопоставимые результаты, имейте в виду (4 — количество ядер):
echo 3 > /proc/sys/vm/drop_caches между каждым запуском-j 4 -a --no-unicode --no-pcre2-unicode -uuu --mmap в ripgrep , так как по умолчанию он будет соответствовать Unicode, который в 3 раза медленнее, и пытается компенсировать потерю скорости, пропуская 'игнорировать' файлы на основе. -e быстрее, чем -P , поэтому лучше выбрать -e , но он не такой мощный, как PCRE./dev/null чтобы избежать эффектов, основанных на tty-H -n 4 в greppin, если хотите добиться максимальной производительности. -H совместим с PCRE лишь за очень немногими исключениями (согласно документу Hyperscan).setfattr -n user.pax.flags -v "m" /path/to/binary если вы работаете в системах grsec и требуете JIT-сопоставлений rwx Тогда просто идите и проверьте тайминги. Даже если гиперсканирование не используется, greppin работает значительно быстрее, чем rg , при использовании выражений PCRE2 (PCRE2 и PCRE2) и еще быстрее при сравнении самых быстрых выражений (-e и гиперсканирование).
