Allineamento dei rami per loop che coinvolgono istruzioni micro-codificate su CPU Intel SnB-family

Questo è correlato, ma non è lo stesso, a questa domanda: Ottimizzazione delle prestazioni dell’assembly x86-64 – Allineamento e previsione dei rami ed è leggermente correlato alla mia domanda precedente: Conversione da 64 bit a doppia conversione: perché questo algoritmo da g ++

Quello che segue è un caso di test non reale . Questo algoritmo di test di primalità non è ragionevole. Sospetto che qualsiasi algoritmo del mondo reale non eseguirà mai un loop interno così piccolo tante volte ( num è un numero primo di dimensioni circa 2 ** 50). In C ++ 11:

 using nt = unsigned long long; bool is_prime_float(nt num) { for (nt n=2; n<=sqrt(num); ++n) { if ( (num%n)==0 ) { return false; } } return true; } 

Quindi g++ -std=c++11 -O3 -S produce quanto segue, con RCX contenente n e XMM6 contenente sqrt(num) . Vedere il mio post precedente per il codice rimanente (che non viene mai eseguito in questo esempio, poiché RCX non diventa mai abbastanza grande da essere trattato come un negativo firmato).

 jmp .L20 .p2align 4,,10 .L37: pxor %xmm0, %xmm0 cvtsi2sdq %rcx, %xmm0 ucomisd %xmm0, %xmm6 jb .L36 // Exit the loop .L20: xorl %edx, %edx movq %rbx, %rax divq %rcx testq %rdx, %rdx je .L30 // Failed divisibility test addq $1, %rcx jns .L37 // Further code to deal with case when ucomisd can't be used 

L’ho usato std::chrono::steady_clock . Ho continuato a ricevere strane modifiche alle prestazioni: dall’aggiunta o eliminazione di altro codice. Alla fine ho rintracciato questo problema di allineamento. Il comando .p2align 4,,10 cercato di allineare un limite di 2 ** 4 = 16 byte, ma utilizza solo un massimo di 10 byte di padding per farlo, suppongo di bilanciare tra l’allineamento e la dimensione del codice.

Ho scritto uno script Python per sostituire .p2align 4,,10 con un numero di istruzioni nop controllato manualmente. Il seguente grafico a dispersione mostra il più veloce 15 di 20 esecuzioni, il tempo in secondi, il numero di byte di padding sull’asse x:

Trama sparsa

Da objdump senza padding, l’istruzione pxor si verificherà all’offset 0x402f5f. In esecuzione su un laptop, Sandybridge i5-3210m, turboboost disabilitato , l’ho trovato

  • Per riempimento di 0 byte, prestazione lenta (0,42 sec)
  • Per 1-4 byte padding (offset 0x402f60 a 0x402f63) ottenere leggermente migliore (0.41s, visibile sul grafico).
  • Per 5-20 byte di padding (offset 0x402f64 a 0x402f73) ottenere prestazioni veloci (0,37s)
  • Per riempimento di 21-32 byte (offset 0x402f74 a 0x402f7f) prestazioni lente (0,42 sec)
  • Quindi esegue il ciclo su un campione da 32 byte

Quindi un allineamento a 16 byte non offre le migliori prestazioni, ci mette nella regione leggermente migliore (o solo meno variazione, dalla trama a dispersione). L’allineamento di 32 più 4 a 19 offre le migliori prestazioni.

Perché vedo questa differenza di prestazioni? Perché questo sembra violare la regola di allineare i target di ramo con un limite di 16 byte (vedi ad esempio il manuale di ottimizzazione di Intel)

Non vedo alcun problema di previsione dei branch. Potrebbe essere una stranezza di cache Uop ??

Modificando l’algoritmo C ++ per memorizzare sqrt(num) in un numero intero a 64-bit e quindi creare il numero intero puramente basato su loop, rimuovo il problema– l’allineamento ora non fa alcuna differenza.

Ecco cosa ho trovato su Skylake per lo stesso ciclo. Tutto il codice per riprodurre i miei test sul tuo hardware è su github .

Osservo tre diversi livelli di prestazione basati sull’allineamento, mentre l’OP ha visto solo 2 primari. I livelli sono molto distinti e ripetibili 2 :

