如何加速逐行读取ASCII文件的速度？（C++）

Question

这里有一段代码，在进行一些测试后发现它是一个相当大的瓶颈：

//-----------------------------------------------------------------------------
//  Construct dictionary hash set from dictionary file
//-----------------------------------------------------------------------------
void constructDictionary(unordered_set<string> &dict)
{
    ifstream wordListFile;
    wordListFile.open("dictionary.txt");

    std::string word;
    while( wordListFile >> word )
    {
        if( !word.empty() )
        {
            dict.insert(word);
        }
    }

    wordListFile.close();
}

我正在读取约200,000个单词，这需要大约240毫秒在我的机器上完成。在这里使用ifstream是否高效？有没有更好的方法？我正在阅读关于mmap()实现的内容，但我并不完全理解它们。输入文件只是带有*nix行终止符的文本字符串。

编辑：后续问题针对被建议的替代方案： 除了增加流缓冲区大小之外，任何替代方案是否意味着我需要编写一个解析器来检查每个字符的换行符？我有点喜欢流的简单语法，但如果为了速度而必须重写某些更详细的东西，我可以这样做。将整个文件读入内存是可行的选择，它只有约2mb大小。

编辑＃2：我发现我的速度减慢是由于集合插入，但对于那些仍然对逐行读取文件IO进行加速感兴趣的人，请阅读此处的答案并查看Matthieu M.关于此主题的延续。

- Jon

---

读取方面最大的收益是使用大缓冲区，这样您就不需要为每一行（或小缓冲区）遍历所有操作系统层，并且不要反复为此支付性能开销惩罚。虽然我不知道如何增加 ifstream 的读取缓冲区大小的 API，但这就是为什么这是一个注释而不是答案。但是我相信有一种方法可以调整缓冲区的大小（或分配自己的缓冲区，指定其大小）。 - TheBlastOne

当性能出现问题时，你应该做的第一件事是进行___分析___。看看你的代码花费了大部分时间的地方。我们都知道，它可能是在将值添加到字典中。虽然不太可能，但如果你需要性能，你真的需要知道。 - sbi

@sbi：这并不是不可能的。在一个高性能的统计应用程序中，我发现 Boost 版本的 unordered_map 比 Google 的 sparsehash 慢了一个数量级，而且比 GNU 的 std::map 快不了多少。 - Fred Foo

@sbi 和 @larsmans：你们说得对，看已接受的答案。 - Jon

Answer 1

我在我的系统上（linux-2.6.37，gcc-4.5.2，并使用-O3编译）进行了快速分析，发现I/O不是瓶颈。无论是使用fscanf读取到一个char数组，然后再加入dict.insert()，还是像您的代码中一样使用operator>>，它们花费的时间大致相同（读取240k个单词文件需要155-160毫秒）。

将gcc的std::unordered_set替换为std::vector<std::string>在您的代码中可将执行时间降至45毫秒（fscanf）至55毫秒（operator>>）。请尝试单独对I/O和设置插入进行分析。

- Cubbi

---

我正在使用unordered_set来加速代码中字典的查找。但是，确实存在瓶颈。之前我过早地宣称流是瓶颈... - Jon

Answer 2

通常情况下，通过增加缓冲区大小可以获得更好的性能。

在构建ifstream后，您可以使用以下方法设置其内部缓冲区：

char LocalBuffer[4096]; // buffer

std::ifstream wordListFile("dictionary.txt");

wordListFile.rdbuf()->pubsetbuf(LocalBuffer, 4096);

注意：rdbuf的结果如果ifstream的构造成功，则保证不为null。

根据可用内存，强烈建议尽可能扩大缓冲区，以限制与硬盘和系统调用的交互次数。

我使用自己的小型基准测试执行了一些简单的测量，您可以在下面找到代码（我对评论感兴趣）：

gcc 3.4.2 on SLES 10 (sp 3)
C : 9.52725e+06
C++: 1.11238e+07
difference: 1.59655e+06

这导致了惊人的17％的减速。

这考虑到：

• 自动内存管理（无缓冲区溢出）
• 自动资源管理（没有忘记关闭文件的风险）
• 处理locale

因此，我们可以说流是慢的...但请不要随意抛出代码片段并抱怨它很慢，优化是艰苦的工作。

---

相应的代码，其中benchmark是我自己的一个小实用程序，它使用gettimeofday测量重复执行（此处启动50次迭代）的时间。

#include <fstream>
#include <iostream>
#include <iomanip>

#include <cmath>
#include <cstdio>

#include "benchmark.h"

struct CRead
{
  CRead(char const* filename): _filename(filename) {}

  void operator()()
  {
    FILE* file = fopen(_filename, "r");

    int count = 0;
    while ( fscanf(file,"%s", _buffer) == 1 ) { ++count; }

    fclose(file);
  }

