☰

递归 grep 的奇怪执行时间

tag-icon • tag-icon performance grep
递归 grep 的奇怪执行时间

我在一台 Linux Ubuntu 机器上，grepping 了大量文件。有人能解释一下这些时间吗？

>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确认开放的 RAM 空间）。

不区分大小写会导致速度慢近 100 倍？这应该是处理量的一个常数时间增长。管道运算符会导致速度慢 30 倍？我想我无法反驳结果，但我只是好奇如何编写 grep 使其以这种方式执行，以及是否有任何解决方法。高性能 grep，有人吗？

答案1

不区分大小写会导致速度降低近 100 倍？这应该是处理量的一个常数时间增长。

嗯，不是。首先，有 1024 个不同的字符串可以匹配账户保证金使用-i开关。

匹配账户保证金区分大小写很容易；如果当前字符不是A，跳过。使用大小写折叠时，您必须检查当前字符是否是A或A。这不仅仅是两个测试，你还有很多不能直接跳过的匹配。1对于非 ASCII 字符来说，这变得更加困难。

尽管如此，grep -i速度不应该这么慢。当预期有多字节字符时（即使文件中没有字符），这似乎是大小写折叠的糟糕实现。

可能的解决方法

  1. 不要使用-i开关并手动构建不区分大小写的正则表达式。

  2. 如果文件仅包含 ASCII 字符，则临时设置环境变量的编码标识符语言到ISO-8859-1（又名西欧、拉丁-1 或代码页 819）。

  3. 选择一种非默认的正则表达式类型（--fixed-strings，--extended-regexp或--perl-regexp）。

  4. 如果文件仅包含 ASCII 字符和大小写折叠输出是可以接受的，不要使用-i开关和管道大小写折叠字符来 grep。

测试设置

我在我的计算机2上创建了一个 500 MB 的 Base64 编码伪随机字节文件，终止了所有占用大量 CPU 或内存的进程，并将上述解决方法的执行时间与普通的grep或的执行时间进行了比较grep -i。

我使用重定向器将输入文件提供给 grep 和 tr，并丢弃输出以消除潜在的偏差源。

我已经运行每个命令几次；执行时间稳定（最大变化为±0.01 秒）。

基准

$ # 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

默认正则表达式类型和其他非默认正则表达式类型之间没有可测量的差异。

标准 Ubuntu 存储库中的最新版本的 grep (2.10) 和 GNU grep 的最新稳定版本 (2.14) 之间没有可测量的差异。

结论

  • 解决方法 1 和 2 可实现相同的加速。

    这表明解决方法 1 与在不预期多字节字符时 grep 的大小写折叠的工作方式类似。

  • 尽管--perl-regexp区分大小写的匹配速度要慢得多，但区分大小写的匹配速度却快得多。

  • --perl-regexp如果没有预期的多字节字符，则速度会变得更快。

  • 解决方法 4 以折叠输出的大小写为代价，可以像区分大小写的匹配一样快。

1我并不是说 grep 的内部工作方式就是这样的。这是为了说明为什么不区分大小写的匹配更为复杂。

2英特尔酷睿 i5-3570K，16 GiB RAM，Ubuntu 12.10

相关内容