inserisci la descrizione dell'immagine qui

Qui vediamo tre distinti livelli di prestazioni (le ripetizioni di pattern a partire dall’offset 32), che chiameremo regioni 1, 2 e 3, da sinistra a destra (la regione 2 è divisa in due parti a cavallo della regione 3). La regione più veloce (1) è compresa tra 0 e 8, quella centrale (2) tra 9-18 e 28-31 e la più lenta (3) tra 19-27. La differenza tra ciascuna regione è vicina o esattamente 1 ciclo / iterazione.

Sulla base dei contatori delle prestazioni, la regione più veloce è molto diversa dalle altre due:

  • Tutte le istruzioni sono fornite dal decodificatore legacy, non dal DSB 1 .
  • Ci sono esattamente 2 decoder <-> switch microcode (idq_ms_switches) per ogni iterazione del loop.

Sulla mano, le due regioni più lente sono abbastanza simili:

  • Tutte le istruzioni sono fornite dal DSB (cache uop) e non dal decodificatore legacy.
  • Esistono esattamente 3 decoder <-> switch microcode per iterazione del loop.

La transizione dalla regione più veloce a quella centrale, poiché l’offset cambia da 8 a 9, corrisponde esattamente a quando il loop inizia ad adattarsi nel buffer uop, a causa di problemi di allineamento. Lo contate esattamente nello stesso modo di Peter nella sua risposta:

Offset 8:

  LSD? <_start.L37>: ab 1 4000a8: 66 0f ef c0 pxor xmm0,xmm0 ab 1 4000ac: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx ab 1 4000b1: 66 0f 2e f0 ucomisd xmm6,xmm0 ab 1 4000b5: 72 21 jb 4000d8 <_start.L36> ab 2 4000b7: 31 d2 xor edx,edx ab 2 4000b9: 48 89 d8 mov rax,rbx ab 3 4000bc: 48 f7 f1 div rcx !!!! 4000bf: 48 85 d2 test rdx,rdx 4000c2: 74 0d je 4000d1 <_start.L30> 4000c4: 48 83 c1 01 add rcx,0x1 4000c8: 79 de jns 4000a8 <_start.L37> 

Nella prima colonna ho annotato come gli UOP di ciascuna istruzione finiscono nella cache di uop. “ab 1” significa che vanno nel set associato all’indirizzo come ...???a? o ...???b? (ogni set copre 32 byte, ovvero 0x20 ), mentre 1 indica il modo 1 (su un massimo di 3).

Al punto !!! questo esce dalla cache di uop perché l’istruzione di test non ha dove andare, tutti i 3 modi sono esauriti.

Diamo un’occhiata all’offset 9 d’altra parte:

 00000000004000a9 <_start.L37>: ab 1 4000a9: 66 0f ef c0 pxor xmm0,xmm0 ab 1 4000ad: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx ab 1 4000b2: 66 0f 2e f0 ucomisd xmm6,xmm0 ab 1 4000b6: 72 21 jb 4000d9 <_start.L36> ab 2 4000b8: 31 d2 xor edx,edx ab 2 4000ba: 48 89 d8 mov rax,rbx ab 3 4000bd: 48 f7 f1 div rcx cd 1 4000c0: 48 85 d2 test rdx,rdx cd 1 4000c3: 74 0d je 4000d2 <_start.L30> cd 1 4000c5: 48 83 c1 01 add rcx,0x1 cd 1 4000c9: 79 de jns 4000a9 <_start.L37> 

Ora non c’è nessun problema! L’istruzione di test è scivolata nella successiva linea 32B (la linea cd ), quindi tutto rientra nella cache di uop.

Questo spiega perché le cose cambiano tra il MITE e il DSB a quel punto. Tuttavia, non spiega perché il percorso MITE sia più veloce. Ho provato alcuni test più semplici con div in un loop, e puoi riprodurlo con loop più semplici senza nessuna delle cose in virgola mobile. È strano e sensibile alle altre cose casuali che hai inserito nel ciclo.

Ad esempio questo ciclo si esegue anche più velocemente dal decodificatore legacy rispetto al DSB:

 ALIGN 32  .top: add r8, r9 xor eax, eax div rbx xor edx, edx times 5 add eax, eax dec rcx jnz .top 

