c++ なぜ、要素ごとの加算は、結合されたループよりも別々のループではるかに高速ですか?




performance compiler-optimization (8)

a1b1c1d1がヒープメモリを指し、数値コードが次のコアループを持つとします。

const int n = 100000;

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
    c1[j] += d1[j];
}

このループは、別の外部forループを介して10,000回実行さforます。 それをスピードアップするために、コードを次のように変更しました。

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
}

for (int j = 0; j < n; j++) {
    c1[j] += d1[j];
}

完全な最適化を行ったMS Visual C ++ 10.0でコンパイルし、 Intel Core 2 Duo(x64)で32ビット対応のSSE2コンパイルした場合、最初の例は5.5秒、ダブルループの例はわずか1.9秒です。 私の質問は:(下の私の言い直した質問を参照してください)

PS:これが役立つかどうかわかりません:

最初のループの逆アセンブリは基本的に次のようになります(このブロックはフルプログラムで約5回繰り返されます)。

movsd       xmm0,mmword ptr [edx+18h]
addsd       xmm0,mmword ptr [ecx+20h]
movsd       mmword ptr [ecx+20h],xmm0
movsd       xmm0,mmword ptr [esi+10h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [edx+20h]
addsd       xmm0,mmword ptr [ecx+28h]
movsd       mmword ptr [ecx+28h],xmm0
movsd       xmm0,mmword ptr [esi+18h]
addsd       xmm0,mmword ptr [eax+38h]

ダブルループの例の各ループはこのコードを生成します(次のブロックは約3回繰り返されます)。

addsd       xmm0,mmword ptr [eax+28h]
movsd       mmword ptr [eax+28h],xmm0
movsd       xmm0,mmword ptr [ecx+20h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [ecx+28h]
addsd       xmm0,mmword ptr [eax+38h]
movsd       mmword ptr [eax+38h],xmm0
movsd       xmm0,mmword ptr [ecx+30h]
addsd       xmm0,mmword ptr [eax+40h]
movsd       mmword ptr [eax+40h],xmm0

その問題は、配列(n)の大きさとCPUキャッシュに大きく依存するため、関連性がないことが判明しました。 だからさらなる興味があるなら、私はその質問に言い換えます:

次のグラフの5つの領域で示されているように、さまざまなキャッシュ動作につながる細かいことについていくつか確かな情報を提供できますか?

これらのCPUに類似のグラフを提供することによって、CPU /キャッシュアーキテクチャの違いを指摘することも興味深いかもしれません。

PPS:ここに完全なコードがあります。 TBB_TIMINGマクロを定義しないことによって無効にすることができる、より高い解像度のタイミングにTBB Tick_Countを使用します。

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>

//#define TBB_TIMING

#ifdef TBB_TIMING   
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#endif

using namespace std;

//#define preallocate_memory new_cont

enum { new_cont, new_sep };

double *a1, *b1, *c1, *d1;


void allo(int cont, int n)
{
    switch(cont) {
      case new_cont:
        a1 = new double[n*4];
        b1 = a1 + n;
        c1 = b1 + n;
        d1 = c1 + n;
        break;
      case new_sep:
        a1 = new double[n];
        b1 = new double[n];
        c1 = new double[n];
        d1 = new double[n];
        break;
    }

    for (int i = 0; i < n; i++) {
        a1[i] = 1.0;
        d1[i] = 1.0;
        c1[i] = 1.0;
        b1[i] = 1.0;
    }
}

void ff(int cont)
{
    switch(cont){
      case new_sep:
        delete[] b1;
        delete[] c1;
        delete[] d1;
      case new_cont:
        delete[] a1;
    }
}

double plain(int n, int m, int cont, int loops)
{
#ifndef preallocate_memory
    allo(cont,n);
#endif

#ifdef TBB_TIMING   
    tick_count t0 = tick_count::now();
#else
    clock_t start = clock();
#endif

    if (loops == 1) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                a1[j] += b1[j];
                c1[j] += d1[j];
            }
        }
    } else {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a1[j] += b1[j];
            }
            for (int j = 0; j < n; j++) {
                c1[j] += d1[j];
            }
        }
    }
    double ret;

#ifdef TBB_TIMING   
    tick_count t1 = tick_count::now();
    ret = 2.0*double(n)*double(m)/(t1-t0).seconds();
#else
    clock_t end = clock();
    ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC);
#endif

#ifndef preallocate_memory
    ff(cont);
#endif

    return ret;
}


