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

Trovo questo argomento Perché è più veloce elaborare una matrice ordinata rispetto a una matrice non ordinata? . E prova a eseguire questo codice. E trovo un comportamento strano. Se compilo questo codice con il -O3 ottimizzazione -O3 ci vuole 2.98605 sec per essere eseguito. Se compilo con -O2 ci vogliono 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, puoi spiegarmi perché succede? Leggo gcc manual e vedo che -O3 include -O2 . Grazie per il tuo aiuto.

PS aggiungi codice

 #include  #include  #include  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 = 128) sum += data[c]; } } double elapsedTime = static_cast(clock() - start) / CLOCKS_PER_SEC; std::cout << elapsedTime << std::endl; std::cout << "sum = " << sum << std::endl; } 

gcc -O3 usa un cmov per il condizionale, quindi allunga la catena di dipendenza trasportata dal ciclo per includere un cmov (che è 2 uops e 2 cicli di latenza sulla CPU Intel Sandybridge, secondo le tabelle di istruzioni di Agner Fog . tag wiki). Questo è uno dei casi in cui cmov schifo .

Se i dati fossero anche moderatamente imprevedibili, cmov sarebbe probabilmente una vittoria, quindi questa è una scelta abbastanza ragionevole da fare per un compilatore. (Tuttavia, i compilatori possono a volte usare troppo codice senza branch .)

Ho messo il tuo codice sul explorer del compilatore Godbolt per vedere l’asm (con una bella evidenziazione e filtrando le righe irrilevanti. Devi comunque scorrere verso il basso oltre il codice di ordinamento per arrivare a main (), comunque).

 .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 avrebbe potuto salvare il MOV usando LEA invece di 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 fusi, quindi può emettere uno per 2 cicli. Anche la pressione delle porte di esecuzione non è un collo di bottiglia tanto brutto quanto la latenza della catena di sumsum , ma è vicina (Sandybridge ha solo 3 porte ALU, a differenza del 4 di Haswell).

A proposito, scrivendolo come sum += (data[c] >= 128 ? data[c] : 0); portare il cmov fuori dalla catena di dep portata in loop è potenzialmente utile. Ancora molte istruzioni, ma il cmov in ogni iterazione è indipendente. Compilano come previsto in gcc6.3 -O2 e precedenti , 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 toglie il cmov dal percorso critico anche con la fonte originale.


gcc -O2 usa un ramo (per gcc5.x e precedenti), che predice bene perché i tuoi dati sono ordinati. Poiché le moderne CPU usano la branch-forecast per gestire le dipendenze di controllo, la catena di dipendenze del ciclo è più breve: solo un 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 

Esistono due catene di dipendenza trasportate da loop: sum e il contatore di loop. sum è 0 o 1 ciclo e il contatore dei 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 funziona a circa un 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 predizione dell’analisi della pipeline corrisponde quasi esattamente ai tempi di ~ 3 sec per -O3 vs. ~ 2 sec per -O2.


Haswell / Skylake potrebbe eseguire il caso non preso ad uno per 1,25 cicli, dal momento che può eseguire un ramo non preso nello stesso ciclo di un ramo preso e ha 4 porte ALU. (O un po ‘meno da quando un ciclo di 5 uop non si risolve a 4 UOP ad ogni ciclo ).

(Appena testato: Skylake @ 3.9GHz esegue la versione ramificata dell’intero programma in 1.45s, o la versione senza ramo in 1.68s. Quindi la differenza è molto più piccola lì.)


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

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

La versione CMOV del ciclo da newer gcc utilizza add ecx,-128 / cmovge rbx,rdx invece di 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.


Il nuovo gcc auto-vettorizza il ciclo con -O3, che è una significativa accelerazione anche con solo SSE2. (ad esempio, il mio i7-6700k Skylake esegue la versione vettoriale 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 vettorializzata ha un sacco di istruzioni, ma non è male, e la maggior parte di esse non fa parte di una catena di dep di gestione del ciclo. 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.