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



performance compiler-optimization (7)

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 .)

https://rueisnom.com


Answer #1

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.


Answer #2

Die zweite Schleife beinhaltet viel weniger Cache-Aktivität, sodass der Prozessor den Speicheranforderungen leichter gerecht wird.


Answer #3

Dies liegt nicht an einem anderen Code, sondern an einer Zwischenspeicherung: Das RAM ist langsamer als die CPU-Register und ein Cache-Speicher befindet sich in der CPU, um zu vermeiden, dass das RAM jedes Mal geschrieben wird, wenn sich eine Variable ändert. Da der Arbeitsspeicher jedoch nicht groß ist, bildet er nur einen Bruchteil davon ab.

Der erste Code modifiziert entfernte Speicheradressen, indem er sie in jeder Schleife abwechselt, so dass der Cache fortlaufend ungültig werden muss.

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


Answer #4

Nach einer weiteren Analyse glaube ich, dass dies (zumindest teilweise) auf das Datenabgleich der vier Zeiger zurückzuführen ist. Dies führt zu einem gewissen Grad an Cache-Bank / Weg-Konflikten.

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

Dies bedeutet, dass alle Ihre Zugriffe in jeder Schleife auf den gleichen Cache-Weg fallen. Intel-Prozessoren verfügen jedoch seit einiger Zeit über eine 8-Wege-L1-Cache-Assoziativität. In der Realität ist die Leistung jedoch nicht völlig einheitlich. Der Zugriff auf 4-Wege ist noch langsamer als etwa 2-Wege.

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

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 aktuellen 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 exakt wieder.

  • In den ersten beiden Tests werden die Arrays separat zugewiesen. Sie werden feststellen, dass sie alle in Bezug auf die Seite die gleiche Ausrichtung haben.

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

Wie @Stephen Cannon in den Kommentaren darauf hinweist, ist es sehr wahrscheinlich, dass diese Ausrichtung zu falschem Aliasing in den Lade- / Speichereinheiten oder im Cache führt. Ich googelte dafür herum und stellte fest, dass Intel einen Hardware-Zähler für teilweise Adressen-Aliasing- Stände 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. Das Dataset ist so klein, dass die Leistung von Overhead wie Schleifen und Verzweigen dominiert wird.

Region 2:

Mit zunehmender Datengröße sinkt hier der relative Aufwand und die Leistung "sättigt". Hier sind zwei Schleifen langsamer, weil sie doppelt so viele Schleifen und Verzweigungen haben.

Ich bin mir nicht sicher, was genau hier vor sich geht ... Alignment könnte immer noch einen Effekt zeigen, da Agner Fog Cache-Bank-Konflikte erwähnt . (Bei diesem Link geht es um Sandy Bridge, die Idee sollte jedoch auf Core 2 zutreffen.)

Region 3:

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

Region 4:

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

Damit jedoch falsches Aliasing auftritt, müssen die Datenmengen ausreichend groß sein. Deshalb sieht man das in Region 3 nicht.

Region 5:

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


Answer #5

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.


Answer #6

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 dafür war, warum viele Maschinenarchitekturen und -Entwickler schließlich Multi-Core-Systeme mit der Fähigkeit, Multithread-Anwendungen und parallele Programmierung auszuführen, bauten und konstruierten.

Wenn Sie es von einem solchen Ansatz aus betrachten, ohne die Zusammenhänge zwischen Hardware, Betriebssystem und Compiler (n) bei der Heap-Zuweisung zu berücksichtigen, die das Arbeiten mit RAM, Cache, Seitendateien usw. umfasst. Die Mathematik, die diesen Algorithmen zugrunde liegt, zeigt uns, welche der beiden Lösungen die bessere Lösung ist. Wir können eine Analogie verwenden, bei der ein Boss oder eine Summation , die eine For Loop , die zwischen Arbeitern A und B reisen muss, leicht erkennen kann, dass Fall 2 mindestens 1/2 so schnell ist, wenn nicht etwas mehr als Fall 1 aufgrund von der Unterschied in der Entfernung, die erforderlich ist, um zu reisen und die Zeit zwischen den Arbeitern. Diese Mathematik stimmt nahezu virtuell mit den Benchmark-Zeiten und den unterschiedlichen Montageanweisungen überein.

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

Bewertung des Problems

Der Code des OP:

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 2 Varianten der for-Schleifen und seiner geänderten Frage zum Verhalten von Caches sowie zu vielen anderen hervorragenden Antworten und nützlichen Kommentaren; Ich möchte versuchen, etwas anderes zu tun, indem ich einen anderen Ansatz in Bezug auf diese Situation und dieses Problem nehme.

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. Eine, die weder die Cache- und Seitendateien noch die Ausführung der Speicherzuordnung einbezieht, betrifft in der Tat überhaupt nicht die tatsächliche Hardware oder die Software.

