需要比“wc -l”更快的东西

Question

对于像 1GBwc -l这样的非常大的文件来说，速度很慢。我们是否有更快的方法来计算特定文件的换行数？

Answer 1

您可以尝试用 C 编写：

#include <unistd.h>
#include <stdio.h>
#include <string.h>
int main(){
  char buf[BUFSIZ];
  int nread;
  size_t nfound=0;
  while((nread=read(0, buf, BUFSIZ))>0){
    char const* p;
    for(p=buf; p=memchr(p,'\n',nread-(p-buf)); nfound++,p++) {;}
  }
  if(nread<0) { perror("Error"); return 1; }
  printf("%lu\n", nfound);
  return 0;
}

保存在 eg, wcl.c, 编译 eg, withgcc wcl.c -O2 -o wcl和 run with

<yourFile ./wcl

这会在大约370 毫秒（重复运行）内发现换行符散布在我系统上的 1GB 文件中。（增加缓冲区大小会略微增加时间，这是意料之中的——BUFSIZ 应该接近最优）。这是对〜很媲美380ms我从得到wc -l。

Mmaping 给了我一个更好的时间大约280ms，但它当然有仅限于真实文件的限制（没有 FIFOS，没有终端输入等）：

<yourFile ./wcl

我创建了我的测试文件：

 $ dd if=/dev/zero of=file bs=1M count=1042 

并添加了一些测试换行符：

 $ echo >> 1GB 

和一个十六进制编辑器。

Answer 2

您可以通过减少对read. 有很多调用BUFSIZ从 1Gb 文件中读取块。这样做的常用方法是增加缓冲区大小：

• 只是为了好玩，尝试将缓冲区大小增加 10 倍。或 100。在我的 Debian 7 上，BUFSIZ是 8192。使用原始程序，这是 12 万次读取操作。您可能可以负担得起 1Mb 的输入缓冲区，以将其减少 100 倍。
• 对于更优化的方法，应用程序可以分配一个与文件一样大的缓冲区，需要一次读取操作。这对于“小”文件来说已经足够好了（尽管有些读者在他们的机器上有超过 1Gb 的容量）。
• 最后，您可以尝试使用内存映射 I/O，它处理分配。

在对各种方法进行基准测试时，您可能要记住，某些系统（例如 Linux）使用机器的大部分未使用内存作为磁盘缓存。不久前（大约 20 年前，在卑鄙的 FAQ 中提到过），我对一个（不是很好的）分页算法出乎意料的好结果感到困惑，我开发了该算法来处理文本编辑器中的低内存情况。有人向我解释说，它运行得很快，因为该程序是从用于读取文件的内存缓冲区中工作的，并且只有重新读取或写入文件时，速度才会有所不同。

这同样适用于mmap（在另一个情况下仍然在我的待办事项列表中以合并到常见问题解答中，开发人员在磁盘缓存是改进的实际原因的情况下报告了非常好的结果）。开发基准测试需要时间和精力来分析性能好（或差）的原因。

进一步阅读：

• 使用更大的缓冲区有用吗？
• mmap() 与读取块
• mmap、munmap - 将文件或设备映射或取消映射到内存中（显示示例程序）
• 13.7 内存映射 I/O（GNU C 库）
• 如何清除 Linux 上的磁盘 I/O 缓存
• 如何清空 Linux 系统上的缓冲区和缓存？