Странное время выполнения для рекурсивного grep

Question

Я на машине с Linux Ubuntu, собирая большое количество файлов. Кто-нибудь может объяснить эти сроки?

>time grep -nIr acct_margin *
[... 3 results ...]
real    0m0.555s
user    0m0.400s
sys     0m0.150s

Без учета регистра:

>time grep -niIr acct_margin *
[... 3 results ...]

real    0m45.739s
user    0m45.300s
sys     0m0.240s

С оператором "или" в регулярном выражении:

>time grep -nIr "acct_margin\|MARGIN_TABLE" *
[... 5 results ...]

real    0m15.892s
user    0m15.540s
sys     0m0.260s

Без учета регистра:

>time grep -niIr "acct_margin\|MARGIN_TABLE" *
[... 5 results ...]

real    0m52.433s
user    0m52.050s
sys     0m0.200s

Я выполнил команды достаточно, чтобы файлы были кэшированы (htop подтверждает открытое пространство оперативной памяти).

Нечувствительность к регистру возрастает почти в 100 раз? Это должно быть постоянное увеличение времени обработки. Трубный оператор в 30 раз медленнее? Думаю, я не могу спорить с результатами, но мне просто любопытно, как кто-то пишет grep так, что он работает таким образом, и есть ли способ обойти это. Высокая производительность, кто угодно?

Answer 1

Нечувствительность к регистру возрастает почти в 100 раз? Это должно быть постоянное увеличение времени обработки.

Ну нет. Для начала, есть 1024 различных строки, которые соответствуют acct_margin с ключом -i .

Соответствие acct_margin чувствительно к регистру; если текущий символ не является a, пропустите. При прецедентном складывании, вы должны проверить , если текущий символ является а или а. Это не только два теста, у вас также есть намного больше матчей, которые вы не можете пропустить напрямую. ¹ Это становится сложнее для не-ASCII символов.

Тем не менее, grep -i не должен быть таким медленным. Это кажется плохой реализацией свертывания регистра, когда ожидаются многобайтовые символы (даже если в файлах их нет).

Возможные обходные пути

1. Не используйте ключ -i и создайте регистрозависимое регулярное выражение вручную.

2. Если файлы содержат только символы ASCII, временно установите для идентификатора кодировки переменной среды LANG значение ISO-8859-1 (также известное как Western European, Latin-1 или Code Page 819).

3. Выберите один из нестандартных типов регулярных выражений (--fixed-strings , --extended-regexp или --perl-regexp).

4. Если в файлах содержатся только символы ASCII и вывод с учетом регистра допустим, не используйте ключ -i и передайте символы, сложенные в регистр, для grep.

Испытательная установка

Я создал 500 МБ файл псевдослучайных байтов в кодировке Base64 на моем компьютере ², уничтожил все процессы, интенсивно использующие процессор или память, и сравнил время выполнения вышеупомянутых обходных путей с простым grep или grep -i .

Я передал входной файл grep и tr с помощью перенаправителя и отбросил вывод, чтобы устранить потенциальные источники смещения.

Я запускал каждую команду несколько раз; время выполнения было стабильным (максимальное отклонение ± 0,01 с).

Bechmarks

$ # Make time output only elapsed time:
$ TIME="  %es"
$ # C create 500MB file of 76 printable ASCII characters per line:
$ < /dev/urandom base64 | head -c 500MB > file
$ # Verify that current character encoding is UTF8:
$ echo "  $LANG"
  en_US.UTF-8
# Benchmark of case-sensitive `grep' for comparison:
$ < file time grep test > /dev/null
  0.45s
$ # Benchmark of case-sensitive `grep --perl-regexp' for comparison:
$ < file time grep -P test > /dev/null
  0.82s
$ # Benchmark of case-insensitive `grep' for comparison:
$ < file time grep -i test > /dev/null
  21.08s
$ # Workaround 1:
$ < file time grep [Tt][Ee][Ss][Tt] > /dev/null
  1.53s
$ # Workaround 2:
$ (LANG=en_US.ISO-8859-1; < file time grep -i test > /dev/null)
  1.53s
$ # Workaround 3:
$ < file time grep -Pi test > /dev/null
  1.33s
$ # Workarounds 2 and 3 combined:
$ (LANG=en_US.ISO-8859-1; < file time grep -Pi test > /dev/null)
  1.25s
$ # Workarounds 4:
$ < file time tr [A-Z] [a-z] | grep test > /dev/null
  0.46s

Между стандартными и другими нестандартными типами регулярных выражений не было ощутимой разницы.

Не было заметного различия между последней версией grep из стандартных репозиториев Ubuntu (2.10) и последней стабильной версией GNU grep (2.14).

Выводы

• Обходной путь 1 и 2 приводят к одинаковому ускорению.

  Это говорит о том, что обходной путь 1 аналогичен тому, как работает grep в случае, когда многобайтовые символы не ожидаются.

• Хотя параметр --perl-regexp намного медленнее для сопоставления с учетом регистра, он значительно быстрее для сопоставления без учета регистра.

• --perl-regexp становится еще быстрее, если не ожидается многобайтовых символов.

• За счет сворачивания в регистр вывода обходной путь 4 может быть таким же быстрым, как и регистрозависимое сопоставление.

---

_{¹ Я не утверждаю, что именно так внутренне работает grep. Это наглядно показывает, почему сопоставление без учета регистра более сложно.}

_{² Intel Core i5-3570K, 16 ГБ ОЗУ, Ubuntu 12.10}