  char const* _filename;
  char _buffer[1024];
};

struct CppRead
{
  CppRead(char const* filename): _filename(filename), _buffer() {}

  enum { BufferSize = 16184 };

  void operator()()
  {
    std::ifstream file(_filename);
    file.rdbuf()->pubsetbuf(_buffer, BufferSize);

    int count = 0;
    std::string s;
    while ( file >> s ) { ++count; }
  }

  char const* _filename;
  char _buffer[BufferSize];
};


int main(int argc, char* argv[])
{
  size_t iterations = 1;
  if (argc > 1) { iterations = atoi(argv[1]); }

  char const* filename = "largefile.txt";

  CRead cread(filename);
  CppRead cppread(filename);

  double ctime = benchmark(cread, iterations);
  double cpptime = benchmark(cppread, iterations);

  std::cout << "C  : " << ctime << "\n"
               "C++: " << cpptime << "\n";

  return 0;
}

- Matthieu M.

---

因此，我们可以争论流是慢的...但请不要抛出你的随机代码并抱怨它很慢，优化是艰苦的工作。Matthieu的观点是，你必须经过艰苦的努力才能使C++版本表现得合理，并且令人惊讶的是，单行读取循环的比较最终表现如此截然不同。不过了解缓冲区也是好事。 - Bogatyr

@Matthieu--实际上我喜欢流，我通常不在我的工作中使用C i/o，但是我大量使用流。毫无疑问，流带来了很多好处。然而令人惊讶的是，“简单”情况下的性能代价。尽管如此，我仍然无法接近您17%的差异，不过我会逐字逐句地尝试您的代码。 - Bogatyr

强烈建议您增加缓冲区的大小，以限制与硬盘的交互。4096对应于大多数HDD扇区的大小。从技术上讲，HDD扇区的大小为512字节，只有操作系统倾向于将它们分组为4K块，以便更容易匹配一个虚拟内存页面。有可能整个轨道而不是仅仅一个扇区在操作系统级别上被乐观地缓存。在轨道的大小（先验未知）范围内，您所观察到的只是通过减少系统调用而实现的改进，而不是与磁盘的交互。因此，是的，您的建议是明智的，可以达到预期效果，但不够精确。 - PypeBros

使用您的代码，当执行一次遍历单个大文件时，我仍然发现C++比C慢2-3倍。 - Bogatyr

希望你的“基准测试”（重复50次等）在第一次运行时被丢弃，否则C版本可能没有OS文件缓存中的内容，而C++有。 - Jonathan Graehl

Answer 3

我的系统版本为 (3.2.0-52-generic, g++-4.7 (Ubuntu/Linaro 4.7.3-2ubuntu1~12.04) 4.7.3，如果没有指定则使用 -O2 编译，CPU：i3-2125)。

在我的测试用例中，我使用了一个包含 295068 个单词的字典（比你的多了 10 万个）：http://dl.dropboxusercontent.com/u/4076606/words.txt

从时间复杂度的角度来看：

• 最坏情况下，你的程序复杂度为：O(n*n)=O(n[读取数据]*n[插入到无序集合])
• 平均情况下，你的程序复杂度为：O(n)=O(n[读取数据]*1[插入到无序集合])

实用提示：

• 最简单的数据结构具有更少的时间开销。简单的数组比向量更快。字符数组比字符串更快。网上有很多相关信息。

我的测量结果：

注意：我没有刷新操作系统缓存和硬盘缓存。后者我无法控制，但前者可以通过以下方法进行控制：

sync; sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'

此外，我没有省略那些包含很多上下文切换等内容的测量。因此，有空间进行更好的测量。

我的代码（从文件读取和插入数据；搜索所有单词）：

14-16毫秒读取文件并将数据插入到2D字符数组（读取和插入）n次中

65-75毫秒用二分搜索搜索所有单词（搜索n次）：

总计=79-91毫秒

61-78毫秒从文件中读取和插入数据到无序集合字符数组（读取和插入）n次

7-9毫秒通过哈希n次搜索

总计=68-87毫秒

如果搜索次数大于插入次数，请选择哈希表（unordered_set），否则使用简单数组进行二分搜索。

您的原始代码（搜索和插入）：

编译时使用-O2：157-182毫秒

使用-O0编译（如果省略了-O标志，则默认为“-O”级别也是0）：223-248毫秒

因此，编译器选项也很重要，在这种情况下，它意味着66毫秒的速度提升。您没有指定任何一个。所以，我最好的猜测是您没有使用它。因此，我试图回答您的主要问题。

您可以使用当前代码做什么最简单但更好的事情？

1. [更好地使用高级API]使用“getline（wordListFile，word）”而不是“wordListFile>> word”。我认为“getline”比“>>”运算符更可读。

