Nehmen wir an a1, b1, c1und d1Punkt Heapspeicher und meine numerischen Code hat den folgenden 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 forSchleife ausgeführt. Um es zu beschleunigen, habe ich den Code geändert in:

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

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

Kompiliert unter 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 Beispiel mit doppelter Schleife nur 1,9 Sekunden. Meine Frage ist: (Bitte beziehen Sie sich auf meine umformulierte Frage unten)

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 stellte sich als nicht relevant heraus, da das Verhalten stark von der Größe der Arrays (n) und des CPU-Cache abhängt. Wenn also weiteres Interesse besteht, formuliere ich die Frage neu:

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

Es könnte auch interessant sein, auf die Unterschiede zwischen CPU / Cache-Architekturen hinzuweisen, indem ein ähnliches Diagramm 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, indem das TBB_TIMINGMakro 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.)

Nach weiterer Analyse glaube ich, dass dies (zumindest teilweise) durch die Datenausrichtung der vier Zeiger verursacht wird. Dies führt zu Konflikten zwischen Cache-Bank und Weg.

Wenn ich richtig geraten habe, wie Sie Ihre Arrays zuordnen, werden sie wahrscheinlich an der Seitenlinie ausgerichtet .

Dies bedeutet, dass alle Ihre Zugriffe in jeder Schleife auf den gleichen Cache-Weg fallen. Intel-Prozessoren haben jedoch seit einiger Zeit eine 8-Wege-L1-Cache-Assoziativität. In Wirklichkeit ist die Leistung jedoch nicht ganz einheitlich. Der Zugriff auf 4-Wege ist immer noch langsamer als etwa 2-Wege.

BEARBEITEN: Es sieht tatsächlich so aus, als würden Sie alle Arrays separat zuweisen. Wenn so große Zuordnungen angefordert werden, fordert der Zuweiser normalerweise neue Seiten vom Betriebssystem an. Daher besteht eine hohe Wahrscheinlichkeit, dass große Zuordnungen im gleichen Versatz von einer Seitengrenze angezeigt werden.

Hier ist der Testcode:

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

Benchmark-Ergebnisse:

BEARBEITEN: Ergebnisse auf einer tatsächlichen Core 2-Architekturmaschine:

2 x Intel Xeon X5482 Harpertown bei 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

Beobachtungen:

• 6,206 Sekunden mit einer Schleife und 2,116 Sekunden mit zwei Schleifen. Dies gibt die Ergebnisse des OP genau wieder.

• In den ersten beiden Tests werden die Arrays separat zugeordnet. Sie werden feststellen, dass alle relativ zur Seite dieselbe Ausrichtung haben.

• In den zweiten beiden Tests werden die Arrays zusammengepackt, um diese Ausrichtung zu unterbrechen. Hier werden Sie feststellen, dass beide Schleifen schneller sind. Außerdem ist die zweite (Doppel-) Schleife jetzt die langsamere, wie Sie es normalerweise erwarten würden.

Wie @Stephen Cannon in den Kommentaren hervorhebt, besteht sehr wahrscheinlich die Möglichkeit, dass diese Ausrichtung zu falschem Aliasing in den Lade- / Speichereinheiten oder im Cache führt. Ich habe danach gegoogelt und festgestellt, dass Intel tatsächlich einen Hardware-Zähler für teilweise Adress-Aliasing- Stalls hat:

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

5 Regionen - Erklärungen

Region 1:

Dieser ist einfach. Der Datensatz ist so klein, dass die Leistung von Overhead wie Schleifen und Verzweigungen dominiert wird.

Region 2:

Hier nimmt mit zunehmender Datengröße der relative Overhead ab und die Leistung "sättigt" sich. Hier sind zwei Schleifen langsamer, weil sie doppelt so viel Schleifen- und Verzweigungsaufwand haben.

Ich bin mir nicht sicher, was genau hier vor sich geht ... Die Ausrichtung könnte immer noch einen Effekt haben, da Agner Fog Konflikte zwischen Cache-Banken erwähnt . (Dieser Link handelt von Sandy Bridge, aber die Idee sollte weiterhin auf Core 2 anwendbar sein.)

Region 3:

Zu diesem Zeitpunkt passen die Daten nicht mehr in den L1-Cache. Die Leistung wird also durch die Cache-Bandbreite von L1 <-> L2 begrenzt.

Region 4:

Der Leistungsabfall in der Einzelschleife ist das, was wir beobachten. Und wie bereits erwähnt, ist dies auf die Ausrichtung zurückzuführen, die (höchstwahrscheinlich) zu falschen Aliasing- Verzögerungen in den Prozessorlade- / Speichereinheiten führt.

