C和C++几乎相同的代码执行时间差异很大（x9）。

Question

我试图解决来自www.spoj.com的这个练习：FCTRL - 阶乘

如果你好奇的话，你不需要真正阅读它，只需完成它 :)

首先，我用C++实现了它（这是我的解决方案）：

#include <iostream>
using namespace std;

int main() {
    unsigned int num_of_inputs;
    unsigned int fact_num;
    unsigned int num_of_trailing_zeros;

    std::ios_base::sync_with_stdio(false); // turn off synchronization with the C library’s stdio buffers (from https://dev59.com/eH3aa4cB1Zd3GeqPbEuh#22225421)

    cin >> num_of_inputs;

    while (num_of_inputs--)
    {
        cin >> fact_num;

        num_of_trailing_zeros = 0;

        for (unsigned int fives = 5; fives <= fact_num; fives *= 5)
            num_of_trailing_zeros += fact_num/fives;

        cout << num_of_trailing_zeros << "\n";
    }

    return 0;
}

我将其上传作为解决方案，适用于g++ 5.1

结果是：时间0.18内存3.3M

但是后来我看到一些评论声称他们的执行时间少于0.1。由于我无法想出更快的算法，我尝试在C中实现相同的代码：

#include <stdio.h>

int main() {
    unsigned int num_of_inputs;
    unsigned int fact_num;
    unsigned int num_of_trailing_zeros;

    scanf("%d", &num_of_inputs);

    while (num_of_inputs--)
    {
        scanf("%d", &fact_num);

        num_of_trailing_zeros = 0;

        for (unsigned int fives = 5; fives <= fact_num; fives *= 5)
            num_of_trailing_zeros += fact_num/fives;

        printf("%d", num_of_trailing_zeros);
        printf("%s","\n");
    }

    return 0;
}

我将其上传为解决方案，适用于gcc 5.1

这次的结果是：时间0.02 内存2.1M

现在代码几乎相同，我按照这里建议的方式添加了std::ios_base::sync_with_stdio(false);到C ++代码中，以关闭与C库的stdio缓冲区的同步。 我还将printf（“％d \ n”，num_of_trailing_zeros）; 分成， printf（“％d”，num_of_trailing_zeros）; printf（“％s”，“\n”）; 来补偿cout << num_of_trailing_zeros<< "\n"; 中对operator<<的双重调用。

但是我仍然看到C与C ++代码相比具有x9更好的性能和更低的内存使用率。

为什么会这样呢？

编辑

我在C代码中将unsigned long修正为unsigned int。它应该是unsigned int，上面显示的结果与新版本（unsigned int）相关。

- Alex Lop.

---

C++流设计上故意慢。因为“慢而稳定”才是赢得比赛的关键 :P（在我被喷之前） - Mysticial

速度缓慢并不是由于安全性或适应性。它被设计过度，使用了大量的流标志。 - Karoly Horvath

使用std::ostringstream来累积输出并在结尾时一次性将其发送到std::cout可以将时间缩短到0.02。在循环中使用std::cout会在他们的环境中变慢，我认为没有简单的方法可以改善它。 - Blastfurnace

难道没有其他人担心这些时间是使用ideone获得的事实吗？ - ildjarn

@Olaf：恐怕我不同意，这种问题非常适合所有选定标签的主题。在C和C++中，一般来说是足够接近的，因此性能上的差异需要解释。我很高兴我们找到了答案。或许GNU libc++应该因此得到改进。 - chqrlie

Answer 1

两个程序的功能完全相同。它们使用相同的算法，并且由于其低复杂度，它们的性能主要受输入和输出处理的效率限制。

在一个程序中使用 scanf("%d", &fact_num); 扫描输入，在另一个程序中使用 cin >> fact_num; 似乎都不会很昂贵。事实上，在C++中应该更少耗费时间，因为类型转换在编译时已知，正确的解析器可以直接被C++编译器调用。输出也是一样的。你甚至特别写了一个单独的 printf("%s","\n"); 函数调用，但C编译器足够聪明，可以将其编译为调用 putchar('\n'); 。

因此，从I/O和计算的复杂性来看，C++版本应该比C版本更快。

完全禁用 stdout 缓冲会使C实现变得比C++版本更慢。AlexLop进行了另一个测试，在最后一个 printf 之后加入 fflush(stdout); 与C++版本的性能相似。它没有像完全禁用缓冲那样慢，因为输出被分成小块写入系统，而不是一个字节一个字节地写入。

这似乎指向您的C++库的特定行为：我怀疑您的系统实现 cin 和 cout 在从 cin 请求输入时刷新输出到 cout 。一些C库也会这样做，但通常只在读/写终端时才这样做。www.spoj.com网站进行的基准测试可能将输入和输出重定向到文件。

AlexLop进行了另一个测试：一次将所有输入读入一个向量中，然后计算并写入所有输出有助于理解为什么C++版本要慢得多。它将性能提高到与C版本相同，这证明了我的观点，并消除了对C++格式化代码的怀疑。

Blastfurnace 进行了另一个测试，将所有输出存储在std::ostringstream中，并在最后一次操作时进行冲洗，这样做能够改善 C++ 的性能，使其与基本的 C 版本相同。QED。

交织从cin输入和对cout的输出会导致非常低效的I/O处理，破坏了流缓冲方案，使性能降低了10倍。

PS：当fact_num >= UINT_MAX / 5时，您的算法是不正确的，因为fives *= 5会在成为> fact_num之前溢出并重新循环。您可以通过将fives设置为unsigned long或unsigned long long来更正此问题，如果这些类型中存在一个比 unsigned int 更大，则使用%u作为scanf格式。您很幸运www.spoj.com上的人们对其基准测试不太严格。

