Immagina il codice assembly che verrebbe generato da:
if (__builtin_expect(x, 0)) {
foo();
...
} else {
bar();
...
}
Immagino che dovrebbe essere qualcosa del tipo:
cmp $x, 0
jne _foo
_bar:
call bar
...
jmp after_if
_foo:
call foo
...
after_if:
Puoi vedere che le istruzioni sono disposte in modo tale che il bar maiuscole e minuscole precede il foo caso (al contrario del codice C). Questo può utilizzare meglio la pipeline della CPU, poiché un salto esegue il thrash delle istruzioni già recuperate.
Prima che il salto venga eseguito, le istruzioni sottostanti (il bar caso) vengono inviati alla pipeline. Dal foo caso è improbabile, anche il salto è improbabile, quindi è improbabile che si rompa la pipeline.
Decompiliamo per vedere cosa ci fa GCC 4.8
Blagovest ha menzionato l'inversione del ramo per migliorare la pipeline, ma i compilatori attuali lo fanno davvero? Scopriamolo!
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)
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 0a jne 1a <main+0x1a>
10: bf 00 00 00 00 mov $0x0,%edi
11: R_X86_64_32 .rodata.str1.1
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
L'ordine delle istruzioni in memoria è rimasto invariato:prima il puts e poi 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 07 je 17 <main+0x17>
10: 31 c0 xor %eax,%eax
12: 48 83 c4 08 add $0x8,%rsp
16: c3 retq
17: bf 00 00 00 00 mov $0x0,%edi
18: R_X86_64_32 .rodata.str1.1
1c: e8 00 00 00 00 callq 21 <main+0x21>
1d: R_X86_64_PC32 puts-0x4
21: eb ed jmp 10 <main+0x10>
Il puts è stato spostato alla fine della funzione, il retq torna!
Il nuovo codice è fondamentalmente lo stesso di:
int i = !time(NULL);
if (i)
goto puts;
ret:
return 0;
puts:
puts("a");
goto ret;
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 quei 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.
L'idea di __builtin_expect è dire al compilatore che di solito troverai che l'espressione valuta c, in modo che il compilatore possa ottimizzare per quel caso.
Immagino che qualcuno pensasse di essere intelligente e che stesse accelerando le cose facendo questo.
Sfortunatamente, a meno che la situazione non sia compresa molto bene (è probabile che non abbiano fatto nulla del genere), potrebbe aver peggiorato le cose. La documentazione dice anche:
In generale, dovresti preferire utilizzare il feedback effettivo del profilo per questo (
-fprofile-arcs), poiché i programmatori sono notoriamente incapaci di prevedere le prestazioni effettive dei loro programmi. Tuttavia, ci sono applicazioni in cui questi dati sono difficili da raccogliere.
In generale, non dovresti usare __builtin_expect a meno che:
- Hai un vero problema di prestazioni
- Hai già ottimizzato gli algoritmi nel sistema in modo appropriato
- Disponi di dati sulle prestazioni a sostegno della tua affermazione secondo cui un caso particolare è il più probabile