Damit jedoch ein falsches Aliasing auftritt, muss zwischen den Datensätzen ein ausreichend großer Schritt vorhanden sein. Aus diesem Grund sehen Sie dies in Region 3 nicht.

Region 5:

Zu diesem Zeitpunkt passt nichts in den Cache. Sie sind also an die Speicherbandbreite gebunden.

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

Es gibt viele Antworten, die zu vielen Diskussionen geführt haben, 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: Es stellte sich heraus, dass sie sich an einem sehr interessanten Punkt im Cache-Diagramm befand.

Die Antwort von @ Mysticial überzeugte viele Menschen (einschließlich mich), wahrscheinlich weil es das einzige war, das sich auf Fakten zu stützen schien, aber es war nur ein "Datenpunkt" der Wahrheit.

Deshalb habe ich seinen Test (unter Verwendung einer kontinuierlichen oder getrennten Zuordnung) und den Rat von @James 'Answer kombiniert.

Die folgenden Grafiken zeigen, dass die meisten Antworten und insbesondere die meisten Kommentare zu Fragen und Antworten je nach dem genauen 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 zeigt (aus Versehen) ein besonderes Verhalten:

1. Es weist die größte Diskrepanz zwischen der Version mit einer und zwei Schleifen auf (fast ein Faktor von drei).

2. Dies ist der einzige Punkt, an dem One-Loop (nämlich mit kontinuierlicher Zuordnung) die Two-Loop-Version schlägt. (Dies machte die Antwort von Mysticial überhaupt möglich.)

Das Ergebnis mit initialisierten Daten:

Das Ergebnis unter Verwendung nicht initialisierter Daten (dies wurde von Mysticial getestet):

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

Vorschlag

Jede leistungsbezogene Frage auf niedriger Ebene zum Stapelüberlauf sollte erforderlich sein, um MFLOPS-Informationen für den gesamten Bereich der cache-relevanten Datengrößen bereitzustellen! Es ist Zeitverschwendung, über Antworten nachzudenken und sie insbesondere mit anderen ohne diese Informationen zu diskutieren.

Die zweite Schleife beinhaltet viel weniger Cache-Aktivität, so dass der Prozessor leichter mit den Speicheranforderungen Schritt halten kann.

Stellen Sie sich vor, Sie arbeiten an einer Maschine, auf der n genau der richtige Wert vorhanden war, um nur zwei Ihrer Arrays gleichzeitig im Speicher zu halten, aber der über das Festplatten-Caching verfügbare Gesamtspeicher reichte immer noch aus, um alle vier zu speichern.

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 zuerst verursachen aund bin den RAM geladen und dann vollständig im RAM bearbeitet werden. Wenn die zweite Schleife beginnt, cundd dann von der Festplatte in den RAM geladen und bearbeitet wird.

die andere Schleife

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

löscht zwei Arrays und die anderen beiden jedes Mal um die Schleife herum ausblenden . Dies wäre offensichtlich viel langsamer.

Wahrscheinlich sehen Sie in Ihren Tests kein Festplatten-Caching, aber Sie sehen wahrscheinlich die Nebenwirkungen einer anderen Form des Caching.

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

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

Unter der Annahme einer ziemlich dummen Caching-Richtlinie, ob sich das Byte nicht im Cache befindet, legen Sie es dort ab und holen Sie sich auch 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];
  }

• Cache a[0]und a[1]dann b[0]und b[1]und a[0] = a[0] + b[0]in Cache gesetzt - es gibt jetzt vier Bytes im Cache,a[0], a[1] und b[0], b[1]. Kosten = 100 + 100.

• einstellen a[1] = a[1] + b[1] in Cache. Kosten = 1 + 1.
• Wiederholen 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 a[0] = a[0] + b[0]in Cache gesetzt - es gibt jetzt 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 auswerfen c[0]und c[1]dann d[0]und d[1]und setzenc[0] = c[0] + d[0] in Cache setzen. 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.

Dies liegt nicht an einem anderen Code, sondern am Caching: RAM ist langsamer als die CPU-Register und ein Cache-Speicher befindet sich in der CPU, um zu vermeiden, dass der RAM jedes Mal geschrieben wird, wenn sich eine Variable ändert. Der Cache ist jedoch nicht so groß wie der RAM, daher wird nur ein Bruchteil davon zugeordnet.

Der erste Code ändert entfernte Speicheradressen, die sie in jeder Schleife abwechseln, und erfordert daher eine kontinuierliche Ungültigmachung des Caches.