void main()
{   
    freopen("C:\\test.csv", "w", stdout);

    char *s = " ";

    string na[2] ={"new_cont", "new_sep"};

    cout << "n";

    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= 2; i++)
#ifdef preallocate_memory
            cout << s << i << "_loops_" << na[preallocate_memory];
#else
            cout << s << i << "_loops_" << na[j];
#endif

    cout << endl;

    long long nmax = 1000000;

#ifdef preallocate_memory
    allo(preallocate_memory, nmax);
#endif

    for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2)))
    {
        const long long m = 10000000/n;
        cout << n;

        for (int j = 0; j < 2; j++)
            for (int i = 1; i <= 2; i++)
                cout << s << plain(n, m, j, i);
        cout << endl;
    }
}

(これは、 n異なる値に対してFLOP / sを表示します)。


私はここで議論した結果を再現することはできません。

貧弱なベンチマークコードが責任を負うかどうかはわかりませんが、次のコードを使用して2つのメソッドがお互いの10%以内にあり、1つのループは通常2つより少し速いです。期待する。

アレイのサイズは、2つのループを使用して2 ^ 16から2 ^ 24の範囲でした。 私はソース配列を初期化するように注意していましたので、 +=代入はFPUにdoubleとして解釈されるメモリガーベジを追加するように要求していませんでした。

ループ内にb[j]d[j]InitToZero[j]InitToZero[j]したり、 += b[j] = 1+= d[j] = 1を使ってさまざまなスキームで遊んだ+= d[j] = 1 、そして私はかなり一貫した結果を得ました。

期待どおり、 InitToZero[j]を使ってループ内でbd初期化aと、 ac代入の前にInitToZero[j]してInitToZero[j]れるため、組み合わされたアプローチが有利になりましたが、まだ10%以内です。 Go figure。

ハードウェアは、 Dell XPS 8500で 、第3世代のCore i7 @ 3.4 GHzおよび8 GBのメモリを搭載しています。 8つのループを使用する2 ^ 16〜2 ^ 24の場合、累積時間はそれぞれ44.987と40.965でした。 完全に最適化されたVisual C ++ 2010

PS:ループをゼロにカウントダウンするように変更しました。結合方法はやや速かったです。 私の頭を傷つける。 新しい配列のサイジングとループカウントに注意してください。

// MemBufferMystery.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <string>
#include <time.h>

#define  dbl    double
#define  MAX_ARRAY_SZ    262145    //16777216    // AKA (2^24)
#define  STEP_SZ           1024    //   65536    // AKA (2^16)

int _tmain(int argc, _TCHAR* argv[]) {
    long i, j, ArraySz = 0,  LoopKnt = 1024;
    time_t start, Cumulative_Combined = 0, Cumulative_Separate = 0;
    dbl *a = NULL, *b = NULL, *c = NULL, *d = NULL, *InitToOnes = NULL;

    a = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    b = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    c = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    d = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    InitToOnes = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    // Initialize array to 1.0 second.
    for(j = 0; j< MAX_ARRAY_SZ; j++) {
        InitToOnes[j] = 1.0;
    }

    // Increase size of arrays and time
    for(ArraySz = STEP_SZ; ArraySz<MAX_ARRAY_SZ; ArraySz += STEP_SZ) {
        a = (dbl *)realloc(a, ArraySz * sizeof(dbl));
        b = (dbl *)realloc(b, ArraySz * sizeof(dbl));
        c = (dbl *)realloc(c, ArraySz * sizeof(dbl));
        d = (dbl *)realloc(d, ArraySz * sizeof(dbl));
        // Outside the timing loop, initialize
        // b and d arrays to 1.0 sec for consistent += performance.
        memcpy((void *)b, (void *)InitToOnes, ArraySz * sizeof(dbl));
        memcpy((void *)d, (void *)InitToOnes, ArraySz * sizeof(dbl));

        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
                c[j] += d[j];
            }
        }
        Cumulative_Combined += (clock()-start);
        printf("\n %6i miliseconds for combined array sizes %i and %i loops",
                (int)(clock()-start), ArraySz, LoopKnt);
        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
            }
            for(j = ArraySz; j; j--) {
                c[j] += d[j];
            }
        }
        Cumulative_Separate += (clock()-start);
        printf("\n %6i miliseconds for separate array sizes %i and %i loops \n",
                (int)(clock()-start), ArraySz, LoopKnt);
    }
    printf("\n Cumulative combined array processing took %10.3f seconds",
            (dbl)(Cumulative_Combined/(dbl)CLOCKS_PER_SEC));
    printf("\n Cumulative seperate array processing took %10.3f seconds",
        (dbl)(Cumulative_Separate/(dbl)CLOCKS_PER_SEC));
    getchar();

    free(a); free(b); free(c); free(d); free(InitToOnes);
    return 0;
}

