从stdin C++读取数百万整数的最快方法？

Question

我正在进行一个排序项目，我已经到了主要瓶颈正在读取数据的地步。我的程序花费了大约20秒的时间来对使用cin和std::ios::sync_with_stdio(false);的标准输入读入的100,000,000个整数进行排序，但结果显示，其中有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-style 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 = ::calloc(1, sb.st_size + 1); 
size_t totalRead = 0UL; 
while (totalRead < st.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 filename | YourProgram，因为在这种情况下，fstat()调用不会返回有用的文件大小。你需要检查struct stat的sb.st_mode领域的呼叫后，看看有什么stdin流真的是：

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

（而对于真正的高性能系统，它可以是重要的，以确保内存页如果数据到达的速度比内核的内存管理系统能够创建虚拟到物理的映射，那么数据将被转储到您的进程地址空间中。实际上，性能可能会停滞。）

要尽可能快地处理大文件，您希望使用多线程，一个线程读取数据并提供一个或多个数据处理g线程，以便在读完之前开始处理数据。

编辑：解析数据。

同样，防止编译器优化可能会使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++代码来执行所有的处理，使用优化的编译器，并且运行速度几乎与我发布的代码一样快 - 它没有错误检查，并且在未预料到的和未定义的方式下会以惊人的速度失败意外的数据。

Answer 2

你可以把它更快，如果你使用SolidState硬盘。如果你想问一些关于代码性能的问题，你需要先发布你如何做事。

Answer 3

您可以通过将数据读入缓冲区，然后将缓冲区中的文本转换为内部表示来加速程序。

背后的想法是，所有流设备都喜欢保持流式传输。开始和停止流浪费时间。块读取通过一次事务传输大量数据。

虽然cin缓冲，通过使用cin.read和缓冲区，你可以做出比cin使用缓冲区大了很多。

如果数据具有固定宽度的字段，则有机会加速输入和转换过程。

编辑1：实施例

const unsigned int BUFFER_SIZE = 65536; 
char    text_buffer[BUFFER_SIZE]; 
//... 
cin.read(text_buffer, BUFFER_SIZE); 
//... 
int value1; 
int arguments_scanned = snscanf(&text_buffer, REMAINING_BUFFER_SIZE, 
           "%d", &value1); 

棘手的部分是处理其中一个数字的文本在缓冲器的端部被切断的情况。

Answer 4

与没有注释行的测试相比，你可以运行这个小测试吗？

#include <iostream> 
#include <cstdlib> 

int main() 
{ 
    std::ios::sync_with_stdio(false); 

    char buffer[20] {0,}; 

    int t = 0; 

    while(std::cin.get(buffer, 20)) 
    { 
//  t = std::atoi(buffer); 
     std::cin.ignore(1); 
    } 

    return 0; 
} 

纯读取测试：

#include <iostream> 
#include <cstdlib> 

int main() 
{ 
    std::ios::sync_with_stdio(false); 

    char buffer[1024*1024]; 


    while(std::cin.read(buffer, 1024*1024)) 
    { 

    } 


    return 0; 
}