Der zweite Code wechselt nicht: Er fließt nur zweimal auf benachbarte Adressen. Dadurch wird der gesamte Auftrag im Cache abgeschlossen und erst nach dem Start der zweiten Schleife ungültig.

Ich kann die hier diskutierten Ergebnisse nicht replizieren.

Ich weiß nicht, ob schlechter Benchmark-Code schuld ist oder was, aber die beiden Methoden liegen auf meinem Computer mit dem folgenden Code innerhalb von 10% voneinander, und eine Schleife ist normalerweise nur geringfügig schneller als zwei - wie Sie es möchten erwarten von.

Die Arraygrößen lagen zwischen 2 ^ 16 und 2 ^ 24 unter Verwendung von acht Schleifen. Ich habe sorgfältig darauf geachtet, die Quell-Arrays zu initialisieren +=, damit die FPU bei der Zuweisung nicht aufgefordert wurde , Speichermüll hinzuzufügen, der als Double interpretiert wird.

Ich habe mit verschiedenen Schemata herumgespielt, z. B. mit der Zuordnung von b[j], d[j]zu InitToZero[j]innerhalb der Schleifen und auch mit += b[j] = 1und += d[j] = 1, und ich habe ziemlich konsistente Ergebnisse erzielt.

Wie zu erwarten war, verschaffte die Initialisierung bund ddie Verwendung innerhalb der Schleife InitToZero[j]dem kombinierten Ansatz einen Vorteil, da sie vor den Zuweisungen an aund hintereinander durchgeführt wurden c, jedoch immer noch innerhalb von 10%. Stelle dir das vor.

Hardware ist Dell XPS 8500 mit Core i7 der 3. Generation bei 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 Schleifen so geändert, dass sie auf Null herunterzählen, und die kombinierte Methode war geringfügig schneller. Ich kratzte mir am Kopf. Beachten Sie die neue Arraygröße und die Anzahl der Schleifen.

// 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 entschieden wurde, dass MFLOPS eine relevante Metrik ist. Ich dachte, die Idee war, sich auf Speicherzugriffe zu konzentrieren, also habe ich versucht, die Rechenzeit für Gleitkommazahlen zu minimieren. Ich bin in der +=, aber ich bin nicht sicher warum.

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

Dies liegt daran, dass die CPU nicht so viele Cache-Fehler aufweist (wo sie warten muss, bis die Array-Daten von den RAM-Chips stammen). Es wäre interessant für Sie, die Größe der Arrays kontinuierlich anzupassen, damit Sie die Größe der Arrays überschreiten Level 1-Cache (L1) und dann des Level 2-Cache (L2) Ihrer CPU und die für Ihren Code benötigte Zeit zeichnen gegen die Größe der Arrays ausführen. Das Diagramm sollte keine gerade Linie sein, wie Sie es erwarten würden.

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

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

Die ursprüngliche Frage

Warum ist eine Schleife so viel langsamer als zwei Schleifen?

Fazit:

Fall 1 ist ein klassisches Interpolationsproblem, das zufällig ineffizient ist. Ich denke auch, dass dies einer der Hauptgründe war, warum viele Maschinenarchitekturen und Entwickler Multi-Core-Systeme mit der Fähigkeit zum Erstellen und Entwerfen von Multithread-Anwendungen sowie zur parallelen Programmierung erstellt und entworfen haben.

Betrachten Sie es von einem solchen Ansatz aus, ohne zu berücksichtigen, wie Hardware, Betriebssystem und Compiler zusammenarbeiten, um Heap-Zuweisungen vorzunehmen, die das Arbeiten mit RAM, Cache, Auslagerungsdateien usw. umfassen. Die Mathematik, die diesen Algorithmen zugrunde liegt, zeigt uns, welche dieser beiden die bessere Lösung ist.

Wir können eine Analogie eines BossWesens verwenden Summation, das ein Wesen darstellt For Loop, das zwischen Arbeitern Aund Menschen reisen muss B.

Wir können leicht erkennen, dass Fall 2 mindestens halb so schnell ist, wenn nicht etwas mehr als Fall 1, da sich die für die Reise erforderliche Entfernung und die zwischen den Arbeitern benötigte Zeit unterscheiden. Diese Mathematik stimmt fast virtuell und perfekt sowohl mit der BenchMark Times als auch mit der Anzahl der Unterschiede in der Montageanleitung überein.

Ich werde jetzt unten erklären, wie das alles funktioniert.

Bewertung des Problems

Der OP-Code:

const int n=100000;

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

Und

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

Die Überlegung

