Langsames Schreiben in Array in C++

Question

Ich habe mich gerade gefragt, ob dies erwartetes Verhalten in C++ ist. Der folgende Code bei etwa 0,001 ms ausgeführt wird:

for(int l=0;l<100000;l++){ 
     int total=0; 
     for(int i = 0; i < num_elements; i++) 
     { 
      total+=i; 
     } 
    } 

jedoch, wenn die Ergebnisse auf ein Array geschrieben werden, nimmt die Zeit der Ausführung bis 15 ms bis:

int *values=(int*)malloc(sizeof(int)*100000); 
     for(int l=0;l<100000;l++){ 
      int total=0; 
      for(unsigned int i = 0; i < num_elements; i++) 
      { 
       total+=i; 
      } 
      values[l]=total; 
     } 

kann ich erkennen, dass an die Schreib Array braucht Zeit, aber ist die Zeit proportional?

Prost jeden

Answer 1

Das erste Beispiel kann mit nur CPU-Registern implementiert werden. Auf diese kann Milliarden Mal pro Sekunde zugegriffen werden. Das zweite Beispiel verwendet so viel Speicher, dass es sicherlich L1 und möglicherweise L2-Cache überläuft (abhängig vom CPU-Modell). Das wird langsamer sein. Immerhin kommen 15 ms/100.000 Schreibvorgänge auf 1,5 ns pro Schreibvorgang - 667 MHz effektiv. Das ist nicht langsam.

Answer 2

Es sieht aus wie der Compiler wird diese Schleife aus ganz im ersten Fall zu optimieren.

Der Gesamteffekt der Schleife ist ein No-Op, also entfernt der Compiler ihn nur.

Answer 3

Ich würde vermuten, dass was Sie sehen, ist ein Effekt von virtual memory und möglicherweise Paging. Der malloc Anruf wird einen anständigen großen Teil des Speichers reservieren, der wahrscheinlich durch eine Anzahl von virtuellen Seiten repräsentiert wird. Jede Seite ist separat in den Prozessspeicher eingebunden.

Sie können auch die Kosten für den Anruf malloc je nachdem, wie Sie die Schleife zeitlich festgelegt haben, messen. In beiden Fällen wird die Leistung sehr empfindlich auf Compiler-Optimierungsoptionen, Threading-Optionen, Compiler-Versionen, Laufzeitversionen und so gut wie alles andere reagieren. Sie können nicht sicher davon ausgehen, dass die Kosten linear mit der Größe der Zuweisung sind. Die einzige Sache, die Sie tun können, ist es zu messen und herauszufinden, wie man am besten optimieren kann, sobald es sich als ein Problem erwiesen hat.

Answer 4

Es ist sehr einfach. Im ersten Fall Sie haben nur 3 Variablen, die leicht in GPR (General Purpose Registers) gespeichert werden können, aber es bedeutet nicht, dass sie ständig da sind, aber sie sind wahrscheinlich in L1 Cache-Speicher, was bedeutet, dass sie kann sehr schnell erreicht werden.

Im zweiten Fall Sie haben mehr als 100k Variablen, und Sie benötigen etwa 400kB, um sie zu speichern. Das ist definitiv zu viel für Register und L1-Cache-Speicher. Im besten Fall könnte es im L2-Cache-Speicher sein, aber wahrscheinlich werden nicht alle von ihnen in L2 sein. Wenn etwas nicht im Register ist, L1, L2 (ich nehme an, dass Ihr Prozessor nicht über L3 verfügt), bedeutet dies, dass Sie im RAM suchen müssen und es dauert viel mehr Zeit.