flag di ottimizzazione gcc -O3 rende il codice più lento quindi -O2

Question

Trovo questo argomento Why is it faster to process a sorted array than an unsorted array?. E prova a eseguire questo codice. E trovo un comportamento strano. Se compilo questo codice con il flag di ottimizzazione -O3, è necessario eseguire 2.98605 sec. Se compilo con -O2 ci vuole 1.98093 sec. Cerco di eseguire questo codice più volte (5 o 6) sulla stessa macchina nello stesso ambiente, chiudo tutti gli altri software (chrome, skype etc).

gcc --version 
gcc (Ubuntu 4.9.2-0ubuntu1~14.04) 4.9.2 
Copyright (C) 2014 Free Software Foundation, Inc. 
This is free software; see the source for copying conditions. There is NO 
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 

Quindi, per favore si può spiegare a me perché questo accade? Ho letto il manuale gcc e vedo che -O3 include -O2. Grazie per il tuo aiuto.

P.S. metti codice

#include <algorithm> 
#include <ctime> 
#include <iostream> 

int main() 
{ 
    // Generate data 
    const unsigned arraySize = 32768; 
    int data[arraySize]; 

    for (unsigned c = 0; c < arraySize; ++c) 
     data[c] = std::rand() % 256; 

    // !!! With this, the next loop runs faster 
    std::sort(data, data + arraySize); 

    // Test 
    clock_t start = clock(); 
    long long sum = 0; 

    for (unsigned i = 0; i < 100000; ++i) 
    { 
     // Primary loop 
     for (unsigned c = 0; c < arraySize; ++c) 
     { 
      if (data[c] >= 128) 
       sum += data[c]; 
     } 
    } 

    double elapsedTime = static_cast<double>(clock() - start)/CLOCKS_PER_SEC; 

    std::cout << elapsedTime << std::endl; 
    std::cout << "sum = " << sum << std::endl; 
} 

Answer 1