In Anbetracht der ursprünglichen Frage des OP zu den beiden Varianten der for-Schleifen und seiner geänderten Frage zum Verhalten von Caches zusammen mit vielen anderen hervorragenden Antworten und nützlichen Kommentaren; Ich möchte versuchen, hier etwas anderes zu tun, indem ich diese Situation und dieses Problem anders betrachte.

Die Vorgehensweise

In Anbetracht der beiden Schleifen und der gesamten Diskussion über Cache- und Seitenablage möchte ich einen anderen Ansatz wählen, um dies aus einer anderen Perspektive zu betrachten. Bei einem Ansatz, bei dem weder der Cache und die Auslagerungsdateien noch die Ausführungen zum Zuweisen von Speicher erforderlich sind, betrifft dieser Ansatz überhaupt nicht die eigentliche Hardware oder Software.

Die Perspektive

Nachdem man sich den Code eine Weile angesehen hatte, wurde ziemlich deutlich, was das Problem ist und was es erzeugt. Lassen Sie uns dies in ein algorithmisches Problem zerlegen und es aus der Perspektive der Verwendung mathematischer Notationen betrachten und dann eine Analogie auf die mathematischen Probleme sowie auf die Algorithmen anwenden.

Was wir wissen

Wir wissen, dass diese Schleife 100.000 Mal ausgeführt wird. Wir wissen auch , dass a1, b1, c1& d1sind Zeiger auf einer 64-Bit - Architektur. In C ++ auf einem 32-Bit-Computer sind alle Zeiger 4 Byte und auf einem 64-Bit-Computer 8 Byte groß, da Zeiger eine feste Länge haben.

Wir wissen, dass wir in beiden Fällen 32 Bytes zuweisen müssen. Der einzige Unterschied besteht darin, dass wir jeder Iteration 32 Bytes oder 2 Sätze von 2-8 Bytes zuweisen, wobei wir im zweiten Fall 16 Bytes für jede Iteration für beide unabhängigen Schleifen zuweisen.

Beide Schleifen entsprechen immer noch 32 Bytes in der Gesamtzuweisung. Mit diesen Informationen wollen wir nun die allgemeine Mathematik, die Algorithmen und die Analogie dieser Konzepte zeigen.

Wir wissen, wie oft dieselbe Gruppe oder Gruppe von Operationen in beiden Fällen ausgeführt werden muss. Wir kennen die Speichermenge, die in beiden Fällen zugewiesen werden muss. Wir können davon ausgehen, dass die Gesamtarbeitsbelastung der Zuweisungen zwischen beiden Fällen ungefähr gleich sein wird.

Was wir nicht wissen

Wir wissen nicht, wie lange es für jeden Fall dauern wird, es sei denn, wir setzen einen Zähler und führen einen Benchmark-Test durch. Die Benchmarks wurden jedoch bereits aus der ursprünglichen Frage sowie aus einigen Antworten und Kommentaren aufgenommen. und wir können einen signifikanten Unterschied zwischen den beiden sehen und dies ist die ganze Begründung für diesen Vorschlag zu diesem Problem.

Lassen Sie uns untersuchen

Es ist bereits offensichtlich, dass viele dies bereits getan haben, indem sie sich die Heap-Zuordnungen, Benchmark-Tests, RAM, Cache und Auslagerungsdateien angesehen haben. Das Betrachten spezifischer Datenpunkte und spezifischer Iterationsindizes wurde ebenfalls aufgenommen, und die verschiedenen Gespräche über dieses spezifische Problem haben viele Leute dazu gebracht, andere verwandte Dinge darüber in Frage zu stellen. Wie fangen wir an, dieses Problem zu betrachten, indem wir mathematische Algorithmen verwenden und eine Analogie darauf anwenden? Wir beginnen mit ein paar Aussagen! Dann bauen wir von dort aus unseren Algorithmus aus.

Unsere Behauptungen:

• Wir lassen unsere Schleife und ihre Iterationen eine Summation sein, die bei 1 beginnt und bei 100000 endet, anstatt wie in den Schleifen mit 0 zu beginnen, da wir uns nicht um das 0-Indizierungsschema der Speicheradressierung kümmern müssen, da wir nur daran interessiert sind der Algorithmus selbst.
• In beiden Fällen müssen 4 Funktionen bearbeitet und 2 Funktionsaufrufe ausgeführt werden, wobei für jeden Funktionsaufruf 2 Operationen ausgeführt werden. Wir werden diese nach oben als Funktionen und Aufrufe von Funktionen wie die folgenden Satz: F1(), F2(), f(a), f(b), f(c)und f(d).

Die Algorithmen:

1. Fall: - Nur eine Summation, aber zwei unabhängige Funktionsaufrufe.

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