编译时使用-O2：142-170毫秒。与您的原始代码相比，速度提升了12-15毫秒。

使用-O0编译（如果省略了-O标志，则默认为“-O”级别也是0）：213-235毫秒。与您的原始代码相比，速度提升了10-13毫秒。

2. [更好地使用高级API]使用“dict.reserve（XXXXXX）;”避免重新哈希，@David Rodríguez-dribeas也提到了这一点。如果您的字典是静态的或者您可以猜测您的字典大小（例如通过文件大小除以平均单词长度）。首先运行没有“reserve”的程序，并输出bucket_count（cout<<“bucket_count =”<< dict.bucket_count()<<“\n”;），在我的情况下为299951。然后我添加了“dict.reserve（299951）;”。

编译使用-O2选项:与您的原始代码相比，速度提升了99-121-[137]毫秒。 ~ 33-43-[49]毫秒。

你可以做哪些更高级的优化来加速它？

为您特定的数据输入实现自己的哈希函数。使用char数组而不是STL字符串。在此之后，仅使用直接OS I / O编写代码。正如您所注意到的（从我的测量中也可以看出），数据结构是瓶颈。如果媒体非常慢，但CPU非常快，请压缩文件并在程序中解压缩。

---

我的代码并不完美，但仍然比上面任何东西都要好：http://pastebin.com/gQdkmqt8（哈希函数来自网络，也可以做得更好）

---

您能否提供更多关于您计划优化哪个系统（一个或一系列）的详细信息？

时间复杂度的信息应该是链接...但我在stackoverflow上是初学者，声望不够。

我的回答仍然与任何事情相关吗？请添加评论或投票，因为我看不到PM。

- KęstutisV

Answer 4

将整个文件一次性读入内存，然后对其进行操作可能会更快，因为它避免了反复返回磁盘以读取另一个数据块的情况。

0.25秒真的是个问题吗？如果您不打算加载更大的文件，那么是否有必要使其更快，即使这样会使其难以阅读？

- Jon Cage

---

提前读取整个文件并不总是可行的选择。使用纯C文件I/O逐行输入要比c++流快得多，至少在我上次测量时是这样。与直觉相反，但测量才是王道。 - Bogatyr

同意，但是原帖并没有提到任何需要担心的限制，比如内存。 - Jon Cage

这是一个典型的内存与速度之间的权衡。因此，一种选择是最小化I/O操作的数量，仅将其一次性读入字符串中，然后将该字符串转换为无序单词集合。 - Mephane

Answer 5

C++和C库以相同的速度从磁盘读取数据，并已经进行了缓冲以弥补磁盘I/O延迟。添加更多缓冲不会使它更快。

最大的区别在于C++流基于语言环境进行了大量操作。字符转换/标点等等。

因此，C库会更快。

替换失效链接

由于某些原因，链接的问题已被删除。因此，我将相关信息移至此处。链接的问题是关于C++中隐藏功能的。

---

虽然不是STL的一部分。
流库是标准C++库的一部分。

对于流：

语言环境。

很少有人真正费心去学习如何正确地设置和/或操作流的语言环境。

第二酷的事情是迭代器模板。
对于我来说，最具体的是流迭代器，它基本上将流转换为非常基本的容器，然后可以与标准算法结合使用。

例如：

• 您知道吗，语言环境会自动将十进制数中的“.”更改为任何其他字符。
• 您知道吗，语言环境会在每三个数字后添加“，”以使其易于阅读。
• 您知道吗，可以使用语言环境来在传递过程中操作文本（即在写入文件时从UTF-16转换为UTF-8）。

等等。

例如：

• 每三位添加逗号
• 使用空格作为分隔符
• 设置小数点分隔符
• 简单的输出过滤器
• 设置当前区域设置
• 计算发送到输出的字符数量
• 缩进每行
• UTF-16（流）-> UTF-16（内部）转换器（未经测试）

- Martin York

---

关于区域设置（locale）一词，它是否也在二进制模式下激活？在我的基准测试中，我没有看到二进制和非二进制之间的性能差异。 - Matthieu M.

@Matthieu M：好问题。我刚在DevStudio中逐步执行了代码，确实如此。二进制标识不会影响区域设置的使用。它唯一做的事情是改变行尾序列的处理方式（这不是区域设置的一部分）。 - Martin York

谢谢 :) 这与我的观察一致。你知道有没有办法“禁用”这个区域设置吗？区域设置的问题在于所有这些方面的操作等等...我可以看到注入新的区域设置的方法，但我无法看到完全删除它的任何方法，并且我不确定放置一个没有任何方面的区域设置是否会实际上显著提高性能。 - Matthieu M.