MFLOPSが適切な基準であると決められた理由はわかりません。 私はメモリアクセスに焦点を当てることを考えましたが、浮動小数点計算時間を最小限に抑えようとしました。 私は+=で去ったが、私は理由は分からない。

計算のない直線的な代入は、メモリアクセス時間のよりクリーンなテストであり、ループ回数に関係なく一様なテストを作成する。 たぶん私は会話で何かを逃したが、それについて二度考えてみる価値がある。 プラスを割り当てから外した場合、累積時間はそれぞれ31秒でほぼ同じになります。


これをさらに分析すると、これは(少なくとも部分的に)4つのポインタのデータ整列によって引き起こされると考えられます。 これにより、あるレベルのキャッシュ・バンク/ウェイ競合が発生します。

配列をどのように割り当てているかを正確に推測していれば、それらはページ行に合わせられる可能性があります

これは、各ループ内のすべてのアクセスが同じキャッシュ方法で行われることを意味します。 しかし、Intelプロセッサーはしばらくの間、8ウェイのL1キャッシュ連想を持っていました。 しかし実際には、パフォーマンスは完全に均一ではありません。 4ウェイへのアクセスは、2ウェイというよりもまだ遅いです。

編集:実際には、すべての配列を別々に割り当てるように見えます。 通常、このような大きな割り当てが要求されると、アロケータはOSに新しいページを要求します。 したがって、大きな割り当てがページ境界から同じオフセットに現れる可能性が高くなります。

ここにテストコードがあります:

int main(){
    const int n = 100000;

#ifdef ALLOCATE_SEPERATE
    double *a1 = (double*)malloc(n * sizeof(double));
    double *b1 = (double*)malloc(n * sizeof(double));
    double *c1 = (double*)malloc(n * sizeof(double));
    double *d1 = (double*)malloc(n * sizeof(double));
#else
    double *a1 = (double*)malloc(n * sizeof(double) * 4);
    double *b1 = a1 + n;
    double *c1 = b1 + n;
    double *d1 = c1 + n;
#endif

    //  Zero the data to prevent any chance of denormals.
    memset(a1,0,n * sizeof(double));
    memset(b1,0,n * sizeof(double));
    memset(c1,0,n * sizeof(double));
    memset(d1,0,n * sizeof(double));

    //  Print the addresses
    cout << a1 << endl;
    cout << b1 << endl;
    cout << c1 << endl;
    cout << d1 << endl;

    clock_t start = clock();

    int c = 0;
    while (c++ < 10000){

#if ONE_LOOP
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
            c1[j] += d1[j];
        }
#else
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
        }
        for(int j=0;j<n;j++){
            c1[j] += d1[j];
        }
#endif

    }

    clock_t end = clock();
    cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl;

    system("pause");
    return 0;
}

ベンチマーク結果:

編集: 実際のコア2アーキテクチャマシンの結果:

2 x Intel Xeon X5482 Harpertown @ 3.2 GHz:

#define ALLOCATE_SEPERATE
#define ONE_LOOP
00600020
006D0020
007A0020
00870020
seconds = 6.206

#define ALLOCATE_SEPERATE
//#define ONE_LOOP
005E0020
006B0020
00780020
00850020
seconds = 2.116

//#define ALLOCATE_SEPERATE
#define ONE_LOOP
00570020
00633520
006F6A20
007B9F20
seconds = 1.894

//#define ALLOCATE_SEPERATE
//#define ONE_LOOP
008C0020
00983520
00A46A20
00B09F20
seconds = 1.993

観察:

  • 1つのループで6.206秒 、2つのループで2.116秒 。 これはOPの結果を正確に再現します。

  • 最初の2つのテストでは、配列は別々に割り当てられます。 これらのページはすべてページと同じ位置にあることに気付くでしょう。

  • 2番目の2つのテストでは、配列が一緒に詰め込まれ、その配置が解除されます。 ここでは、両方のループが高速であることがわかります。 さらに、2番目の(ダブル)ループは、通常は予想通り遅いループになりました。