2. Fall: - Zwei Summierungen, aber jede hat ihren eigenen Funktionsaufruf.

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

Wenn Sie bemerkt haben F2(), existiert nur in Sumvon Case1wo F1()ist in Sumvon Case1und in beiden Sum1und Sum2von enthalten Case2. Dies wird später deutlich, wenn wir zu dem Schluss kommen, dass innerhalb des zweiten Algorithmus eine Optimierung stattfindet.

Die Iterationen durch die ersten SumFallaufrufe f(a), die sich selbst hinzufügen, rufen f(b)dann auff(c) , die dasselbe tun f(d), sich jedoch für jede 100000Iteration selbst hinzufügen . Im zweiten Fall haben wir Sum1und Sum2dass beide dasselbe tun , als ob sie dieselbe Funktion wären, die zweimal hintereinander aufgerufen wird.

In diesem Fall können wir behandeln Sum1und Sum2als einfach alt SumwoSum in diesem Fall so aussieht: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }und jetzt sieht dies wie eine Optimierung aus, bei der wir es einfach als dieselbe Funktion betrachten können.

Zusammenfassung mit Analogie

Mit dem, was wir im zweiten Fall gesehen haben, scheint es fast so, als ob es eine Optimierung gibt, da beide for-Schleifen dieselbe exakte Signatur haben, aber dies ist nicht das eigentliche Problem. Das Problem ist nicht die Arbeit, die von erledigt wird f(a),f(b) , f(c), und f(d). In beiden Fällen und beim Vergleich zwischen beiden ist es der Unterschied in der Entfernung, die die Summation jeweils zurücklegen muss, der den Unterschied in der Ausführungszeit ergibt.

Denken Sie an den For Loopsals das Wesen Summations, das die Iterationen tut als ein Wesen , Bossdie Aufträge zu zwei Personen geben Aund Bund dass ihre Arbeitsplätze sind Fleisch Cund Djeweils und abholen einige Pakete von ihnen und gibt es zurück. In dieser Analogie repräsentieren die for-Schleifen oder Summationsiterationen und Bedingungsprüfungen selbst nicht die Boss. Was das tatsächlich darstellt, Bossist nicht direkt aus den tatsächlichen mathematischen Algorithmen, sondern aus dem tatsächlichen Konzept Scopeund Code Blockinnerhalb einer Routine oder Unterroutine, Methode, Funktion, Übersetzungseinheit usw. Der erste Algorithmus hat 1 Bereich, wobei der zweite Algorithmus 2 aufeinanderfolgende Bereiche hat.

Im ersten Fall auf jedem Anrufzettel Bossgeht der zu Aund gibt den Befehl und Ageht los, um das B'sPaket abzurufen , dann Bossgeht der zu Cund gibt den Befehl, dasselbe zu tun und das Paket Dbei jeder Iteration zu erhalten.

Im zweiten Fall arbeitet das Bossdirekt mit Adem Abrufen des B'sPakets, bis alle Pakete empfangen wurden. Dann Bossfunktioniert das mit C, um das Gleiche zu tun, um alle D'sPakete zu erhalten.

Da wir mit einem 8-Byte-Zeiger arbeiten und uns mit der Heap-Zuweisung befassen, betrachten wir das folgende Problem. Nehmen wir an, das Bossist 100 Fuß von Aund das Aist 500 Fuß von C. Wir brauchen uns wegen der Reihenfolge der Hinrichtungen keine Gedanken darüber zu machen, wie weit das Bossanfänglich entfernt ist C. In beiden Fällen Bossfährt der zunächst von Azuerst nach B. Diese Analogie soll nicht heißen, dass diese Entfernung genau ist; Es ist nur ein nützliches Testfallszenario, um die Funktionsweise der Algorithmen zu zeigen.

In vielen Fällen variieren diese Abstände zwischen Adresspositionen bei der Heap-Zuweisung und bei der Arbeit mit den Cache- und Auslagerungsdateien möglicherweise nicht so stark oder können je nach Art der Datentypen und Array-Größen erheblich variieren.

Die Testfälle:

Erster Fall: Bei der ersten IterationBossmuss der zunächst 100 Fuß gehen, um den Bestellschein zu geben,AundAgeht los und macht sein Ding, aber dannBossmuss er 500 Fuß zurücklegenC, um ihm seinen Bestellschein zu geben. Dann bei der nächsten Iteration und jeder zweiten Iteration nach demBoss muss 500 Fuß zwischen den beiden hin und her gehen.

