Problemi con ADC / SBB e INC / DEC in loop stretti su alcune CPU

Sto scrivendo un semplice tipo BigInteger in Delphi. Esso consiste principalmente in una matrice dynamic di TLimb, in cui un TLimb è un intero senza segno a 32 bit e un campo di dimensione a 32 bit, che contiene anche il bit di segno per BigInteger.

Per aggiungere due BigIntegers, creo un BigInteger nuovo della dimensione appropriata e poi, dopo un po ‘di contabilità, chiamo la seguente procedura, passando tre puntatori ai rispettivi inizi degli array per l’operando sinistro e destro e il risultato, così come il numero di arti per sinistra e destra, rispettivamente.

Codice semplice :

class procedure BigInteger.PlainAdd(Left, Right, Result: PLimb; LSize, RSize: Integer); asm // EAX = Left, EDX = Right, ECX = Result PUSH ESI PUSH EDI PUSH EBX MOV ESI,EAX // Left MOV EDI,EDX // Right MOV EBX,ECX // Result MOV ECX,RSize // Number of limbs at Left MOV EDX,LSize // Number of limbs at Right CMP EDX,ECX JAE @SkipSwap XCHG ECX,EDX // Left and LSize should be largest XCHG ESI,EDI // so swap @SkipSwap: SUB EDX,ECX // EDX contains rest PUSH EDX // ECX contains smaller size XOR EDX,EDX @MainLoop: MOV EAX,[ESI + CLimbSize*EDX] // CLimbSize = SizeOf(TLimb) = 4. ADC EAX,[EDI + CLimbSize*EDX] MOV [EBX + CLimbSize*EDX],EAX INC EDX DEC ECX JNE @MainLoop POP EDI INC EDI // Do not change Carry Flag DEC EDI JE @LastLimb @RestLoop: MOV EAX,[ESI + CLimbSize*EDX] ADC EAX,ECX MOV [EBX + CLimbSize*EDX],EAX INC EDX DEC EDI JNE @RestLoop @LastLimb: ADC ECX,ECX // Add in final carry MOV [EBX + CLimbSize*EDX],ECX @Exit: POP EBX POP EDI POP ESI end; // RET is inserted by Delphi compiler. 

Questo codice ha funzionato bene e ne sono stato abbastanza soddisfatto fino a quando non ho notato che, nel mio setup di sviluppo (Win7 in un Parallels VM su un iMac) una semplice routine di aggiunta PURE PASCAL, facendo lo stesso mentre emulando il carry con una variabile e alcune clausole if , era più veloce della mia routine di assemblatore semplice e lineare.

Mi ci è voluto un po ‘per scoprire che su determinate CPU (incluso il mio iMac e un vecchio laptop), la combinazione di DEC o INC ADC o SBB poteva essere estremamente lenta. Ma sulla maggior parte degli altri (ho altri cinque PC per testarlo, anche se quattro di questi sono esattamente gli stessi), è stato abbastanza veloce.

Così ho scritto una nuova versione, emulando INC e DEC usando invece LEA e JECXZ , in questo modo:

Parte del codice di emulazione :

 @MainLoop: MOV EAX,[ESI + EDX*CLimbSize] LEA ECX,[ECX - 1] // Avoid INC and DEC, see above. ADC EAX,[EDI + EDX*CLimbSize] MOV [EBX + EDX*CLimbSize],EAX LEA EDX,[EDX + 1] JECXZ @DoRestLoop // LEA does not modify Zero flag, so JECXZ is used. JMP @MainLoop @DoRestLoop: // similar code for the rest loop 

Ciò ha reso il mio codice sulle macchine “lente” quasi tre volte più veloce, ma circa il 20% più lento sulle macchine “più veloci”. Quindi ora, come codice di inizializzazione, eseguo un semplice ciclo di temporizzazione e lo uso per decidere se imposterò l’unità in modo che chiami la routine o le routine emulate. Questo è quasi sempre corretto, ma a volte sceglie le routine semplici (più lente) quando dovrebbe aver scelto le routine di emulazione.

Ma non so se questo è il modo migliore per farlo.

Domanda

Ho dato la mia soluzione, ma i guru asm qui forse conoscono un modo migliore per evitare la lentezza su certe CPU?

Aggiornare

Le risposte di Peter e Nils mi hanno aiutato molto ad andare sulla strada giusta. Questa è la parte principale della mia soluzione finale per la versione DEC :

