Suggeriscono al compilatore di emettere istruzioni che faranno sì che la previsione del ramo favorisca il lato "probabile" di un'istruzione di salto. Questa può essere una grande vittoria, se la previsione è corretta significa che l'istruzione di salto è sostanzialmente gratuita e richiederà zero cicli. D'altra parte, se la previsione è errata, significa che la pipeline del processore deve essere svuotata e può costare diversi cicli. Fintanto che la previsione è corretta per la maggior parte del tempo, questo tenderà ad essere positivo per le prestazioni.
Come tutte queste ottimizzazioni delle prestazioni, dovresti farlo solo dopo un'ampia profilazione per assicurarti che il codice si trovi davvero in un collo di bottiglia e, probabilmente, data la natura micro, che venga eseguito in un ciclo stretto. Generalmente gli sviluppatori di Linux sono piuttosto esperti, quindi immagino che l'avrebbero fatto. A loro non interessa molto la portabilità in quanto prendono di mira solo gcc e hanno un'idea molto precisa dell'assembly che vogliono generare.
Decompiliamo per vedere cosa ci fa GCC 4.8
Senza __builtin_expect
#include "stdio.h"
#include "time.h"
int main() {
/* Use time to prevent it from being optimized away. */
int i = !time(NULL);
if (i)
printf("%d\n", i);
puts("a");
return 0;
}
Compila e decompila con GCC 4.8.2 x86_64 Linux:
gcc -c -O3 -std=gnu11 main.c
objdump -dr main.o
Uscita:
0000000000000000 <main>:
0: 48 83 ec 08 sub $0x8,%rsp
4: 31 ff xor %edi,%edi
6: e8 00 00 00 00 callq b <main+0xb>
7: R_X86_64_PC32 time-0x4
b: 48 85 c0 test %rax,%rax
e: 75 14 jne 24 <main+0x24>
10: ba 01 00 00 00 mov $0x1,%edx
15: be 00 00 00 00 mov $0x0,%esi
16: R_X86_64_32 .rodata.str1.1
1a: bf 01 00 00 00 mov $0x1,%edi
1f: e8 00 00 00 00 callq 24 <main+0x24>
20: R_X86_64_PC32 __printf_chk-0x4
24: bf 00 00 00 00 mov $0x0,%edi
25: R_X86_64_32 .rodata.str1.1+0x4
29: e8 00 00 00 00 callq 2e <main+0x2e>
2a: R_X86_64_PC32 puts-0x4
2e: 31 c0 xor %eax,%eax
30: 48 83 c4 08 add $0x8,%rsp
34: c3 retq
L'ordine delle istruzioni in memoria era invariato:prima il printf e poi puts e il retq ritorno.
Con __builtin_expect
Ora sostituisci if (i) con:
if (__builtin_expect(i, 0))
e otteniamo:
0000000000000000 <main>:
0: 48 83 ec 08 sub $0x8,%rsp
4: 31 ff xor %edi,%edi
6: e8 00 00 00 00 callq b <main+0xb>
7: R_X86_64_PC32 time-0x4
b: 48 85 c0 test %rax,%rax
e: 74 11 je 21 <main+0x21>
10: bf 00 00 00 00 mov $0x0,%edi
11: R_X86_64_32 .rodata.str1.1+0x4
15: e8 00 00 00 00 callq 1a <main+0x1a>
16: R_X86_64_PC32 puts-0x4
1a: 31 c0 xor %eax,%eax
1c: 48 83 c4 08 add $0x8,%rsp
20: c3 retq
21: ba 01 00 00 00 mov $0x1,%edx
26: be 00 00 00 00 mov $0x0,%esi
27: R_X86_64_32 .rodata.str1.1
2b: bf 01 00 00 00 mov $0x1,%edi
30: e8 00 00 00 00 callq 35 <main+0x35>
31: R_X86_64_PC32 __printf_chk-0x4
35: eb d9 jmp 10 <main+0x10>
Il printf (compilato in __printf_chk ) è stato spostato alla fine della funzione, dopo puts e il ritorno per migliorare la previsione del ramo come menzionato da altre risposte.
Quindi è praticamente uguale a:
int main() {
int i = !time(NULL);
if (i)
goto printf;
puts:
puts("a");
return 0;
printf:
printf("%d\n", i);
goto puts;
}
Questa ottimizzazione non è stata eseguita con -O0 .
Ma buona fortuna per la scrittura di un esempio che funzioni più velocemente con __builtin_expect che senza, le CPU sono davvero intelligenti in questi giorni. I miei ingenui tentativi sono qui.
C++20 [[likely]] e [[unlikely]]
Il C++20 ha standardizzato questi built-in C++:Come utilizzare l'attributo probabile/improbabile del C++20 nell'istruzione if-else Probabilmente (un gioco di parole!) faranno la stessa cosa.
Queste sono macro che danno suggerimenti al compilatore su quale direzione può prendere un ramo. Le macro si espandono in estensioni specifiche di GCC, se disponibili.
GCC li utilizza per ottimizzare la previsione dei rami. Ad esempio, se hai qualcosa di simile al seguente
if (unlikely(x)) {
dosomething();
}
return x;
Quindi può ristrutturare questo codice in modo che sia qualcosa di più simile a:
if (!x) {
return x;
}
dosomething();
return x;
Il vantaggio di ciò è che quando il processore prende un ramo per la prima volta, c'è un sovraccarico significativo, perché potrebbe aver caricato ed eseguito speculativamente il codice più avanti. Quando determina che prenderà il ramo, deve invalidarlo e iniziare dall'obiettivo del ramo.
La maggior parte dei processori moderni ora ha una sorta di predizione del ramo, ma questo aiuta solo quando hai già attraversato il ramo e il ramo è ancora nella cache di previsione del ramo.
Esistono numerose altre strategie che il compilatore e il processore possono utilizzare in questi scenari. Puoi trovare maggiori dettagli su come funzionano i predittori di rami su Wikipedia:http://en.wikipedia.org/wiki/Branch_predictor