[c++] Warum sind elementweise Additionen in separaten Schleifen viel schneller als in einer kombinierten Schleife?


3 Answers

OK, die richtige Antwort muss definitiv etwas mit dem CPU-Cache machen. Die Verwendung des Cache-Arguments kann jedoch sehr schwierig sein, insbesondere ohne Daten.

Es gibt viele Antworten, die zu vielen Diskussionen führten, aber seien wir ehrlich: Cache-Probleme können sehr komplex sein und sind nicht eindimensional. Sie hängen stark von der Größe der Daten ab, daher war meine Frage ungerecht: Es stellte sich heraus, dass es sich um einen sehr interessanten Punkt im Cache-Diagramm handelte.

@ Mysticials Antwort hat eine Menge Leute (einschließlich mir) überzeugt, wahrscheinlich weil sie die einzige war, die sich auf Fakten zu verlassen schien, aber es war nur ein "Datenpunkt" der Wahrheit.

Deshalb habe ich seinen Test (mit einer kontinuierlichen vs. separaten Zuweisung) und den Rat von @James 'Antwort kombiniert.

Die folgenden Grafiken zeigen, dass die meisten Antworten und insbesondere die meisten Kommentare zu den Fragen und Antworten je nach dem verwendeten Szenario und den verwendeten Parametern als völlig falsch oder wahr angesehen werden können.

Beachten Sie, dass meine erste Frage bei n = 100.000 war . Dieser Punkt weist (aus Versehen) ein besonderes Verhalten auf:

  1. Es besitzt die größte Diskrepanz zwischen der ein und zwei Loop-Version (fast ein Faktor von drei)

  2. Es ist der einzige Punkt, an dem eine Schleife (nämlich mit kontinuierlicher Zuweisung) die Zwei-Schleifen-Version schlägt. (Dies machte Mysticials Antwort überhaupt möglich.)

Das Ergebnis mit initialisierten Daten:

Das Ergebnis mit nicht initialisierten Daten (das hat Mysticial getestet):

Und das ist schwer zu erklären: Initialisierte Daten, die einmal zugewiesen und für jeden folgenden Testfall mit unterschiedlicher Vektorgröße wiederverwendet werden:

Vorschlag

Jede Low-Level-Performance-Frage zu Stack Overflow sollte erforderlich sein, um MFLOPS-Informationen für die gesamte Bandbreite cache-relevanter Datengrößen bereitzustellen! Es ist eine Verschwendung aller Zeit, an Antworten zu denken und sie mit anderen ohne diese Informationen zu besprechen.

Question

Angenommen, a1 , b1 , c1 und d1 zeigen auf den Heapspeicher und mein numerischer Code hat die folgende Kernschleife.

const int n = 100000;

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

Diese Schleife wird 10.000 mal über eine andere äußere for Schleife ausgeführt. Um es zu beschleunigen, änderte ich den Code zu:

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

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

Kompiliert auf MS Visual C ++ 10.0 mit voller Optimierung und SSE2 aktiviert für 32-Bit auf einem Intel Core 2 Duo (x64), dauert das erste Beispiel 5,5 Sekunden und das Doppel-Loop-Beispiel dauert nur 1,9 Sekunden. Meine Frage ist: (Bitte beziehen Sie sich auf die umformulierte Frage unten)

PS: Ich bin mir nicht sicher, ob das hilft:

Die Demontage für die erste Schleife sieht grundsätzlich so aus (dieser Block wird im vollen Programm etwa fünfmal wiederholt):

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]

Jede Schleife des Doppelschleifenbeispiels erzeugt diesen Code (der folgende Block wird etwa dreimal wiederholt):

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

EDIT: Die Frage stellte sich als nicht relevant heraus, da das Verhalten stark von der Größe der Arrays (n) und dem CPU-Cache abhängt. Wenn es also weiteres Interesse gibt, formuliere ich die Frage:

Können Sie einen guten Einblick in die Details geben, die zu den verschiedenen Cache-Verhaltensweisen führen, wie die fünf Regionen in der folgenden Grafik zeigen?

Es könnte auch interessant sein, die Unterschiede zwischen CPU- / Cache-Architekturen aufzuzeigen, indem ein ähnliches Diagramm für diese CPUs bereitgestellt wird.

PPS: Hier ist der vollständige Code. Es verwendet TBB Tick_Count für eine höhere Zeitauflösung, die deaktiviert werden kann, indem das Makro TBB_TIMING nicht definiert wird:

#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;
    }
}

(Es zeigt FLOP / s für verschiedene Werte von n .)




Die erste Schleife wechselt das Schreiben in jede Variable. Die zweite und dritte machen nur kleine Sprünge der Elementgröße.

Versuchen Sie, zwei parallele Linien von 20 Kreuzen mit einem Stift und Papier zu schreiben, die durch 20 cm getrennt sind. Versuchen Sie einmal, die eine und dann die andere Zeile zu beenden und versuchen Sie es erneut, indem Sie abwechselnd in jede Zeile ein Kreuz schreiben.




Stellen Sie sich vor, Sie arbeiten an einem Rechner, auf dem n genau der richtige Wert ist, um nur zwei Ihrer Arrays gleichzeitig im Speicher zu halten, aber der verfügbare Gesamtspeicher über das Festplatten-Caching war immer noch ausreichend, um alle vier zu halten.

Unter der Annahme einer einfachen LIFO-Caching-Richtlinie lautet dieser Code:

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