Codice semplice:

 class procedure BigInteger.PlainAdd(Left, Right, Result: PLimb; LSize, RSize: Integer); asm PUSH ESI PUSH EDI PUSH EBX MOV ESI,EAX // Left MOV EDI,EDX // Right MOV EBX,ECX // Result MOV ECX,RSize MOV EDX,LSize CMP EDX,ECX JAE @SkipSwap XCHG ECX,EDX XCHG ESI,EDI @SkipSwap: SUB EDX,ECX PUSH EDX XOR EDX,EDX XOR EAX,EAX MOV EDX,ECX AND EDX,$00000003 SHR ECX,2 CLC JE @MainTail @MainLoop: // Unrolled 4 times. More times will not improve speed anymore. MOV EAX,[ESI] ADC EAX,[EDI] MOV [EBX],EAX MOV EAX,[ESI + CLimbSize] ADC EAX,[EDI + CLimbSize] MOV [EBX + CLimbSize],EAX MOV EAX,[ESI + 2*CLimbSize] ADC EAX,[EDI + 2*CLimbSize] MOV [EBX + 2*CLimbSize],EAX MOV EAX,[ESI + 3*CLimbSize] ADC EAX,[EDI + 3*CLimbSize] MOV [EBX + 3*CLimbSize],EAX // Update pointers. LEA ESI,[ESI + 4*CLimbSize] LEA EDI,[EDI + 4*CLimbSize] LEA EBX,[EBX + 4*CLimbSize] // Update counter and loop if required. DEC ECX JNE @MainLoop @MainTail: // Add index*CLimbSize so @MainX branches can fall through. LEA ESI,[ESI + EDX*CLimbSize] LEA EDI,[EDI + EDX*CLimbSize] LEA EBX,[EBX + EDX*CLimbSize] // Indexed jump. LEA ECX,[@JumpsMain] JMP [ECX + EDX*TYPE Pointer] // Align jump table manually, with NOPs. Update if necessary. NOP // Jump table. @JumpsMain: DD @DoRestLoop DD @Main1 DD @Main2 DD @Main3 @Main3: MOV EAX,[ESI - 3*CLimbSize] ADC EAX,[EDI - 3*CLimbSize] MOV [EBX - 3*CLimbSize],EAX @Main2: MOV EAX,[ESI - 2*CLimbSize] ADC EAX,[EDI - 2*CLimbSize] MOV [EBX - 2*CLimbSize],EAX @Main1: MOV EAX,[ESI - CLimbSize] ADC EAX,[EDI - CLimbSize] MOV [EBX - CLimbSize],EAX @DoRestLoop: // etc... 

Ho rimosso molto spazio bianco e immagino che il lettore possa ottenere il resto della routine. È simile al ciclo principale. Un miglioramento della velocità di ca. 20% per i BigInteger più grandi e circa il 10% per quelli piccoli (solo pochi arti).

La versione a 64 bit ora utilizza l’aggiunta a 64 bit dove ansible (nel loop principale e in Main3 e Main2, che non sono “fall-through” come sopra) e prima, 64 bit era molto più lento di 32 bit, ma ora è il 30% più veloce di 32 bit e due volte più veloce dell’originale loop a 64 bit.

Quello che vedi è una bancarella a bandierine parziali.

Le CPU Intel (diverse da P4) rinominano separatamente ogni bit di flag, quindi JNE dipende solo dall’ultima istruzione che imposta tutte le flag utilizzate (in questo caso, solo il flag Z ). In effetti, le recenti CPU Intel possono persino combinare internamente un inc/jne in un singolo inc/jne inc-and-branch (macro-fusion). Tuttavia, il problema si presenta quando si legge un bit di flag che non è stato modificato dall’ultima istruzione che ha aggiornato eventuali flag.

Agner Fog afferma che le CPU Intel (anche PPro / PII) non si bloccano su inc / jnz . Non è in realtà l’ inc/jnz che sta bloccando, è l’ adc nella prossima iterazione che deve leggere la bandiera CF dopo che inc scritto altre bandiere ma ha lasciato CF non modificato.

 ; Example 5.21. Partial flags stall when reading unmodified flag bits cmp eax, ebx inc ecx jc xx ; Partial flags stall (P6 / PIII / PM / Core2 / Nehalem) 

Agner Fog dice anche più in generale: “Evita il codice che si basa sul fatto che INC o DEC lasciano invariata la flag di carry”. (per Pentium M / Core2 / Nehalem). Il suggerimento di evitare inc / dec interamente è obsoleto e si applica solo a P4. Altre CPU rinominano le diverse parti di EFLAG separatamente, e hanno solo problemi quando è richiesta l’unione (leggendo un flag che non è stato modificato dall’ultima insn per scrivere alcun flag).

