Come funzionano le macro probabili () e improbabili () nel kernel di Linux e qual è il loro vantaggio?

Ho scavato alcune parti del kernel di Linux e ho trovato chiamate come questa:

if (unlikely(fd < 0)) { /* Do something */ } 

o

 if (likely(!err)) { /* Do something */ } 

Ho trovato la definizione di loro:

 #define likely(x) __builtin_expect((x),1) #define unlikely(x) __builtin_expect((x),0) 

So che sono per l’ottimizzazione, ma come funzionano? E quanta riduzione di prestazioni / dimensioni può essere prevista dal loro utilizzo? E vale la pena (e probabilmente perdere la portabilità) almeno nel codice del collo di bottiglia (in userspace, ovviamente).

Sono suggerimenti per il compilatore di emettere istruzioni che causeranno la previsione del ramo per favorire il lato “probabile” di un’istruzione di salto. Questo può essere una grande vittoria, se la previsione è corretta significa che l’istruzione di salto è fondamentalmente libera e richiederà zero cicli. D’altro canto, se la previsione è sbagliata, significa che la pipeline del processore deve essere svuotata e può costare diversi cicli. Finché la previsione è corretta per la maggior parte del tempo, questo tenderà ad essere buono per le prestazioni.

Come tutte le ottimizzazioni delle prestazioni, dovresti farlo solo dopo una profilazione approfondita per assicurarti che il codice sia realmente in un collo di bottiglia, e probabilmente dato il carattere micro, che venga eseguito in un ciclo stretto. Generalmente gli sviluppatori Linux sono piuttosto esperti quindi immagino che lo avrebbero fatto. Non si preoccupano troppo della portabilità perché scelgono solo gcc e hanno un’idea molto vicina dell’assembly che vogliono generare.

Queste sono macro che forniscono suggerimenti al compilatore sul modo in cui un ramo può andare. Le macro si espandono alle estensioni specifiche GCC, se disponibili.

GCC li usa per ottimizzare per la previsione delle filiali. Ad esempio, se hai qualcosa di simile al seguente

 if (unlikely(x)) { dosomething(); } return x; 

Quindi può ristrutturare questo codice per essere qualcosa di più simile a:

 if (!x) { return x; } dosomething(); return x; 

Il vantaggio di questo è che quando il processore prende un ramo per la prima volta, vi è un sovraccarico significativo, perché potrebbe essere stato il caricamento e l’esecuzione speculativa del codice più avanti. Quando determina che prenderà il ramo, allora deve invalidarlo e iniziare dal target del ramo.

La maggior parte dei processori moderni ha ora una sorta di previsione dei rami, ma solo quando si è passati attraverso il ramo e il ramo si trova ancora nella cache di previsione dei rami.

Esistono numerose altre strategie che il compilatore e il processore possono utilizzare in questi scenari. Puoi trovare maggiori dettagli su come predittori di ramo su Wikipedia: http://en.wikipedia.org/wiki/Branch_predictor

Decompiliamo per vedere cosa fa GCC 4.8 con esso

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; } 

Compilare e decompilare con GCC 4.8.2 x86_64 Linux:

 gcc -c -O3 -std=gnu11 main.c objdump -dr main.o 

Produzione:

 0000000000000000 
: 0: 48 83 ec 08 sub $0x8,%rsp 4: 31 ff xor %edi,%edi 6: e8 00 00 00 00 callq b
7: R_X86_64_PC32 time-0x4 b: 48 85 c0 test %rax,%rax e: 75 14 jne 24
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
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
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 è rimasto invariato: prima la printf e poi puts e il retq restituisce.

Con __builtin_expect

Ora sostituire if (i) con:

 if (__builtin_expect(i, 0)) 

e otteniamo:

 0000000000000000 
: 0: 48 83 ec 08 sub $0x8,%rsp 4: 31 ff xor %edi,%edi 6: e8 00 00 00 00 callq b
7: R_X86_64_PC32 time-0x4 b: 48 85 c0 test %rax,%rax e: 74 11 je 21
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
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
31: R_X86_64_PC32 __printf_chk-0x4 35: eb d9 jmp 10