编辑：正如vitaux后来解释的那样，这种行为确实是C ++标准规定的。默认情况下，cin与cout相关联。对于需要重新填充输入缓冲区的输入操作，将导致cout刷新挂起的输出。在 OP 实现中，cin似乎系统地刷新cout，这有点过度并且效率低下。

Ilya Popov提供了一个简单的解决方案：cin可以通过在std::ios_base::sync_with_stdio(false);之外施加另一个魔法咒语来解除与cout的关联：

cin.tie(nullptr);

还要注意，使用std::endl而不是'\n'在cout上产生行尾时也会出现强制刷新。将输出行更改为更符合C++习惯和看起来无害的cout << num_of_trailing_zeros << endl;同样会降低性能。

- chqrlie

---

你关于流刷新的想法可能是正确的。在std::ostringstream中收集输出并在最后一次性输出可以将时间降至与C版本相同。 - Blastfurnace

@DavidC.Rankin：我提出了一个猜想（即在读取cin时，cout被刷新），设计了一种证明方法，AlexLop实现了它并且确实给出了令人信服的证据，但Blastfurnace提出了另一种证明方法，他的测试也给出了同样令人信服的证据。我认为这是证明，但当然它不是完全正式的证明，查看C++源代码可能会更好。 - chqrlie

我尝试使用ostringstream进行输出，结果时间为0.02 QED :). 关于fact_num >= UINT_MAX / 5，非常好的观点！ - Alex Lop.

将所有输入收集到一个“向量”中，然后进行计算处理（不使用“ostringstream”），可以得到相同的结果！时间 0.02。结合使用“向量”和“ostringstream”并不能进一步提高它。相同的时间 0.02。 - Alex Lop.

一个更简单的修复方法，即使 sizeof(int) == sizeof(long long) 也可以工作：在 num_of_trailing_zeros += fact_num/fives; 后的循环体中添加一个测试，以检查 fives 是否已达到其最大值：if (fives > UINT_MAX / 5) break; - chqrlie

Answer 2

另一个让你同时使用 cin 和 cout 时加速 iostream 的技巧是调用

cin.tie(nullptr);

默认情况下，当您从cin输入任何内容时，它会刷新cout。如果您同时进行输入和输出，则可能会严重影响性能。这是为命令行界面使用而设计的，您可以在其中显示某些提示，然后等待数据：

std::string name;
cout << "Enter your name:";
cin >> name;

在这种情况下，您希望确保在开始等待输入之前实际显示提示。使用上面的代码，您打破了这个关系，cin和cout变得独立起来。

自C++11以来，使用 std::getline 和 std::stoi 是实现iostream更好性能的另一种方式，像这样：

std::string line;
for (int i = 0; i < n && std::getline(std::cin, line); ++i)
{
    int x = std::stoi(line);
}

使用这种方法可以接近C语言的性能，甚至可以超越scanf。使用getchar，特别是与手写解析一起使用getchar_unlocked仍然提供更好的性能。

PS. 我曾经写过一篇文章，对比了几种C ++中输入数字的方法，对于在线评测非常有用，但很抱歉它只有俄语版。不过，代码样例和最终的表格应该还是可以理解的。

- Ilya Popov

---

感谢您的解释和+1的解决方案，但是您提出的使用std::readline和std::stoi的替代方法与OPs代码在功能上并不等效。 cin >> x;和scanf（“％f”，&x）;都接受任何空格作为分隔符，同一行上可能有多个数字。 - chqrlie

Answer 3

问题在于，引用cppreference的说法：

从std::cin输入、输出到std::cerr，或程序终止都会强制调用std::cout.flush()

这很容易测试：如果您替换

cin >> fact_num;

与

scanf("%d", &fact_num);

对于cin >> num_of_inputs也是如此，但要保留cout，那么在您的C++版本（或者说IOStream版本）中几乎可以获得与C语言版本相同的性能：

如果保留cin但替换

cout << num_of_trailing_zeros << "\n";

随着

printf("%d", num_of_trailing_zeros);
printf("%s","\n");

如Ilya Popov所提到的，一个简单的解决方案是将cout和cin分开使用：

cin.tie(nullptr);

标准库的实现在某些情况下允许省略对flush的调用，但并非总是如此。以下是C++14 27.7.2.1.3的一段引文（感谢chqrlie）：

类basic_istream::sentry: 首先，如果is.tie()不是空指针，则函数调用is.tie()->flush()以将输出序列与任何相关联的外部C流同步。除非可以在is.tie()的put区域为空的情况下抑制此调用。此外，实现允许推迟对flush的调用，直到发生is.rdbuf()->underflow()的调用。如果在sentry对象被销毁之前没有这样的调用，则可能完全消除对flush的调用。

- vitaut

---

感谢您的解释。然而引用C++14 27.7.2.1.3：Class basic_istream::sentry：首先，如果is.tie()不是空指针，则函数调用is.tie()->flush()来将输出序列与任何关联的外部C流同步。除非可以在is.tie()的放置区域为空的情况下抑制此调用。进一步，实现允许推迟对flush的调用，直到发生is.rdbuf()->underflow()的调用。如果在sentry对象被销毁之前没有这样的调用，则可以完全消除对flush的调用。 - chqrlie

像往常一样，C++的事情比看起来的要复杂。OP的C++库不如标准允许的那样高效。 - chqrlie

感谢提供cppreference链接。不过我不太喜欢屏幕截图中的“错误答案”☺ - Alex Lop.

@AlexLop。哎呀，修复了“错误答案”的问题=)。忘记更新另一个cin（这不会影响计时）。 - vitaut

@chqrlie 对的，但即使在下溢情况下，性能也很可能比stdio解决方案差。感谢标准参考。 - vitaut