Почему "grep -ignore-case" в 50 раз медленнее?

Я был очень удивлен, увидев, что когда вы добавляете опцию --ignore-case в grep, это может замедлить поиск в 50 раз. Я тестировал это на двух разных машинах с тем же результатом. Мне любопытно узнать объяснение огромной разницы в производительности.

Я также хотел бы увидеть альтернативную команду grep для поиска без учета регистра. Мне не нужны регулярные выражения, просто фиксированный поиск строк. Сначала тестовый файл будет текстовым файлом размером 50 Мб с некоторыми фиктивными данными, вы можете использовать следующий код для его создания:

Создать test.txt

yes all work and no play makes Jack a dull boy | head -c 50M > test.txt
echo "Jack is no fun" >> test.txt
echo "Jack is no Fun" >> test.txt

Демонстрация

Ниже приведена демонстрация медленности. Добавляя параметр --ignore-case, команда становится в 57 раз медленнее.

$ time grep fun test.txt
all work and no plJack is no fun
real    0m0.061s

$ time grep --ignore-case fun test.txt
all work and no plJack is no fun
Jack is no Fun
real    0m3.498s

Возможные пояснения

Google google вокруг меня нашел дискуссию о том, что grep медленнее в локали UTF-8. Поэтому я провел следующий тест, и он ускорился. Языковой стандарт по умолчанию на моей машине en_US.UTF-8, поэтому установка его на POSIX, похоже, сделала загрузку производительности, но теперь, конечно, я не могу правильно искать текст Unicode, что нежелательно. Это также еще в 2,5 раза медленнее.

$ time LANG=POSIX grep --ignore-case fun test.txt
all work and no plJack is no fun
Jack is no Fun
real    0m0.142s

Альтернативы

Мы могли бы использовать Perl вместо этого быстрее, но все же в 5,5 раза быстрее, чем чувствительный к регистру grep. И POSIX grep выше примерно в два раза быстрее.

$ time perl -ne '/fun/i && print' test.txt
all work and no plJack is no fun
Jack is no Fun
real    0m0.388s

Поэтому мне бы хотелось найти верную альтернативу и объяснение, если у кого-нибудь есть.

ОБНОВЛЕНИЕ - CentOS

Две машины, которые были испытаны выше обоих, выполняли Ubuntu один 11.04 (Natty Narwhal), другой 12.04 (Precise Pangolin). Выполнение тех же тестов на машине CentOS 5.3 дает следующие интересные результаты. Результаты работы двух случаев почти идентичны. Теперь CentOS 5.3 был выпущен в январе 2009 года, а работает grep 2.5.1, в то время как Ubuntu 12.04 работает с grep 2.10. Таким образом, в новой версии могут быть изменения и различия в двух дистрибутивах.

$ time grep fun test.txt
Jack is no fun
real    0m0.026s

$ time grep --ignore-case fun test.txt
Jack is no fun
Jack is no Fun
real    0m0.027s

Ответ 1

Я думаю, что этот отчет об ошибках помогает понять, почему он медленный:

отчет об ошибке grep, медленный в игнор-случае

Ответ 2

Эта медленность обусловлена тем, что grep (в локали UTF-8) постоянно обращается к файлам "/usr/lib/locale/locale-archive" и "/usr/lib/gconv/gconv-modules.cache".

Это можно показать с помощью утилиты strace. Оба файла находятся из glibc.

Ответ 3

Чтобы сделать поиск без учета регистра, grep сначала должен преобразовать ваш весь файл размером 50 Мб в один случай или другой. Это займет время. Не только это, но есть копии памяти...

В вашем тестовом примере вы сначала сгенерируете файл. Это означает, что он будет кэшироваться памятью. Первый запуск grep должен mmap кэшировать страницы; ему даже не нужно обращаться к диску.

Нечувствительный к регистру grep делает то же самое, но затем пытается изменить эти данные. Это означает, что ядро примет исключение для каждой модифицированной страницы 4 kB, и в итоге вам придется скопировать весь 50 МБ в новую память, по одной странице за раз.

В принципе, я ожидаю, что это будет медленнее. Может быть, не 57 раз медленнее, но определенно медленнее.

Ответ 4

Причина в том, что ему нужно выполнить сравнение с Unicode для текущей локали, и, судя по словам Марата, это не очень эффективно при этом.

Это показывает, насколько быстрее это происходит, когда Unicode не учитывается:

$ time LC_CTYPE=C grep -i fun test.txt
all work and no plJack is no fun
Jack is no Fun
real    0m0.192s

Конечно, эта альтернатива не будет работать с символами других языков, таких как Ñ/ñ, Ø/ø,/ð, Æ/æ и т.д.

Другой альтернативой является изменение регулярного выражения так, чтобы оно соответствовало нечувствительности к регистру:

$ time grep '[Ff][Uu][Nn]' test.txt
all work and no plJack is no fun
Jack is no Fun
real    0m0.193s

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

Для сравнения, в моей системе:

$ time grep fun test.txt
all work and no plJack is no fun
real    0m0.085s

$ time grep -i fun test.txt
all work and no plJack is no fun
Jack is no Fun
real    0m3.810s