c++ - 为什么并行读取大文本文件不好？

Question

我有一个大的txt文件，其中包含约3000万行，每行由行分隔符\n分隔。我想将所有行读取到无序列表（例如std::list<std::string>）。

std::list<std::string> list;
std::ifstream file(path);
while(file.good())
{
    std::string tmp;
    std::getline(file, tmp);
    list.emplace_back(tmp);
}
process_data(list);

当前的实现速度非常慢，因此我正在学习如何按块读取数据。

但是在看到 this comment之后：


  在HDD上并行化将使情况变得更糟，其影响取决于HDD上文件的分布。在SSD上，它可能会（！）有所改善。


并行读取文件是否不好？如何在不使用任何库的情况下尽可能快地将文件的所有行读取到无序容器（例如 std::list，普通数组等）的算法，并且代码必须是跨平台的？

Answer 1

并行读取文件是否不好？读取所有内容的算法是什么
  文件到无序容器的行（例如std :: list，正常
  数组...）尽可能快地进行操作，而无需使用任何库，并且
  代码必须跨平台？


我想我将尝试回答这一问题，以免垃圾评论。在多种情况下，我基本上使用多线程加速了文本文件的解析。但是，此处的关键字是解析，而不是磁盘I / O（尽管几乎所有读取的文本文件都涉及某种程度的解析）。现在首先要注意的是：



VTune在这里告诉我，我的主要热点正在解析中（很抱歉，此图像是数年前拍摄的，我没有展开调用图以显示obj_load内部大部分时间的内容，但它是sscanf ）。这个分析会议实际上使我感到非常惊讶。尽管进行剖析已有数十年，直到我的直觉不太准确（不够准确，无法进行剖析，请注意，甚至不是亲近，但我已经将我的直观蜘蛛感觉调整到了剖析会话的程度即使没有明显的算法效率低下，通常也不会令我感到惊讶-尽管由于我不太擅长汇编，我可能仍然不知道它们为什么存在。

但是这次我真的很后退，因此感到震惊，因此这个示例一直是我用来向即使是最怀疑的同事展示的示例，这些同事不想使用探查器来显示为什么分析如此重要。他们中的一些人实际上擅长猜测热点的位置，而有些人尽管从未使用过，但实际上正在创建性能出色的解决方案，但是它们都不擅长猜测什么不是热点，而且它们都无法绘制基于他们的预感的调用图。因此，我一直喜欢使用此示例来尝试转换怀疑论者，并让他们花一天时间尝试VTune（而且我们从英特尔那里获得了大量免费许可证，他们与我们合作极大地浪费了我们的团队，我以为是个悲剧，因为VTune是一款非常昂贵的软件）。

这次我被带回的原因并不是因为我对sscanf热点感到惊讶。毫无疑问，史诗文本文件的非平凡解析通常会因字符串解析而成为瓶颈。我可能已经猜到了。从未接触过分析器的同事可能已经猜到了。我无法猜测的是它有多大的瓶颈。考虑到我正在加载数百万个多边形和顶点，纹理坐标，法线，创建边缘并查找邻接数据，使用索引FOR压缩，将材料从MTL文件关联到多边形，反向工程对象法线存储在OBJ中的事实，我认为文件并合并它们以形成边缘折痕，等等。我至少还将在网格系统中分配大量的时间（我猜想在网格引擎中所花费的时间为25-33％）。

事实证明，网格系统几乎没有让我感到最惊喜的时间，而我的直觉完全是关于它的。到目前为止，解析是超级瓶颈（不是磁盘I / O，不是网格引擎）。

因此，当我将这种优化应用于多线程分析时，它起到了很大的作用。我什至最初以一个非常适度的多线程实现开始，该实现几乎不执行任何解析，只是扫描字符缓冲区中每个线程的行尾以最终在加载线程中进行解析，而这已经有了相当大的帮助（减少了16秒到大约14 IIRC，我最终将它降低到大约8秒，这是在只有两个内核和超线程的i3上。因此，无论如何，通过在单个线程中从文本文件读取的字符缓冲区的多线程解析，您可能可以使事情变得更快。我不会使用线程来使磁盘I / O更快。

我正在将文件中的字符从二进制文件读取到单个线程中的大char缓冲区中，然后使用并行循环，让线程找出该缓冲区中行的整数范围。

// Stores all the characters read in from the file in big chunks.
// This is shared for read-only access across threads.
vector<char> buffer;

// Local to a thread:
// Stores the starting position of each line.
vector<size_t> line_start;
// Stores the assigned buffer range for the thread:
size_t buffer_start, buffer_end;

基本上是这样的：



LINE1和LINE2被视为属于线程1，而LINE3被视为属于线程2。由于LINE6没有EOL，因此不被视为属于任何线程。取而代之的是，LINE6的字符将与从文件读取的下一个大块缓冲区合并。

每个线程首先查看其分配的字符缓冲区范围内的第一个字符。然后它向后工作，直到找到EOL或到达缓冲区的开头。之后，它将继续工作并解析每一行，查找EOL并执行我们想要执行的其他任何操作，直到到达指定的字符缓冲区范围的末尾。最后一个“不完整的行”不是由线程处理的，而是由下一个线程处理的（或者，如果该线程是最后一个线程，则在第一个线程读取的下一个大块缓冲区中对其进行处理）。该图太小了（无法容纳太多），但是在线程以并行循环解析它们之前，我从加载线程的文件中读取了大块（兆字节）的字符缓冲区，然后每个线程可能会从中解析出数千行其指定的缓冲区范围。

std::list<std::string> list;
std::ifstream file(path);

while(file.good())
{
    std::string tmp;
    std::getline(file, tmp);
    list.emplace_back(tmp);
}
process_data(list);

有点呼应Veedrac的评论，如果您想真正快速载入大量的行，则将行存储在 std::list<std::string>中不是一个好主意。实际上，与多线程相比，解决该问题的优先级更高。我将把它变成仅 std::vector<char> all_lines存储所有字符串，并且您可以使用 std::vector<size_t> line_start存储 nth行的起始行位置，可以像这样检索：

// note that 'line' will be EOL-terminated rather than null-terminated 
// if it points to the original buffer.
const char* line = all_lines.data() + line_start[n];

没有自定义分配器的 std::list的直接问题是每个节点的堆分配。最重要的是，我们浪费了内存，每行存储两个额外的指针。 std::string在这里是有问题的，因为避免堆分配的SBO优化会使小字符串占用过多内存（从而增加高速缓存未命中），或者最终仍然会为每个非小字符串调用堆分配。因此，您最终避免了所有这些问题，只是将所有内容都存储在一个巨大的char缓冲区中，例如 std::vector<char>中。 I / O流（包括字符串流和 getline之类的函数）的性能也很糟糕，只是让我感到非常失望，因为我的第一个OBJ加载器使用那些I / O流时，它的速度比第二个版本慢20倍以上我移植了所有这些I / O流运算符和函数，并使用 std::string来利用C函数和我自己在char缓冲区上操作的手动滚动内容。在性能至关重要的上下文中进行解析时，像 sscanf和 memchr这样的C函数以及普通的旧字符缓冲区往往比C ++的实现方法快得多，但是您至少仍可以使用 std::vector<char>存储巨大的缓冲区，例如，避免访问 malloc/free并在访问存储在其中的字符缓冲区时进行一些调试构建的健全性检查。