grep -f的性能问题

Question

我正在使用grep在单个文件中搜索几个正则表达式.特别是,我正在考虑一个带有英文字幕的100 MB文件, 并运行存储在文件patterns.txt中的以下正则表达式:

Cas.*eharden
acr.*otic
syn.*thesizing
sub.*abbot
iss.*acharite
bot.*onne
dis.*similatory
ove.*rmantel
isa.*tin
ado.*nijah
sol.*ution
zei.*st
fam.*ousness
inq.*uisitress
aor.*tography
via.*duct
ama.*sa
der.*ive
pie.*tas
kit.*chenette

在这样做时,我观察到grep所需的时间不会与正则表达式的数量呈线性增长.实际上,它似乎呈指数级增长.

实验

系统: Intel(R)Core(TM)i5-5200U CPU @ 2.20GHz; 4个核心; 8 GB RAM

案例1:20 regexps

命令grep -c -f patterns.txt subtitles.txt计数2214次并且需要
2,19s用户0,00s系统99%cpu 2,192总计.

案例2:30 regexps

如果我将以下表达式添加到patterns.txt

ort.*hros
ove.*ridentify
mis.*tiest
pay.*ne
int.*erchasing
jej.*uneness
sta.*lactiform
und.*ertrain
cob.*bles
Sub.*category

命令grep -c -f patterns.txt subtitles.txt计数2894次并占用71,35s用户0,06s系统99%cpu 1:11,42总计.

案例3:35个正则表达式

再添加五个表达式:

dis.*embosom
imp.*ortunateness
ema.*thion
rho.*mb
haz.*elwood

命令grep -c -f patterns.txt subtitles.txt计数2904次发生并占用211,18s用户0,22s系统99%cpu 3:31,58总计

为什么grep -f表现出这种行为？它在内部做什么？

我一直在使用的整套正则表达式都可以在这里找到

Answer 1

从阅读grep源代码来看，文件中的正则表达式似乎不是一次执行一个。相反，它们会被一次性读入一个大的正则表达式中：

case 'f':
  fp = STREQ (optarg, "-") ? stdin : fopen (optarg, O_TEXT ? "rt" : "r");
  if (!fp)
    error (EXIT_TROUBLE, errno, "%s", optarg);
  for (keyalloc = 1; keyalloc <= keycc + 1; keyalloc *= 2)
    ;
  keys = xrealloc (keys, keyalloc);
  oldcc = keycc;
  while ((cc = fread (keys + keycc, 1, keyalloc - 1 - keycc, fp)) != 0)
    {
      keycc += cc;
      if (keycc == keyalloc - 1)
        keys = x2nrealloc (keys, &keyalloc, sizeof *keys);
    }

strace观察grep 在您的命令上运行即可证实这一点：

open("testreg", O_RDONLY)               = 3
fstat(3, {st_mode=S_IFREG|0664, st_size=124, ...}) = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fd8912fe000
read(3, "ort.*hros\nove.*ridentify\nmis.*ti"..., 4096) = 124

回溯正则表达式实现（允许反向引用）不会在 O(n) 时间内运行，而是在 O(2^m) 时间内运行，这可能会导致灾难性的运行时间。

您的假设grep是简单地依次循环每个正则表达式，将每个正则表达式编译成 DFA，然后执行它，这是完全合理的。然而，grep作者似乎假设通过同时运行所有正则表达式，他们在某些情况下可能可以更有效地做到这一点。结果是，通过将正则表达式添加到文件中，您将陷入 O(2^m) 运行时间，从而导致运行时间呈指数增长。

事实证明，简单地循环每个正则表达式一次执行一个，强制 grep 线性运行可能会更有效。在我的笔记本电脑上，运行 grep 版本 2.20，我仅使用您提供的文件中的最后 29 个正则表达式得到以下结果：

[Downloads]$ wc -l patterns.txt 
29 patterns.txt

[Downloads]$ time grep -c -f ~/Downloads/patterns.txt /usr/share/dict/linux.words 
117

real    0m3.092s
user    0m3.027s
sys     0m0.047s

[csd@alcazar Downloads]$ time for regex in `cat ~/Downloads/patterns.txt`; do grep -c $regex /usr/share/dict/linux.words > /dev/null; done
real    0m0.474s
user    0m0.312s
sys     0m0.158s