@Matthieu M：不，我不知道如何禁用它们。但是codecvt facet有一个单一的方法(always_noconv)，指示是否需要调用其他方法。我认为其他facet类型也有技巧，在什么都不做时限制虚拟调用的数量。 - Martin York

Answer 6

一个合适的IO库实现应该为您缓存数据，避免过多的磁盘访问和系统调用。我建议您使用系统调用级别的工具（例如，在Linux下使用strace）来检查您的IO实际发生了什么。

显然，如果dict.insert(xxx)不允许O(1)插入，它也可能会成为一个麻烦。

- PypeBros

---

'dict'是一个无序集合（哈希集合），因此插入时间应为O(1)。 - Jon

我会研究一下你的strace建议。谢谢。 - Jon

重点不是“适当”的实现会做什么，而是现有实现实际上做了什么。在C++流中逐行读取明显、可衡量地比在C I/O中进行相同操作慢。 - Bogatyr

@Jon：摊销O(1)并不意味着它不能更快。特别是，在创建unordered_set时添加大小提示可以避免中间内存分配（这很昂贵）和复制（从旧分配的集合到新集合）。虽然理论上有和没有提示插入都是O(1)操作，但在现实生活中，性能可能会受到影响。 - David Rodríguez - dribeas

Answer 7

信不信由你，标准库流在读取数据方面的性能远低于C库例程。如果您需要顶级IO读取性能，请勿使用c++流。我在算法竞赛网站上通过艰苦的方式发现了这一点——使用c++流读取stdin时，我的代码会超时，但使用普通的C FILE操作则可以在充足的时间内完成。

编辑：只需在一些示例数据上尝试这两个程序即可。我在Mac OS X 10.6.6上使用g++ i686-apple-darwin10-g++-4.2.1（GCC）4.2.1（Apple Inc. build 5664）运行了一个包含100万行“howdythere”的文件，scanf版本始终比cin版本快5倍：

#include <stdio.h>

int main()
{
    int count = 0;
    char buf[1024];
    while ( scanf("%s", buf) == 1 )
        ++ count;

    printf( "%d lines\n", count );
}

并且

#include <iostream>

int main()
{
    char buf[1024];
    int count = 0;

    while ( ! std::cin.eof() )
    {
        std::cin.getline( buf, 1023 );
        if ( ! std::cin.eof() )
            ++count;
    }
   std::cout << count << " lines" << std::endl;
}

编辑：将数据文件更改为“howdythere”以消除两种情况之间的差异。计时结果没有改变。

编辑：我认为这个答案受到了很多关注（和负评），这表明现实与普遍观点相反。人们只是不相信在C和流中读取输入这个简单的情况可以如此不同。在你给出负评之前：去测量一下吧。重点不是设置大量状态（通常没有人设置），而是人们最频繁编写的代码。性能上的意见毫无意义：测量、测量、再测量才是最重要的。

- Bogatyr

---

这并不是所有情况下都成立的。例如，在我参加的一个算法竞赛中，我需要读入大量的整数，而C++流实际上比C I/O更快。这在很大程度上取决于编译器、系统和I/O类型。 - flight

你在问谁？如果你在问我，那么我已经回答过了。（编译器，系统和输入/输出类型的差异） - flight

@Bogatyr：你试过增加流缓存吗？因为与C版本不同，你的C++版本根本不能保证每次从磁盘中读取1023字节，尽管你只看到这样大小的块。 - Matthieu M.

C++的iostream在本地处理方面做了很多工作，而C I/O库没有这么做。 - Martin York

@Bogatyr，@Space_C0wb0y：我测量了一个**17%**的减速（请参见答案中的代码），所以，正如我所说，这更多是缓冲的问题。当正确调整时，它并不那么慢，尽管我当然希望它更快 :) - Matthieu M.

Answer 8

很遗憾，在使用fstream时，你无法做太多来提高性能。

通过读取较大的文件块然后解析单个单词，您可能能够获得非常轻微的速度提升，但这取决于您的fstream实现如何进行缓冲。

唯一可以获得巨大改善的方法是使用操作系统的I/O函数。例如，在Windows上，使用FILE_FLAG_SEQUENTIAL_SCAN标志打开文件可以加快读取速度，还可以使用异步读取从磁盘获取数据并并行解析。

- Collin Dauphinee

Answer 9

如果你真的想要快速，就放弃使用 istream 和 string，创建一个围绕着 const char* & size 的简单类 Read_Only_Text，然后将文件映射到内存中，并插入到 unordered_set<Read_Only_Text> 中，同时引用嵌入字符串。这意味着即使您的唯一键数量可能少得多，您也需要保留 2mb 文件，但是填充速度非常快。我知道这很麻烦，但我已经为各种任务做了几次，结果非常好。

- Tony Delroy