Die Perspektive

Nachdem man sich den Code eine Weile angesehen hatte, wurde deutlich, was das Problem ist und was es erzeugt. Lassen Sie uns dies in ein algorithmisches Problem aufschlüsseln 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 seine Schleife 100.000 Mal läuft.Wir wissen auch , dass a1, b1, c1&d1sind Zeiger auf eine 64-Bit-Architektur. In C ++ sind auf einer 32-Bit-Maschine alle Zeiger 4 Byte und auf einer 64-Bit-Maschine 8 Byte groß, da die Zeiger eine feste Länge haben. Wir wissen, dass wir in beiden Fällen 32 Bytes für die Zuweisung haben. Der einzige Unterschied besteht darin, dass wir bei jeder Iteration 32 Bytes oder 2 Sätze von 2–8 Bytes zuordnen. Im zweiten Fall werden 16 Bytes für jede Iteration für beide unabhängigen Schleifen zugewiesen. Beide Loops entsprechen also insgesamt 32 Byte in der Gesamtzuordnung. Mit diesen Informationen wollen wir die allgemeine Mathematik, den Algorithmus und die Analogie davon zeigen. Wir wissen, wie oft dieselbe Gruppe oder Gruppe von Operationen in beiden Fällen ausgeführt werden muss. Wir wissen, wie viel Speicher in beiden Fällen zugewiesen werden muss.Wir können feststellen, dass die Gesamtbelastung der Zuweisungen zwischen den beiden Fällen ungefähr gleich ist.

Was wir nicht wissen

Wir wissen nicht, wie lange es in jedem Fall dauern wird, es sei denn, wir setzen einen Zähler und führen einen Benchmark-Test durch. Die Benchmarks waren jedoch bereits aus der ursprünglichen Frage sowie aus einigen Antworten und Kommentaren enthalten, und wir können einen deutlichen Unterschied zwischen den beiden erkennen, und dies ist der gesamte Grund, warum diese Frage auf dieses Problem und für die Beantwortung dieses Problems gerichtet ist anfangen mit.

Lass uns nachforschen

Es ist bereits offensichtlich, dass viele dies bereits getan haben, indem sie die Heap-Zuordnungen, Benchmark-Tests, RAM, Cache und Page Files betrachten. Ein Blick auf bestimmte Datenpunkte und spezifische Iterationsindizes wurde ebenfalls aufgenommen, und bei den verschiedenen Gesprächen über dieses spezielle Problem haben viele Leute angefangen, andere verwandte Dinge in Frage zu stellen. Wie beginnen wir, dieses Problem zu betrachten, indem wir mathematische Algorithmen verwenden und eine Analogie darauf anwenden? Wir beginnen mit ein paar Behauptungen! Dann bauen wir unseren Algorithmus von dort aus auf.

Unsere Behauptungen:

  • Wir lassen unsere Schleife und ihre Iterationen aus einer Summation bestehen, die bei 1 beginnt und bei 100000 endet, anstatt bei 0 wie in den Schleifen zu beginnen, da wir uns nicht um das 0-Indexierungsschema der Speicheradressierung kümmern müssen, da wir nur daran interessiert sind der Algorithmus selbst.
  • In beiden Fällen haben wir 4 Funktionen zum Arbeiten und 2 Funktionsaufrufe, wobei für jeden Funktionsaufruf 2 Vorgänge ausgeführt werden. So werden wir diese aufgebaut wie Funktionen und Funktion sein rufen 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 F2()nur festgestellt haben , Sumwo beides Sum1und Sum2nur enthält F1(). Dies wird sich auch später zeigen, wenn wir zu dem Schluss kommen, dass eine Art Optimierung durch den zweiten Algorithmus erfolgt.

Die Iterationen durch die ersten SumFallaufrufe f(a), die sich selbst hinzufügen, f(b)dann Aufrufe f(c), die dasselbe tun f(d), sich jedoch für jeden hinzufügen 100000 iterations. Im zweiten Fall haben wir Sum1und Sum2Und beide verhalten sich so, als wären sie die gleiche Funktion, die zweimal hintereinander aufgerufen wurde. In diesem Fall können wir behandeln Sum1und Sum2einfach nur alt sein, Sumwo Sumin diesem Fall folgendes aussieht: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }und jetzt sieht das aus wie eine Optimierung, bei der wir nur die gleiche Funktion betrachten können.

Zusammenfassung mit Analogie

