Perché l’istruzione del ciclo è lenta? Intel non l’ha implementata in modo efficiente?

LOOP ( Intel ref manual entry ) decrementa ecx / rcx, quindi salta se diverso da zero . È lento, ma Intel non è riuscito a farcela velocemente? dec/jnz già macro-fusibili in un singolo uop sulla famiglia Sandybridge; l’unica differenza è che imposta le bandiere.

loop su varie microarchitetture, dalle tabelle di istruzioni di Agner Fog :

  • K8 / K10: 7 m-ops
  • Bulldozer-famiglia / Ryzen : 1 m-op (stesso costo del test-and-branch, o jecxz )

  • P4: 4 uops (uguale a jecxz )

  • P6 (PII / PIII): 8 uops
  • Pentium M, Core2: 11 uops
  • Nehalem: 6 uops. (11 per loope / loopne ). Throughput = 4c ( loop ) o 7c ( loope/ne ).
  • Famiglia SnB : 7 uops. (11 per loope / loopne ). Throughput = uno per 5 cicli , tanto più di un collo di bottiglia come mantenere il tuo contatore di loop in memoria! jecxz è solo 2 uops con lo stesso rendimento del jcc regolare
  • Silvermont: 7 uops
  • AMD Jaguar (bassa potenza): 8 uop, 5c throughput
  • Via Nano3000: 2 uops

I decodificatori non potevano decodificarli come ” lea rcx, [rcx-1] / jrcxz ? Quello sarebbe 3 uops. Almeno questo sarebbe il caso senza prefisso dimensione indirizzo, altrimenti deve usare ecx e troncare RIP a EIP se il salto è preso; forse la strana scelta di dimensioni dell’indirizzo che controllano la larghezza del decremento spiega i molti Uops?

O meglio, decodificarlo come dec-e-branch fuso che non imposta flag? dec ecx / jnz su SnB decodifica su un singolo uop (che imposta i flag).

So che il codice reale non lo usa (perché è stato lento almeno dal P5 o qualcosa del genere), ma AMD ha deciso che valeva la pena renderlo veloce per Bulldozer. Probabilmente perché era facile.


  • Sarebbe facile per l’uarch della famiglia SnB avere un loop veloce? Se è così, perché no? Se no, perché è difficile? Un sacco di transistor decodifica? O bit extra in un deco fuso e ramo uop per registrare che non imposta i flag? Cosa potrebbero fare quei 7 uops? È un’istruzione davvero semplice.

  • Cosa c’è di speciale in Bulldozer che ha reso un loop veloce facile / vale la pena? O forse AMD ha sprecato un sacco di transistor per velocizzare il loop ? Se è così, presumibilmente qualcuno ha pensato che fosse una buona idea.


Se il loop fosse veloce , sarebbe perfetto per loop adc precisione arbitraria di BigInteger, per evitare stallo / rallentamenti a bandiera parziale (vedi i miei commenti sulla mia risposta), o qualsiasi altro caso in cui si desidera eseguire il ciclo senza toccare i flag. Ha anche un minor vantaggio in termini di dimensioni del codice rispetto a dec/jnz . (E dec/jnz solo macro-fusibili sulla famiglia SnB).

Nelle moderne CPU in cui dec/jnz va bene in un ciclo ADC, il loop sarebbe comunque utile per i loop ADCX / ADOX (per preservare OF).

Se il loop fosse stato veloce, i compilatori lo userebbero già come ottimizzazione dello spioncino per la velocità in dimensioni del codice + sulle CPU senza macro-fusione.


Non mi impedirebbe di annoiarmi a tutte le domande con un codice a 16 bit scadente che utilizza il loop per ogni ciclo, anche quando hanno bisogno di un altro contatore all’interno del ciclo. Ma almeno non sarebbe così male.

Ora che ho cercato su Google dopo aver scritto la mia domanda, risulta essere un duplicato esatto di uno su comp.arch , che è venuto fuori subito. Mi aspettavo che fosse difficile da google (un sacco di “perché è il mio loop slow”), ma il mio primo tentativo ( why is the x86 loop instruction slow ) ha ottenuto dei risultati.

Questa non è una risposta buona o completa.

Potrebbe essere il migliore che otterremo, e dovremo essere sufficienti a meno che qualcuno non riesca a far luce su di esso. Non avevo intenzione di scrivere questo come una risposta-mia-domanda personale.


Buoni post con diverse teorie in quel thread:

Roberto

LOOP divenne lento su alcune delle prime macchine (circa 486) quando cominciò a verificarsi un pipelining significativo, e l’esecuzione di qualsiasi istruzione, tranne le più semplici, lungo la pipeline era tecnologicamente poco pratica. Quindi LOOP è stato lento per un numero di generazioni. Quindi nessuno l’ha usato. Quindi, quando è stato ansible accelerarlo, non c’era un reale incentivo a farlo, dal momento che nessuno lo stava effettivamente utilizzando.


Anton Ertl :

