performance - 我可以期望 grep 处理 10 TB 文件多长时间？

Question

我有一个 10 TB 的文件，其中包含来自多本书的单词，我正在尝试为一些不常见的字符串(无正则表达式)进行 grep。例如:
grep "cappucino" filename
我正在尝试估计这需要多长时间。我并不是真的在寻找这是否是正确的方法。当我调用 grep 时，我想更多地了解幕后真正发生的事情。

如果我错了，请纠正我:

我使用读取速度大约为 200 MB/s 的机械硬盘，所以大约需要 1000 万/200 = 50000 秒 = 14 小时才能完成。这是一个准确的估计吗？

Answer 1

最简洁的答案是不。

更长的答案是:这取决于。

更长的答案是:grep 的性能取决于很多事情:

您是否正在运行固定字符串搜索(-F，fgrep) - grep 使用 Boyer-Moore 算法，该算法本身无法找到正则表达式，所以 grep 所做的(或至少曾经做过)是它首先找到一个正则表达式中的固定字符串，尝试在文本中使用 BM 找到它并进行正则表达式匹配(不确定当前实现是使用 NFA 还是 DFA 实现，可能是混合)

您的模式有多长 - BM 对于更长的模式运行速度更快

您将拥有多少匹配项 - 匹配项越少，速度就越快

你的 CPU 和内存是多少 - 硬盘只会在阅读期间帮助你，而不是在计算时间

您在 grep 中使用了哪些其他选项

14 小时甚至可能不是您的下限，因为 Boyer-Moore 足够聪明，可以计算可能发生下一个可能匹配的偏移量，因此它不需要读入整个文件。这确实取决于实现和 只是我的猜测 .在以更长的模式重新运行以下测试后，我能够降低到 0.23 秒，而且我认为我的磁盘没有那么快。 但是可能会涉及一些缓存。

例如，我在 500MB/s SSD 上运行(至少制造商是这么说的)并且用非常短的模式(几个字符)grepp 一个 200MB 的文件给了我:

与 808320命中

real    0m1.734s
user    0m1.334s
sys 0m0.120s

与 0命中:

real    0m0.059s
user    0m0.046s
sys 0m0.016s

@Edit:简而言之，请阅读 Boyer-Moore :-)

@Edit2:要检查 grep 是如何工作的，您应该检查源代码，我在上面描述了一个非常通用的工作流程。