二进制文件中求最长零字节序列长度的优化计算

Question

我需要尽可能快地计算二进制文件中最长的零字节序列的长度。下面我有一个C++的基本实现：

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>

int get_max_zero_streak(std::string fname)
{
  std::ifstream myfile(fname, std::ios_base::binary);
  int length = 0;
  int streak = 0;
  while(myfile) 
  {
    unsigned char x = myfile.get(); // unsigned 8 bit integer
    if(x == 0)
    {
      streak += 1;
    }
    else
    {
      length = std::max(length, streak);
      streak = 0;
    }
  }
  return length;
}

int main() 
{
  std::cout << get_max_zero_streak("000_c.aep") << std::endl;
  std::cout << get_max_zero_streak("000_g1.aep") << std::endl;
  std::cout << get_max_zero_streak("000_g2.aep") << std::endl;
  std::cout << get_max_zero_streak("001_c.aep") << std::endl;
  std::cout << get_max_zero_streak("001_g1.aep") << std::endl;
  std::cout << get_max_zero_streak("001_g2.aep") << std::endl;
  std::cout << get_max_zero_streak("002_c.aep") << std::endl;
  std::cout << get_max_zero_streak("002_g1.aep") << std::endl;
  std::cout << get_max_zero_streak("002_g2.aep") << std::endl;
  return 0;
}

对于较小的文件来说，这是可以的，但是对于较大的文件(例如50 GB+)来说，这是非常慢的。是否有一种更有效的方式来写这个，或者并行化是我唯一的希望？我正在从一个NVMe SSD读取文件，所以我不认为驱动器读取速度是限制。

Answer 1

这段代码的主要瓶颈是字节/字节IO读取，这会阻止循环满足大多数SSD(很大幅度)。实际上，每次迭代都调用myfile.get()是缓慢的，编译器在实践中并不对其进行优化。解决这个问题的解决方案是逐块读取数据，并在当前块上使用内部循环操作。块必须足够大以摊销IO调用的成本，并且足够小，以便从缓存中读取数据(类似于32 the ~256 the的缓冲区应该足够好)。

另一个瓶颈是计算循环本身：条件在现代处理器上是缓慢的，除非它们能够被预测为(例如。如果大多数值为0或1，且两者之间没有太多不可预测的开关)。使用无分支代码会显着地提高循环的速度，但是循环携带的依赖项才是主要问题。Clang能够生成一个无分支的装配循环，但是GCC没有成功地完成这一优化。尽管如此，循环仍然是串行的和标量的，因此处理器不能比自己的频率更快地计算字节。实际上，由于指令延迟和依赖关系，它要少得多。解决这个问题的一个有效解决方案是同时在多个字节上操作。一种解决方案是使用x86 SIMD指令(x86-特定和快速)。另一种解决方案是加载8个字节，并使用位调整对大整数进行操作，但是要有效地执行有点棘手，我怀疑它最终会更快。

对于SIMD解决方案，其思想是按16字节块加载数据，同时将16字节与0进行比较，并针对比较的结果将整数设置为1或0。然后，您可以非常快地检查尾随0位的数量(使用generic code或使用__builtin_ctz之类的编译器内置程序生成快速x86指令)。最后，您需要将结果与发现的尾随0的数目相转换。如果有许多0-1开关，这个解决方案不是很快，但是当有许多0(或1)的大块时，这个解决方案是非常快的。请注意，使用AVX-2，甚至可以在一行中计算32个字节。用于操作的SIMD指令是_mm_load_si128、_mm_cmpeq_epi8和_mm_movemask_epi8。

注意，当有大量开关时，可以使用查找表 (LUT)来加快速度。但是，这并不简单，因为需要将两个连续掩码中的0相加在一起。LUT可以包括找到的先前挂起的0的数量，这样会更快。这样做的目的是在8位掩码(代表8字节)中，根据先前找到的0字节数，找到最大的连续0位数。

另一个可能的优化是并行计算块。这样做的目的是将块减少到3个值:挂起的0字节数、前导0字节数和两者之间的最大连续字节数。注意，应该考虑所有字节都为0的特殊情况。这些值必须是临时存储的，您可以在文件的末尾执行最后一次传递，即合并所有块的结果。如果您在任务中使用OpenMP (每个块一个)，则可以很简单地实现此操作。