IIRC LOOP è stato utilizzato in alcuni software per i cicli di sincronizzazione; c’era (importante) software che non funzionava su CPU dove LOOP era troppo veloce (questo era nei primi anni ’90 o giù di lì). Quindi i produttori di CPU hanno imparato a rallentare LOOP.


(Paul e chiunque altro: sei libero di postare la tua stessa scrittura come risposta personale. La rimuoverò dalla mia risposta e la voterò in su).

@Paul A. Clayton (occasionale poster di SO e ragazzo dell’architettura della CPU) ha indovinato come si potrebbero usare così tanti UOP . (Questo sembra come loope/ne che controlla sia il contatore che ZF):

Potrei immaginare una versione 6-μop possibilmente ragionevole:

 virtual_cc = cc; temp = test (cc); rCX = rCX - temp; // also setting cc cc = temp & cc; // assumes branch handling is not // substantially changed for the sake of LOOP branch cc = virtual_cc 

(Si noti che questo è di 6 uop, non di SnB 11 per LOOPE / LOOPNE, ed è un’ipotesi totale che non tenta nemmeno di prendere in considerazione qualcosa di noto dai contatori di SnB perf.)

Allora Paolo disse:

Sono d’accordo sul fatto che una sequenza più breve dovrebbe essere ansible, ma stavo cercando di pensare a una sequenza gonfia che avrebbe senso se fossero consentiti minimi aggiustamenti microarchitetturali.

sumrio: i progettisti volevano che il loop fosse supportato solo tramite microcodice, senza alcuna rettifica dell’hardware vero e proprio.

Se un’istruzione inutile e di sola compatibilità viene consegnata agli sviluppatori di microcodice, potrebbero ragionevolmente non essere in grado o disposti a suggerire modifiche minori alla microarchitettura interna per migliorare tale istruzione. Non solo preferirebbero usare il loro “capitale di suggerimento per il cambiamento” in maniera più produttiva, ma la proposta di un cambiamento per un caso inutile ridurrebbe la credibilità di altri suggerimenti.

(La mia opinione: Intel probabilmente lo sta ancora rallentando di proposito, e non si è preoccupato di riscrivere il loro microcodice per un lungo periodo. Le moderne CPU sono probabilmente troppo veloci per qualsiasi cosa che usi il loop in modo ingenuo per funzionare correttamente.)

… continua Paul:

Gli architetti di Nano potrebbero aver scoperto di evitare l’involucro speciale di LOOP, semplificando il loro design in termini di area o potenza. Oppure potrebbero aver avuto incentivi dagli utenti incorporati per fornire un’implementazione rapida (per i vantaggi della densità del codice). Quelle sono solo supposizioni di WILD .

Se l’ottimizzazione di LOOP non rientra nelle altre ottimizzazioni (come la fusione di confronto e ramo), potrebbe essere più semplice modificare LOOP in un’istruzione di percorso veloce piuttosto che gestirlo in microcodice, anche se le prestazioni di LOOP non erano importanti.