Bei dem, was wir im zweiten Fall gesehen haben, scheint es fast so, als gäbe es eine Optimierung, da beide for-Schleifen die gleiche genaue Signatur haben. Dies ist jedoch nicht das eigentliche Problem. In beiden Fällen handelt es sich nicht um die Arbeit, die von & ausgeführt f(a)wird f(b), f(c)und f(d)in beiden Fällen ist es der Unterschied in der Entfernung, die die Summation in beiden Fällen zurücklegen muss, um den zeitlichen Unterschied zu bestimmen.

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 der Analogie repräsentieren hier die for-Loop- oder Summations-Iterationen und Condition-Checks selbst nicht die Boss. Was hier tatsächlich dargestellt wird Boss, stammt nicht von den tatsächlichen mathematischen Algorithmen direkt, sondern von dem tatsächlichen Konzept Scopeund Code Blockinnerhalb einer Routine oder Subroutine, Methode, Funktion, Übersetzungseinheit usw. Der erste Algorithmus hat 1 Geltungsbereich, wobei der 2. Algorithmus 2 hat aufeinander folgende Bereiche.

Im ersten Fall bei jedem Aufruf rutschen die Bossgehen an Aund gibt den Befehl , und Aerlischt zu holen B'sPaket dann das Bosszu geht Cund gibt die Befehle , das Gleiche zu tun und das Paket aus erhält Dbei jeder Iteration.

Im zweiten Fall Bossarbeitet das Paket direkt mit Adem B'sPaket " go" und "holen" , bis alle Pakete empfangen wurden. Dann Bossfunktioniert das mit Cdem gleichen, um alle D'sPakete zu bekommen.

Da wir mit einem 8-Byte-Zeiger arbeiten und uns mit der Heap-Zuordnung befassen, betrachten wir dieses Problem hier. Nehmen wir an, das Bossist 100 Fuß von Aund das Aist 500 Fuß von C. Wir müssen uns keine Gedanken darüber machen, wie weit das Bossanfänglich Caufgrund der Reihenfolge der Hinrichtungen ist. In beiden Fällen Bossreist der Azuerst von dann nach B. Diese Analogie bedeutet nicht, dass diese Entfernung genau ist. Es ist nur ein Testfallszenario, in dem die Funktionsweise der Algorithmen dargestellt wird. In vielen Fällen, wenn Heap-Zuordnungen vorgenommen werden und mit den Cache- und Seitendateien gearbeitet wird, variieren diese Abstände zwischen Adressorten möglicherweise nicht so stark in den Unterschieden oder sie hängen sehr stark von der Art der Datentypen und der Arraygröße ab.

Die Testfälle:

Erster Fall: Bei der ersten Iteration muss derBossBenutzer zunächst 100 Fuß gehen, um den Auftrag abzugebenAund zuAerledigen, und dann macht er sein Ding, aber dannBossmuss er 500 Fuß zurücklegenC, um ihm den Auftragszettel zu geben. Dann bei der nächsten Iteration und jeder weiteren Iteration danachBossmuss man 500 Fuß zwischen den beiden hin und her gehen.

Zweiter Fall: The Boss muss bei der ersten Iteration 100 Fuß zurücklegenA, aber danach ist er bereits da und wartet nurAdarauf, zurück zu kommen, bis alle Belege gefüllt sind. DannBossmuss er 500 Fuß bei der ersten Iteration zurücklegen,CdaC500 Fuß vonAdaBoss( Summation, For Loop )ist,da dieserdirekt nach der Arbeit aufgerufen wird,Aund wartet dann so, wie er es getan hat,Abis alleC'sBestellungslücken 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 von willkürlichen Werten

Wir können leicht erkennen, dass 600 weit weniger als 10 Millionen beträgt. Das ist jetzt nicht genau, da wir nicht genau wissen, wie groß die Entfernung zwischen der Adresse des RAM oder der Cache- oder Seitendatei ist, die jeder Aufruf bei jeder Iteration durch viele andere unsichtbare Variablen verursacht eine Beurteilung der Situation, um sich der Situation bewusst zu werden und versuchen, sie aus dem Worst-Case-Szenario zu betrachten.

Bei diesen Zahlen würde es fast so aussehen, als wäre Algorithmus Eins 99% langsamer als Algorithmus Zwei; Dies ist jedoch nur der The 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. Der Job der Chefs macht also nur etwa 15 - 40% der gesamten Arbeit aus. Der Großteil der Arbeit, die von den Arbeitern geleistet wird, hat einen geringfügig größeren Einfluss darauf, das Verhältnis der Geschwindigkeitsunterschiede auf etwa 50-70% zu halten.

Die Beobachtung: - Die Unterschiede zwischen den beiden Algorithmen

