c++ - STL 算法是否针对速度进行了优化？

Question

我正在测试 std::vector 上不同循环方式的速度。 在下面的代码中，我考虑了 5 种方法来计算 N = 10000000 个元素的 vector 的所有元素的总和:

1. 使用迭代器
2. 使用整数索引
3. 使用整数索引，按因子 2 展开
4. 使用整数索引，按因子 4 展开
5. 使用 std::accumulate

代码是用g++ for windows编译的，用于编译的命令行是:

g++ -std=c++11 -O3 loop.cpp -o loop.exe

我运行代码 4 次，测量每个方法的时间，我得到以下结果(时间以微秒为单位，给出了最大值和最小值):

• 迭代器:8002 - 8007
• 整数索引:8004 - 9003
• 展开 2:6004 - 7005
• 展开 4:4001 - 5004
• 累积:8005 - 9007

这些实验似乎表明:

1. 使用迭代器循环与整数索引没有太大区别，至少在完全优化的情况下是这样。

2. 展开循环会有返回

3. 令人惊讶的是，STL::accumulate 的性能更差。

虽然结论 1 和 2 在某种程度上是意料之中的，但数字 3 却相当令人惊讶。不是所有的书都说用STL算法而不是自己写循环吗？

我在测量时间或解释结果的方式上是否有任何错误？ 如果您尝试下面给出的代码，你们会遇到不同的情况吗？

#include <iostream>
#include <chrono>
#include <vector>
#include <numeric>

using namespace std;
using namespace std::chrono;



int main()
{
    const int N = 10000000;
    vector<int> v(N);
    for (int i = 0; i<N; ++i)
        v[i] = i;

    //looping with iterators
    {
        high_resolution_clock::time_point t1 = high_resolution_clock::now();

        long long int sum = 0;
        for (auto it = v.begin(); it != v.end(); ++it)
            sum+=*it;

        high_resolution_clock::time_point t2 = high_resolution_clock::now();

        auto duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();

        cout << duration << "microseconds  output = " << sum << " (Iterators)\n";
    }

    //looping with integers
    {
        high_resolution_clock::time_point t1 = high_resolution_clock::now();

        long long int sum = 0;
        for (int i = 0; i<N; ++i)
            sum+=v[i];

        high_resolution_clock::time_point t2 = high_resolution_clock::now();

        auto duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();

        cout << duration << "microseconds  output = " << sum << " (integer index)\n";
    }

    //looping with integers (UNROLL 2)
    {
        high_resolution_clock::time_point t1 = high_resolution_clock::now();

        long long int sum = 0;
        for (int i = 0; i<N; i+=2)
            sum+=v[i]+v[i+1];

        high_resolution_clock::time_point t2 = high_resolution_clock::now();

        auto duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();

        cout << duration << "microseconds  output = " << sum << " (integer index, UNROLL 2)\n";
    }

    //looping with integers (UNROLL 4)
    {
        high_resolution_clock::time_point t1 = high_resolution_clock::now();

        long long int sum = 0;
        for (int i = 0; i<N; i+=4)
            sum+=v[i]+v[i+1]+v[i+2]+v[i+3];

        high_resolution_clock::time_point t2 = high_resolution_clock::now();

        auto duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();

        cout << duration << "microseconds  output = " << sum << " (integer index, UNROLL 4)\n";
    }

    //using std::accumulate
    {
        high_resolution_clock::time_point t1 = high_resolution_clock::now();

        long long int sum = accumulate(v.begin(), v.end(), static_cast<long long int>(0));

        high_resolution_clock::time_point t2 = high_resolution_clock::now();

        auto duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();

        cout << duration << "microseconds  output = " << sum << " (std::accumulate)\n";
    }
    return 0;
}

Answer 1

使用标准库算法的原因不是获得更好的效率，而是让你在更高的抽象层次上思考。

虽然在某些情况下算法可能比您自己的手动代码更快，但这不是它们的目的。 C++ 的一大优点是它允许您在有特定需要时绕过内置库。如果您的基准测试表明标准库导致严重减速，您可以自由探索经典替代方案，例如循环展开。对于大多数永远不需要的目的。

话虽如此，编写良好的标准库算法永远不会比您自己的直接实现慢得可怕，除非您利用对数据细节的了解。