Sospetto che tali decisioni siano basate su dettagli specifici dell’implementazione. Le informazioni su tali dettagli non sembrano essere generalmente disponibili e interpretare tali informazioni sarebbe al di là del livello di abilità della maggior parte delle persone. (Io non sono un progettista di hardware – e non ne ho mai suonato uno in televisione o sono stato in un Holiday Inn Express. 🙂


Il thread è poi andato fuori tema nel regno di AMD, soffiando la nostra unica possibilità di ripulire il cruft nella codifica delle istruzioni x86. È difficile dare la colpa a loro, poiché ogni cambiamento è un caso in cui i decodificatori non possono condividere i transistor. E prima che Intel adottasse x86-64, non era nemmeno chiaro che avrebbe preso piede. AMD non voleva appesantire le proprie CPU con hardware che nessuno utilizzava se AMD64 non si impigliava.

Ma ancora, ci sono così tante piccole cose: setcc potrebbe essere cambiato a 32 bit. (Di solito devi usare xor-zero / test / setcc per evitare false dipendenze, o perché hai bisogno di un registro esteso a zero). Shift potrebbe avere flag scritti incondizionatamente, anche con zero shift count (rimuovendo la dipendenza dai dati di input su eflags per il conteggio dei conteggi variabili per l’esecuzione di OOO). L’ultima volta che ho digitato questa lista di pet peeves, penso ci fosse un terzo … Oh sì, bt / bts ecc. Con gli operandi di memoria l’indirizzo dipende dai bit superiori dell’indice (stringa di bit, non solo bit all’interno una parola macchina).

bts istruzioni di bts sono molto utili per le cose sul campo di bit, e sono più lente del necessario, quindi è quasi sempre necessario caricarle in un registro e utilizzarle. (Di solito è più veloce spostare / mascherare per ottenere un indirizzo tu stesso, invece di usare 10 uop bts [mem], reg su Skylake, ma richiede istruzioni aggiuntive, quindi aveva senso 386, ma non K8). La manipolazione di bit atomici deve usare il form di memoria-dest, ma la versione lock ed ha bisogno di un sacco di uops in ogni caso. È ancora più lento di quanto non potrebbe accedere al di fuori del dword cui sta operando.

Per favore vedi il bell’articolo di Abrash, Michael, pubblicato nel Journal del Dr. Dobb March 1991 v16 n3 p16 (8): http://archive.gamedev.net/archive/reference/articles/article369.html

Il riepilogo dell’articolo è il seguente:

Ottimizzare il codice per i microprocessori 8088, 80286, 80386 e 80486 è difficile perché i chip utilizzano architetture di memoria e tempi di esecuzione delle istruzioni significativamente diversi. Il codice non può essere ottimizzato per la famiglia 80×86; piuttosto, il codice deve essere progettato per produrre buone prestazioni su una gamma di sistemi o ottimizzato per particolari combinazioni di processori e memoria. I programmatori devono evitare le istruzioni insolite supportate dall’8088, che hanno perso il margine di prestazioni nei chip successivi. Le istruzioni per le stringhe dovrebbero essere usate ma non invocate. I registri dovrebbero essere usati piuttosto che le operazioni di memoria. La ramificazione è anche lenta per tutti e quattro i processori. Gli accessi alla memoria devono essere allineati per migliorare le prestazioni. In generale, l’ottimizzazione di un 80486 richiede esattamente i passaggi opposti rispetto all’ottimizzazione di un 8088.

Con “istruzioni insolite supportate dall’8088” l’autore significa anche “loop”:

Qualsiasi programmatore 8088 sostituirà istintivamente: DEC CX JNZ LOOPTOP con: LOOPTOP LOOP perché LOOP è significativamente più veloce su 8088. LOOP è anche più veloce sul 286. Sul 386, tuttavia, LOOP è in realtà di due cicli più lento di DEC / JNZ. Il pendolo oscilla ulteriormente sul 486, dove LOOP è circa due volte più lento di DEC / JNZ – e, badate bene, stiamo parlando di ciò che era in origine forse l’ottimizzazione più ovvia dell’intero set di istruzioni 80×86.

Questo è un ottimo articolo e lo consiglio vivamente. Anche se è stato pubblicato nel 1991, è sorprendentemente molto importante oggi.

Ma questo articolo dà solo consigli, incoraggia a testare la velocità di esecuzione e scegliere varianti più veloci. Non spiega PERCHÉ alcuni comandi diventano molto lenti, quindi non risponde completamente alla tua domanda.

La risposta è che i processori precedenti, come 80386 (rilasciato nel 1985) e prima, eseguivano le istruzioni una per una, in sequenza.

I processori successivi hanno iniziato a utilizzare il pipelining delle istruzioni, inizialmente semplice per 804086 e, infine, Pentium Pro (rilasciato nel 1995) ha introdotto una pipeline interna radicalmente diversa, chiamandola nucleo Out of Order (OOO) in cui le istruzioni venivano trasformate in piccoli frammenti di operazioni chiamate micro-ops o μops, e quindi tutte le micro-operazioni di diverse istruzioni sono state messe in un ampio pool di micro-operazioni in cui avrebbero dovuto essere eseguite simultaneamente, purché non dipendessero l’una dall’altra. Questo principio del gasdotto OOO è ancora utilizzato, quasi invariato, sui processori moderni. Puoi trovare ulteriori informazioni sul pipelining delle istruzioni in questo brillante articolo: https://www.gamedev.net/resources/_/technical/general-programming/a-journey-through-the-cpu-pipeline-r3115

Per semplificare la progettazione dei chip, Intel ha deciso di creare processori in modo tale che le istruzioni si trasformassero in micro-op in modo molto efficiente, mentre altre no.

La conversione efficiente dalle istruzioni alle micro-operazioni richiede più transistor, quindi Intel ha deciso di risparmiare sui transistor a un costo di decodifica e esecuzione più lente di alcune istruzioni “complesse” o “usate raramente”.

Ad esempio, il “Manuale di riferimento sull’ottimizzazione dell’architettura Intel®” http://download.intel.com/design/PentiumII/manuals/24512701.pdf menziona quanto segue: “Evita di utilizzare istruzioni complesse (ad esempio, inserisci, esci o loop ) che generalmente hanno più di quattro μop e richiedono più cicli da decodificare. Usa invece sequenze di istruzioni semplici. ”

Quindi, Intel in qualche modo ha deciso che l’istruzione “loop” è “complessa” e, da allora, è diventata molto lenta. Tuttavia, non vi è alcun riferimento ufficiale a Intel sulla scomposizione delle istruzioni: quante micro-operazioni ogni istruzione produce e quanti cicli sono necessari per decodificarlo.

È inoltre ansible leggere informazioni su The Execution Engine Out-of-Order nel “Manuale di riferimento dell’ottimizzazione delle architetture Intel® 64 e IA-32” http://www.intel.com/content/dam/www/public/us/en/ documenti / manuali / 64-ia-32-architectures-optimization-manual.pdf la sezione 2.1.2.