コメントで@Stephen Cannonが指摘しているように、この位置合わせがロード/ストアユニットまたはキャッシュで偽のエイリアシングを引き起こす可能性が非常に高いです。 私はこれについて調査し、Intelが実際に部分的なアドレスのエイリアシング・ストールのためのハードウェア・カウンタを持っていることを発見しました。

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html

5地域 - 説明

地域1:

これは簡単です。 データセットは非常に小さく、ループや分岐などのオーバーヘッドによってパフォーマンスが支配されます。

リージョン2:

ここでは、データサイズが増加するにつれて、相対オーバーヘッドの量が減り、パフォーマンスが「飽和」します。 ここでは、ループと分岐のオーバーヘッドが2倍になるため、2つのループが遅くなります。

私はここで何が起こっているのか正確にはわかりません... Agner Fogがキャッシュバンクの競合について言及しても、アライメントはまだ有効です。 (そのリンクはSandy Bridgeに関するものですが、このアイデアはCore 2にも当てはまるはずです)

リージョン3:

この時点で、データはもはやL1キャッシュに収まりません。 したがって、パフォーマンスはL1 < - > L2キャッシュ帯域幅によって制限されます。

リージョン4:

シングルループのパフォーマンス低下は、私たちが観察しているものです。 前述のように、これは(おそらく)プロセッサのロード/ストア単位でエイリアスが発生する原因となるアラインメントによるものです。

ただし、falseエイリアシングが発生するには、データセット間に十分なストライドがなければなりません。 このため、地域3ではこれが表示されません。

リージョン5:

この時点では、キャッシュには何も適合しません。 つまり、あなたはメモリ帯域幅に縛られています。


1つのマシンで2つのアレイを同時に保持することは可能ですが、ディスクキャッシュを介して使用可能なメモリの合計が4つすべてを保持するのに十分であったマシンで作業しているとします。

単純なLIFOキャッシュポリシーを仮定すると、このコードは次のようになります。

for(int j=0;j<n;j++){
    a[j] += b[j];
}
for(int j=0;j<n;j++){
    c[j] += d[j];
}

最初にabをRAMにロードしてから、RAM全体で処理します。 2番目のループが開始されると、 cdはディスクからRAMにロードされて操作されます。

もう一方のループ

for(int j=0;j<n;j++){
    a[j] += b[j];
    c[j] += d[j];
}

2つの配列をページアウトし、ループの周りのたびに他の2つのページをページします 。 これは明らかにはるかに遅いでしょう。

おそらくあなたのテストでディスクキャッシングが見えていないかもしれませんが、おそらく他のキャッシングの副作用が見られるでしょう。

ここで少し混乱や誤解があるようですので、例を使って少し詳しく説明します。

n = 2と言って、バイトで作業しています。 私のシナリオでは、このようにわずか4バイトのRAMしか持っておらず、メモリの残りの部分はかなり遅くなります(たとえば100倍長いアクセス)。

バイトがキャッシュにない場合のかなりダムのキャッシュポリシーを仮定すると、 そこに置いて、次のバイトも取得します。この間、次のようなシナリオが得られます。

  • for(int j=0;j<n;j++){
     a[j] += b[j];
    }
    for(int j=0;j<n;j++){
     c[j] += d[j];
    }
    
  • b[0]b[1]をキャッシュしa[0]次にb[0]b[1]をセットしa[0] = a[0] + b[0]キャッシュにa[0] = a[0] + b[0] a[0], a[1]b[0], b[1] 。 コスト= 100 + 100。

  • a[1] = a[1] + b[1]をキャッシュに設定する。 コスト= 1 + 1。
  • cd繰り返します。
  • 総コスト= (100 + 100 + 1 + 1) * 2 = 404

  • for(int j=0;j<n;j++){
     a[j] += b[j];
     c[j] += d[j];
    }
    
  • b[0]b[1]をキャッシュしa[0]次にb[0]b[1]をセットしa[0] = a[0] + b[0]キャッシュにa[0] = a[0] + b[0] a[0], a[1]b[0], b[1] 。 コスト= 100 + 100。

  • c[0]およびc[1]をキャッシュから取り出しa[0], a[1], b[0], b[1] d[0]およびd[1]a[0], a[1], b[0], b[1]キャッシュ内のc[0] = c[0] + d[0] 。 コスト= 100 + 100。
  • 私はどこに行くのか見始めていると思う。
  • 総コスト= (100 + 100 + 100 + 100) * 2 = 800