Il printf (compilato per __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 è fondamentalmente lo stesso di:

 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 a scrivere un esempio che gira più velocemente con __builtin_expect che senza, le CPU sono davvero intelligenti in questi giorni . I miei ingenui tentativi sono qui .

Fanno in modo che il compilatore emetta i suggerimenti di ramo appropriati in cui l’hardware li supporta. Questo di solito significa semplicemente girare qualche bit nell’opcode dell’istruzione, quindi la dimensione del codice non cambierà. La CPU inizierà a recuperare le istruzioni dalla posizione prevista, a svuotare la pipeline e ricominciare da capo se ciò risulta errato al raggiungimento del ramo; nel caso in cui il suggerimento sia corretto, questo renderà il ramo molto più veloce – precisamente quanto più veloce dipenderà dall’hardware; e quanto questo influisce sulle prestazioni del codice dipenderà da quale proporzione del suggerimento temporale è corretta.

Ad esempio, su una CPU PowerPC un ramo non allacciato potrebbe richiedere 16 cicli, uno accostato correttamente a 8 e uno suggerito in modo errato. 24. Nei loop più interni un buon accenno può fare un’enorme differenza.

La portabilità non è davvero un problema – presumibilmente la definizione è in un’intestazione per piattaforma; puoi semplicemente definire “probabile” e “improbabile” a zero per piattaforms che non supportano i suggerimenti sulle derivazioni statiche.

 long __builtin_expect(long EXP, long C); 

Questo costrutto dice al compilatore che l’espressione EXP molto probabilmente avrà il valore C. Il valore restituito è EXP. __builtin_expect è pensato per essere utilizzato in un’espressione condizionale. In quasi tutti i casi verrà utilizzato nel contesto di espressioni booleane, nel qual caso è molto più conveniente definire due macro di supporto:

 #define unlikely(expr) __builtin_expect(!!(expr), 0) #define likely(expr) __builtin_expect(!!(expr), 1) 

Queste macro possono quindi essere utilizzate come in

 if (likely(a > 1)) 

Riferimento: https://www.akkadia.org/drepper/cpumemory.pdf

(commento generale – altre risposte coprono i dettagli)

Non c’è motivo per cui dovresti perdere la portabilità usandoli.

Hai sempre la possibilità di creare un semplice effetto “in linea” o macro che ti consentirà di compilare su altre piattaforms con altri compilatori.

Non otterrai il vantaggio dell’ottimizzazione se sei su altre piattaforms.

Come per il commento di Cody , questo non ha nulla a che fare con Linux, ma è un suggerimento per il compilatore. Quello che succede dipenderà dall’architettura e dalla versione del compilatore.

Questa particolare caratteristica di Linux è piuttosto errata nei driver. Come Osgx fa notare nella semantica dell’attributo hot , qualsiasi funzione hot o cold chiamata con in un blocco può suggerire automaticamente che la condizione sia probabile o meno. Ad esempio, dump_stack() è marcato a cold quindi è ridondante,

  if(unlikely(err)) { printk("Driver error found. %d\n", err); dump_stack(); } 

Le versioni future di gcc potrebbero inlineizzare in modo selettivo una funzione basata su questi suggerimenti. Ci sono stati anche suggerimenti che non è boolean , ma un punteggio come molto probabilmente , ecc. In generale, dovrebbe essere preferibile utilizzare un meccanismo alternativo come il cold . Non vi è alcun motivo per utilizzarlo in qualsiasi posto, ma percorsi caldi. Ciò che un compilatore farà su un’architettura può essere completamente diverso su un altro.

In molte versioni di Linux, puoi trovare complier.h in / usr / linux /, puoi includerlo semplicemente per l’uso. E un’altra opinione, improbabile () è più utile piuttosto che probabile (), perché

 if ( likely( ... ) ) { doSomething(); } 

può essere ottimizzato anche in molti compilatori.

E a proposito, se vuoi osservare il comportamento dei dettagli del codice, puoi fare semplicemente come segue:

gcc -c test.c objdump -d test.o> obj.s

Quindi, apri obj.s, puoi trovare la risposta.

Sono suggerimenti per il compilatore per generare i prefissi di suggerimento sui rami. Su x86 / x64, occupano un byte, quindi ottieni al massimo un aumento di un byte per ogni ramo. Per quanto riguarda le prestazioni, dipende interamente dall’applicazione – in molti casi, il predittore di ramo sul processore le ignorerà, al giorno d’oggi.

Modifica: Hai dimenticato un posto in cui possono davvero aiutarti. Può consentire al compilatore di riordinare il grafico del stream di controllo per ridurre il numero di rami presi per il percorso “probabile”. Questo può avere un netto miglioramento nei cicli in cui stai controllando più casi di uscita.

Queste sono le funzioni GCC per il programmatore per dare un suggerimento al compilatore su quale sarà la condizione di ramo più probabile in una determinata espressione. Ciò consente al compilatore di compilare le istruzioni del ramo in modo che il caso più comune impieghi il minor numero di istruzioni da eseguire.

Il modo in cui le istruzioni di ramo sono costruite dipende dall’architettura del processore.