Zweiter Fall: DerBossmuss bei der ersten Iteration 100 Fuß zurücklegenA, aber danach ist er bereits da und wartet nur daraufA, dass er zurückkommt, bis alle Belege gefüllt sind. DannBossmuss der 500 Fuß bei der ersten Iteration zurücklegen,Cweil erC500 Fuß entfernt istA. Da diesBoss( Summation, For Loop )direkt nach der Arbeit aufgerufen wird,Awartet er dort einfach so, wie er es getan hat,Abis alleC'sBestellscheine fertig sind.

Der Unterschied in den zurückgelegten Entfernungen

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;    

Der Vergleich beliebiger Werte

Wir können leicht erkennen, dass 600 weit weniger als 10 Millionen sind. Dies ist nicht genau, da wir den tatsächlichen Unterschied in der Entfernung zwischen der Adresse des RAM oder dem Cache oder der Auslagerungsdatei nicht kennen. Jeder Aufruf bei jeder Iteration wird auf viele andere unsichtbare Variablen zurückzuführen sein. Dies ist nur eine Einschätzung der Situation, die Sie im schlimmsten Fall kennen und betrachten müssen.

Aus diesen Zahlen scheint es fast so, als ob Algorithmus Eins 99%langsamer sein sollte als Algorithmus Zwei; Dies ist jedoch nur der Boss'sTeil oder die Verantwortung der Algorithmen und berücksichtigt nicht den tatsächlichen Arbeiter A, B, C, und Dund , was sie haben auf jedem und jede Iteration der Schleife zu tun. Die Arbeit des Chefs macht also nur etwa 15 - 40% der gesamten geleisteten Arbeit aus. Der Großteil der Arbeit, die von den Arbeitern erledigt wird, hat einen etwas größeren Einfluss darauf, das Verhältnis der Geschwindigkeitsratenunterschiede zu etwa 50-70% zu halten

Die Beobachtung: - Die Unterschiede zwischen den beiden Algorithmen

In dieser Situation ist es die Struktur des Arbeitsprozesses. Es zeigt sich, dass Fall 2 sowohl bei der teilweisen Optimierung einer ähnlichen Funktionsdeklaration als auch bei der Definition effizienter ist, wenn sich nur die Variablen nach Name und zurückgelegter Entfernung unterscheiden.

Wir sehen auch, dass die in Fall 1 zurückgelegte Gesamtstrecke viel weiter ist als in Fall 2, und wir können diese zurückgelegte Strecke als unseren Zeitfaktor zwischen den beiden Algorithmen betrachten. Fall 1 hat erheblich mehr Arbeit zu erledigen als Fall 2 .

Dies ist aus dem Nachweis der ASMAnweisungen ersichtlich, die in beiden Fällen gezeigt wurden. Zusammen mit dem, was bereits über diese Fälle erwähnt, ist dies zu berücksichtigen nicht die Tatsache , dass in Fall 1 der Chef wird für beide warten müssen Aund Czurück zu bekommen , bevor er zurück zu gehen , kann Awieder für jede Iteration. Es berücksichtigt auch nicht die Tatsache, dass, wenn Aoder wenn Bes extrem lange dauert, sowohl der Bossals auch die anderen Arbeiter untätig sind und darauf warten, ausgeführt zu werden.

In Fall 2 ist der einzige, der untätig ist, der, Bossbis der Arbeiter zurückkommt. Auch dies hat Auswirkungen auf den Algorithmus.

Die geänderten Fragen der OP

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

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

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

Zu diesen Fragen

Wie ich ohne Zweifel gezeigt habe, gibt es ein zugrunde liegendes Problem, noch bevor die Hardware und Software beteiligt werden.

Nun zur Verwaltung des Speichers und zum Zwischenspeichern zusammen mit Auslagerungsdateien usw., die alle in einem integrierten Satz von Systemen zusammenarbeiten, zwischen den folgenden:

• The Architecture {Hardware, Firmware, einige eingebettete Treiber, Kernel und ASM-Befehlssätze}.
• The OS{Datei- und Speicherverwaltungssysteme, Treiber und die Registrierung}.
• The Compiler {Übersetzungseinheiten und Optimierungen des Quellcodes}.
• Und sogar das sich Source Codeselbst mit seinen (n) markanten Algorithmen.

Wir können bereits sehen , dass es ein Engpass ist , die innerhalb des ersten Algorithmus geschehen , bevor wir es auch mit jeder beliebigen an jede Maschine gelten Architecture, OSund im Programmable LanguageVergleich zum zweiten Algorithmus. Es gab bereits ein Problem, bevor die Eigenschaften eines modernen Computers berücksichtigt wurden.

Die Endergebnisse

