massimo di 3 valori, prestazioni della versione associativa a sinistra rispetto alla versione associativa a destra

Question

Il seguente codice mostra una grande differenza di prestazioni delle due versioni di min_3 sulla mia macchina (Windows 7, VC++ 2015, versione).

#include <algorithm> 
#include <chrono> 
#include <iostream> 
#include <random> 

template <typename X> 
const X& max_3_left(const X& a, const X& b, const X& c) 
{ 
    return std::max(std::max(a, b), c); 
} 

template <typename X> 
const X& max_3_right(const X& a, const X& b, const X& c) 
{ 
    return std::max(a, std::max(b, c)); 
} 

int main() 
{ 
    std::random_device r; 
    std::default_random_engine e1(r()); 
    std::uniform_int_distribution<int> uniform_dist(1, 6); 
    std::vector<int> numbers; 
    for (int i = 0; i < 1000; ++i) 
     numbers.push_back(uniform_dist(e1)); 

    auto start1 = std::chrono::high_resolution_clock::now(); 
    int sum1 = 0; 
    for (int i = 0; i < 1000; ++i) 
     for (int j = 0; j < 1000; ++j) 
      for (int k = 0; k < 1000; ++k) 
       sum1 += max_3_left(numbers[i], numbers[j], numbers[k]); 
    auto finish1 = std::chrono::high_resolution_clock::now(); 
    std::cout << "left " << sum1 << " " << 
     std::chrono::duration_cast<std::chrono::microseconds>(finish1 - start1).count() 
     << " us" << std::endl; 

    auto start2 = std::chrono::high_resolution_clock::now(); 
    int sum2 = 0; 
    for (int i = 0; i < 1000; ++i) 
     for (int j = 0; j < 1000; ++j) 
      for (int k = 0; k < 1000; ++k) 
       sum2 += max_3_right(numbers[i], numbers[j], numbers[k]); 
    auto finish2 = std::chrono::high_resolution_clock::now(); 
    std::cout << "right " << sum2 << " " << 
     std::chrono::duration_cast<std::chrono::microseconds>(finish2 - start2).count() 
     << " us" << std::endl; 
} 

uscita:

left 739861041 796056 us 
right 739861041 1442495 us 

Sulla ideone la differenza è più piccola ma comunque non trascurabile.

Perché esiste questa differenza?

Answer 1

gcc e clang (e presumibilmente MSVC) riescono a capire che max è un'operazione associativa come aggiunta. v[i] max (v[j] max v[k]) (max_3_right) è uguale a (v[i] max v[j]) max v[k] (max_3_left). Sto scrivendo max come operatore infisso per indicare la somiglianza con + e altre operazioni associative.

Dal momento che v[k] è l'unico ingresso che sta cambiando all'interno del ciclo interno, è ovviamente una grande vittoria per sollevare il (v[i] max v[j]) dal ciclo interno.

---

Per vedere cosa sta succedendo, dobbiamo sempre guardare l'asm. Per semplificare la ricerca di asm per i loop, I split them out into separate functions. (Fare in modo che un modello funzioni con la funzione max3 come parametro sarebbe più simile a C++). Questo ha l'ulteriore vantaggio di prendere il codice che vogliamo ottimizzato da main, which gcc marks as "cold", disabling some optimizations.

#include <algorithm> 
#define SIZE 1000 
int sum_maxright(const std::vector<int> &v) { 
    int sum = 0; 
    for (int i = 0; i < SIZE; ++i) 
     for (int j = 0; j < SIZE; ++j) 
      for (int k = 0; k < SIZE; ++k) 
       sum += max_3_right(v[i], v[j], v[k]); 
    return sum; 
} 

Il ciclo interno-la maggior parte di che compila (GCC 5.3 mira x86-64 Linux ABI con -std=gnu++11 -fverbose-asm -O3 -fno-tree-vectorize -fno-unroll-loops -march=haswell con alcune annotazioni a mano)

## from outer loops: rdx points to v[k] (starting at v.begin()). r8 is v.end(). (r10 is v.begin) 
## edi is v[i], esi is v[j] 
## eax is sum 