これは古典的なキャッシュスラッシュシナリオです。


最初のループは各変数の書き込みを交互に行います。 2番目と3番目の要素は要素サイズの小さなジャンプだけです。

ペンと紙を20 cm離れた2本の20本の十字線を2本書きます。 一度やり直してもう一度試してみて、交互に各行に十字を書くことでもう一度試してみてください。


古いC ++や最適化があるかもしれません。私のコンピュータで私はほぼ同じ速度を得ました:

1ループ:1.577ms 2ループ:1.507ms

私はVS2015をE5-1620 3.5Ghzプロセッサで16Gb RAMで実行します


OK、正しい答えは間違いなくCPUキャッシュで何かをしなければなりません。 しかし、キャッシュ引数を使用することは、特にデータなしでは非常に困難です。

多くの議論につながった多くの答えがありますが、それに直面しましょう:キャッシュの問題は非常に複雑であり、一次元ではありません。 彼らはデータのサイズに大きく依存するので、私の質問は不公平でした:それはキャッシュ・グラフの非常に興味深い点にあることが判明しました。

@ Mysticialの答えは、事実に頼っていると思われる唯一のものだったと思われるため、多くの人(私を含む)を説得しましたが、真実の「データポイント」は1つだけでした。

だから、私は彼のテスト(連続的な割り当てと別々の割り当てを使って)と@James 'Answerのアドバイスを組み合わせたのです。

下のグラフは、答えの大部分、特に質問と回答に対するコメントの大半が、使用された正確なシナリオとパラメータに応じて完全に間違っていると考えられることを示しています。

最初の質問はn = 100.000であったことに注意してください。 この点(偶然)は特別な動作を示します。

  1. それは、1つと2つのループのバージョン(ほぼ3の要素)の間に最大の不一致を持っています。

  2. これは、1つのループ(すなわち、連続的な割り当てを伴う)が2ループバージョンに勝つ唯一のポイントです。 (これはMysticialの答えを可能にしました。)

初期化されたデータを使用した結果:

初期化されていないデータを使用した結果(これはMysticialがテストしたものです):

これは説明が難しい:初期化されたデータ。一度割り当てられ、異なるベクトルサイズの次のテストケースごとに再利用されます。

提案

に関する低レベルのパフォーマンス関連の質問はすべて、キャッシュ関連のデータサイズの全範囲に対してMFLOPS情報を提供する必要があります。 回答を考え、特にこの情報なしで他の人と話し合うことは、みんなの時間の無駄です。


2番目のループではキャッシュのアクティビティが大幅に少なくなるため、プロセッサはメモリの要求に対応しやすくなります。


元の質問

1つのループが2つのループよりもずっと遅いのはなぜですか?

問題の評価

OPのコード:

const int n=100000;

for(int j=0;j<n;j++){
    a1[j] += b1[j];
    c1[j] += d1[j];
}

そして

for(int j=0;j<n;j++){
    a1[j] += b1[j];
}
for(int j=0;j<n;j++){
    c1[j] += d1[j];
}

考察

OPループの2つのバリエーションについてのOPのオリジナルの質問と、キャッシュの振る舞いに対する彼の修正された質問と、他の優れた解答および有用なコメントの多くを考慮して、 私は、この状況と問題について別のアプローチをとることで、ここで何か違うことを試してみたいと思います。

アプローチ

2つのループと、キャッシュとページファイリングについての議論のすべてを考慮して、これを別の観点から見ることについて別のアプローチをとってみたいと思います。 実際には、このアプローチは実際のハードウェアやソフトウェアにはまったく関係しません。実際には、キャッシュやページファイルやメモリを割り当てるための実行を伴わないものです。

展望

しばらくの間、コードを見た後、問題が何であり、それが何を生成しているのかがはっきりと分かりました。 これをアルゴリズムの問​​題に分解し、数学的表記を使用するという視点から見て、数学問題とアルゴリズムに類推を適用してみましょう。

私たちが知っていること

彼のループは10万回実行されることがわかっています。 また、 a1b1c1d1は64ビットアーキテクチャ上のポインタであることもわかります。 32ビットマシン上のC ++では、ポインタはすべて固定長であるため、すべてのポインタは4バイトで、64ビットマシンでは8バイトです。 我々は、両方の場合に割り当てられる32バイトがあることを知っています。 唯一の違いは、2回目のケースでは、両方の独立したループに対して16バイトを各反復に割り当てる各反復で32バイトまたは2セットの2〜8バイトを割り当てることです。 したがって、両方のループは合計割り当てで32バイトに相当します。 この情報を使って、一般的な数学、アルゴリズム、それに類推を見てみましょう。 どちらの場合も、同じセットまたはオペレーショングループが実行されなければならない時間の量を知っています。 どちらの場合でも割り当てが必要なメモリ量はわかります。 両方のケースの間の割り当ての全体的な作業負荷はほぼ同じになると考えることができます。