Jedoch; Es ist nicht zu sagen, dass diese neuen Fragen nicht von Bedeutung sind, weil sie selbst sind und schließlich eine Rolle spielen. Sie wirken sich auf die Verfahren und die Gesamtleistung aus. Dies wird anhand der verschiedenen Grafiken und Bewertungen von vielen deutlich, die ihre Antworten und / oder Kommentare abgegeben haben.

Wenn Sie die Aufmerksamkeit auf die Analogie des eingezahlten Bossund die beiden Arbeiter Aund Bdie mussten Pakete aus gehen und Abrufen C& Djeweils und unter Berücksichtigung der mathematischen Bezeichnungen der beiden Algorithmen in Frage; Sie können sehen, ohne die Beteiligung der Computerhardware und -software Case 2ist etwa 60%schneller als Case 1.

Wenn Sie sich die Grafiken und Diagramme ansehen, nachdem diese Algorithmen auf einen Quellcode angewendet, kompiliert, optimiert und über das Betriebssystem ausgeführt wurden, um ihre Operationen auf einer bestimmten Hardware auszuführen, können Sie sogar eine geringfügig stärkere Verschlechterung zwischen den Unterschieden feststellen in diesen Algorithmen.

Wenn das DataSet ziemlich klein ist, scheint es zunächst nicht so schlimm zu sein. Da Case 1es jedoch ungefähr 60 - 70%langsamer ist, als Case 2wir das Wachstum dieser Funktion im Hinblick auf die Unterschiede in der Zeitausführung betrachten können:

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)

Diese Annäherung ist die durchschnittliche Differenz zwischen diesen beiden Schleifen sowohl algorithmisch als auch Maschinenoperationen, die Softwareoptimierungen und Maschinenanweisungen umfassen.

Wenn der Datensatz linear wächst, wächst auch der Zeitunterschied zwischen den beiden. Algorithmus 1 hat mehr Fetches als Algorithmus 2 , die evident ist , wenn der Bosszurück zu reisen hat und her dem maximalen Abstand zwischen A& Cfür jede Iteration nach der ersten Iteration , während Algorithmus 2 die Bossmuß Fahren auf Aeinmal und dann , nachdem sich mit getan Aer muss Reise ein maximaler Abstand nur einmal , als ging von Azu C.

Der Versuch, sich darauf zu Bosskonzentrieren, zwei ähnliche Dinge gleichzeitig zu tun und sie hin und her zu jonglieren, anstatt sich auf ähnliche aufeinanderfolgende Aufgaben zu konzentrieren, wird ihn am Ende des Tages ziemlich wütend machen, da er doppelt so viel reisen und arbeiten musste. Verlieren Sie daher nicht den Umfang der Situation, indem Sie Ihren Chef in einen interpolierten Engpass geraten lassen, da der Ehepartner und die Kinder des Chefs dies nicht schätzen würden.

Änderung: Software Engineering Design Principles

- Der Unterschied zwischen Local Stackund Heap AllocatedBerechnungen innerhalb von iterativen for-Schleifen und der Unterschied zwischen ihrer Verwendung, ihrer Effizienz und Effektivität -

Der oben vorgeschlagene mathematische Algorithmus gilt hauptsächlich für Schleifen, die Operationen an Daten ausführen, die auf dem Heap zugeordnet sind.

• Aufeinanderfolgende Stapeloperationen:
  • Wenn die Schleifen Operationen an Daten lokal innerhalb eines einzelnen Codeblocks oder Bereichs ausführen, der sich innerhalb des Stapelrahmens befindet, wird dies immer noch angewendet, aber die Speicherorte sind viel näher, wo sie typischerweise sequentiell sind, und der Unterschied in der zurückgelegten Entfernung oder der Ausführungszeit ist fast vernachlässigbar. Da im Heap keine Zuweisungen vorgenommen werden, wird der Speicher nicht verstreut und der Speicher wird nicht über den RAM abgerufen. Der Speicher ist typischerweise sequentiell und relativ zum Stapelrahmen und Stapelzeiger.
  • Wenn aufeinanderfolgende Operationen auf dem Stapel ausgeführt werden, speichert ein moderner Prozessor sich wiederholende Werte und Adressen zwischen, wobei diese Werte in lokalen Cache-Registern gehalten werden. Die Zeit der Operationen oder Anweisungen liegt hier in der Größenordnung von Nanosekunden.
