主页 / unix / 问题 / 782407
Accepted
αғsнιη
Asked: 2024-08-23 11:34:41 +0800 CST

grep 命令因内存不足错误而失败

  • 772

我在运行

grep -Fxvf file1 file2

文件 1 大小：~200MB
文件 2 大小：~300MB
每个文件中的记录数：~300K
平均记录长度：~1K（仅 ASCII 字符）
两个文件之间的差异为 ~18K 条记录

可用内存：~16GB

我尝试了几个不同的grep版本，并在 VM、WSL 和物理服务器上进行了尝试，但得到了相同的结果。

请注意，我运行了相同的命令，但只使用了两个文件中的几行来识别它不会由于文件中有一些特殊字符而陷入无限循环，并且它是成功的。

这是正常的吗？

我正在尝试输出file2不存在的记录file1。

我已经在awk相同的环境中解决了我的需求，并在不到 10 秒的时间内获得了输出，但我想知道为什么会grep出现 OOM 的结果。

当我需要查询相同要求时，我几乎总是使用相同的命令，甚至我比较了两个非常大的文件，比如两个大小约为 2GB 的文件，每个文件约有 90M 条记录，并且记录最多包含约 20 个 ASCII 字符，在同一个框中没有任何问题。

我grep在 SLES12 上使用了 GNU 2.7、2.16，grep在 WSL 中的 Ubnutu 22.04 上使用了 GNU 3.7。

linux

2 个回答

  1. Best Answer

    如果你看一下GNU 实现的代码，grep以了解当被调用时会发生什么grep -Fxvf file1 file2，你会看到：

    1. file1读取内存中的全部内容
    2. 使用哈希表对该列表中的行进行重复数据删除（每行需要几个额外的字节内存，尽管在重复数据删除后该内存会被回收）¹。
    3. 然后，它使用Aho-Corasick 算法（与中的Aho 相同，与 70 年代原始版本中使用的算法相同）编译模式树，以便在寻找主题中的匹配行时尽量减少比较次数。aawkfgrep

    3 即使-F与 for 结合使用时也会发生-x这种情况，对于要匹配的多个字符串，使用哈希表可能会更有效率（具有讽刺意味的是，在第 2 阶段刚刚构建了一个哈希表）。

    最后第 3 部分很可能是最耗 CPU 和需要最多内存的。

    跑步：

    base64 -w 1000 /dev/urandom | head -n 10000 |
  \time -f %MKiB grep -Fvxf - /dev/null

    并且改变 10000，我看到它为模式文件的每个字节分配大约 96 字节的 RAM，因此对于 200MiB 文件来说将是 18GiB。

    在中观察它gdb，我们发现它struct trie至少为模式文件中的大多数（如果不是全部）字节分配了一个（64 字节）。

    grep通常用于在任意大小的输入中搜索字符串或正则表达式或字符串或正则表达式的短列表，它不是用于比较文件。

    为此，使用哈希表，就像在awk或perl中使用时所做的那样：

    awk '!file1_processed {hash[$0]; next}
     ! ($0 in hash)' file1 file1_processed=1 file2

    是正确的做法。只需要将 的全部内容存储file1在内存中（加上哈希表开销）。 中的匹配file2只是哈希表查找。

    对于已经排序的文件，使用comm会更有效。

    现在看看grep可以在 GNU/Linux 上找到或构建的其他实现：

    $ () { \time -f '%MKiB %E' grep -Fvxf $1 $1; } =(base64 -w 1000 /dev/urandom | head -n 20000)
Command exited with non-zero status 1
1918504KiB 0:04.01

    $ () { \time -f '%MKiB %E' busybox grep -Fvxf $1 $1; } =(base64 -w 1000 /dev/urandom | head -n 20000)
Command exited with non-zero status 1
24644KiB 0:15.55

    $ () { \time -f '%MKiB %E' toybox grep -Fvxf $1 $1; } =(base64 -w 1000 /dev/urandom | head -n 20000)
Command exited with non-zero status 1
22892KiB 0:00.11

    $ () { \time -f '%MKiB %E' ast-open-grep -Fvxf $1 $1; } =(base64 -w 1000 /dev/urandom | head -n 20000)
Command exited with non-zero status 1
48416KiB 0:21.90

    $ () { \time -f '%MKiB %E' heirloom/grep/grep_su3 -Fvxf $1 $1; } =(base64 -w 1000 /dev/urandom | head -n 20000)
Command exited with non-zero status 1
805476KiB 0:13.58

    GNU 和 heirloom toolchest（来自 OpenSolaris 可能基于原版fgrep）使用大量内存但“相对”速度较快。busybox 和 ast-open 使用较少内存但速度较慢，可能使用了更愚蠢的算法。

    Toybox' 非常快（尽管仍然比该方法慢得多awk），并且不占用太多内存（略大于 的大小file1）。它使用一种粗略的哈希表，其中“哈希”是字符串的第一个字节，因此虽然它进行简单的比较，但它只需要与第一个字节相同的字符串列表进行比较，对于像我测试中的 base64 编码随机字符串，这意味着要执行的比较次数除以 64。

    如果我们不使用 20000 行 1000 字节长的随机 base64 文本，而是使用seq -f %01000g 20000只有行的最后一个字节发生变化的输出，则时间会变得非常不同，其中 GNU/heirloom 是迄今为止最快的（不到一秒，显示了使用 Aho-Corasick 算法的好处），busybox/ast-open/toybox 似乎需要很长时间（我在 5 分钟后就放弃等待了），toybox' 落后于 ast-open's（不是 busybox，它是迄今为止最慢的²），因为第一个字节总是一样的，而且所有的比较都需要比较前 990+ 个字节，所以我们可以预期它的速度会和随机数据一样慢大约 64*990。

    ¹ 它还在另一个表中记录了读取模式的位置，尽管它仅在报告正则表达式错误时使用，因此对于固定字符串来说毫无意义。

    ² 可能是因为它用于strstr()str在ing 中搜索ingstr而strcmp()不是使用-x。

    • 17

  2. 正如评论中提到的并回答你的问题：它失败是因为 grep 正在读取 file1 的全部内容并使用该文件的每一行作为静态文本模式在 file2 中搜索/匹配

    虽然这在原则上可行，但当您想要获取两个文件中相同的行时，它效率非常低。

    根据建议，使用：comm

    comm -23 <(sort file2) <(sort file1)

    这将比较排序后的内容和 file2 所特有的输出行（-2 抑制 file1 所特有的行，-3 抑制两个文件所共有的行）。

    （或者在将两个文件传递给通信命令之前对它们进行排序）

    • -1

相关问题