In quel ciclo, aggiungendo l’aggiunta inutile add r8, r9 istruzione add r8, r9 , che non interagisce realmente con il resto del ciclo, ha accelerato le cose per la versione MITE (ma non per la versione DSB).

Quindi penso che la differenza tra la regione 1 e le regioni 2 e 3 sia dovuta al fatto che il primo è uscito dal decoder legacy (che, stranamente, lo rende più veloce).


Diamo anche un’occhiata all’offset 18 per compensare la transizione 19 (dove region2 termina e 3 inizia):

Compensazione 18:

 00000000004000b2 <_start.L37>: ab 1 4000b2: 66 0f ef c0 pxor xmm0,xmm0 ab 1 4000b6: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx ab 1 4000bb: 66 0f 2e f0 ucomisd xmm6,xmm0 ab 1 4000bf: 72 21 jb 4000e2 <_start.L36> cd 1 4000c1: 31 d2 xor edx,edx cd 1 4000c3: 48 89 d8 mov rax,rbx cd 2 4000c6: 48 f7 f1 div rcx cd 3 4000c9: 48 85 d2 test rdx,rdx cd 3 4000cc: 74 0d je 4000db <_start.L30> cd 3 4000ce: 48 83 c1 01 add rcx,0x1 cd 3 4000d2: 79 de jns 4000b2 <_start.L37> 

Offset 19:

 00000000004000b3 <_start.L37>: ab 1 4000b3: 66 0f ef c0 pxor xmm0,xmm0 ab 1 4000b7: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx ab 1 4000bc: 66 0f 2e f0 ucomisd xmm6,xmm0 cd 1 4000c0: 72 21 jb 4000e3 <_start.L36> cd 1 4000c2: 31 d2 xor edx,edx cd 1 4000c4: 48 89 d8 mov rax,rbx cd 2 4000c7: 48 f7 f1 div rcx cd 3 4000ca: 48 85 d2 test rdx,rdx cd 3 4000cd: 74 0d je 4000dc <_start.L30> cd 3 4000cf: 48 83 c1 01 add rcx,0x1 cd 3 4000d3: 79 de jns 4000b3 <_start.L37> 

L’unica differenza che vedo qui è che le prime 4 istruzioni nel caso offset 18 si adattano alla linea cache ab , ma solo 3 nel caso offset 19. Se ipotizziamo che il DSB può fornire solo uops all’IDQ da un set di cache, ciò significa che a un certo punto si può emettere un uop ed eseguire un ciclo prima nello scenario 18 offset rispetto allo scenario 19 (si immagini, ad esempio, che l’IDQ è vuoto). A seconda di esattamente a quale porta va il uop nel contesto del stream di uop circostante, ciò può ritardare il ciclo di un ciclo. In effetti, la differenza tra le regioni 2 e 3 è ~ 1 ciclo (entro il margine di errore).

Quindi penso che possiamo dire che la differenza tra 2 e 3 è probabilmente dovuta all’allineamento della cache di uop – la regione 2 ha un allineamento leggermente migliore di 3, in termini di emettere un ciclo di uop addizionale in precedenza.


Alcune note di aggiunta su cose che ho controllato che non sono state evidenziate come possibili cause dei rallentamenti:

  • Nonostante le modalità DSB (regioni 2 e 3) con 3 switch microcode rispetto al 2 del percorso MITE (regione 1), questo non sembra causare direttamente il rallentamento. In particolare, i cicli più semplici con div eseguono in conteggi di cicli identici, ma mostrano ancora gli interruttori 3 e 2 rispettivamente per i percorsi DSB e MITE. Quindi è normale e non implica direttamente il rallentamento.

  • Entrambi i percorsi eseguono essenzialmente un numero identico di UOP e, in particolare, hanno un numero identico di UOP generati dal sequencer del microcodice. Quindi non è come se ci fosse più lavoro in generale nelle diverse regioni.

  • Non c’era davvero una differenza nei miss della cache (molto bassa, come previsto) a vari livelli, mispredictions (essenzialmente zero 3 ), o qualsiasi altro tipo di penalità o condizioni insolite che ho controllato.

