GNU grep 3.7 был выпущен с исправлением ошибки, вызывающей «резкое снижение производительности» в некоторых типах поиска.
Этот инструмент поиска, который ищет шаблоны символов в файлах, является основной утилитой в Linux и других Unix-подобных операционных системах. В ноябре прошлого года пользователь заметил: «У меня есть случай использования, когда я запускаю grep с большим количеством шаблонов поиска в большом текстовом файле. Он хорошо работает с grep-3.3, но с grep-3.4 он быстро сжигает гигабайты. памяти и почти заблокировал мою систему из-за подкачки … даже с 30 000 шаблонов он превышает предел в 5 ГБ ».
Напротив, grep 3.3 использовал «всего несколько 100 МБ».
Сопровождающий Grep Джим Мейеринг обнаружил ошибку, которая «вызывает чрезмерные коллизии хэшей … из-за которой новая фаза предварительной обработки шаблонов занимает O (N ^ 2) времени для N шаблонов».
В объявлении о версии 3.7 Майеринг сказал, что пример использования (ниже) теперь занимает «секунды, а не дни».
: | grep -Ff <(seq 6400000 | tr 0-9 A-J)
Ошибка появляется только в тех случаях, когда «слишком много шаблонов хешируется в слишком мало корзин».
Grep обычно работает на удивление быстро и дает гораздо больше удовольствия, чем, например, мучительные попытки поиска строки в большом каталоге в проводнике Windows.
В 2010 году автор GNU grep Майк Хэртель написал о том, «почему GNU grep работает быстро».
Haertel сказал, что он избегает просмотра каждого входного байта, пропуская вперед «всякий раз, когда он находит несоответствующий символ», избегает копирования данных и выполняет «менее 3 инструкций x86, выполняемых для каждого входного байта, который он фактически просматривает».
Текущая документация объясняет используемые алгоритмы (Boyer-Moore и Aho-Corasick) и признает, что, будучи обычно эффективным, «в некоторых случаях он может быть довольно медленным».
Некоторые регулярные выражения могут привести к «использованию экспоненциального алгоритма в худшем случае». Поиск без учета регистра и многобайтовые символы также могут замедлить его.
Те, кто ищет более быстрый grep, могут захотеть взглянуть на ripgrep, написанный на Rust в основном Эндрю Галлантом и который, согласно его тестам, обычно быстрее, чем grep, по причинам, включая постоянную поддержку Unicode.
Grep обычно работает хорошо, и в случае проблем с производительностью, возможно, стоит проверить версию 3.7. Тем не менее, фильтрация новых версий grep в дистрибутивы занимает некоторое время: например, версия в нашей подсистеме Windows для Linux – 2.25.
Напоминание Майклу Ларабелю из Phoronix, обнаружившему исправление®.