私たちが知らないもの

カウンターを設置してベンチマークテストを実施しない限り、どのくらい時間がかかるかはわかりません。 しかし、ベンチマークは元々の質問から、またいくつかの回答とコメントからすでに含まれており、両者の間に大きな違いが見られます。これはこの問題のこの全般的な理由と、で始まる。

調査しましょう

ヒープ割り当て、ベンチマークテスト、RAM、キャッシュ、およびページファイルを調べることで多くの人がすでにこれを行っていることはすでに明らかです。 特定のデータポイントと特定の反復インデックスを見ることも含まれていました。この特定の問題に関するさまざまな会話では、多くの人々が他の関連することに疑問を持ち始めています。 だから、私たちは数学的アルゴリズムを使ってこの問題を見て、それに類推を加えるにはどうしたらよいでしょうか? 私たちはいくつかの主張をすることから始めます! 次に、そこからアルゴリズムを構築します。

私たちの主張:

  • 私たちのループとその反復は、1から始まり100000で終わります。ループのように0で始まるのではなく、メモリアドレス指定の0インデックス付けスキームについて心配する必要はないからです。アルゴリズムそのもの。
  • どちらの場合も、4つの関数と2つの関数呼び出しがあり、それぞれの関数呼び出しで2つの操作が行われます。 F1()F2()f(a)f(b)f(c)f(d)関数と関数呼び出しとしてこれらを設定します。

アルゴリズム:

1番目のケース: - 1つの集計だけですが、2つの独立した関数呼び出し。

Sum n=1 : [1,100000] = F1(), F2();
                       F1() = { f(a) = f(a) + f(b); }
                       F2() = { f(c) = f(c) + f(d);  }

2番目のケース: - 2つの合計が、それぞれ独自の関数呼び出しを持ちます。

Sum1 n=1 : [1,100000] = F1();
                        F1() = { f(a) = f(a) + f(b); }

Sum2 n=1 : [1,100000] = F1();
                        F1() = { f(c) = f(c) + f(d); }

あなたが気づいた場合F2()のみに存在するSumところの両方Sum1Sum2のみを含みますF1()。これは、第2のアルゴリズムから起こっている最適化の一種があると結論づけ始めるときにも、後で明らかになるであろう。

最初のケースを通じて、反復Sum呼び出しf(a)自己に追加されますf(b)、それが呼び出すf(c)同じことを行うが、追加することf(d)ごとに自分自身に100000 iterations。2つ目のケースではSum1Sum2andが同じ関数が2回連続して呼び出された場合と同じように動作します。このケースでは扱うことができますSum1し、Sum2単に昔ながらとしてSumどこSumこの場合には、次のようになりますSum n=1 : [1,100000] { f(a) = f(a) + f(b); }と、今、これは私達はちょうどそれが同じ機能であることを考慮することができ、最適化のように見えます。

アナロジーによる要約

2番目のケースで見たように、両方のループが同じ正確なシグネチャを持つため、最適化があるかのように見えますが、これは実際の問題ではありません。問題はで行われている作業ではありませんf(a)f(b)f(c)f(d)両方のケースと2の間の比較では、総和があなたの時間の実行に差を与える両方のケースで移動しなければならない距離の差です。

考えてFor LoopsいるようSummationsであるとして反復を行い、そのBoss二人に命令を与えていることAB、そのジョブが肉にしていることCD、それぞれ、そこからいくつかのパッケージをピックアップし、それを返すように。ここでの類推において、forループまたは総和反復および条件チェック自体は、実際には表現されていませんBoss。何実際表しBoss、ここでは直接実際の数学的アルゴリズムからではなく、実際の概念からScope及びCode Block等ルーチンまたはサブルーチン、メソッド、関数内、翻訳部、最初のアルゴリズムは、第2のアルゴリズムが2を有する1つの範囲を有します連続スコープ。

各呼び出しの最初のケース内にはスリップBossに行くAと秩序を与え、Aフェッチするために消灯しB's、パッケージをBossに行くCと同じことを行うと、からパッケージを受け取るために命令を与えD、各繰り返しで。

