Come mai questo ciclo viene eseguito ugualmente velocemente quando compilato con -O3, ma non quando è compilato con -O2?

Question

Nel programma seguente mi aspetto che test1 funzioni più lentamente a causa delle istruzioni dipendenti. Un test con -O2 sembrava confermare questo. Ma poi ho provato con -O3 e ora i tempi sono più o meno uguali. Come può essere?

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

volatile int x = 0; // used for preventing certain optimizations 


enum { size = 60 * 1000 * 1000 }; 
std::vector<unsigned> a(size + x); // `size + x` makes the vector size unknown by compiler 
std::vector<unsigned> b(size + x); 


void test1() 
{ 
    for (auto i = 1u; i != size; ++i) 
    { 
     a[i] = a[i] + a[i-1]; // data dependency hinders pipelining(?) 
    } 
} 


void test2() 
{ 
    for (auto i = 0u; i != size; ++i) 
    { 
     a[i] = a[i] + b[i]; // no data dependencies 
    } 
} 


template<typename F> 
int64_t benchmark(F&& f) 
{ 
    auto start_time = std::chrono::high_resolution_clock::now(); 
    f(); 
    auto elapsed_ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - start_time); 
    return elapsed_ms.count(); 
} 


int main(int argc, char**) 
{ 
    // make sure the optimizer cannot make any assumptions 
    // about the contents of the vectors: 
    for (auto& el : a) el = x; 
    for (auto& el : b) el = x; 

    test1(); // warmup 
    std::cout << "test1: " << benchmark(&test1) << '\n'; 

    test2(); // warmup   
    std::cout << "\ntest2: " << benchmark(&test2) << '\n'; 

    return a[x] * x; // prevent optimization and exit with code 0 
} 

ottengo questi risultati:

g++-4.8 -std=c++11 -O2 main.cpp && ./a.out 
test1: 115 
test2: 48 

g++-4.8 -std=c++11 -O3 main.cpp && ./a.out 
test1: 29 
test2: 38 

Answer 1

Perché in -O3 gcc elimina efficacemente la dipendenza dei dati, memorizzando il valore di a[i] in un registro e riutilizzandolo nell'iterazione successiva invece di caricare a[i-1].

Il risultato è più o meno equivalente a:

void test1() 
{ 
    auto x = a[0]; 
    auto end = a.begin() + size; 
    for (auto it = next(a.begin()); it != end; ++it) 
    { 
     auto y = *it; // Load 
     x = y + x; 
     *it = x; // Store 
    } 
} 

che ha compilato in -O2 cedere stesso assieme esattamente come il vostro codice compilato in -O3.

Il secondo ciclo nella domanda è srotolato in -O3, quindi la velocità. Le due ottimizzazioni applicate sembrano non essere correlate a me, il primo caso è più veloce semplicemente perché gcc ha rimosso un'istruzione di caricamento, la seconda perché è srotolata.

In entrambi i casi, non penso che l'ottimizzatore abbia fatto qualcosa in particolare per migliorare il comportamento della cache, entrambi i modelli di accesso alla memoria sono facilmente prevedibili dalla CPU.

Answer 2

ottimizzatori sono pezzi molto sofisticati di software e non sempre prevedibili.

Con g ++ 5.2.0 e -O2 test1 e test2 viene compilato in codice macchina simile:

;;;; test1 inner loop 
    400c28: 8b 50 fc    mov -0x4(%rax),%edx 
    400c2b: 01 10     add %edx,(%rax) 
    400c2d: 48 83 c0 04    add $0x4,%rax 
    400c31: 48 39 c1    cmp %rax,%rcx 
    400c34: 75 f2     jne 400c28 <_Z5test1v+0x18> 

    ;;;; test2 inner loop 
    400c50: 8b 0c 06    mov (%rsi,%rax,1),%ecx 
    400c53: 01 0c 02    add %ecx,(%rdx,%rax,1) 
    400c56: 48 83 c0 04    add $0x4,%rax 
    400c5a: 48 3d 00 1c 4e 0e  cmp $0xe4e1c00,%rax 
    400c60: 75 ee     jne 400c50 <_Z5test2v+0x10> 

comunque con -O3 test1 rimane più o meno simili

;;;; test1 inner loop 
    400d88: 03 10     add (%rax),%edx 
    400d8a: 48 83 c0 04    add $0x4,%rax 
    400d8e: 89 50 fc    mov %edx,-0x4(%rax) 
    400d91: 48 39 c1    cmp %rax,%rcx 
    400d94: 75 f2     jne 400d88 <_Z5test1v+0x18> 

mentre test2 esplode di quanto sembra una versione srotolata usando i registri xmm e genera codice macchina completamente diverso. Il ciclo interno diventa

;;;; test2 inner loop (after a lot of preprocessing) 
    400e30: f3 41 0f 6f 04 00  movdqu (%r8,%rax,1),%xmm0 
    400e36: 83 c1 01    add $0x1,%ecx 
    400e39: 66 0f fe 04 07   paddd (%rdi,%rax,1),%xmm0 
    400e3e: 0f 29 04 07    movaps %xmm0,(%rdi,%rax,1) 
    400e42: 48 83 c0 10    add $0x10,%rax 
    400e46: 44 39 c9    cmp %r9d,%ecx 
    400e49: 72 e5     jb  400e30 <_Z5test2v+0x90> 

e funziona con più aggiunte per ogni iterazione.

Se si desidera testare il comportamento specifico del processore, probabilmente scrivere direttamente in un assemblatore è un'idea migliore in quanto i compilatori C++ possono eseguire una pesante riscrittura di ciò che sta facendo il codice sorgente originale.