Stos funkcja alokacji (wydajność)

Question

W moim małym problemy z wydajnością dochodzenia, zauważyłem ciekawą funkcję alokacji stosu, to jest tutaj szablon do odmierzania czasu:

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

Teraz to wszystko o foo() wdrożenie, w każdej realizacji będzie przeznacza się łączną 500000 ints:

1. przydzielane jeden fragmencie:

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

   Wynik: 7,3 sekundy;

2. przydzielane dwa kawałki:

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

   wynikowe: 3,5 sekundy;

3. przydzielane cztery kawałki:

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

   Wynik: 1,8 sekundy.

i etc ... I podzielić go na kawałki16 i dostać Wynik czas 0,38 sekundy.

---

Wyjaśnij mi, proszę, dlaczego i jak to się dzieje?
Użyłem MSVC 2013 (v120), Wydanie kompilacji.

UPD:
Moja maszyna to platforma x64. I skompilowałem go za pomocą platformy Win32.
Kiedy kompiluję go z platformą x64, wówczas we wszystkich przypadkach uzyskuje około 40 ms.
Dlaczego wybór platformy ma tak duży wpływ?

Answer 1

Patrząc na demontaż z VS2015 Update 3, w wersjach z 2 i 4 tablicami foo, kompilator optymalizuje nieużywane tablice tak, że rezerwuje tylko przestrzeń stosu dla 1 tablicy w każdej funkcji. Ponieważ późniejsze funkcje mają mniejsze tablice, zajmuje to mniej czasu. Przypisanie x odczytuje tę samą lokalizację pamięci dla obu/wszystkich 4 tablic. (Ponieważ tablice są niezainicjowane, odczytanie z nich jest niezdefiniowanym zachowaniem). Bez optymalizacji kodu istnieją 2 lub 4 odrębne tablice, z których można odczytać.

Dłuższy czas wykonywania tych funkcji wynika z sondowania stosu przeprowadzonego przez __chkstk w ramach wykrywania przepełnienia stosu (niezbędnego, gdy kompilator potrzebuje więcej niż 1 strona miejsca na przechowywanie wszystkich zmiennych lokalnych).

Answer 2

Powinieneś spojrzeć na wynikowy kod assemblera, aby zobaczyć, co naprawdę robi twój kompilator z kodem. W przypadku gcc/clang/icc możesz użyć Matt Godbolt's Compiler Explorer.

dzyń optymalizuje wszystko z powodu UB, a wynik jest (foo - pierwsza wersja, foo2 - druga wersja:

foo:         # @foo 
     retq 

foo2:         # @foo2 
     retq 

ICC traktuje obie wersje bardzo podobne:

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 

i gcc tworzy inny kod assemblera dla innej wersji. n 6.1 produkuje kodu, które wykazują podobne zachowanie jak eksperymentów:

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 

Tak więc jedynym sposobem, aby zrozumieć różnicę jest, aby spojrzeć na kod asemblera produkowanego przez swojej kompilatora, wszystko inne jest tylko zgadywać.