c++ übungen for - Warum sind elementweise Ergänzungen in separaten Schleifen viel schneller als in einer kombinierten Schleife?





5 Answers

OK, die richtige Antwort hat definitiv etwas mit dem CPU-Cache zu tun. Die Verwendung des Cache-Arguments kann jedoch recht 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 unfair: Sie befand sich an einem sehr interessanten Punkt im Cache-Diagramm.

Die Antwort von Mysticial überzeugte viele Leute (einschließlich mich), wahrscheinlich weil es der einzige war, der sich auf Fakten stützte, aber es war nur ein "Datenpunkt" der Wahrheit.

Deshalb kombinierte ich seinen Test (mit einer kontinuierlichen vs. getrennten Zuordnung) und den @James's Answer-Hinweis.

Die nachstehenden Grafiken zeigen, dass die meisten Antworten und vor allem die meisten Kommentare zu den Fragen und Antworten als völlig falsch oder wahr betrachtet werden können, abhängig vom genauen Szenario und den verwendeten Parametern.

Beachten Sie, dass meine ursprüngliche Frage bei n = 100.000 lag . Dieser Punkt zeigt (durch Zufall) ein besonderes Verhalten:

  1. Es weist die größte Diskrepanz zwischen der Ein-und Zwei-Schleife-Version auf (fast ein Faktor von drei).

  2. Es ist der einzige Punkt, an dem eine Schleife (dh mit kontinuierlicher Zuordnung) die Zwei-Schleifen-Version übertrifft. (Dies machte die Antwort von Mysticial überhaupt möglich.)

Das Ergebnis mit initialisierten Daten:

Das Ergebnis unter Verwendung nicht initialisierter Daten (das hat Mysticial getestet):

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

Vorschlag

Jede leistungsbezogene Frage zu Stack Overflow sollte erforderlich sein, um MFLOPS-Informationen für den gesamten Bereich der Cache-relevanten Datengrößen bereitzustellen! Es ist eine Verschwendung von Zeit für jedermann, über Antworten nachzudenken und sie insbesondere mit anderen ohne diese Informationen zu diskutieren.

while

Angenommen, a1 , b1 , c1 und d1 verweisen auf Speicher, 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, habe ich den Code folgendermaßen geändert:

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 vollständiger Optimierung und aktiviertem SSE2 für 32-Bit auf einem Intel Core 2 Duo (x64), dauert das erste Beispiel 5,5 Sekunden und das Doppelschleifenbeispiel nur 1,9 Sekunden. Meine Frage ist: (Bitte unten auf meine umformulierte Frage verweisen)

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

Die Demontage für die erste Schleife sieht im Wesentlichen so aus (dieser Block wird im vollständigen 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 ungefähr 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

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

Könnten Sie einen fundierten Einblick in die Details geben, die zu den unterschiedlichen Cache-Verhalten führen, wie die fünf Regionen in der folgenden Grafik zeigen?

Es kann auch interessant sein, die Unterschiede zwischen CPU- / Cache-Architekturen hervorzuheben, indem ein ähnlicher Graph für diese CPUs bereitgestellt wird.

PPS: Hier ist der vollständige Code. Es verwendet TBB Tick_Count für ein Timing mit höherer Auflösung, das deaktiviert werden kann, wenn das TBB_TIMING Makro 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 .)




Stellen Sie sich vor, Sie arbeiten an einem Computer, auf dem n genau der richtige Wert war, um nur zwei Ihrer Arrays gleichzeitig im Speicher zu halten, aber der gesamte verfügbare Speicherplatz über das Zwischenspeichern von Festplatten reichte noch für alle vier aus.

Unter der Annahme einer einfachen LIFO-Caching-Richtlinie gilt Folgendes:

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

würde zuerst bewirken, dass a und b in den RAM geladen werden und dann vollständig im RAM bearbeitet werden. Wenn die zweite Schleife startet, werden c und d dann von der Festplatte 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 jedes Mal um die Schleife zwei Arrays und eine Seite in den anderen beiden aus. Das wäre natürlich viel langsamer.