• Aufeinanderfolgende Heap-zugewiesene Operationen:
  • Wenn Sie anfangen, Heap-Zuweisungen anzuwenden, und der Prozessor die Speicheradressen bei aufeinanderfolgenden Aufrufen abrufen muss, kann die Zeit der Operationen oder der Ausführung in Abhängigkeit von der Architektur der CPU, des Bus-Controllers und der Ram-Module in der Größenordnung von Mikro zu liegen Millisekunden. Im Vergleich zu zwischengespeicherten Stapeloperationen sind diese recht langsam.
  • Die CPU muss die Speicheradresse von Ram abrufen, und normalerweise ist alles über den Systembus hinweg langsam im Vergleich zu den internen Datenpfaden oder Datenbussen innerhalb der CPU selbst.

Wenn Sie also mit Daten arbeiten, die sich auf dem Heap befinden müssen, und diese in Schleifen durchlaufen, ist es effizienter, jeden Datensatz und die entsprechenden Algorithmen in einer eigenen Schleife zu halten. Sie erhalten bessere Optimierungen im Vergleich zum Versuch, aufeinanderfolgende Schleifen herauszufiltern, indem Sie mehrere Operationen verschiedener Datensätze, die sich auf dem Heap befinden, in einer einzigen Schleife zusammenfassen.

Es ist in Ordnung, dies mit Daten zu tun, die sich auf dem Stapel befinden, da diese häufig zwischengespeichert werden, jedoch nicht mit Daten, deren Speicheradresse bei jeder Iteration abgefragt werden muss.

Hier kommen Software Engineering und Software Architecture Design ins Spiel. Es ist die Fähigkeit zu wissen, wie Sie Ihre Daten organisieren, wann Sie Ihre Daten zwischenspeichern müssen, wann Sie Ihre Daten auf dem Heap zuordnen müssen, wie Sie Ihre Algorithmen entwerfen und implementieren und wann und wo Sie sie aufrufen müssen.

Möglicherweise haben Sie denselben Algorithmus, der sich auf denselben Datensatz bezieht, aber Sie möchten möglicherweise ein Implementierungsdesign für die Stapelvariante und ein anderes für die Heap-zugewiesene Variante, nur aufgrund des oben genannten Problems, das sich aus der O(n)Komplexität des Algorithmus bei der Arbeit ergibt mit dem Haufen.

Nach dem, was ich im Laufe der Jahre bemerkt habe, berücksichtigen viele Menschen diese Tatsache nicht. Sie tendieren dazu, einen Algorithmus zu entwerfen, der für einen bestimmten Datensatz funktioniert, und sie verwenden ihn unabhängig davon, ob der Datensatz lokal auf dem Stapel zwischengespeichert ist oder ob er auf dem Heap zugewiesen wurde.

Wenn Sie eine echte Optimierung wünschen, scheint dies zwar eine Codeduplizierung zu sein, aber um es zu verallgemeinern, wäre es effizienter, zwei Varianten desselben Algorithmus zu haben. Eine für Stapeloperationen und die andere für Heap-Operationen, die in iterativen Schleifen ausgeführt werden!

Hier ist ein Pseudobeispiel: Zwei einfache Strukturen, ein Algorithmus.

struct A {
    int data;
    A() : data{0}{}
    A(int a) : data{a}{} 
};
struct B {
    int data;
    B() : data{0}{}
    A(int b) : data{b}{}
}                

template<typename T>
void Foo( T& t ) {
    // do something with t
}

// some looping operation: first stack then heap.

// stack data:
A dataSetA[10] = {};
B dataSetB[10] = {};

// For stack operations this is okay and efficient
for (int i = 0; i < 10; i++ ) {
   Foo(dataSetA[i]);
   Foo(dataSetB[i]);
}

// If the above two were on the heap then performing
// the same algorithm to both within the same loop
// will create that bottleneck
A* dataSetA = new [] A();
B* dataSetB = new [] B();
for ( int i = 0; i < 10; i++ ) {
    Foo(dataSetA[i]); // dataSetA is on the heap here
    Foo(dataSetB[i]); // dataSetB is on the heap here
} // this will be inefficient.

// To improve the efficiency above, put them into separate loops... 

for (int i = 0; i < 10; i++ ) {
    Foo(dataSetA[i]);
}
for (int i = 0; i < 10; i++ ) {
    Foo(dataSetB[i]);
}
// This will be much more efficient than above.
// The code isn't perfect syntax, it's only psuedo code
// to illustrate a point.

Dies ist, worauf ich mich bezog, indem ich separate Implementierungen für Stapelvarianten gegenüber Heap-Varianten hatte. Die Algorithmen selbst spielen keine große Rolle, es sind die Schleifenstrukturen, die Sie dabei verwenden werden.

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 3,5-GHz-Prozessor mit 16 GB RAM.