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

Question

我正在处理一个排序项目，我已经到了主要瓶颈是读取数据的地步。使用 cin 对从 stdin 读入的 100,000,000 个整数进行排序需要我的程序大约 20 秒。和 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() 调用不会返回有用的文件大小。您需要在调用后检查 struct stat 的 sb.st_mode 字段，以查看 stdin 流的真正含义:

::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() skipping over leading whitespace ，这意味着如果数值之间除了空格之外还有其他任何内容，它将失败。它还依赖于值的初始计数是否正确。再次 - 如果那不是真的，该代码将失败。因为它可以在检查错误之前替换 next 的值，所以如果它因为错误的数据而偏离轨道，它将无可救药地丢失。

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

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