Spero di aver ridotto la mia domanda a un caso di test semplice e riproducibile. La sorgente (che è here) contiene 10 copie di un loop semplice identico. Ogni ciclo è nella forma:Perché le copie identiche dello stesso ciclo C nello stesso programma richiedono tempi significativamente diversi ma coerenti per l'esecuzione?
#define COUNT (1000 * 1000 * 1000)
volatile uint64_t counter = 0;
void loopN(void) {
for (int j = COUNT; j != 0; j--) {
uint64_t val = counter;
val = val + 1;
counter = val;
}
return;
}
Il 'volatili' della variabile è importante, in quanto costringe il valore di lettura e scrittura dalla memoria ad ogni iterazione. Ogni loop è allineato a 64 byte utilizzando '-falign-loop = 64' e produce montaggio identiche tranne che per l'offset al globale relativa:
400880: 48 8b 15 c1 07 20 00 mov 0x2007c1(%rip),%rdx # 601048 <counter>
400887: 48 83 c2 01 add $0x1,%rdx
40088b: 83 e8 01 sub $0x1,%eax
40088e: 48 89 15 b3 07 20 00 mov %rdx,0x2007b3(%rip) # 601048 <counter>
400895: 75 e9 jne 400880 <loop8+0x20>
sto con Linux 3.11 su un i7-4470 Intel Haswell. Sto compilando il programma con GCC 4.8.1 e la linea di comando:
gcc -std=gnu99 -O3 -falign-loops=64 -Wall -Wextra same-function.c -o same-function
Sono anche utilizzando attributo ((noinline)) nella fonte di rendere il montaggio più chiara, ma questo non è necessario per osservare il problema. Ho trovato le funzioni veloce e più lento con un ciclo shell:
for n in 0 1 2 3 4 5 6 7 8 9;
do echo same-function ${n}:;
/usr/bin/time -f "%e seconds" same-function ${n};
/usr/bin/time -f "%e seconds" same-function ${n};
/usr/bin/time -f "%e seconds" same-function ${n};
done
Si produce risultati coerenti a circa 1% da un'analisi all'altra, con i numeri esatti del più veloce e funzioni lente variano a seconda del binario esatto Layout:
same-function 0:
2.08 seconds
2.04 seconds
2.06 seconds
same-function 1:
2.12 seconds
2.12 seconds
2.12 seconds
same-function 2:
2.10 seconds
2.14 seconds
2.11 seconds
same-function 3:
2.04 seconds
2.04 seconds
2.05 seconds
same-function 4:
2.05 seconds
2.00 seconds
2.03 seconds
same-function 5:
2.07 seconds
2.07 seconds
1.98 seconds
same-function 6:
1.83 seconds
1.83 seconds
1.83 seconds
same-function 7:
1.95 seconds
1.98 seconds
1.95 seconds
same-function 8:
1.86 seconds
1.88 seconds
1.86 seconds
same-function 9:
2.04 seconds
2.04 seconds
2.02 seconds
In questo caso, vediamo che che Loop2() è una delle più lente da eseguire e loop6() è uno dei più veloci, con una differenza poco più del 10%. Riconfermiamo questo testando solo questi due casi ripetutamente con un metodo diverso:
[email protected]$ N=2; for i in {1..10}; do perf stat same-function $N 2>&1 | grep GHz; done
7,180,104,866 cycles # 3.391 GHz
7,169,930,711 cycles # 3.391 GHz
7,150,190,394 cycles # 3.391 GHz
7,188,959,096 cycles # 3.391 GHz
7,177,272,608 cycles # 3.391 GHz
7,093,246,955 cycles # 3.391 GHz
7,210,636,865 cycles # 3.391 GHz
7,239,838,211 cycles # 3.391 GHz
7,172,716,779 cycles # 3.391 GHz
7,223,252,964 cycles # 3.391 GHz
[email protected]$ N=6; for i in {1..10}; do perf stat same-function $N 2>&1 | grep GHz; done
6,234,770,361 cycles # 3.391 GHz
6,199,096,296 cycles # 3.391 GHz
6,213,348,126 cycles # 3.391 GHz
6,217,971,263 cycles # 3.391 GHz
6,224,779,686 cycles # 3.391 GHz
6,194,117,897 cycles # 3.391 GHz
6,225,259,274 cycles # 3.391 GHz
6,244,391,509 cycles # 3.391 GHz
6,189,972,381 cycles # 3.391 GHz
6,205,556,306 cycles # 3.391 GHz
Considerando questo confermato, rileggiamo ogni parola in ogni Intel manuale di architettura mai scritto, setacciare ogni pagina su tutto il web che cita le parole "computer" o "programmazione" e meditano isolatamente su una montagna per 6 anni. Non riuscendo a raggiungere alcun tipo di illuminazione, arriviamo alla civiltà, ci radiamo la barba, facciamo il bagno e chiediamo agli esperti di StackOverflow:
Cosa può accadere qui?
Modifica: Con l'aiuto di Benjamin (vedere la risposta di seguito) Ho trovato un altro succinct test case. Sono 20 linee di montaggio indipendenti. Il passaggio da SUB a SBB causa una differenza del 15% nelle prestazioni anche se il risultato rimane lo stesso e viene eseguito lo stesso numero di istruzioni. Spiegazioni? Penso che mi sto avvicinando a uno.
; Minimal example, see also http://stackoverflow.com/q/26266953/3766665
; To build (Linux):
; nasm -felf64 func.asm
; ld func.o
; Then run:
; perf stat -r10 ./a.out
; On Haswell and Sandy Bridge, observed runtime varies
; ~15% depending on whether sub or sbb is used in the loop
section .text
global _start
_start:
push qword 0h ; put counter variable on stack
jmp loop ; jump to function
align 64 ; function alignment.
loop:
mov rcx, 1000000000
align 64 ; loop alignment.
l:
mov rax, [rsp]
add rax, 1h
mov [rsp], rax
; sbb rcx, 1h ; which is faster: sbb or sub?
sub rcx, 1h ; switch, time it, and find out
jne l ; (rot13 spoiler: foo vf snfgre ol 15%)
fin: ; If that was too easy, explain why.
mov eax, 60
xor edi, edi ; End of program. Exit with code 0
syscall
Come stai contabili per processi in background che interrompono il vostro programma? (Non ho molta familiarità con Linux, ma su Windows questo è un grosso problema quando si prova a utilizzare il codice semplice ma a lunga esecuzione.) Quando il thread va in sospensione, trascorre un intervallo di tempo sconosciuto non in esecuzione quando il timer è ancora - probabile - ticchettio. – xxbbcc
Questo non sembra essere un problema con contesa del processore. Ciò potrebbe spiegare la variazione dei tempi tra le esecuzioni per lo stesso N, ma non tiene conto della differenza consistente e statisticamente significativa dei runtime per diversi N. –
Qual è l'allineamento degli indirizzi per, ad esempio, 'loop6' e' loop1 '- Sono entrambi allineati a 32 byte? Hanno lo stesso allineamento generale? –