第二ケース内でBoss直接持つ作品がA行くとフェッチするB'sすべてのパッケージが受信されるまで、パッケージを。その後、すべてのパッケージを取得するために同じようにBoss動作します。CD's

私たちは8バイトのポインタで作業しているので、ヒープ割り当てを扱うので、ここでこの問題を考えてみましょう。私たちBossは100フィートから500フィートであるAと言いましょう。私たちは、実行の順序のために最初からどのくらい離れているか心配する必要はありません。どちらの場合も、最初は最初から最初に移動します。この類推は、この距離が正確であるとは言いません。アルゴリズムの動作を示すのは単なる使用テストケースのシナリオです。多くの場合、ヒープ割り当てを行い、キャッシュファイルとページファイルを操作するとき、アドレスの場所の間のこれらの距離は、違いがそれほど変わらないか、データ型の性質と配列のサイズによって大きく異なる場合があります。ACBossCBossAB

テストケース:

最初のケース:最初の繰り返しオンザはBoss、当初に注文票を与えるために100フィートを行かなければならないAA消灯し、彼のことをしますが、その後インクルードはBossして500フィートを移動しなければならないC彼に彼の注文票を得ました。その後、次の反復とBoss2回の間を500フィート前後で移動しなければならないすべての反復で。

2番目のケース: The Boss最初の反復で100フィートを走行しなければなりませんAが、その後はすでにそこにいて、Aすべての伝票がいっぱいになるまで戻ってくるのを待っています。その後、Boss最初の反復で500フィートを走行するC必要Cがあります。AこれBoss( Summation, For Loop )は、作業後直ちに呼び出されてから500フィートであるため、すべての注文伝票が完了するまで、A彼が行ったように待っているからです。AC's

移動距離の違い

