Stapel Zuordnungsmerkmal (Performance)

Question

Während meiner kleinen Performance-Probleme Untersuchung, ich eine interessante Stapel Zuordnung Feature bemerkt, hier ist es Vorlage für Messzeit:

#include <chrono> 
#include <iostream> 

using namespace std; 
using namespace std::chrono; 

int x; //for simple optimization suppression 
void foo(); 

int main() 
{ 
    const size_t n = 10000000; //ten millions 
    auto start = high_resolution_clock::now(); 

    for (size_t i = 0; i < n; i++) 
    { 
     foo(); 
    } 

    auto finish = high_resolution_clock::now(); 
    cout << duration_cast<milliseconds>(finish - start).count() << endl; 
} 

Jetzt geht es um foo() Implementierung in jeder Implementierung

1. Zugeteilte in einem chunk:: insgesamt 500000 ints zugeordnet werden

   void foo() 
   { 
       const int size = 500000; 
       int a1[size]; 
   
       x = a1[size - 1]; 
   } 
   

   Ergebnis: 7,3 Sekunden;

2. in zwei Brocken Allocated:

   void foo() 
   { 
       const int size = 250000; 
       int a1[size]; 
       int a2[size]; 
   
       x = a1[size - 1] + a2[size - 1]; 
   } 
   

   Ergebnis: 3,5 Sekunden;

3. in vier Brocken Allocated:

   void foo() 
   { 
       const int size = 125000; 
       int a1[size]; 
       int a2[size]; 
       int a3[size]; 
       int a4[size]; 
   
       x = a1[size - 1] + a2[size - 1] + 
        a3[size - 1] + a4[size - 1]; 
   } 
   

   Ergebnis: 1,8 Sekunden.

und etc ... Ich spaltete es in 16 Stücke und bekommen Zeit 0,38 Sekunden führen.

---

Erklären Sie es mir bitte, warum und wie das passiert?
Ich habe MSVC 2013 (v120), Release-Build verwendet.

UPD:
Meine Maschine ist x64-Plattform. Und ich kompilierte es mit Win32-Plattform.
Wenn ich es mit x64-Plattform kompiliere, dann ergibt es in allen Fällen ca. 40ms.
Warum Plattformwahl so viel beeinflussen?

Answer 1

Mit Blick auf Disassembly von VS2015 Update 3, in den 2 und 4 Array-Versionen von foo, optimiert der Compiler die ungenutzten Arrays, so dass es nur Stack-Platz für 1 Array in jeder Funktion reserviert. Da die späteren Funktionen kleinere Arrays haben, dauert dies weniger Zeit. Die Zuweisung zu x liest den gleichen Speicherort für beide/alle 4 Arrays. (Da die Arrays nicht initialisiert sind, ist das Lesen von ihnen nicht definiertes Verhalten.) Ohne den Code zu optimieren, gibt es 2 oder 4 verschiedene Arrays, aus denen gelesen wird.

Die lange für diese Funktionen benötigte Zeit ist auf Stacksonden zurückzuführen, die von __chkstk als Teil der Stapelüberlauferkennung ausgeführt werden (erforderlich, wenn der Compiler mehr als eine Seite Speicherplatz für alle lokalen Variablen benötigt).

Answer 2

Sie sollten sich den resultierenden Assembler-Code anschauen, um zu sehen, was Ihr Compiler wirklich mit dem Code macht. Für gcc/clang/icc können Sie Matt Godbolt's Compiler Explorer verwenden.

Klirren wegen UB alles heraus optimiert und das Ergebnis ist (foo - erste Version, foo2 - zweite Version:

foo:         # @foo 
     retq 

foo2:         # @foo2 
     retq 

icc behandelt beide Versionen sehr ähnlich:

foo: 
     pushq  %rbp           #4.1 
     movq  %rsp, %rbp         #4.1 
     subq  $2000000, %rsp        #4.1 
     movl  -4(%rbp), %eax        #8.9 
     movl  %eax, x(%rip)         #8.5 
     leave             #10.1 
     ret              #10.1 

foo2: 
     pushq  %rbp           #13.1 
     movq  %rsp, %rbp         #13.1 
     subq  $2000000, %rsp        #13.1 
     movl  -1000004(%rbp), %eax       #18.9 
     addl  -4(%rbp), %eax        #18.24 
     movl  %eax, x(%rip)         #18.5 
     leave             #19.1 
     ret 

und gcc erstellt verschiedene Assembler-Code für verschiedene Versionen n 6.1 erzeugt Code, der ein ähnliches Verhalten wie Ihre Experimente zeigen würde:

foo: 
     pushq %rbp 
     movq %rsp, %rbp 
     subq $2000016, %rsp 
     movl 1999996(%rsp), %eax 
     movl %eax, x(%rip) 
     leave 
     ret 
foo2: 
     pushq %rbp 
     movl $1000016, %edx #only the first array is allocated 
     movq %rsp, %rbp 
     subq %rdx, %rsp 
     leaq 3(%rsp), %rax 
     subq %rdx, %rsp 
     shrq $2, %rax 
     movl 999996(,%rax,4), %eax 
     addl 999996(%rsp), %eax 
     movl %eax, x(%rip) 
     leave 
     ret 

So ist die einzige Möglichkeit, den Unterschied zu verstehen, ist an der Assembler-Code von Ihre Compiler erzeugt zu sehen, alles andere ist nur raten.