In dieser Situation ist es die Struktur des Prozesses der durchgeführten Arbeit, und es zeigt sich, dass Fall 2 sowohl durch die teilweise Optimierung einer ähnlichen Funktionsdeklaration als auch durch die Definition effizienter ist, wobei sich nur die Variablen nach Namen unterscheiden . Und wir sehen auch, dass die Gesamtstrecke, die in Fall 1 zurückgelegt wurde, viel weiter ist als in Fall 2, und wir können diese zurückgelegte Entfernung als unseren Zeitfaktor zwischen den beiden Algorithmen betrachten. Fall 1 hat wesentlich mehr Arbeit als Fall 2 . Dies wurde auch in den Beweisen derASMdas wurde zwischen beiden Fällen gezeigt. Auch mit dem, was schon war über diese Fälle , sagte, ist es auch nicht berücksichtigt , dass in Fall 1 der Chef wird warten müssen für beide A& Czurück zu bekommen , bevor er zurück gehen Awieder auf die nächste Iteration und es doesn auch Es ist nicht zu berücksichtigen, dass wenn Aoder Bextrem lange gedauert wird, dann Bosswarten sowohl der als auch der andere Arbeiter im Leerlauf. In Fall 2 ist der einzige, der im Leerlauf ist, der, Bossbis der Arbeiter zurückkommt. Also auch das hat Auswirkungen auf den Algorithmus.

Die geänderten OPs der OP (s)

BEARBEITEN: 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.

Zu diesen Fragen

Wie ich zweifelsfrei gezeigt habe, gibt es ein grundlegendes Problem, noch bevor Hardware und Software beteiligt sind. Nun wie bei der Verwaltung von Speicher und Zwischenspeicherung zusammen mit Seitendateien usw., die alle in einer integrierten Gruppe von Systemen zusammenarbeiten: The Architecture{Hardware, Firmware, einige eingebettete Treiber, Kernel und ASM-Befehlssätze}, The OS{Datei- und Speicherverwaltungssysteme , Treiber und die Registry}, The Compiler{Übersetzungseinheiten und Optimierungen des Quellcodes} und sogar die Source Codeselbst mit ihren verschiedenen Algorithmen; können wir sehen bereits , dass es einen Engpass, der innerhalb des ersten Algorithmus geschieht , bevor wir wenden sie auch an jede Maschine mit einer beliebigen Architecture, OSundProgrammable Languageim Vergleich zum zweiten Algorithmus. Es bestand also bereits ein Problem, bevor es sich mit dem modernen Computer befasste.

Die Endergebnisse

Jedoch; Es ist nicht zu sagen, dass diese neuen Fragen nicht von Bedeutung sind, weil sie selbst eine Rolle spielen und doch eine Rolle spielen. Sie wirken sich auf die Verfahren und die Gesamtleistung aus, und das zeigen die verschiedenen Grafiken und Bewertungen vieler, die ihre Antwort (en) und / oder Kommentare abgegeben haben. Wenn Sie die Aufmerksamkeit auf die Analogie der zahlen Bossund die beiden Arbeiter Aund Bdie musste gehen und Abrufen von Paketen aus C& Djeweils und die mathematischen Bezeichnungen der beiden Algorithmen in Frage bedenkt , kann man auch ohne die Beteiligung des Computers sehen , dass Case 2etwa 60% schneller alsCase 1 Wenn Sie die Diagramme und Diagramme betrachten, nachdem diese Algorithmen auf den Quellcode angewendet, kompiliert und optimiert wurden und durch das Betriebssystem ausgeführt wurden, um Operationen mit der jeweiligen Hardware auszuführen, sehen Sie sogar eine etwas geringere Verschlechterung zwischen den Unterschieden in diesen Algorithmen.

Wenn der "Data" -Datensatz relativ klein ist, scheint dies zunächst nicht allzu schlimm zu sein, da Case 1es sich jedoch um etwas 60 - 70%langsamer handelt, als Case 2wir das Wachstum dieser Funktion im Hinblick auf die Unterschiede bei 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)

Und diese Annäherung ist die durchschnittliche Differenz zwischen diesen beiden Schleifen, sowohl algorithmisch als auch maschinell, einschließlich Softwareoptimierungen und Maschinenanweisungen. Wenn also der Datensatz linear wächst, wächst auch der Zeitunterschied zwischen den beiden. Algorithmus 1 hat mehr Abrufe als Algorithmus 2, was offensichtlich ist, wenn der Bossmaximale Abstand zwischen A& Cfür jede Iteration nach der ersten Iteration hin- und herbewegt werden musste, während Algorithmus 2 einmal hinfahren Bossmusste Aund dann, nachdem er damit fertig Awar eine maximale Entfernung nur einmal, wenn Sie von Anach gehen C.

Zu versuchen, Bosssich auf zwei ähnliche Dinge gleichzeitig zu konzentrieren 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, weil er doppelt so viel reisen und arbeiten musste. Verlieren Sie deshalb 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 zu schätzen wissen.


Answer #7

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.





vectorization