const n = 100000
distTraveledOfFirst = (100 + 500) + ((n-1)*(500 + 500); 
// Simplify
distTraveledOfFirst = 600 + (99999*100);
distTraveledOfFirst = 600 + 9999900;
distTraveledOfFirst =  10000500;
// Distance Traveled On First Algorithm = 10,000,500ft

distTraveledOfSecond = 100 + 500 = 600;
// Distance Traveled On Second Algorithm = 600ft;    

任意の値の比較

600は1000万にはるかに少ないことがわかります。これは厳密ではありません。なぜなら、RAMのアドレスと、各繰り返しで呼び出されるキャッシュファイルまたはページファイルとの間の実際の距離の違いが、目に見えない他の多くの変数に起因することになるからです。最悪の場合のシナリオからそれを認識し、それを見ようとする状況の評価。

したがって、これらの数字によって、アルゴリズム1がアルゴリズム2より99%遅くなるように見えるでしょう。しかし、これが唯一であるThe Boss's一部またはアルゴリズムの責任と、それが実際の労働者を考慮していないABC、&Dと彼らはそれぞれ、ループの反復ごとに行う必要があります。ボスの仕事は、行われている仕事全体の約15〜40%しか占めていません。したがって、労働者によって行われる作業の大部分は、速度差の比率を約50〜70%

観測: - 2つのアルゴリズムの違い

この状況では、それは作業のプロセスの構造であり、ケース2は、類似の関数宣言と定義を持つ部分的な最適化と、名前によって異なる変数。また、ケース1で移動した距離の合計がケース2よりもはるかに大きく、この距離が2つのアルゴリズム間で時間ファクタを移動したと考えることができます。ケース1は、ケース2よりもかなり多くの作業が必要です。これはまた、ASM両方の症例の間に示された。これらの事件について既に述べられているものであっても、ケース1では、上司は両方のACを待たなければならないという事実を説明していないのでA、次の反復で再び戻ることができます。非常に長い時間がかかっている場合Aや、他の作業者がアイドル状態で待っているという事実を説明していません。でケース2のアイドルであることだけである労働者が取り戻すまで。したがって、これもアルゴリズムに影響を与えます。BBossBoss

結論:

ケース1は、古典的な補間問題であり、非効率的な問題である。私は、これが、多くのマシンアーキテクチャーと開発者が、マルチスレッドアプリケーションと並行プログラミングを行うマルチコアシステムの構築と設計を終えた主な理由の1つだとも考えています。

ハードウェア、OS、コンパイラがどのように連携してRAM、キャッシュ、ページファイルなどの作業を含むヒープ割り当てを行うのかにかかわらず、このアプローチから見てもそうです。その背後にある数学は、すでに上記の類推使用してより良いソリューションですこれら二つのどの私たちを示していBossたりSummations、それらのことFor Loops労働者の間を移動しなければならなかったことA&しBケース2は、移動距離の差と時間が異なるため、ケース1と比べて少なくとも1/2の速さであることが容易にわかります。そして、この数学は、ベンチマーク・タイムズと、組立説明書の量の違いの量と、ほぼ事実上完全に並んでいます。

OPs修正された質問

EDIT:問題は、関連性がないことが判明しました。これは、動作がアレイ(n)のサイズとCPUキャッシュに大きく依存するためです。だからさらなる興味があるなら、私はその質問に言い換えます:

次のグラフの5つの領域で示されているように、さまざまなキャッシュ動作につながる細かいことについていくつか確かな情報を提供できますか?

これらのCPUに類似のグラフを提供することによって、CPU /キャッシュアーキテクチャの違いを指摘することも興味深いかもしれません。

これらの質問について

私が間違いなく実証したように、ハードウェアとソフトウェアが関与する前でも根本的な問題があります。今では、The Architecture{ハードウェア、ファームウェア、いくつかの組み込みドライバ、カーネル、ASM命令セット}、The OS{ファイルとメモリ管理システムの間の統合されたシステムセットで一緒に動作するページファイルなどと一緒にメモリとキャッシュの管理、ドライバとレジストリ}、The Compiler{ソースコードの翻訳単位と最適化}、さらにSource Codeは独自のアルゴリズムのセットを使用しています。我々はすでに私たちも任意で任意のマシンにそれを適用する前に、最初のアルゴリズムの中に起こっているボトルネックがあることがわかりますArchitectureOSProgrammable Language第2のアルゴリズムと比較して。したがって、現代のコンピュータの本質を取り入れる前にすでに問題が存在していました。

エンディング結果

しかしながら;これらの新しい質問は重要ではないと言っているわけではありません。なぜなら、彼らは自分自身であり、結局のところ役割を果たしているからです。彼らは手続きや全体的なパフォーマンスに影響を与えますが、それは回答やコメントを与えてくれた多くのグラフや評価で明らかです。あなたがのアナロジーに注意を払う場合Bossと2人の労働者ABからパッケージを移動して、取得しなければならなかったCD、それぞれ、問題の2つのアルゴリズムの数学的表記を考慮あなたもせずに、コンピュータの関与があることがわかりますCase 2約60%であり、より速くCase 1 これらのアルゴリズムがソースコードに適用され、OSを介してコンパイル、最適化、実行された後、グラフやグラフを見ると、ハードウェアの操作を実行すると、これらのアルゴリズムの違いの間にさらに悪化が見られます。

「データ」のセットがかなり小さい場合今では最初に差異のすべてが悪いと思えないかもしれないが、あるためには、Case 1についてです60 - 70%より遅くCase 2、我々は時間の実行の違いという点にあると、この関数の成長を見ることができます。

DeltaTimeDifference approximately = Loop1(time) - Loop2(time)
//where 
Loop1(time) = Loop2(time) + (Loop2(time)*[0.6,0.7]) // approximately
// So when we substitute this back into the difference equation we end up with 
DeltaTimeDifference approximately = (Loop2(time) + (Loop2(time)*[0.6,0.7])) - Loop2(time)
// And finally we can simplify this to
DeltaTimeDifference approximately = [0.6,0.7]*(Loop2(time)

そして、この近似は、ソフトウェア最適化と機械命令を含むアルゴリズムと機械操作の両方におけるこれら2つのループの平均差である。したがって、データセットが線形に増加すると、その2つの間の時間差も変化します。アルゴリズム1は、とき明らかであるアルゴリズム2よりも多くのフェッチを持ってBossいたが、前後の間の最大距離を移動するACアルゴリズム2インクルードをしながら、最初の反復の後にすべての反復のためにBossへの旅行をしていたA一度、その後に行われた後A、彼は旅していましたA〜に行くときに最大距離は1回だけCです。

それで、Boss2つの同様のことを一度に行い、同様の連続した仕事に焦点を当てるのではなく、前後にジャグリングすることに集中しようとすると、旅行と二倍の作業をしなければならないため、そのためボスの配偶者や子供たちがそれに感謝しないので、あなたの上司が補間されたボトルネックに入るようにして、状況の範囲を失うことはありません。







vectorization