gcc arithmetics simple loop performance

Question

Il problema: una riga evidente di un codice accelera un programma quasi due volte.

Questo è piuttosto difficile da formulare un problema originale, deriva da un algoritmo di eliminazione del controllo dei limiti. Quindi, solo un semplice test che non riesco a capire.

Una riga in più evidente di un codice porta ad accelerare un programma quasi due volte.

C'è fonte seguente:

#include <stdlib.h> 
#include <stdio.h> 

int main(void) 
{ 
    long i = 0, a = 0, x = 0; 
    int up = 200000000; 

    int *values = malloc(sizeof(int)*up); 

    for (i = 0; i < up ; ++i) 
    { 
     values[i]=i % 2; 
    } 
    for (i = 0; i < up ; ++i) 
    { 
     x = (a & i); 
#ifdef FAST 
     x = 0; 
#endif 
     a += values[x]; 
    } 
    printf ("a=%ld\n", a); 
    return 0; 
}/*main*/ 

In questo esempio il valore 'a' è sempre 0. La linea x = 0; è extra.

Ma, (aspetto -! NO alcuna ottimizzazione)
$ gcc -o -O0 breve short.c & & tempo ./short
a = 0
reali 0m2.808s
0m2.196s utente
sys 0m0.596s

$ gcc -O0 -DFAST -o brevi short.c & & tempo ./short
a = 0
0m1.869s reali
utente 0m1.260s
sys 0m0.608s

E, questo è riproducibile su molti compilatori/opzioni di ottimizzazione e variazioni di programma.

Inoltre, hanno veramente lo stesso codice assemblatore, tranne che per mettere questo stupido 0 in più in qualche registro! Ad esempio:

gcc -S -O0 -DFAST short.c & & mv short.s shortFAST.s
gcc -S -O0 short.c & & short.s mv shortSLOW.s
shortFAST.s diff shortSLOW.s
55d54
< movq $ 0, -24 (% RBP)

E, un po 'dopo - lo stesso effetto su alcune (tutto quello che ho avuto modo di testare) altri compilatori/lingue (tra cui Java JIT). L'unica cosa è stata condivisa - l'architettura x86-64. È stato testato su processori Intel e AMD ...

Answer 1

Risposta breve: l'archiviazione di uno 0 elimina una dipendenza di lettura dopo scrittura in uno dei loop.

Dettagli:

ho pensato che questo era una domanda interessante, e anche se vi siete concentrati sul livello di ottimizzazione O0, lo stesso aumento di velocità è visto a O3 pure. Ma guardando O0 è più facile concentrarsi su ciò che il processore sta facendo per ottimizzare il codice piuttosto che sul compilatore, perché come si è notato il codice di assemblaggio risultante differisce solo di 1 istruzione.

Il codice assembly per il ciclo di interesse Di seguito è mostrata

movq $0, -32(%rbp) 
    jmp .L4 
.L5:  
    movq -32(%rbp), %rax 
    movq -24(%rbp), %rdx 
    andq %rdx, %rax  
    movq %rax, -16(%rbp) 
    movq $0, -16(%rbp)  ;; This instruction in FAST but not SLOW 
    movq -16(%rbp), %rax 
    leaq 0(,%rax,4), %rdx 
    movq -8(%rbp), %rax 
    addq %rdx, %rax  
    movl (%rax), %eax  
    cltq     
    addq %rax, -24(%rbp) 
    addq $1, -32(%rbp) 
.L4:      
    movl -36(%rbp), %eax 
    cltq     
    cmpq -32(%rbp), %rax 
    jg .L5  

Correndo con perf stat sul mio sistema ottengo i seguenti risultati:

Risultati per codice lento

Performance counter stats for './slow_o0': 

    1827.438670 task-clock    # 0.999 CPUs utilized   
      155 context-switches   # 0.085 K/sec     
      1 CPU-migrations   # 0.001 K/sec     
     195,448 page-faults    # 0.107 M/sec     
6,675,246,466 cycles     # 3.653 GHz      
4,391,690,661 stalled-cycles-frontend # 65.79% frontend cycles idle 
1,609,321,845 stalled-cycles-backend # 24.11% backend cycles idle 
7,157,837,211 instructions    # 1.07 insns per cycle   
             # 0.61 stalled cycles per insn 
    490,110,757 branches     # 268.195 M/sec     
     178,287 branch-misses    # 0.04% of all branches   

    1.829712061 seconds time elapsed 

Risultati per codice rapido

Performance counter stats for './fast_o0': 

    1109.451910 task-clock    # 0.998 CPUs utilized   
      95 context-switches   # 0.086 K/sec     
      1 CPU-migrations   # 0.001 K/sec     
     195,448 page-faults    # 0.176 M/sec     
4,067,613,078 cycles     # 3.666 GHz      
1,784,131,209 stalled-cycles-frontend # 43.86% frontend cycles idle 
    438,447,105 stalled-cycles-backend # 10.78% backend cycles idle 
7,356,892,998 instructions    # 1.81 insns per cycle   
             # 0.24 stalled cycles per insn 
    489,945,197 branches     # 441.610 M/sec     
     176,136 branch-misses    # 0.04% of all branches   

    1.111398442 seconds time elapsed 

Così si può vedere che anche se il codice "veloce" esegue più istruzioni ha meno stalli. Quando una CPU out-of-order (come la maggior parte delle architetture x64) sta eseguendo il codice, tiene traccia delle dipendenze tra le istruzioni. Un'istruzione di attesa può essere ignorata da un'altra istruzione se gli operandi sono pronti.

In questo esempio il punto critico è probabile che questa sequenza di istruzioni:

andq %rdx, %rax 
    movq %rax, -16(%rbp) 
    movq $0, -16(%rbp)  ;; This instruction in FAST but not SLOW 
    movq -16(%rbp), %rax 
    leaq 0(,%rax,4), %rdx 
    movq -8(%rbp), %rax  

Nel codice veloce l'istruzione movq -8(%rbp), %rax otterrà il risultato da movq $0, -16(%rbp) trasmessole e sarà in grado di eseguire più presto. Considerando che la versione più lenta dovrà attendere il movq %rax, -16(%rbp) che ha più dipendenze tra iterazioni di loop.

Si noti che senza saperne di più sulla microarchitettura specifica, questa analisi è probabilmente troppo semplicistica. Ma sospetto che la causa sottostante sia questa dipendenza e che l'esecuzione dell'archivio di 0 (l'istruzione movq $0, -16(%rbp)) consenta alla CPU di eseguire una speculazione più aggressiva durante l'esecuzione della sequenza di codice.