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と、 long long の代わりに int を使用して累積されます。

手動ループを次のようにコーディングすると、同等になります。

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

または、次のように Accumulate を呼び出すことができます。

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

の 3 番目のパラメーターが値 0であるため、元のコードはループとstd::accumulate同等ではないことに注意してください。を使用して合計を実行し、最後にのみ結果を に格納します。3 番目のパラメータを変更して、アルゴリズムがアキュムレータを使用するように強制すると、次のような結果になります。forstd::accumulateintintlong long0LLlong 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 に答える