In den Tests sehen Sie wahrscheinlich keine Datenträger-Zwischenspeicherung, wahrscheinlich aber auch die Nebenwirkungen einer anderen Form des Zwischenspeicherung.

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

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

Unter der Annahme einer ziemlich dummen Zwischenspeicherungsrichtlinie, falls sich das Byte nicht im Cache befindet, legen Sie es dort ab und holen Sie sich das folgende Byte, während wir gerade dabei sind. Sie erhalten ein Szenario wie das Folgende :

  • Mit

    for(int j=0;j<n;j++){
     a[j] += b[j];
    }
    for(int j=0;j<n;j++){
     c[j] += d[j];
    }
    
  • a[0] und a[1] dann b[0] und b[1] und a[0] = a[0] + b[0] im Cache setzen - jetzt sind 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 dies 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];
    }
    
  • a[0] und a[1] dann b[0] und b[1] und a[0] = a[0] + b[0] im Cache setzen - jetzt sind vier Bytes im Cache, a[0], a[1] und b[0], b[1] . Kosten = 100 + 100.

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

Dies ist ein klassisches Cache-Thrash-Szenario.




Ich kann die hier diskutierten Ergebnisse nicht replizieren.

Ich weiß nicht, ob ein schlechter Benchmark-Code Schuld ist oder was, aber die beiden Methoden liegen auf meinem Computer innerhalb von 10%, wobei der folgende Code verwendet wird, und eine Schleife ist normalerweise etwas schneller als zwei - wie Sie es tun würden erwarten von.

Die Arraygrößen reichten von 2 ^ 16 bis 2 ^ 24 mit acht Schleifen. Ich habe die Quell-Arrays sorgfältig initialisiert, sodass die += -Umgabe die FPU nicht aufforderte, Speicherbereinigung hinzuzufügen, die als Double interpretiert wird.

Ich habe mit verschiedenen Schemata InitToZero[j] , zum Beispiel 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 zu erwarten, hat die Initialisierung von b und d innerhalb der Schleife mit InitToZero[j] dem kombinierten Ansatz einen Vorteil verschafft, da diese vor den Zuweisungen zu a und c InitToZero[j] wurden, jedoch immer noch innerhalb von 10%. Stelle dir das vor.

Hardware ist Dell XPS 8500 mit der Generation 3 Core i7 bei 3,4 GHz und 8 GB Arbeitsspeicher. Bei 2 ^ 16 bis 2 ^ 24 betrug die kumulative Zeit bei Verwendung von acht Schleifen 44.987 bzw. 40.965. Visual C ++ 2010, vollständig optimiert.

PS: Ich habe die Schleifen geändert, um auf null herunterzuzählen, und die kombinierte Methode war geringfügig schneller. Ich kratzte mich am Kopf. Beachten Sie die neuen Arraygrößen und Schleifenzahlen.

// 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 nicht sicher, warum entschieden wurde, dass MFLOPS eine relevante Messgröße ist. Die Idee bestand zwar darauf, sich auf Speicherzugriffe zu konzentrieren, also versuchte ich, die Dauer der Gleitkomma-Rechenzeit zu minimieren. Ich bin im += gegangen, aber ich weiß nicht warum.

Eine direkte Zuordnung ohne Berechnung wäre ein sauberer Test der Speicherzugriffszeit und würde einen Test erzeugen, der unabhängig von der Schleifenanzahl einheitlich ist. Vielleicht habe ich im Gespräch etwas verpasst, aber es lohnt sich, darüber nachzudenken. Wenn das Plus nicht in der Zuordnung enthalten ist, ist die kumulierte Zeit mit jeweils 31 Sekunden nahezu identisch.




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

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




Es kann altes C ++ und Optimierungen sein. Auf meinem Computer habe ich fast die gleiche Geschwindigkeit erreicht:

Eine Schleife: 1,577 ms

Zwei Schleifen: 1,507 ms

Ich verwende Visual Studio 2015 auf einem E5-1620-Prozessor mit 3,5 GHz und 16 GB RAM.




Related