È possibile dire al predittore del ramo quanto è probabile seguire il ramo?

Question

Giusto per chiarire, non sto andando per alcun tipo di portabilità qui, quindi qualsiasi soluzione che mi legherà a una certa scatola va bene.

Fondamentalmente, ho un'istruzione if che valuterà il 99% delle volte true, e sto provando a eliminare ogni ultimo clock di prestazioni, posso eseguire una sorta di comando del compilatore (utilizzando GCC 4.1.2 e il x86 ISA, se è importante) per dire al predittore del ramo che dovrebbe memorizzare nella cache per quel ramo?

Answer 1

Sì. http://kerneltrap.org/node/4705

Il __builtin_expect è un metodo che gcc (versioni> = 2.96) offerta per programmatori per indicare ramo informazioni di previsione al compilatore. Il valore restituito di __builtin_expect è il primo argomento (che potrebbe essere solo un numero intero) passato ad esso.

if (__builtin_expect (x, 0)) 
       foo(); 

    [This] would indicate that we do not expect to call `foo', since we 
    expect `x' to be zero. 

Answer 2

No, perché non c'è nessun comando di montaggio per lasciare che il predittore ramo so. Non preoccuparti, il predittore del ramo è piuttosto intelligente.

Inoltre, commento obbligatorio sull'ottimizzazione prematura e su come è malvagio.

MODIFICA: Drakosha ha menzionato alcune macro per GCC. Tuttavia, ritengo che si tratti di un'ottimizzazione del codice e in realtà non ha nulla a che fare con la previsione delle filiali.

Answer 3

Mi sembra eccessivo: questo tipo di ottimizzazione consente di risparmiare un minimo di tempo. Ad esempio, l'utilizzo di una versione più moderna di gcc avrà un'influenza molto maggiore sulle ottimizzazioni. Inoltre, prova a abilitare e disabilitare tutti i diversi flag di ottimizzazione; non tutti migliorano le prestazioni.

Fondamentalmente, sembra improbabile che ciò possa fare una differenza significativa rispetto a molti altri percorsi fruttuosi.

MODIFICA: grazie per i commenti. Ho creato questo wiki della comunità, ma l'ho lasciato in modo che altri possano vedere i commenti.

Answer 4

SUN C Studio ha definito alcuni pragmi per questo caso.

#pragma rarely_called()

Questo funziona se una parte di un'espressione condizionale è una chiamata di funzione o inizia con una chiamata di funzione.

Ma non c'è modo di codificare un generico se/while

Answer 5

Come Drakosha dice, raccontando gcc che si diramano è il caso comune, in modo che genera un codice migliore per il caso in cui il predittore ramo è freddo, e quindi il percorso veloce attraverso la funzione è facile da eseguire per la CPU, è probabilmente molto utile.

FYI, Pentium 4 aveva suggerimenti di predittore di ramo come prefisso alle istruzioni di jcc, ma solo la microarchitettura netburst ha mai fatto qualcosa con loro. Vedi http://ref.x86asm.net/geek32.html. E Section 3.5 of Agner Fog's excellent asm opt guide, da http://www.agner.org/optimize/. Ha anche una guida per l'ottimizzazione in C++.

Non viene pubblicato molto su come si comportano esattamente i predittori di ramo e i buffer di destinazione delle ultime CPU Intel e AMD. I manuali di ottimizzazione (facili da trovare sui siti Web di AMD e Intel) forniscono alcuni consigli, ma non documentano un comportamento specifico. Alcune persone hanno eseguito test per provare a divinare l'implementazione, ad es. quante voci di BTB Core2 ha ... Ad ogni modo, l'idea di suggerire esplicitamente il predittore è stata abbandonata (per ora). Ciò che è documentato è ad esempio che Core2 ha un buffer di cronologia delle filiali che può evitare di interpretare erroneamente l'uscita del ciclo se il ciclo esegue sempre un numero breve e costante di iterazioni, < 8 o 16 IIRC. Ma non essere troppo veloce per srotolarlo, perché un loop che rientra in 64bytes (o 19uops su Penryn) non avrà i colli di bottiglia dell'istruzione, perché si riproduce da un buffer ... leggi i pdf di Agner Fog, sono eccellenti.

Answer 6

Sì, ma avrà l'effetto no. Le eccezioni sono architetture obsolete (obsolete) pre Netburst, e anche allora non fa nulla di misurabile.

C'è un opcode "suggerimento ramo" introdotto da Intel con l'architettura Netburst e una previsione di ramo statica predefinita per salti a freddo (previsione anticipata all'indietro, previsione anticipata non eseguita) su alcune architetture meno recenti. GCC implementa questo con __builtin_expect (x, prediction), in cui la previsione è in genere 0 o 1. Il codice operativo emesso dal compilatore è ignorato su tutte le più recenti architetture di processore (> = Core 2). Il piccolo caso d'angolo in cui questo effettivamente fa qualcosa è il caso di un salto freddo sulla vecchia architettura Netburst. Intel consiglia ora di non utilizzare i suggerimenti di derivazione statica, probabilmente perché considerano l'aumento delle dimensioni del codice più dannoso rispetto alla possibile accelerazione marginale.

Oltre al suggerimento di ramo inutile per il predittore, __builtin_expect ha il suo uso, il compilatore può riordinare il codice per migliorare l'utilizzo della cache o per risparmiare memoria.

Ci sono diversi motivi per cui non funziona come previsto.

• Il processore è in grado di prevedere piccoli cicli (n. < 64) perfettamente.
• Il processore può prevedere perfettamente i piccoli motivi ripetuti (n ~ 7).
• Il processore stesso può stimare la probabilità di un ramo durante l'esecuzione migliore del compilatore/programmatore durante la compilazione.
• La prevedibilità (= probabilità che un ramo venga previsto correttamente) di un ramo è molto più importante della probabilità che il ramo venga prelevato. Sfortunatamente questo è altamente dipendente dall'architettura e il predire la prevedibilità del ramo è notoriamente difficile.

Maggiori informazioni sui lavori interni della previsione ramo di Agner Fogs manuals. Vedere anche gcc mailing list.

Answer 7

Suggerisco piuttosto di preoccuparsi della previsione delle filiali, del profilo del codice e dell'ottimizzazione del codice per ridurre il numero di filiali. Un esempio è lo srotolamento del ciclo e un altro utilizzando le tecniche di programmazione booleana anziché utilizzare le istruzioni if.

La maggior parte dei processori amano precaricare le dichiarazioni. Generalmente, un estratto conto genera un errore all'interno del processore, provocando lo svuotamento della coda di prelettura.Questo è dove la pena più grande è. Per ridurre questo tempo di penalità, riscrivi (e progetta) il codice in modo che siano disponibili meno rami. Inoltre, alcuni processori possono eseguire istruzioni in modo condizionale senza doversi ramificare.

Ho ottimizzato un programma da 1 ora del tempo di esecuzione a 2 minuti utilizzando lo srotolamento del loop e grandi buffer di I/O. La previsione del ramo non avrebbe offerto molto risparmio di tempo in questo caso.