Ciò che ha portato frutto sta guardando il modello di utilizzo delle unità di esecuzione tra le varie regioni. Ecco una panoramica della distribuzione di uops eseguiti per ciclo e alcune metriche di stallo:

 +----------------------------+----------+----------+----------+ | | Region 1 | Region 2 | Region 3 | +----------------------------+----------+----------+----------+ | cycles: | 7.7e8 | 8.0e8 | 8.3e8 | | uops_executed_stall_cycles | 18% | 24% | 23% | | exe_activity_1_ports_util | 31% | 22% | 27% | | exe_activity_2_ports_util | 29% | 31% | 28% | | exe_activity_3_ports_util | 12% | 19% | 19% | | exe_activity_4_ports_util | 10% | 4% | 3% | +----------------------------+----------+----------+----------+ 

Ho campionato alcuni valori di offset diversi ed i risultati erano coerenti all’interno di ogni regione, eppure tra le regioni hai risultati abbastanza diversi. In particolare, nella regione 1, si hanno meno cicli di stallo (cicli in cui non viene eseguito nessun uop). Hai anche una variazione significativa nei cicli di non stallo, sebbene non sia evidente una chiara tendenza “migliore” o “peggiore”. Ad esempio, la regione 1 ha molti più cicli (10% vs 3% o 4%) con 4 uop eseguiti, ma le altre regioni lo compensano in gran parte con più cicli con 3 uop eseguiti e pochi cicli con 1 uop eseguito.

La differenza in UPC 4 che la distribuzione di esecuzione di cui sopra implica completamente spiega la differenza di prestazioni (questa è probabilmente una tautologia poiché abbiamo già confermato che il conteggio uop è lo stesso tra di loro).

Vediamo cosa deve dire su toplev.py … (risultati omessi).

Bene, toplev suggerisce che il collo di bottiglia principale è il front-end (50 +%). Non penso che ci si possa fidare di questo perché il modo in cui calcola il limite di FE sembra interrotto nel caso di lunghe stringhe di istruzioni micro-codificate. FE-bound è basato su frontend_retired.latency_ge_8 , che è definito come:

Istruzioni ritirate che vengono recuperate dopo un intervallo in cui il front-end non ha emesso messaggi per un periodo di 8 cicli che non è stato interrotto da uno stallo di back-end. (Supporta PEBS)

Normalmente questo ha un senso. Stai contando le istruzioni che sono state ritardate perché il frontend non stava erogando cicli. La condizione “non interrotto da uno stallo di back-end” assicura che questo non si inneschi quando il front-end non sta erogando gli UOP semplicemente perché il back-end non è in grado di accettarli (ad esempio, quando la RS è piena perché il backend sta eseguendo alcune istruzioni low-thocutut).

Sembra un po ‘per istruzioni div – anche un semplice ciclo con praticamente un solo div mostra:

 FE Frontend_Bound: 57.59 % [100.00%] BAD Bad_Speculation: 0.01 %below [100.00%] BE Backend_Bound: 0.11 %below [100.00%] RET Retiring: 42.28 %below [100.00%] 

Cioè, l’unico collo di bottiglia è il front-end (“ritirarsi” non è un collo di bottiglia, rappresenta il lavoro utile). Chiaramente, tale loop è banalmente gestito dal front-end ed è invece limitato dalla capacità del backend di masticare per lanciare tutti gli UOP generati dall’operazione div . Toplev potrebbe ottenere questo veramente sbagliato perché (1) potrebbe essere che gli uop consegnati dal sequencer del microcode non sono contati nei contatori frontend_retired.latency... , in modo che ogni operazione div faccia in modo che quell’evento conti tutte le istruzioni successive ( anche se la CPU era occupata durante quel periodo – non c’era un vero stallo), o (2) il sequencer del microcode poteva fornire tutti i suoi up essenzialmente “in anticipo”, sbattendo ~ 36 uops nell’IDQ, a quel punto non lo fa consegnare altro fino a quando il div è finito, o qualcosa del genere.

Tuttavia, possiamo guardare i livelli inferiori di toplev per suggerimenti:

La differenza principale tra le regioni 1 e 2 e 3 è la maggiore penalità di ms_switches per le ultime due regioni (poiché esse subiscono 3 ogni iterazione vs 2 per il percorso legacy. Internamente, toplev stima una penalità di 2 cicli in il frontend per tali interruttori Naturalmente, se queste penalità rallentano effettivamente qualcosa dipende in modo complesso dalla coda di istruzioni e da altri fattori Come menzionato sopra, un semplice ciclo con div non mostra alcuna differenza tra i percorsi DSB e MITE , un loop con istruzioni addizionali lo fa, quindi potrebbe essere che la bolla extra di switch sia assorbita in loop più semplici (dove l’elaborazione back-end di tutti gli uops generati dal div è il fattore principale), ma una volta che si aggiunge qualche altro lavoro nel loop, gli switch diventano un fattore almeno per il periodo di transizione tra il lavoro div e non div.

Quindi penso che la mia conclusione sia che il modo in cui l’istruzione div interagisce con il resto del stream del frontend uop e l’esecuzione backend non è completamente ben compreso. Sappiamo che comporta un stream di UOP, fornito sia dal MITE / DSB (sembra 4 uops per div ) sia dal sequencer del microcode (sembra come ~ 32 uops per div , anche se cambia con diversi valori di input per il div op) – ma non sappiamo cosa siano questi uops (possiamo vedere la distribuzione della porta però). Tutto ciò rende il comportamento piuttosto opaco, ma penso che sia probabilmente fino a che gli interruttori MS non controllano il front-end, o lievi differenze nel stream di consegna di uop, con conseguenti decisioni di schedulazione che finiscono per rendere l’ordine master del MITE.


1 Naturalmente, la maggior parte degli uops non viene fornita dal decoder legacy o dal DSB, ma dal sequencer del microcode (ms). Quindi parliamo vagamente delle istruzioni fornite, non del tutto.

2 Notare che l’asse x qui è “offset byte dall’allineamento 32B”. Cioè, 0 significa che la parte superiore del ciclo (etichetta .L37) è allineata a un limite 32B e 5 significa che il ciclo inizia cinque byte al di sotto di un limite 32B (utilizzando nop per il riempimento) e così via. Quindi i miei byte e offset offset sono gli stessi. L’OP ha usato un significato diverso per l’offset, se ho capito bene: il suo 1 byte di padding ha dato come risultato un offset di 0. Quindi devi sottrarre 1 dai valori di pad dell’OP per ottenere i miei valori di offset.

3 In effetti, il tasso di predizione del ramo per un test tipico con prime=1000000000000037 era ~ 99,99999% , riflettendo solo 3 rami errati nell’intera corsa (probabilmente sul primo passaggio attraverso il ciclo e l’ultima iterazione).

4 UPC, ovvero, uops per ciclo – una misura strettamente correlata all’IPC per programmi simili, e una che è un po ‘più precisa quando stiamo esaminando in dettaglio i flussi uop. In questo caso, sappiamo già che i conteggi uop sono gli stessi per tutte le variazioni di allineamento, quindi UPC e IPC saranno direttamente proporzionali.

Non ho una risposta specifica, solo alcune ipotesi diverse che non sono in grado di testare (mancanza di hardware). Pensavo di aver trovato qualcosa di conclusivo, ma avevo l’allineamento di uno (perché la domanda conta il riempimento da 0x5F, non da un confine allineato). Comunque, spero sia utile postare questo comunque per descrivere i fattori che sono probabilmente in gioco qui.

La domanda inoltre non specifica la codifica dei rami (breve (2B) o vicina (6B)). Ciò lascia troppe possibilità di guardare e teorizzare esattamente su quale istruzione che attraversa o meno un limite di 32B sta causando il problema.


Penso che sia una questione di adattamento del loop nella cache di uop o no, oppure è una questione di allineamento che conta se decodifica velocemente con i decoder legacy.


Ovviamente il ciclo asm potrebbe essere migliorato molto (ad esempio sollevando il punto fluttuante da esso, per non parlare usando un algoritmo completamente diverso), ma non è questa la domanda. Vogliamo solo sapere perché l’allineamento è importante per questo ciclo esatto.

Ci si potrebbe aspettare che un loop che colli di bottiglia sulla divisione non abbia un collo di bottiglia sul front-end o risulti condizionato dall’allineamento, perché la divisione è lenta e il ciclo esegue pochissime istruzioni per orologio. È vero, ma il DIV a 64 bit è micro-codificato come 35-57 micro-op (uops) su IvyBridge, quindi risulta che possono esserci problemi front-end.

I due principali modi in cui l’allineamento può avere importanza sono:

  • Colli di bottiglia di front-end (nelle fasi di recupero / decodifica), che portano a bolle nel mantenere il core out-of-order fornito di lavoro da fare.
  • Predizione del ramo: se due rami hanno lo stesso indirizzo modulo un po ‘più grande di 2, possono alias l’un l’altro nell’hardware di previsione del ramo. L’allineamento del codice in un file object sta influenzando le prestazioni di una funzione in un altro file object che graffia la superficie di questo problema, ma molto è stato scritto a riguardo.

Sospetto che si tratti di un problema puramente front-end, non di una previsione di branch, dal momento che il codice passa tutto il suo tempo in questo ciclo e non sta eseguendo altri rami che potrebbero essere alias con quelli qui.

La tua CPU Intel IvyBridge è un die-shrink di SandyBridge. Ha alcune modifiche (come l’eliminazione del movimento e ERMSB), ma il front-end è simile tra SnB / IvB / Haswell. Il pdf di microarch di Agner Fog contiene abbastanza dettagli per analizzare cosa dovrebbe accadere quando la CPU esegue questo codice. Vedi anche l’articolo su SandyBridge di David Kanter per uno schema a blocchi degli stadi di recupero / decodifica , ma divide il recupero / decodifica dalla cache di uop, dal microcode e dalla coda decodificata. Alla fine, c’è un diagramma a blocchi completo di un intero nucleo. Il suo articolo Haswell ha uno schema a blocchi che include l’intero front-end, fino alla coda decodificata-uop che alimenta la fase del problema. (IvyBridge, come Haswell, ha un buffer di loop / loopback di 56 uop quando non usa Hyperthreading. Sandybridge le partiziona staticamente in code 2×0 uop ​​anche se HT è distriggersto.)

L'annotazione per SnB di David Kanter

Immagine copiata dall’eccellente scrittura di David Kanter Haswell , in cui include i decodificatori e la cache di uop in un diagramma.

Diamo un’occhiata a come la cache di uop memorizzerà probabilmente questo ciclo, una volta che le cose si sistemeranno. (cioè supponendo che la voce di loop con una jmp nel mezzo del loop non abbia alcun effetto a lungo termine sul modo in cui il loop si trova nella cache di uop).

Secondo il manuale di ottimizzazione di Intel ( 2.3.2.2 ICC decodificato ):

  • Tutte le micro-operazioni in un modo (linea cache uop) rappresentano istruzioni che sono staticamente contigue nel codice e hanno i loro EIP all’interno della stessa regione allineata di 32 byte. (Penso che questo significhi che un’istruzione che si estende oltre il limite va nella cache di uop per il blocco che contiene il suo inizio, piuttosto che la fine. Le istruzioni di spanning devono andare da qualche parte, e l’indirizzo di destinazione del ramo che eseguirà l’istruzione è l’inizio del insn, quindi è molto utile metterlo in linea per quel blocco).
  • Un’istruzione multi-micro-op non può essere suddivisa in modi.
  • Un’istruzione che accende il MSROM consuma un intero modo. (cioè qualsiasi istruzione che richiede più di 4 uop (per il reg, reg form) è microcodificata.Ad esempio, DPPD non è micro-codificato (4 uops), ma DPPS è (6 uop). DPPD con un operando di memoria che può Il micro-fusibile sarebbe 5 uop totali, ma non avrebbe ancora bisogno di accendere il sequencer del microcodice (non testato).
  • Sono ammessi fino a due rami per Way.
  • Una coppia di istruzioni con fusione di macro viene mantenuta come una micro-operazione.

La stesura di SnB di David Kanter contiene altri dettagli sulla cache di uop .


Vediamo come il codice effettivo andrà nella cache di uop

 # let's consider the case where this is 32B-aligned, so it runs in 0.41s # ie this is at 0x402f60, instead of 0 like this objdump -Mintel -d output on a .o # branch displacements are all 00, and I forgot to put in dummy labels, so they're using the rel32 encoding not rel8. 0000000000000000 <.text>: 0: 66 0f ef c0 pxor xmm0,xmm0 # 1 uop 4: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx # 2 uops 9: 66 0f 2e f0 ucomisd xmm6,xmm0 # 2 uops d: 0f 82 00 00 00 00 jb 0x13 # 1 uop (end of one uop cache line of 6 uops) 13: 31 d2 xor edx,edx # 1 uop 15: 48 89 d8 mov rax,rbx # 1 uop (end of a uop cache line: next insn doesn't fit) 18: 48 f7 f1 div rcx # microcoded: fills a whole uop cache line. (And generates 35-57 uops) 1b: 48 85 d2 test rdx,rdx ### PROBLEM!! only 3 uop cache lines can map to the same 32-byte block of x86 instructions. # So the whole block has to be re-decoded by the legacy decoders every time, because it doesn't fit in the uop-cache 1e: 0f 84 00 00 00 00 je 0x24 ## spans a 32B boundary, so I think it goes with TEST in the line that includes the first byte. Should actually macro-fuse. 24: 48 83 c1 01 add rcx,0x1 # 1 uop 28: 79 d6 jns 0x0 # 1 uop 

Quindi, con l’allineamento 32B per l’inizio del ciclo, deve essere eseguito dai decoder legacy, che è potenzialmente più lento di quello eseguito dalla cache di uop. Ci potrebbe anche essere un po ‘di overhead nel passaggio dalla cache di uop ai decodificatori legacy.

@ I test di Iwill (vedere i commenti sulla domanda) rivelano che qualsiasi istruzione microcodice impedisce l’esecuzione di un loop dal buffer di loopback . Vedi i commenti sulla domanda. (LSD = Loop Stream Detector = loop buffer, fisicamente la stessa struttura dell’IDQ (coda di decodifica dell’istruzione) DSB = Decode Stream Buffer = la cache di uop. MITE = decoder di legacy.)

Busting della cache di uop danneggerà le prestazioni anche se il loop è abbastanza piccolo per essere eseguito dall’LSD (minimo 28 uops o 56 senza hyperthreading su IvB e Haswell).

Il manuale di ottimizzazione di Intel (sezione 2.3.2.4) dice che i requisiti dell’LSD includono

  • Tutte le micro-op sono anche residenti nell’ICache decodificato.

Quindi questo spiega perché il microcodice non si qualifica: in questo caso la cache di uop tiene solo un puntatore nel microcodice, non gli stessi utenti. Si noti inoltre che ciò significa che il busting della cache di uop per qualsiasi altra ragione (ad esempio molte istruzioni NOP a byte singolo) significa che un loop non può essere eseguito dall’LSD.


Con il riempimento minimo per andare veloce , secondo i test dell’OP.

 # branch displacements are still 32-bit, except the loop branch. # This may not be accurate, since the question didn't give raw instruction dumps. # the version with short jumps looks even more unlikely 0000000000000000 : ... 5c: 00 00 add BYTE PTR [rax],al 5e: 90 nop 5f: 90 nop 60: 90 nop # 4NOPs of padding is just enough to bust the uop cache before (instead of after) div, if they have to go in the uop cache. # But that makes little sense, because looking backward should be impossible (insn start ambiguity), and we jump into the loop so the NOPs don't even run once. 61: 90 nop 62: 90 nop 63: 90 nop 0000000000000064 : #uops #decode in cycle A..E 64: 66 0f ef c0 pxor xmm0,xmm0 #1 A 68: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx #2 B 6d: 66 0f 2e f0 ucomisd xmm6,xmm0 #2 C (crosses 16B boundary) 71: 0f 82 db 00 00 00 jb 152 #1 C 77: 31 d2 xor edx,edx #1 C 79: 48 89 d8 mov rax,rbx #1 C 7c: 48 f7 f1 div rcx #line D # 64B boundary after the REX in next insn 7f: 48 85 d2 test rdx,rdx #1 E 82: 74 06 je 8a #1 E 84: 48 83 c1 01 add rcx,0x1 #1 E 88: 79 da jns 64 #1 E 

Il prefisso REX del test rdx,rdx trova nello stesso blocco del DIV, quindi questo dovrebbe bloccare la cache di uop. Un altro byte di padding l’avrebbe inserito nel prossimo blocco 32B, il che avrebbe perfettamente senso. Forse i risultati dell’OP sono sbagliati, o forse i prefissi non contano, ed è la posizione del byte opcode che conta. Forse questo è importante, o forse un test + ramo maculato viene estratto al prossimo blocco?

La fusione delle macro avviene attraverso il limite della linea L1I-cache 64B, poiché non ricade sul confine tra le istruzioni.

La fusione di macro non avviene se la prima istruzione termina sul byte 63 di una linea di cache e la seconda istruzione è un ramo condizionale che inizia al byte 0 della successiva linea di cache. – Manuale di ottimizzazione di Intel, 2.3.2.1

O forse con una breve codifica per un salto o l’altro, le cose sono diverse?

O forse il busting della cache di uop non ha nulla a che fare con questo, e va bene finchè decodifica velocemente, cosa che questo allineamento fa accadere . Questa quantità di padding mette a malapena la fine di UCOMISD in un nuovo blocco 16B, quindi forse ciò migliora l’efficienza lasciandolo decodificare con le altre istruzioni nel successivo blocco 16B allineato. Tuttavia, non sono sicuro che debbano essere allineati un pre-decodificatore 16B (lunghezza di istruzione) o un blocco di decodifica 32B.


Mi sono anche chiesto se la CPU dovesse passare frequentemente dalla cache di uop alla decodifica legacy. Questo può essere peggio che partire sempre dalla decodifica legacy.

Passare dai decodificatori alla cache di uop o viceversa richiede un ciclo, secondo la guida microarch di Agner Fog. Intel dice:

Quando le micro-op non possono essere memorizzate nell’ICache decodificato a causa di queste restrizioni, vengono consegnate dalla pipeline di decodifica legacy. Una volta che le micro-operazioni sono state consegnate dalla pipeline legacy, il recupero di micro-op da ICache decodificato può riprendere solo dopo la successiva micro-operazione del ramo. Gli interruttori frequenti possono subire una penalità.


La fonte che ho assemblato + disassemblata:

 .skip 0x5e nop # this is 0x5F #nop # OP needed 1B of padding to reach a 32B boundary .skip 5, 0x90 .globl loop_start loop_start: .L37: pxor %xmm0, %xmm0 cvtsi2sdq %rcx, %xmm0 ucomisd %xmm0, %xmm6 jb .Loop_exit // Exit the loop .L20: xorl %edx, %edx movq %rbx, %rax divq %rcx testq %rdx, %rdx je .Lnot_prime // Failed divisibility test addq $1, %rcx jns .L37 .skip 200 # comment this to make the jumps rel8 instead of rel32 .Lnot_prime: .Loop_exit: 

From what I can see in your algorithm, there is certainly not much you can do to improve it.

The problem you are hitting is probably not so much the branch to an aligned position, although that can still help, you’re current problem is much more likely the pipeline mechanism.

When you write two instructions one after another such as:

  mov %eax, %ebx add 1, %ebx 

In order to execute the second instruction, the first one has to be complete. For that reason compilers tend to mix instructions. Say you need to set %ecx to zero, you could do this:

  mov %eax, %ebx xor %ecx, %ecx add 1, %ebx 

In this case, the mov and the xor can both be executed in parallel. This makes things go faster… The number of instructions that can be handled in parallel vary very much between processors (Xeons are generally better at that).

The branch adds another parameter where the best processors may start executing both sides of the branch (the true and the false…) simultaneously. But really most processors will make a guess and hope they are right.

Finally, it is obvious that converting the sqrt() result to an integer will make things a lot faster since you will avoid all that non-sense with SSE2 code which is definitively slower if used only for a conversion + compare when those two instructions could be done with integers.

Now… you are probably still wondering why the alignment does not matter with the integers. The fact is that if your code fits in the L1 instruction cache, then the alignment is not important. If you lose the L1 cache, then it has to reload the code and that’s where the alignment becomes quite important since on each loop it could otherwise be loading useless code (possibly 15 bytes of useless code…) and memory access is still dead slow.

The performance difference can be explained by the different ways the instruction encoding mechanism “sees” the instructions. A CPU reads the instructions in chunks (was on core2 16 byte I believe) and it tries to give the different superscalar units microops. If the instructions are on boundaries or ordered unlikely the units in one core can starve quite easily.