Sulle macchine dove è veloce (Sandybridge e versioni successive), stanno inserendo un extra uop per unire il registro flags quando si leggono bit che non sono stati scritti dall’ultima istruzione che lo ha modificato. Questo è molto più veloce dello stallo per 7 cicli, ma non è ancora l’ideale.

P4 traccia sempre interi registri, invece di rinominare registri parziali, nemmeno EFLAGS. Quindi inc/jz ha una dipendenza “falsa” da qualunque cosa abbia scritto le bandiere prima di esso. Ciò significa che la condizione del ciclo non può rilevare la fine del ciclo fino a quando non viene eseguita l’esecuzione della catena di distribuzione adc , quindi l’errore di codifica che può verificarsi quando il ramo di loop smette di essere rilevato non può essere rilevato in anticipo. Impedisce però qualsiasi stallo di flags parziale, però.

Il tuo lea / jecxz evita il problema in modo lea / jecxz . È più lento su SnB e poi perché non hai srotolato il tuo loop. La tua versione LEA è di 11 uops (può emettere un’iterazione per 3 cicli), mentre la versione di inc è di 7 uops (può emettere un iter per 2 cicli), senza contare l’uop di unione di flag che inserisce anziché stallo.

Se l’istruzione loop non fosse lenta , sarebbe perfetta per questo. In realtà è veloce sulla famiglia AMD Bulldozer (1 m-op, lo stesso costo di un confronto-e-fuso fuso), e Via Nano3000. È male su tutte le CPU Intel, anche se (7 uops su famiglia SnB).


svolgimento

Quando esegui lo srotolamento, puoi ottenere un altro piccolo guadagno usando i puntatori invece delle modalità di indirizzamento indicizzate, poiché le modalità di indirizzamento a 2 reg non possono essere fuse con microscheda su SnB e versioni successive . Un gruppo di istruzioni load / adc / store è 6 uops senza micro-fusione, ma solo 4 con micro-fusione. Le CPU possono emettere 4 UOP / fuso con dominio fuso. (Per i dettagli su questo livello, vedi il documento Microarch della CPU di Agner Fog e le tabelle di istruzioni.)

