从标准输入 C++ 读取数百万个整数的最快方法？

Question

我正在做一个排序项目，我已经到了一个主要瓶颈是读取数据的地步。我的程序需要大约 20 秒才能使用从 stdin 读取的 100,000,000 个整数进行排序cin，std::ios::sync_with_stdio(false);但事实证明，其中 10 秒正在读取数据进行排序。我们确实知道我们将读取多少个整数（计数位于我们需要排序的文件的顶部）。

我怎样才能更快？我知道这是可能的，因为上一学期的学生能够在 3 秒多一点的时间内完成计数排序（这基本上是纯粹的阅读时间）。

该程序只是以换行符分隔的整数输入文件的内容，例如 $ ./program < numstosort.txt

谢谢

这是相关的代码：

    std::ios::sync_with_stdio(false);
    int max;
    cin >> max;
    short num;
    short* a = new short[max];
    int n = 0;
    while(cin >> num) { 
        a[n] = num;
        n++;
    }

Answer 1

假设 Linux/POSIX 在商用硬件上运行，这将尽可能快地将数据存入内存。请注意，由于您显然不允许使用编译器优化，因此 C++ IO 不会是读取数据的最快方法。正如其他人所指出的，如果不进行优化，C++ 代码的运行速度将无法达到应有的速度。

鉴于重定向的文件已作为stdin/打开STDIN_FILENO，请使用低级系统调用/C 风格 IO。这不需要优化，因为它会尽可能快地运行：

struct stat sb;
int rc = ::fstat( STDIN_FILENO, &sb );

// use C-style calloc() to get memory that's been
// set to zero as calloc() is often optimized to be
// faster than a new followed by a memset().
char *data = (char *)::calloc( 1, sb.st_size + 1 );
size_t totalRead = 0UL;
while ( totalRead  < sb.st_size )
{
    ssize_t bytesRead = ::read( STDIN_FILENO,
        data + totalRead, sb.st_size - totalRead );
    if ( bytesRead <= 0 )
    {
        break;
    }
    totalRead += bytesRead;
}

// data is now in memory - start processing it

该代码会将您的数据作为一个长 C 样式字符串读入内存。缺乏编译器优化并不重要，因为它几乎都是裸机系统调用。

使用fstat()获取文件大小可以一次分配所有需要的内存 - 不需要realloc()或复制数据。

您需要添加一些错误检查，并且更强大的代码版本将检查以确保返回的数据fstat()实际上是具有实际大小的常规文件，而不是“无用的 cat”，例如cat filename | YourProgram，因为在这种情况下，fstat()调用将不会返回有用的文件大小。您需要在调用后检查sb.st_mode该字段以查看流的实际内容：struct statstdin

::fstat( STDIN_FILENO, &sb );
...
if ( S_ISREG( sb.st_mode ) )
{
    // regular file...
}

（对于真正的高性能系统，确保将数据读入的内存页实际上映射到进程地址空间中非常重要。如果数据到达的速度快于内核内存管理系统创建的速度，性能可能会真正停滞数据转储到的页面的虚拟到物理映射。）

为了尽可能快地处理大文件，您需要采用多线程，即一个线程读取数据并向一个或多个数据处理线程提供数据，以便您可以在读完数据之前开始处理数据。

编辑：解析数据。

同样，阻止编译器优化可能会使 C++ 操作的开销比 C 样式处理慢。基于这个假设，简单的东西可能会运行得更快。

假设数据位于按上述方式读取的 C 样式字符串中，这在未优化的二进制文件中可能会运行得更快：

char *next;
long count = ::strtol( data, &next, 0 );
long *values = new long[ count ];

for ( long ii = 0; ii < count; ii++ )
{
    values[ ii ] = ::strtol( next, &next, 0 );
}

那也是非常脆弱的。它依赖于strtol()跳过前导空格，这意味着如果数值之间有除空格以外的任何内容，它将失败。它还依赖于值的初始计数是否正确。再说一次 - 如果这不是真的，那么代码将会失败。而且因为它可以替换检查错误之前的值next，所以如果它因为错误数据而偏离轨道，它将无可救药地丢失。

但它应该在不允许编译器优化的情况下尽可能快。

这就是不允许编译器优化的疯狂之处。您可以编写简单、健壮的 C++ 代码来完成所有处理，利用良好的优化编译器，并且可能几乎与我发布的代码一样快地运行 - 它没有错误检查，并且如果喂入，将以意想不到的和未定义的方式严重失败意外的数据。