Come funzionano le macro probabili / improbabili nel kernel Linux e quali sono i loro vantaggi?
https://stackoverflow.com/questions/109710
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho cercato alcune parti del kernel Linux e ho trovato chiamate come questa:
if (unlikely(fd < 0))
{
/* Do something */
}
o
if (likely(!err))
{
/* Do something */
}
Ne ho trovato la definizione:
#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 ci si può aspettare dal loro utilizzo? E vale la pena (probabilmente perdere la portabilità) almeno nel codice del collo di bottiglia (nello spazio utente, ovviamente).
Soluzione
Stanno suggerendo al compilatore di emettere istruzioni che indurranno la previsione del ramo a favorire il "probabile" lato 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 buono per le prestazioni.
Come tutte queste ottimizzazioni delle prestazioni, dovresti farlo solo dopo una profilatura approfondita per garantire che il codice sia davvero un collo di bottiglia, e probabilmente data la micro natura, che viene eseguito in un ciclo stretto. Generalmente gli sviluppatori Linux sono piuttosto esperti quindi immagino che lo avrebbero fatto. A loro non importa molto della portabilità poiché prendono di mira solo gcc e hanno un'idea molto stretta dell'assemblaggio che vogliono che generi.
Altri suggerimenti
Queste sono macro che danno suggerimenti al compilatore su come può andare un ramo. Le macro si espandono in estensioni specifiche di GCC, se disponibili.
GCC li utilizza per ottimizzare la previsione delle filiali. Ad esempio, se hai qualcosa di simile al seguente
if (unlikely(x)) {
dosomething();
}
return x;
Quindi può ristrutturare questo codice in modo che assuma qualcosa di più simile a:
if (!x) {
return x;
}
dosomething();
return x;
Il vantaggio di questo è che quando il processore prende una filiale per la prima volta, si ha un sovraccarico significativo, perché potrebbe essere stato speculativamente caricando ed eseguendo il codice più avanti. Quando determina che prenderà il ramo, allora deve invalidarlo e iniziare dalla destinazione del ramo.
La maggior parte dei processori moderni ora ha una sorta di previsione del ramo, ma ciò aiuta solo quando si è già passati attraverso il ramo e il ramo è ancora nella cache di previsione del ramo.
Esistono diverse altre strategie che il compilatore e il processore possono utilizzare in questi scenari. Puoi trovare maggiori dettagli su come funzionano i predittori di filiali su Wikipedia: http://en.wikipedia.org/wiki / Branch_predictor
Decompiliamo per vedere cosa 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
Output:
0000000000000000 <main>:
0: 48 83 ec 08 sub if (__builtin_expect(i, 0))
x8,%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 0000000000000000 <main>:
0: 48 83 ec 08 sub int i = !time(NULL);
if (i)
goto printf;
puts:
puts("a");
return 0;
printf:
printf("%d\n", i);
goto puts;
x8,%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 <*>x0,%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 <*>x8,%rsp
20: c3 retq
21: ba 01 00 00 00 mov <*>x1,%edx
26: be 00 00 00 00 mov <*>x0,%esi
27: R_X86_64_32 .rodata.str1.1
2b: bf 01 00 00 00 mov <*>x1,%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>
x1,%edx
15: be 00 00 00 00 mov <*>x0,%esi
16: R_X86_64_32 .rodata.str1.1
1a: bf 01 00 00 00 mov <*>x1,%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 <*>x0,%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 <*>x8,%rsp
34: c3 retq
L'ordine delle istruzioni in memoria è rimasto invariato: prima il printf e poi inserisce e il retq ritornano.
Con __builtin_expect
Ora sostituisci if (i) con:
e otteniamo:
<*> Il printf (compilato in __printf_chk ) è stato spostato alla fine della funzione, dopo che inserisce e il ritorno per migliorare la previsione del ramo come indicato da altre risposte.
Quindi è sostanzialmente lo stesso di:
<*> Questa ottimizzazione non è stata eseguita con -O0 .
Ma buona fortuna nello scrivere un esempio che funziona più velocemente con __builtin_expect che senza, Le CPU sono davvero intelligenti quelle giorni . I miei ingenui tentativi sono qui
Fanno sì che il compilatore emetta i suggerimenti di diramazione appropriati dove l'hardware li supporta. Questo di solito significa solo modificare alcuni bit nel codice operativo dell'istruzione, quindi la dimensione del codice non cambierà. La CPU inizierà a recuperare le istruzioni dalla posizione prevista, svuota la pipeline e ricomincia da capo se ciò risulta essere errato quando viene raggiunto il ramo; nel caso in cui il suggerimento sia corretto, questo renderà il ramo molto più veloce - precisamente quanto molto più veloce dipenderà dall'hardware; e quanto ciò influirà sulle prestazioni del codice dipenderà dalla percentuale del suggerimento temporale corretta.
Ad esempio, su una CPU PowerPC un ramo non accennato potrebbe richiedere 16 cicli, uno correttamente accennato 8 e uno erroneamente accennato 24. Nei cicli più interni, un buon accenno può fare un'enorme differenza.
La portabilità non è in realtà un problema - presumibilmente la definizione è in un'intestazione per piattaforma; puoi semplicemente definire " probabilmente " e "improbabile" nulla per le piattaforme che non supportano i suggerimenti sui rami statici.
long __builtin_expect(long EXP, long C);
Questo costrutto dice al compilatore che l'espressione EXP molto probabilmente avrà il valore C. Il valore di ritorno è EXP. __builtin_expect deve essere utilizzato in modo condizionale espressione. In quasi tutti i casi verrà utilizzato in contesto di espressioni booleane nel qual caso è molto più conveniente definire due macro helper:
#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 tu debba perdere la portabilità usandoli.
Hai sempre la possibilità di creare un semplice effetto nullo " inline " o macro che ti permetteranno di compilare su altre piattaforme con altri compilatori.
Non otterrai il vantaggio dell'ottimizzazione se ti trovi su altre piattaforme.
Secondo il commento di Cody , questo non ha nulla a che fare con Linux, ma è un suggerimento per compilatore. Cosa accadrà dipenderà dall'architettura e dalla versione del compilatore.
Questa particolare funzionalità di Linux è in qualche modo utilizzata male nei driver. Come osgx sottolinea in semantica dell'attributo caldo , qualsiasi funzione hot o cold chiamata con un blocco può automaticamente suggerire che la condizione è probabile o no . Ad esempio, dump_stack () è contrassegnato cold quindi è ridondante,
if(unlikely(err)) {
printk("Driver error found. %d\n", err);
dump_stack();
}
Le versioni future di gcc potrebbero incorporare selettivamente una funzione basata su questi suggerimenti. Ci sono stati anche suggerimenti secondo cui non è booleano , ma un punteggio come in molto probabilmente , ecc. In generale, dovrebbe essere preferito usare qualche meccanismo alternativo come freddo . Non vi è alcun motivo per usarlo in qualsiasi luogo tranne che per i percorsi caldi. Ciò che un compilatore farà su un'architettura può essere completamente diverso su un'altra.
In molte versioni di Linux, puoi trovare complier.h in / usr / linux /, puoi includerlo per usarlo semplicemente. E un'altra opinione, improbabile () è più utile che probabile (), perché
if ( likely( ... ) ) {
doSomething();
}
può essere ottimizzato anche in molti compilatori.
E comunque, se vuoi osservare il comportamento dettagliato 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 otterrai al massimo un aumento di un byte per ogni ramo. Per quanto riguarda le prestazioni, dipende interamente dall'applicazione - nella maggior parte dei casi, il predittore di diramazione sul processore li ignorerà, oggigiorno.
Modifica: ho dimenticato un posto in cui possono davvero aiutare. Può consentire al compilatore di riordinare il grafico del flusso di controllo per ridurre il numero di diramazioni prese per il percorso "probabile". Ciò può avere un netto miglioramento nei loop in cui si verificano più casi di uscita.
Queste sono funzioni GCC per il programmatore per dare un suggerimento al compilatore su quale sarà la condizione di ramo più probabile in una data espressione. Ciò consente al compilatore di creare le istruzioni di diramazione in modo che il caso più comune richieda il minor numero di istruzioni da eseguire.
La modalità di creazione delle istruzioni di diramazione dipende dall'architettura del processore.
