Alokacja pamięci zoptymalizowana przez kompilatory

Question

W swoim przemówieniu "Efficiency with algorithms, Performance with data structures", Chandler Carruth mówi o potrzebie lepszego modelu przydziału w C++. Bieżący model alokatora atakuje system typów i sprawia, że ​​prawie niemożliwe jest działanie w wielu projektach z tego powodu. Z drugiej strony, Bloomberg allocator model nie atakuje systemu typów, ale jest oparty na wywołaniach funkcji wirtualnych, co uniemożliwia kompilatorowi "obejrzenie" alokacji i jej optymalizację. W swojej rozmowie opowiada o kompilatorach deduplikujących alokację pamięci (1:06:47).

Zajęło mi trochę czasu, aby znaleźć przykłady optymalizacji alokacji pamięci, ale znalazłem ten przykład kodu, który skompilowany pod klangiem, zoptymalizować całą alokację pamięci i po prostu zwrócić 1000000 bez przydzielania czegokolwiek.

template<typename T> 
T* create() { return new T(); } 

int main() { 
    auto result = 0; 
    for (auto i = 0; i < 1000000; ++i) { 
     result += (create<int>() != nullptr); 
    } 

    return result; 
} 

Poniższy papier http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3664.html mówi również, że alokacja może być sprzężona z kompilatorów i zdaje się sugerować, że niektóre kompilatory już robić tego typu rzeczy.

Ponieważ jestem bardzo zainteresowany strategiami wydajnego przydzielania pamięci, naprawdę chcę zrozumieć, dlaczego Chandler Carruth jest przeciwko wirtualnym połączeniom w modelu Bloomberg. Powyższy przykład wyraźnie pokazuje, że clang optymalizuje rzeczy, gdy widzi przydział.

1. chciałbym mieć „prawdziwy kod życia”, gdzie ta optymalizacja jest przydatna i zrobione przez każdego obecnego kompilatora
2. Czy masz przykład kodu, w którym inny przydział są skondensowane przez Anu obecnego kompilatora?
3. Czy rozumiesz, co Chandler Carruth ma na myśli mówiąc, że kompilatorzy mogą "deduplikować" twoje przydziały w rozmowie o 1:06:47?

Answer 1

Znalazłem ten niesamowity przykład, który odpowiada na pierwszy punkt początkowego pytania. Oba punkty 2 i 3 nie mają jeszcze żadnej odpowiedzi.

#include <iostream> 
#include <vector> 
#include <chrono> 

std::vector<double> f_val(std::size_t i, std::size_t n) { 
    auto v = std::vector<double>(n); 
    for (std::size_t k = 0; k < v.size(); ++k) { 
     v[k] = static_cast<double>(k + i); 
    } 
    return v; 
} 

void f_ref(std::size_t i, std::vector<double>& v) { 
    for (std::size_t k = 0; k < v.size(); ++k) { 
     v[k] = static_cast<double>(k + i); 
    } 
} 

int main (int argc, char const *argv[]) { 
    const auto n = std::size_t{10}; 
    const auto nb_loops = std::size_t{300000000}; 

    // Begin: Zone 1 
    { 
     auto v = std::vector<double>(n, 0.0); 
     auto start_time = std::chrono::high_resolution_clock::now(); 
     for (std::size_t i = 0; i < nb_loops; ++i) { 
      auto w = f_val(i, n); 
      for (std::size_t k = 0; k < v.size(); ++k) { 
       v[k] += w[k]; 
      } 
     } 
     auto end_time = std::chrono::high_resolution_clock::now(); 
     auto time = std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time).count(); 
     std::cout << time << std::endl; 
     std::cout << v[0] << " " << v[n - 1] << std::endl; 
    } 
    // End: Zone 1 

    { 
     auto v = std::vector<double>(n, 0.0); 
     auto w = std::vector<double>(n); 
     auto start_time = std::chrono::high_resolution_clock::now(); 
     for (std::size_t i = 0; i < nb_loops; ++i) { 
      f_ref(i, w); 
      for (std::size_t k = 0; k < v.size(); ++k) { 
       v[k] += w[k]; 
      } 
     } 
     auto end_time = std::chrono::high_resolution_clock::now(); 
     auto time = std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time).count(); 
     std::cout << time << std::endl; 
     std::cout << v[0] << " " << v[n - 1] << std::endl; 
    } 

    return 0; 
} 

gdzie nie ma miejsca na przydzielanie pamięci w pętli for z parametrem f_val. Dzieje się tak tylko w przypadku Clang (zarówno w przypadku Gcc, jak i icpc) i podczas budowania nieco bardziej skomplikowanego przykładu, optymalizacja nie jest wykonywana.