c++ - 具有固定大小数组的 STL 算法的效率

Question

一般来说，我假设任何算法的 STL 实现至少与我能想到的任何算法一样高效(还有无错误的额外好处)。然而，我开始怀疑 STL 对迭代器的关注在某些情况下是否有害。

假设我想计算两个固定大小数组的内积。我天真的实现看起来像这样:

std::array<double, 100000> v1;
std::array<double, 100000> v2;
//fill with arbitrary numbers

double sum = 0.0;
for (size_t i = 0; i < v1.size(); ++i) {
    sum += v1[i] * v2[i];
}

由于迭代次数和内存布局在编译期间是已知的，并且所有操作都可以直接映射到 native 处理器指令，因此编译器应该能够轻松地从中生成“最佳”机器代码(循环展开、向量化/FMA 指令...)。

STL版本

double sum = std::inner_product(cbegin(v1), cend(v1), cbegin(v2), 0.0);

另一方面添加了一些额外的间接寻址，即使所有内容都是内联的，编译器仍然必须推断它正在处理一个连续的内存区域以及该区域所在的位置。虽然原则上这当然是可能的，但我想知道典型的 c++ 编译器是否真的会这样做。

所以我的问题是:您认为，我自己实现在固定大小数组上运行的标准算法是否有性能优势，或者 STL 版本是否总是优于手动实现？

Answer 1

按照建议我做了一些测量和

• 下面的代码
• 在 Release模式下使用 VS2013 为 x64 编译
• 在配备 i7-2640M 的 Win8.1 机器上执行，

算法版本持续慢了大约 20%(15.6-15.7 秒对 12.9-13.1 秒)。 N 和 REPS 的相对差异在两个数量级内也大致保持不变。

所以我猜答案是:使用标准库算法会影响性能。

如果这是一个普遍问题，或者它是否特定于我的平台、编译器和基准测试，它仍然会很有趣。欢迎您发布自己的结果或对基准发表评论。

#include <iostream>
#include <numeric>
#include <array>
#include <chrono>
#include <cstdlib>

#define USE_STD_ALGORITHM

using namespace std;
using namespace std::chrono;

static const size_t N = 10000000; //size of the arrays
static const size_t REPS = 1000; //number of repitions

array<double, N> a1;
array<double, N> a2;

int main(){
    srand(10);
    for (size_t i = 0; i < N; ++i) {
        a1[i] = static_cast<double>(rand())*0.01;
        a2[i] = static_cast<double>(rand())*0.01;
    }

    double res = 0.0;
    auto start=high_resolution_clock::now();
    for (size_t z = 0; z < REPS; z++) {     
        #ifdef USE_STD_ALGORITHM
            res = std::inner_product(a1.begin(), a1.end(), a2.begin(), res);        
        #else           
            for (size_t t = 0; t < N; ++t)  {
                res+= a1[t] * a2[t];
            }
        #endif        
    }
    auto end = high_resolution_clock::now();

    std::cout << res << "  "; // <-- necessary, so that loop isn't optimized away
    std::cout << duration_cast<milliseconds>(end - start).count() <<" ms"<< std::endl;

}
/* 
 * Update: Results (ubuntu 14.04 , haswell)
 * STL: algorithm
 * g++-4.8-2    -march=native -std=c++11 -O3 main.cpp               : 1.15287e+24  3551 ms
 * g++-4.8-2    -march=native -std=c++11 -ffast-math -O3 main.cpp   : 1.15287e+24  3567 ms
 * clang++-3.5  -march=native -std=c++11 -O3 main.cpp               : 1.15287e+24  9378 ms
 * clang++-3.5  -march=native -std=c++11 -ffast-math -O3 main.cpp   : 1.15287e+24  8505 ms
 *
 * loop:
 * g++-4.8-2    -march=native -std=c++11 -O3 main.cpp               : 1.15287e+24  3543 ms
 * g++-4.8-2    -march=native -std=c++11 -ffast-math -O3 main.cpp   : 1.15287e+24  3551 ms
 * clang++-3.5  -march=native -std=c++11 -O3 main.cpp               : 1.15287e+24  9613 ms
 * clang++-3.5  -march=native -std=c++11 -ffast-math -O3 main.cpp   : 1.15287e+24  8642 ms
 */  

编辑:
我在同一台机器上的 fedora 21 Virtual Box VM 上使用 O3 和 std=c++11 使用 g++-4.9.2 和 clang++-3.5 进行了快速检查，并且显然那些编译器没有同样的问题(两个版本的时间几乎相同)。然而，gcc 版本的速度大约是 clang 版本的两倍(7.5 秒对 14 秒)。