Salva gli errori quando puoi per assicurarti che la CPU possa impartire istruzioni più velocemente di eseguire, per assicurarti che possa vedere abbastanza avanti nel stream di istruzioni per assorbire eventuali bolle in insn fetch (ad es. L’inserimento nel buffer di loop 28uop significa anche risparmio di energia (e su Nehalem, evitando i colli di bottiglia di decodifica delle istruzioni.) Ci sono cose come l’allineamento delle istruzioni e l’attraversamento dei limiti della cache-line di uop che rendono difficile il backup di 4 uop / clock completi senza il loop buffer, anche.

Un altro trucco consiste nel mantenere puntatori alla fine dei buffer e contare fino allo zero. (Quindi all’inizio del tuo ciclo, ottieni il primo elemento come end[-idx] ).

  ; pure loads are always one uop, so we can still index it ; with no perf hit on SnB add esi, ecx ; point to end of src1 neg ecx UNROLL equ 4 @MainLoop: MOV EAX, [ESI + 0*CLimbSize + ECX*CLimbSize] ADC EAX, [EDI + 0*CLimbSize] MOV [EBX + 0*CLimbSize], EAX MOV EAX, [ESI + 1*CLimbSize + ECX*CLimbSize] ADC EAX, [EDI + 1*CLimbSize] MOV [EBX + 1*CLimbSize], EAX ; ... repeated UNROLL times. Use an assembler macro to repeat these 3 instructions with increasing offsets LEA ECX, [ECX+UNROLL] ; loop counter LEA EDI, [EDI+ClimbSize*UNROLL] ; Unrolling makes it worth doing LEA EBX, [EBX+ClimbSize*UNROLL] ; a separate increment to save a uop for every ADC and store on SnB & later. JECXZ @DoRestLoop // LEA does not modify Zero flag, so JECXZ is used. JMP @MainLoop @DoRestLoop: 

Un sorteggio di 4 dovrebbe essere buono. Non c’è bisogno di strafare, visto che sei prob. sarà in grado di saturare il carico / immagazzinare le porte di pre-Haswell con uno srotolare di soli 3 o 4, forse anche 2.

Un srotolamento di 2 renderà il loop sopra esattamente 14 uops di dominio fuso per le CPU Intel. adc è 2 ALU (+1 memoria fusa), jecxz è 2, il resto (incluso LEA) sono tutti 1. Nel dominio non utilizzato, 10 ALU / ramo e 6 memoria (beh, 8 memoria se si contano davvero l’indirizzo del negozio e memorizzare i dati separatamente).

  • 14 uops per dominio fuso per iterazione: emettere un iterazione per 4 orologi. (Gli strani 2 UOP alla fine devono essere emessi come un gruppo di 2, anche dal buffer del loop.)
  • 10 ALU e succursali: prende 3.33c per eseguirli tutti in pre-haswell. Non credo che nessuna porta sarà un collo di bottiglia: gli uop di adc possono essere eseguiti su qualsiasi porta e lea può essere eseguito su p0 / p1. I salti usano port5 (e jecx usa anche uno di p0 / p1)
  • 6 operazioni di memoria: richiede 3c per l’esecuzione su CPU pre-Haswell, che possono gestire 2 per orologio. Haswell ha aggiunto un’AGU dedicata per i negozi in modo che possa sostenere 2load + 1ore / ora.

Quindi per le CPU pre-haswell, usando LEA / JECXZ, uno srotolamento di 2 non saturerà del tutto l’ALU o le porte di carico / archivio. Un sorteggio di 4 porterà fino a 22 uops fusi (6 cicli da emettere). 14 ALU e diramazione: 4.66c da eseguire. 12 memoria: 6 cicli da eseguire. Quindi un sorteggio di 4 saturerà le CPU pre-Haswell, ma solo a malapena. La CPU non avrà alcun buffer di istruzioni per sfuggire a una causa errata.

Haswell e in seguito saranno sempre colli di bottiglia sul frontend (limite di 4 uop per clock), perché il carico / adc / store combo richiede 4 uop e può essere sostenuto a uno per orologio. Quindi non c’è mai una “stanza” per l’overhead del loop senza tagliare il throughput di adc . Questo è dove devi sapere di non esagerare e srotolare troppo.

Su Broadwell / Skylake, adc è solo un singolo uop con latenza 1c, e load / adc r, m / store sembra essere la sequenza migliore. adc m, r/i è 4 uops. Questo dovrebbe sostenere un ADC per orologio, come AMD.

Sulle CPU AMD, adc è solo una macro-op, quindi se la CPU può sostenere una frequenza di emissione di 4 (cioè senza colli di bottiglia di decodifica), allora possono usare anche la loro porta 2 carico / 1 per battere Haswell. Inoltre, jecxz su AMD è efficiente come qualsiasi altro ramo: solo una macro-op. La matematica a precisione multipla è una delle poche cose in cui le CPU AMD sono brave. Le latenze più basse su alcune istruzioni intere danno loro un vantaggio in alcune routine GMP.


Uno srotolamento di più di 5 potrebbe danneggiare le prestazioni di Nehalem, poiché ciò renderebbe il loop più grande del buffer di loop 28uop. La decodifica delle istruzioni ti limiterebbe quindi a meno di 4 uop per orologio. Anche prima (Core2), c’è un buffer loop di istruzioni x86 64B (64B di codice x86, non uops), che aiuta alcuni con la decodifica.

A meno che questa routine adc sia l’unico collo di bottiglia nella tua app, manterrò il fattore di sbobinamento a 2 o forse anche a non srotolare, se questo fa risparmiare un sacco di codice prologo / epilogo e le tue BigInts non sono troppo grandi. Non vuoi ingrossare troppo il codice e creare errori di cache quando i chiamanti chiamano molte funzioni di BigInteger, come aggiungi, sub, mul, e fai altre cose nel mezzo. Srotolare troppo per vincere ai microbenchmarks può spararti ai piedi se il tuo programma non impiega molto tempo nel tuo ciclo interno ad ogni chiamata.

Se i tuoi valori BigInt non sono generalmente giganteschi, allora non è solo il ciclo che devi sintonizzare. Un piccolo srotolare potrebbe essere utile per semplificare la logica del prologo / dell’epilogo. Assicurati di controllare le lunghezze in modo che ECX non attraversi lo zero senza mai essere zero, naturalmente. Questo è il problema con lo srotolamento e i vettori. : /


Salvataggio / ripristino di CF per vecchie CPU, invece di loop senza bandiera:

Questo potrebbe essere il modo più efficiente:

 lahf # clobber flags sahf ; cheap on AMD and Intel. This doesn't restore OF, but we only care about CF # or setc al # clobber flags add al, 255 ; generate a carry if al is non-zero 

L’utilizzo dello stesso registro della catena di distribuzione adc non è in realtà un problema: eax sarà sempre pronto allo stesso tempo dell’output CF dell’ultimo adc . (Sulle scritture di registri parziali AMD e P4 / Silvermont hanno un falso dep sul registro completo. Non rinominano i regs parziali separatamente). Il salvataggio / ripristino fa parte della catena di distribuzione dell’adc, non della catena di distribuzione delle condizioni del ciclo.

La condizione del ciclo controlla solo i flag scritti da cmp , sub o dec . Salvare / ripristinare i flag attorno ad esso non lo rende parte della catena di dep di adc , quindi è ansible rilevare l’ adc errato del ramo alla fine del ciclo prima che l’esecuzione di adc arrivi lì. (Una versione precedente di questa risposta ha sbagliato).


C’è quasi sicuramente spazio per eliminare le istruzioni nel codice di installazione, magari usando i registri in cui i valori iniziano. Non è necessario utilizzare edi ed esi per i puntatori, anche se so che facilita lo sviluppo iniziale quando si utilizzano i registri in modo coerente con il loro utilizzo “tradizionale”. (es. puntatore di destinazione in EDI).

Delphi ti permette di usare ebp ? È bello avere un 7 ° registro.

Ovviamente il codice a 64 bit farebbe girare il tuo codice BigInt circa il doppio più velocemente, anche se dovresti preoccuparti di fare un singolo 32b adc alla fine di un ciclo di 64 bit adc . Ti darebbe anche 2 volte la quantità di registri.

Ci sono così tanti chip x86 con tempistiche molto diverse in uso che non si può realisticamente avere un codice ottimale per tutti loro. Il tuo approccio per avere due note funzioni e benchmark noti prima dell’uso è già abbastanza avanzato.

Tuttavia, a seconda delle dimensioni dei BigInteger è probabile che tu possa migliorare il tuo codice con un semplice ciclo di srotolamento. Ciò rimuoverà drasticamente l’overhead del loop.

Ad esempio, è ansible eseguire un blocco specializzato che prevede l’aggiunta di otto numeri interi come questo:

 @AddEight: MOV EAX,[ESI + EDX*CLimbSize + 0*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 0*CLimbSize] MOV [EBX + EDX*CLimbSize + 0*CLimbSize],EAX MOV EAX,[ESI + EDX*CLimbSize + 1*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 1*CLimbSize] MOV [EBX + EDX*CLimbSize + 1*CLimbSize],EAX MOV EAX,[ESI + EDX*CLimbSize + 2*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 2*CLimbSize] MOV [EBX + EDX*CLimbSize + 2*CLimbSize],EAX MOV EAX,[ESI + EDX*CLimbSize + 3*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 3*CLimbSize] MOV [EBX + EDX*CLimbSize + 3*CLimbSize],EAX MOV EAX,[ESI + EDX*CLimbSize + 4*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 4*CLimbSize] MOV [EBX + EDX*CLimbSize + 4*CLimbSize],EAX MOV EAX,[ESI + EDX*CLimbSize + 5*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 5*CLimbSize] MOV [EBX + EDX*CLimbSize + 5*CLimbSize],EAX MOV EAX,[ESI + EDX*CLimbSize + 6*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 6*CLimbSize] MOV [EBX + EDX*CLimbSize + 6*CLimbSize],EAX MOV EAX,[ESI + EDX*CLimbSize + 7*CLimbSize] ADC EAX,[EDI + EDX*CLimbSize + 7*CLimbSize] MOV [EBX + EDX*CLimbSize + 7*CLimbSize],EAX LEA ECX,[ECX - 8] 

Ora ricostruisci il tuo loop, esegui il blocco precedente finché hai più di 8 elementi da elaborare e fai i pochi elementi rimanenti usando il loop di aggiunta di un singolo elemento che hai già.

Per i BitIntegers di grandi dimensioni, trascorrerai la maggior parte del tempo nella parte srotolata che dovrebbe essere eseguita molto più velocemente ora.

Se lo vuoi ancora più veloce, scrivi sette blocchi aggiuntivi che sono specializzati per il conteggio degli elementi rimanenti e derivano da essi in base al conteggio degli elementi. Questo può essere fatto meglio memorizzando i sette indirizzi in una tabella di ricerca, caricando l’indirizzo da esso e saltando direttamente nel codice specializzato.

Per i conteggi di elementi piccoli questo rimuove completamente l’intero ciclo e per elementi di grandi dimensioni si otterrà il massimo beneficio dal ciclo srotolato.