würde zunächst bewirken, dass a und b in den RAM geladen werden und dann vollständig im RAM bearbeitet werden. Wenn die zweite Schleife beginnt, werden c und d dann von der Platte in den RAM geladen und bearbeitet.

die andere Schleife

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

blättert zwei Arrays aus und blättert jedes Mal um die Schleife in den anderen zwei. Dies wäre offensichtlich viel langsamer.

Sie werden in Ihren Tests wahrscheinlich kein Festplatten-Caching sehen, aber Sie sehen wahrscheinlich die Nebenwirkungen einer anderen Art von Caching.

Es scheint hier ein wenig Verwirrung / Missverständnis zu geben, also werde ich versuchen, ein wenig anhand eines Beispiels zu erläutern.

Sagen wir n = 2 und wir arbeiten mit Bytes. In meinem Szenario haben wir also nur 4 Bytes Cache und der Rest unseres Speichers ist deutlich langsamer (sagen wir mal 100 mal länger).

Angenommen, eine ziemlich dumme Caching-Policy von, wenn das Byte nicht im Cache ist, legen Sie es dort und erhalten Sie das folgende Byte auch, während wir dabei sind, erhalten Sie ein Szenario etwa so:

  • Mit

    for(int j=0;j<n;j++){
     a[j] += b[j];
    }
    for(int j=0;j<n;j++){
     c[j] += d[j];
    }
    
  • cache a[0] und a[1] dann b[0] und b[1] und setze a[0] = a[0] + b[0] im Cache - es gibt jetzt vier Bytes im Cache, a[0], a[1] und b[0], b[1] . Kosten = 100 + 100.

  • setze a[1] = a[1] + b[1] im Cache. Kosten = 1 + 1.
  • Wiederholen Sie für c und d .
  • Gesamtkosten = (100 + 100 + 1 + 1) * 2 = 404

  • Mit

    for(int j=0;j<n;j++){
     a[j] += b[j];
     c[j] += d[j];
    }
    
  • cache a[0] und a[1] dann b[0] und b[1] und setze a[0] = a[0] + b[0] im Cache - es gibt jetzt vier Bytes im Cache, a[0], a[1] und b[0], b[1] . Kosten = 100 + 100.

  • Werfen Sie a[0], a[1], b[0], b[1] aus dem Cache aus und cachen Sie c[0] und c[1] dann d[0] und d[1] und setzen Sie c[0] = c[0] + d[0] im Cache. Kosten = 100 + 100.
  • Ich vermute, Sie fangen an zu sehen, wohin ich gehe.
  • Gesamtkosten = (100 + 100 + 100 + 100) * 2 = 800

Dies ist ein klassisches Cache-Thrash-Szenario.




Ich kann die hier besprochenen Ergebnisse nicht replizieren.

Ich weiß nicht, ob schlechter Benchmark-Code schuld ist, oder was, aber die beiden Methoden sind innerhalb von 10% voneinander auf meinem Computer mit dem folgenden Code, und eine Schleife ist normalerweise nur etwas schneller als zwei - wie Sie würden erwarten von.

Array-Größen reichten von 2 ^ 16 bis 2 ^ 24, acht Schleifen verwendend. Ich war vorsichtig, um die Quell-Arrays zu initialisieren, so dass die += Zuweisung die FPU nicht aufforderte, Speichermüll hinzuzufügen, der als Doppel interpretiert wurde.

Ich habe mit verschiedenen Schemata InitToZero[j] wie InitToZero[j] die Zuweisung von b[j] , d[j] zu InitToZero[j] innerhalb der Schleifen und auch mit += b[j] = 1 und += d[j] = 1 , und ich habe ziemlich konsistente Ergebnisse erhalten.

Wie Sie vielleicht erwarten, hat die Initialisierung von b und d innerhalb der Schleife mit InitToZero[j] den kombinierten Ansatz zu einem Vorteil gemacht, da sie Rücken an Rücken vor den Zuweisungen zu a und c , aber immer noch innerhalb von 10%. Stelle dir das vor.

Hardware ist Dell XPS 8500 mit Generation 3 Core i7 @ 3,4 GHz und 8 GB Speicher. Für 2 ^ 16 bis 2 ^ 24, unter Verwendung von acht Schleifen, betrug die kumulative Zeit 44,987 bzw. 40,965. Visual C ++ 2010, vollständig optimiert.

PS: Ich habe die Loops geändert, um auf Null zu zählen, und die kombinierte Methode war marginal schneller. Ich kratze meinen Kopf. Beachten Sie die neuen Array-Größen und Schleifenzählungen.

// 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;
}

Ich bin mir nicht sicher, warum MFLOPS eine relevante Messgröße war. Ich dachte mir, dass ich mich auf Speicherzugriffe konzentrieren sollte, also habe ich versucht, die Berechnungszeit für Gleitkommazahlen zu minimieren. Ich bin in der += , aber ich bin mir nicht sicher warum.

Eine direkte Zuweisung ohne Berechnung wäre ein saubererer Test der Speicherzugriffszeit und würde einen Test erzeugen, der unabhängig von der Schleifenzählung einheitlich ist. Vielleicht habe ich etwas im Gespräch verpasst, aber es lohnt sich, zweimal darüber nachzudenken. Wenn das Plus nicht in der Zuweisung ist, ist die kumulative Zeit fast identisch mit jeweils 31 Sekunden.




Related