gcc -O3 utilizza un cmov per il condizionale, quindi si allunga la catena di dipendenza loop-portato per includere un cmov (che è 2 UOP e 2 cicli di latenza sul Intel Sandybridge CPU, secondo Agner Fog's instruction tables Vedi anche il wiki del tag x86). Questo è one of the cases where cmov sucks.

Se i dati erano anche moderatamente imprevedibili, cmov sarebbe probabilmente una vittoria, quindi questa è una scelta abbastanza ragionevole da fare per un compilatore. (Tuttavia, compilers may sometimes use branchless code too much.)

I put your code on the Godbolt compiler explorer per visualizzare il comando asm (con una bella evidenziazione e il filtraggio di righe non pertinenti. È comunque necessario scorrere verso il basso oltre il codice di ordinamento per arrivare a main(), sebbene).

.L82: # the inner loop from gcc -O3 
    movsx rcx, DWORD PTR [rdx] # sign-extending load of data[c] 
    mov  rsi, rcx 
    add  rcx, rbx  # rcx = sum+data[c] 
    cmp  esi, 127 
    cmovg rbx, rcx  # sum = data[c]>127 ? rcx : sum 
    add  rdx, 4   # pointer-increment 
    cmp  r12, rdx 
    jne  .L82 

gcc potrebbe aver salvato il MOV utilizzando LEA anziché ADD.

I colli di bottiglia del ciclo sulla latenza di ADD-> CMOV (3 cicli), poiché un'iterazione del ciclo scrive rbx con CMO e l'iterazione successiva legge rbx con ADD.

Il loop contiene solo 8 bit di dominio fuso, quindi può essere emesso a uno per 2 cicli. Anche la pressione delle porte di esecuzione non rappresenta un collo di bottiglia tanto male quanto la latenza della catena di depostaggio sum, ma è vicina (Sandybridge ha solo 3 porte ALU, a differenza di Haswell 4).

BTW, scrivendo come sum += (data[c] >= 128 ? data[c] : 0); per prendere il cmov fuori dalla catena di dep portata in ciclo è potenzialmente utile. Ancora un sacco di istruzioni, ma il cmov in ogni iterazione è indipendente. Questo compiles as expected in gcc6.3 -O2 and earlier, ma gcc7 de-ottimizza in un cmov sul percorso critico (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82666). (Si auto-vettorizza anche con versioni precedenti di gcc rispetto al modo if() di scriverlo.)

Clang elimina il cmov dal percorso critico anche con la fonte originale.

---

gcc -O2 utilizza un ramo (per gcc5.x e anziani), che predice bene perché i dati vengono ordinati. Dato che le moderne CPU usano la branch-forecast per gestire le dipendenze di controllo, la catena di dipendenze del ciclo è più breve: solo una add (1 ciclo di latenza).

Il confronto-e-ramo in ogni iterazione è indipendente, grazie alla branch-prediction + all'esecuzione speculativa, che consente di continuare l'esecuzione prima che la direzione del ramo sia nota.

.L83: # The inner loop from gcc -O2 
    movsx rcx, DWORD PTR [rdx] # load with sign-extension from int32 to int64 
    cmp  ecx, 127 
    jle  .L82  # conditional-jump over the next instruction 
    add  rbp, rcx # sum+=data[c] 
.L82: 
    add  rdx, 4 
    cmp  rbx, rdx 
    jne  .L83 

Ci sono due catene di dipendenza loop effettuato: sum e loop-counter. sum è lungo 0 o 1 ciclo e il contatore di loop è sempre lungo 1 ciclo. Tuttavia, il ciclo è di 5 bit di dominio fusi su Sandybridge, quindi non può essere eseguito a 1c per iterazione comunque, quindi la latenza non è un collo di bottiglia.

Probabilmente viene eseguito a circa una iterazione per 2 cicli (con collo di bottiglia sul throughput dell'istruzione di ramo), contro uno per 3 cicli per il ciclo -O3. Il prossimo collo di bottiglia sarebbe il throughput di ALU uop: 4 UU di ALU (nel caso non preso) ma solo 3 porte di ALU. (ADD può essere eseguito su qualsiasi porta).

Questa previsione dell'analisi della pipeline corrisponde esattamente ai tempi di ~ 3 sec per -O3 contro ~ 2 sec per -O2.

---

Haswell/Skylake potrebbe correre il caso non-rilevamenti al 1,25 per cicli, dal momento che può eseguire un ramo non-presa nello stesso ciclo come ramo presa e ha 4 porte ALU. (O leggermente meno dal a 5 uop loop doesn't quite issue at 4 uops every cycle).

(appena testato:.. Skylake @ 3.9GHz esegue la versione branchy di tutto il programma in 1.45s, o la versione senza rami in 1.68s Quindi la differenza è molto più piccolo c'è)

---

g + +6.3.1 utilizza cmov anche a -O2, ma g ++ 5.4 si comporta ancora come 4.9.2.

Con entrambi g ++ 6.3.1 e 5.4 g ++, utilizzando -fprofile-generate/-fprofile-use produce la versione branchy anche a -O3 (con -fno-tree-vectorize).

La versione CMOV del ciclo da newer gcc utilizza add ecx,-128/cmovge rbx,rdx anziché CMP/CMOV. È piuttosto strano, ma probabilmente non lo rallenta. ADD scrive un registro di output e flag, quindi crea più pressione sul numero di registri fisici. Ma fintanto che non è un collo di bottiglia, dovrebbe essere uguale.

---

recente gcc auto-vettorizza il ciclo con -O3, che è un aumento di velocità significativo anche con una SSE2. (ad esempio, il mio i7-6700k Skylake esegue la versione vettorizzata in 0,74s, quindi circa il doppio più veloce di uno scalare oppure -O3 -march=native in 0,35s, utilizzando i vettori AVX2 256b).

La versione vettorizzata ha un sacco di istruzioni, ma non è male, e la maggior parte di esse non fa parte di una catena di dep di trasporto. Deve solo decomprimere gli elementi a 64 bit verso la fine. Lo fa pcmpgtd due volte, però, perché non si rende conto che potrebbe semplicemente estendere zero anziché sign-extend quando la condizione ha già azzerato tutti gli interi negativi.