10

我正在测试算法并遇到这种奇怪的行为，std::accumulate比简单的for循环更快。

看看生成的汇编程序，我并不聪明:-) 似乎for循环被优化为 MMX 指令，而累加则扩展为循环。

这是代码。行为表现在-O3优化级别，gcc 4.7.1

#include <vector>                                                                                                                                                                                                                                                              
#include <chrono>                                                                                                                                                                                                                                                              
#include <iostream>                                                                                                                                                                                                                                                            
#include <random>                                                                                                                                                                                                                                                              
#include <algorithm>                                                                                                                                                                                                                                                           
using namespace std;                                                                                                                                                                                                                                                           

int main()                                                                                                                                                                                                                                                                     
{                                                                                                                                                                                                                                                                              
    const size_t vsize = 100*1000*1000;                                                                                                                                                                                                                                        

    vector<int> x;
    x.reserve(vsize);

    mt19937 rng;
    rng.seed(chrono::system_clock::to_time_t(chrono::system_clock::now()));

    uniform_int_distribution<uint32_t> dist(0,10);

    for (size_t i = 0; i < vsize; i++)
    {
        x.push_back(dist(rng));
    }

    long long tmp = 0;
    for (size_t i = 0; i < vsize; i++)
    {
        tmp += x[i];
    }

    cout << "dry run " << tmp << endl;

    auto start = chrono::high_resolution_clock::now();
    long long suma = accumulate(x.begin(),x.end(),0);
    auto end = chrono::high_resolution_clock::now();

    cout << "Accumulate runtime " << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << " - " << suma << endl;

    start = chrono::high_resolution_clock::now();
    suma = 0;
    for (size_t i = 0; i < vsize; i++)
    {
        suma += x[i];
    }
    end = chrono::high_resolution_clock::now();

    cout << "Manual sum runtime " << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << " - " << suma <<  endl;

    return 0;
}
4

3 回答 3

10

当您通过0累积时，您正在使用 int 而不是 long long 来累积。

如果您像这样编写手动循环，它将是等效的：

int sumb = 0;
for (size_t i = 0; i < vsize; i++)
{
    sumb += x[i];
}
suma = sumb;

或者你可以像这样调用累加：

long long suma = accumulate(x.begin(),x.end(),0LL);
于 2012-11-06T02:52:30.323 回答
7

我使用 Visual Studio 2012 得到了一些不同的结果

// original code
Accumulate runtime 93600 ms
Manual sum runtime 140400 ms

请注意，原始std::accumulate代码不等同于for循环，因为第三个参数 tostd::accumulate是int0 值。它使用 a 执行求和，int并且仅在最后将结果存储在 a 中long long。更改第三个参数以0LL强制算法使用long long累加器并导致以下时间。

// change std::accumulate initial value -> 0LL
Accumulate runtime 265200 ms
Manual sum runtime 140400 ms

由于最终结果适合int我更改suma并std::accumulate返回仅使用int值。在此更改之后，MSVC 2012 编译器能够自动矢量化循环for并导致以下时间。

// change suma from long long to int
Accumulate runtime 93600 ms
Manual sum runtime 46800 ms
于 2012-11-06T02:58:34.453 回答
3

在修复了累积问题后，其他人注意到我使用 Visual Studio 2008 和 2010 进行了测试，累积确实比手动循环更快。

查看反汇编，我看到在手动循环中进行了一些额外的迭代器检查，所以我切换到一个原始数组来消除它。

这是我最终测试的内容：

#include <Windows.h>
#include <iostream>
#include <numeric>
#include <stdlib.h>

int main() 
{
    const size_t vsize = 100*1000*1000;                                                                                                                                                                                                                                        
    int* x = new int[vsize];

    for (size_t i = 0; i < vsize; i++) x[i] = rand() % 1000;

    LARGE_INTEGER start,stop;
    long long suma = 0, sumb = 0, timea = 0, timeb = 0;

    QueryPerformanceCounter( &start );
    suma = std::accumulate(x, x + vsize, 0LL);
    QueryPerformanceCounter( &stop );
    timea = stop.QuadPart - start.QuadPart;

    QueryPerformanceCounter( &start );
    for (size_t i = 0; i < vsize; ++i) sumb += x[i];
    QueryPerformanceCounter( &stop );
    timeb = stop.QuadPart - start.QuadPart;

    std::cout << "Accumulate: " << timea << " - " << suma << std::endl;
    std::cout << "      Loop: " << timeb << " - " << sumb << std::endl;

    delete [] x;
    return 0;
}

Accumulate: 633942 - 49678806711
      Loop: 292642 - 49678806711

使用此代码，手动循环很容易击败累积。最大的不同是编译器将手动循环展开了 4 次，否则生成的代码几乎相同。

于 2012-11-06T03:22:29.583 回答