Lenta istruzione jmp

Come seguito alla mia domanda I vantaggi dell’uso di registri / istruzioni a 32 bit in x86-64 , ho iniziato a misurare i costi delle istruzioni. Sono consapevole che questo è stato fatto più volte (ad es. Agner Fog ), ma lo sto facendo per divertimento e auto-educazione.

Il mio codice di test è piuttosto semplice (per semplicità qui come pseudo codice, in realtà in assembler):

for(outer_loop=0; outer_loop<NO;outer_loop++){ operation #first operation #second ... operation #NI-th } 

Ma ancora alcune cose dovrebbero essere considerate.

  1. Se la parte interna del loop è grande (grande NI>10^7 ), l’intero contenuto del loop non si adatta alla cache delle istruzioni e quindi deve essere caricato più e più volte, facendo sì che la velocità della RAM definisca il tempo necessario per l’esecuzione. Ad esempio, per le parti interne di grandi dimensioni, xorl %eax, %eax (2 byte) è il 33% più veloce di xorq %rax, %rax (3 byte).
  2. Se NI è piccolo e l’intero ciclo si inserisce facilmente nella cache delle istruzioni, rispetto a xorl %eax, %eax e xorq %rax, %rax sono ugualmente veloci e possono essere eseguiti 4 volte per ciclo di clock.

Tuttavia questo semplice modello non trattiene l’acqua per l’istruzione jmp . Per il jmp -instruction il mio codice di test appare come segue:

 for(outer_loop=0; outer_loop<NO;outer_loop++){ jmp .L0 .L0: jmp .L1 L1: jmp L2 .... } 

E i risultati sono:

  1. Per le dimensioni “grandi” del ciclo (già per NI>10^4 ) misuro 4.2 ns / jmp -instruction (equivarrebbe a 42 byte caricati dalla RAM oa circa 12 cicli di clock sulla mia macchina).
  2. Per le dimensioni dei piccoli anelli ( NI<10^3 ) misuro 1 ns / jmp- instruction (che è circa 3 cicli di clock, che suona plausibile – le tabelle di Agner Fog mostrano i costi di 2 cicli di clock).

L’istruzione jmp LX usa la codifica eb 00 2 byte.

Quindi, la mia domanda: quale potrebbe essere la spiegazione dell’elevato costo dell’istruzione jmp nei loop “grandi”?

PS: Se ti piace provarlo sul tuo computer, puoi scaricare gli script da qui , basta eseguire sh jmp_test.sh in src -folder.


Modifica: risultati sperimentali che confermano la teoria della dimensione di BTB di Peter.

La seguente tabella mostra i cicli per istruzione per i diversi valori ǸI (relativi a NI = 1000):

 |oprations/ NI | 1000 | 2000| 3000| 4000| 5000| 10000| |---------------------|------|------|------|------|------|------| |jmp | 1.0 | 1.0 | 1.0 | 1.2 | 1.9 | 3.8| |jmp+xor | 1.0 | 1.2 | 1.3 | 1.6 | 2.8 | 5.3| |jmp+cmp+je (jump) | 1.0 | 1.5 | 4.0 | 4.4 | 5.5 | 5.5| |jmp+cmp+je (no jump) | 1.0 | 1.2 | 1.3 | 1.5 | 3.8 | 7.6| 

Può essere visto:

  1. Per l’istruzione jmp , una risorsa (ancora sconosciuta) diventa scarsa e questo porta a un peggioramento delle prestazioni per ǸI maggiore di 4000.
  2. Questa risorsa non è condivisa con istruzioni come xor – il degrado delle prestazioni aumenta ancora per NI circa 4000, se jmp e xor vengono eseguiti uno dopo l’altro.
  3. Ma questa risorsa è condivisa con je se il salto è fatto – per jmp + je uno dopo l’altro, la risorsa diventa scarsa per NI circa 2000.
  4. Tuttavia, se non si salta affatto, la risorsa sta diventando scarsa ancora una volta perché NI è circa 4000 (4 ° linea).

Gli articoli di reverse engineering sulla previsione delle branch di Matt Godbolt stabiliscono che la capacità del buffer target della diramazione è di 4096 voci. Questa è una prova molto forte del fatto che le mancanze di BTB sono la ragione della differenza di throughput osservata tra i circuiti jmp piccoli e grandi.

TL: DR: la mia ipotesi attuale sta esaurendo le voci BTB (buffer di destinazione del ramo). Vedi sotto.


Anche se i tuoi jmp sono no-op, la CPU non ha transistor aggiuntivi per rilevare questo caso speciale. Vengono gestiti come qualsiasi altro jmp , il che significa dover riavviare il recupero delle istruzioni da una nuova posizione, creando una bolla nella pipeline.

Per saperne di più sui salti e il loro effetto sulle CPU pipeline, Control Hazards in una pipeline RISC classica dovrebbe essere una buona introduzione al motivo per cui i rami sono difficili per le CPU pipeline. Le guide di Agner Fog spiegano le implicazioni pratiche, ma credo che assumano parte di quel tipo di conoscenza di base.


La CPU Intel Broadwell ha una cache uop , che memorizza nella cache le istruzioni decodificate (separate dalla cache I1 32kiB L1).

La dimensione della cache di uop è di 32 set di 8 modi, con 6 uop per riga, per un totale di 1536 uop (se ogni linea è piena di 6 uop, efficienza perfetta). 1536 Uop si trova tra le 1000 e le 10000 dimensioni del test. Prima della modifica, ho previsto che il taglio per lenta a veloce sarebbe di circa 1536 istruzioni totali nel ciclo. Non rallenta affatto fino a ben oltre le 1536 istruzioni, quindi penso che possiamo escludere gli effetti di uop-cache. Questa non è una domanda così semplice come pensavo. 🙂

Esecuzione da uop-cache (dimensioni del codice piccolo) al posto dei decodificatori dell’istruzione x86 (loop di grandi dimensioni) significa che ci sono meno stadi della pipeline prima dello stage che riconosce le istruzioni jmp . Quindi potremmo aspettarci che le bolle da un stream costante di salti siano più piccole, anche se sono previste correttamente.

Correre dai decodificatori dovrebbe dare una maggiore penalità in caso di infrazione (come forse 20 cicli invece di 15), ma questi non sono rami imprevedibili.


Anche se la CPU non ha bisogno di prevedere se il ramo è occupato o meno, potrebbe comunque utilizzare le risorse di previsione delle branch per prevedere che un blocco di codice contiene un ramo preso prima di essere decodificato.

Memorizzando il fatto che vi è un ramo in un certo blocco di codice e il suo indirizzo di destinazione, consente al frontend di iniziare il recupero del codice dalla destinazione del ramo prima che la codifica jmp rel32 sia effettivamente decodificata. Ricorda che la decodifica delle istruzioni x86 a lunghezza variabile è difficile: non sai dove inizia un’istruzione fino a quando la precedente non viene decodificata. Pertanto, non è ansible associare il stream di istruzioni alla ricerca di salti / chiamate incondizionati non appena vengono recuperati.

La mia teoria attuale è che si sta rallentando quando si esauriscono le voci del buffer di destinazione del ramo.

Vedi anche Quale errore di branca viene rilevato dal Buffer di destinazione della diramazione? che ha una bella risposta e discussione in questo thread Realworldtech .

Un punto molto importante: il BTB prevede in termini di quale blocco recuperare successivamente, piuttosto che la destinazione esatta di un ramo specifico all’interno di un blocco di recupero. Quindi, invece di dover prevedere obiettivi per tutti i rami in un blocco di recupero, la CPU deve solo prevedere l’indirizzo del prossimo recupero.


Sì, la larghezza di banda della memoria può essere un collo di bottiglia quando si esegue un throughput molto elevato come xor-zeroing, ma si sta colpendo un collo di bottiglia diverso con jmp . La CPU avrebbe il tempo di recuperare 42B dalla memoria, ma non è quello che sta facendo. Prefetch può facilmente tenere il passo con 2 byte per 3 clock, quindi ci dovrebbero essere quasi zero L1 I-cache misses.

Nel tuo xor con / senza test REX, la larghezza di banda della memoria principale potrebbe essere stata il collo di bottiglia lì se hai testato con un loop abbastanza grande da non adattarsi alla cache L3. Consumo 4 * 2B per ciclo su una CPU ~ 3GHz, il che equivale a un massimo di 25 GB / s di DDR3-1600MHz. Anche la cache L3 sarebbe abbastanza veloce da tenere il passo con 4 * 3B per ciclo.

È interessante notare che la memoria principale BW è il collo di bottiglia; Inizialmente ho intuito che la decodifica (in blocchi di 16 byte) sarebbe il collo di bottiglia per gli XOR a 3 byte, ma suppongo che siano abbastanza piccoli.


Si noti inoltre che è molto più normale misurare i tempi nei cicli di clock principali. Tuttavia, le tue misure in ns sono utili quando stai guardando la memoria, immagino, perché le basse velocità di clock per il risparmio energetico cambiano il rapporto tra la velocità dell’orologio core e la velocità della memoria. (cioè i colli di bottiglia della memoria sono meno di un problema alla velocità minima di clock della CPU.)

Per il benchmarking nei cicli di clock, utilizzare perf stat ./a.out . Esistono altri utili contatori delle prestazioni che sono essenziali per cercare di capire le caratteristiche delle prestazioni.

Vedi x86-64 Prestazioni jmp relative per i perf-counter di Core2 (8 cicli per jmp), e qualche microarchitettura sconosciuta dove è ~ 10c per jmp.


I dettagli delle moderne caratteristiche delle prestazioni della CPU sono abbastanza difficili da comprendere anche in presenza di più o meno condizioni di white-box (leggendo il manuale di ottimizzazione di Intel e cosa hanno pubblicato riguardo gli interni della CPU). Ti bloccerai presto e spesso se insisti sul testing della black-box in cui non leggi articoli come arstechnica sul nuovo design della CPU, o magari cose più dettagliate come la panoramica del microarca di Haswell di David Kanter, o simili Scrittura Sandybridge ho collegato in precedenza.

Se ti blocchi presto e spesso è ok e ti stai divertendo, allora continua a fare quello che stai facendo. Ma rende più difficile per le persone rispondere alle tue domande se non conosci quei dettagli, come in questo caso. : / ad esempio, la mia prima versione di questa risposta presupponeva che tu avessi letto abbastanza per sapere quale fosse la cache di uop.