## inner loop. See the full asm on godbolt.org, link below 
.L10: 
     cmp  DWORD PTR [rdx], esi  # MEM[base: _65, offset: 0], D.92793 
     mov  ecx, esi     # D.92793, D.92793 
     cmovge ecx, DWORD PTR [rdx]  # ecx = max(v[j], v[k]) 
     cmp  ecx, edi  # D.92793, D.92793 
     cmovl ecx, edi  # ecx = max(ecx, v[i]) 
     add  rdx, 4 # pointer increment 
     add  eax, ecx # sum, D.92793 
     cmp  rdx, r8 # ivtmp.253, D.92795 
     jne  .L10  #, 

Clang 3.8 rende il codice simile per il ciclo max_3_right, con due istruzioni cmov all'interno del ciclo interno.(Utilizzare il menu a discesa compilatore nel Godbolt Compiler Explorer per vedere.)

---

gcc e clangore sia ottimizzare il modo in cui ci si aspetterebbe per il ciclo max_3_left, sollevamento tutto, ma un unico cmov fuori dal ciclo interno.

## register allocation is slightly different here: 
## esi = max(v[i], v[j]). rdi = v.end() 
.L2: 
     cmp  DWORD PTR [rdx], ecx  # MEM[base: _65, offset: 0], D.92761 
     mov  esi, ecx # D.92761, D.92761 
     cmovge esi, DWORD PTR [rdx]  # MEM[base: _65, offset: 0],, D.92761 
     add  rdx, 4 # ivtmp.226, 
     add  eax, esi # sum, D.92761 
     cmp  rdx, rdi # ivtmp.226, D.92762 
     jne  .L2  #, 

Quindi c'è molto meno in corso in questo ciclo. (On Intel pre-Broadwell, cmov è un'istruzione 2-UOP, quindi uno in meno cmov è un grosso problema.)

---

BTW, di cache effetti prefetching non può assolutamente spiegare questa:

• L'anello interno accede a numbers[k] in sequenza. Gli accessi ripetuti a numbers[i] e numbers[j] vengono estratti dal loop interno da qualsiasi compilatore decente e non confondono i prefetcher moderni anche se non lo fossero.

  Intel's optimization manual dice che fino a 32 stream di modelli pre-lettura possono essere rilevati e mantenuti (con un limite di un avanti e indietro di una per pagina 4k), per microarchitetture Sandybridge famiglie (sezione 2.3.5.4 Prefetching dati).

  L'OP ha completamente omesso di dire su quale hardware ha eseguito questo microbenchmark, ma poiché i compilatori reali sollevano gli altri carichi lasciando solo il modello di accesso più banale, non ha importanza.

• uno vector di 1000 int s (4B) richiede solo 4kiB. Ciò significa che l'intero array si adatta facilmente alla cache L1D, quindi non è necessario alcun tipo di prefetch in primo luogo. Tutto rimane caldo nella cache L1 praticamente tutto il tempo.

Answer 2

Questo è correlato ai dati cache prefetching a livello hardware.

Se si utilizza la versione associativa di sinistra, gli elementi dell'array vengono utilizzati/caricati nella sequenza prevista dalla cache della CPU, con minore latenza.

La versione associativa corretta interrompe la previsione e genererà più errori di cache, quindi le prestazioni più lente.

Answer 3

Come sottolineato da molbdnilo, il problema potrebbe essere nell'ordine dei cicli. Nel calcolare sum1, il codice può essere riscritta come:

for (int i = 0; i < 1000; ++i) 
    for (int j = 0; j < 1000; ++j) { 
     auto temp = std::max(numbers[i], numbers[j]); 
     for (int k = 0; k < 1000; ++k) 
      sum1 += std::max(temp, numbers[k]); 
    } 

Lo stesso non può essere applicato per il calcolo di sum2. Tuttavia, quando ho reoredered il secondo loop come:

for (int j = 0; j < 1000; ++j) 
    for (int k = 0; k < 1000; ++k) 
     for (int i = 0; i < 1000; ++i) 
     sum2 += ...; 

ho ottenuto gli stessi tempi per entrambi i calcoli. (Inoltre, entrambi i calcoli sono molto più veloci con -O3 che con -O2. Il primo apparentemente accende vettorizzazione secondo uscita smontato.)