Frage Warum sind elementweise Additionen in separaten Schleifen viel schneller als in einer kombinierten Schleife?


Annehmen a1, b1, c1, und d1 zeigen auf 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 ein anderes Äußeres ausgeführt for Schleife. 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];
}

Zusammengestellt auf MS Visual C ++ 10.0 mit voller Optimierung und SSE2 aktiviert für 32-Bit auf a Intel Core 2 Duo (x64), das erste Beispiel dauert 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

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 benutzt TBB  Tick_Count für eine höhere Auflösung Timing, die deaktiviert werden kann, indem die nicht definieren TBB_TIMING Makro:

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

enter image description here


1995
2017-12-17 20:40


Ursprung


Antworten:


Bei einer weiteren Analyse davon glaube ich, dass dies (zumindest teilweise) durch die Datenausrichtung der vier Zeiger verursacht wird. Dies führt zu einer gewissen Anzahl von Cachebank / Wegkonflikten.

Wenn ich richtig erraten habe, wie Sie Ihre Arrays zuweisen, dann sind sie das sind wahrscheinlich auf die Seitenlinie ausgerichtet.

Dies bedeutet, dass alle Ihre Zugriffe in jeder Schleife auf den gleichen Cache-Weg fallen. Allerdings haben Intel-Prozessoren für eine Weile eine assoziative Assoziation mit dem 8-Wege-L1-Cache. Aber in Wirklichkeit ist die Leistung nicht völlig einheitlich. Zugriff auf 4-Wege ist immer noch langsamer als sagen 2-Wege.

EDIT: Es sieht in der Tat so aus, als würden Sie alle Arrays separat zuweisen. Wenn solche großen Zuordnungen angefordert werden, fordert der Zuordner normalerweise neue Seiten vom Betriebssystem an. Daher besteht eine hohe Wahrscheinlichkeit, dass große Zuordnungen bei einem Offset 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:

EDIT: Ergebnisse auf ein tatsächlich 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 bemerken, dass sie alle die gleiche Ausrichtung zur Seite haben.

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

Wie @Stephen Cannon in den Kommentaren hervorhebt, ist es sehr wahrscheinlich, dass diese Ausrichtung verursacht falsches Aliasing in den Lade- / Speichereinheiten oder im Cache. Ich habe dafür gegoogelt und festgestellt, dass Intel eigentlich einen Hardware-Counter hat Teiladressen-Aliasing Stände:

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


5 Regionen - Erläuterungen

Region 1:

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

Region 2:

Wenn die Datengröße zunimmt, sinkt die relative Belastung und die Leistung "sättigt". Hier sind zwei Schleifen langsamer, da sie doppelt so viel Loop- und Branching-Overhead haben.

Ich bin mir nicht sicher, was genau hier vor sich geht ... Die Ausrichtung könnte immer noch Wirkung zeigen, wie Agner Fog erwähnt Cachebankkonflikte. (Dieser Link ist über Sandy Bridge, aber die Idee sollte immer noch auf Core 2 anwendbar sein.)

Region 3:

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

Region 4:

Der Leistungsabfall im Single-Loop ist, was wir beobachten. Und wie erwähnt, liegt dies an der Ausrichtung, die (wahrscheinlich) verursacht falsches Aliasing Stalle in den Prozessor laden / speichern Einheiten.

Damit jedoch falsches Alias ​​auftreten kann, muss zwischen den Datensätzen ein ausreichend großer Schritt sein. Deshalb sehen Sie das nicht in Region 3.

Region 5:

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


2 x Intel X5482 Harpertown @ 3.2 GHz Intel Core i7 870 @ 2.8 GHz Intel Core i7 2600K @ 4.4 GHz


1544
2017-12-17 21:17



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 Mehrheit der 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 ursprüngliche Frage war n = 100.000. 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:

Enter image description here

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

Enter image description here

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

Enter image description here

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.


194
2017-12-18 01:29



Die zweite Schleife beinhaltet viel weniger Cache-Aktivität, so dass es für den Prozessor einfacher ist, mit den Speicheranforderungen Schritt zu halten.


63
2017-12-17 20:47



Stellen Sie sich vor, Sie arbeiten an einer Maschine, wo n Es war genau der richtige Wert, um nur zwei Ihrer Arrays gleichzeitig im Speicher zu halten, aber der gesamte verfügbare Speicherplatz ü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 zuerst verursachen a und b in den Arbeitsspeicher geladen werden und dann vollständig im Arbeitsspeicher bearbeitet werden. Wenn die zweite Schleife beginnt, c und d würde dann von der Platte in den RAM geladen und bearbeitet werden.

die andere Schleife

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

wird zwei Arrays ausgeben und in den anderen zwei Seiten anzeigen jedes Mal um die Schleife herum. Das 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 n = 2 und wir arbeiten mit Bytes. In meinem Szenario haben wir also nur 4 Bytes Cache und der Rest unseres Gedächtnisses ist deutlich langsamer (sagen wir mal 100 mal länger).

Unter der Annahme einer ziemlich dummen Caching - Politik von Wenn das Byte nicht im Cache ist, lege es dorthin und erhalte auch das folgende Byte, während wir dabei sind Sie erhalten ein Szenario in 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];
    }
    
  • Zwischenspeicher a[0] und a[1] dann b[0] und b[1] und einstellen 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.

  • einstellen 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];
    }
    
  • Zwischenspeicher a[0] und a[1] dann b[0] und b[1] und einstellen 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.

  • auswerfen a[0], a[1], b[0], b[1] aus Cache und Cache c[0] und c[1] dann d[0] und d[1] und einstellen 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.


37
2017-12-18 01:36



Es ist nicht wegen eines anderen Codes, sondern wegen des Caching: RAM ist langsamer als die CPU-Register und ein Cache-Speicher ist in der CPU, um zu vermeiden, den RAM jedes Mal zu schreiben, wenn sich eine Variable ändert. Aber der Cache ist nicht so groß wie der RAM, daher bildet er nur einen Bruchteil davon ab.

Der erste Code modifiziert entfernte Speicheradressen, die sie bei jeder Schleife wechseln, wodurch es erforderlich wird, den Cache kontinuierlich ungültig zu machen.

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


27
2017-12-17 20:49



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, die Quell-Arrays so zu initialisieren, dass += Aufgabe fragte nicht die FPU Hinzufügen von Speichermüll, der als Double interpretiert wird.

Ich habe mit verschiedenen Schemata herumgespielt, zum Beispiel die Aufgabe von b[j], d[j] zu InitToZero[j] in den Schleifen, und auch mit += b[j] = 1 und += d[j] = 1und ich habe ziemlich konsistente Ergebnisse.

Wie Sie vielleicht erwarten, Initialisierung b und d innerhalb der Schleife mit InitToZero[j] gab dem kombinierten Ansatz einen Vorteil, wie sie Rücken an Rücken vor den Zuordnungen zu a und c, aber immer noch innerhalb von 10%. Stelle dir das vor.

Hardware ist Dell XPS 8500 mit Generation 3 Kern 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.


16
2017-12-30 01:34



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


14
2017-12-17 20:52



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.


12
2017-08-17 15:23