c++ - Qual è più veloce:x<<1 o x<<10?





performance cpu low-level (9)


È concepibile che, su un processore a 8 bit, x<<1 potrebbe essere molto più lento di x<<10 per un valore a 16 bit.

Ad esempio una traduzione ragionevole di x<<1 può essere:

byte1 = (byte1 << 1) | (byte2 >> 7)
byte2 = (byte2 << 1)

mentre x<<10 sarebbe più semplice:

byte1 = (byte2 << 2)
byte2 = 0

Nota come x<<1 sposta più spesso e anche più lontano di x<<10 . Inoltre il risultato di x<<10 non dipende dal contenuto di byte1. Questo potrebbe accelerare ulteriormente l'operazione.

Non voglio ottimizzare nulla, lo giuro, voglio solo fare questa domanda per curiosità. So che sulla maggior parte dell'hardware c'è un comando di assemblaggio del bit shift (es. shl , shr ), che è un singolo comando. Ma ha importanza (in termini di nanosecondi o CPU-saggio) quanti bit si spostano. In altre parole, uno dei seguenti è più veloce su qualsiasi CPU?

x << 1;

e

x << 10;

E per favore non odiarmi per questa domanda. :)




Questo dipende sia dalla CPU che dal compilatore. Anche se la CPU sottostante ha uno spostamento di bit arbitrario con un barrel shifter, ciò avverrà solo se il compilatore si avvantaggia di tale risorsa.

Tieni presente che spostare qualsiasi cosa al di fuori della larghezza in bit dei dati è "comportamento indefinito" in C e C ++. Il giusto spostamento dei dati firmati è anche "implementazione definita". Piuttosto che troppa preoccupazione per la velocità, preoccupati che tu stia ottenendo la stessa risposta su diverse implementazioni.

Citando da ANSI C sezione 3.3.7:

3.3.7 Operatori di spostamento bit a bit

Sintassi

      shift-expression:
              additive-expression
              shift-expression <<  additive-expression
              shift-expression >>  additive-expression

vincoli

Ciascuno degli operandi deve essere di tipo integrale.

Semantica

Le promozioni integrali vengono eseguite su ciascuno degli operandi. Il tipo del risultato è quello dell'operando sinistro promosso. Se il valore dell'operando di destra è negativo o è maggiore o uguale alla larghezza in bit dell'operando sinistro promosso, il comportamento non è definito.

Il risultato di E1 << E2 è E1 con posizioni E2 spostate a sinistra; i bit vuoti sono pieni di zeri. Se E1 ha un tipo senza segno, il valore del risultato è E1 moltiplicato per la quantità, 2 elevato alla potenza E2, modulo ridotto ULONG_MAX + 1 se E1 ha tipo unsigned long, altrimenti UINT_MAX + 1. (Le costanti ULONG_MAX e UINT_MAX sono definite nell'intestazione.)

Il risultato di E1 >> E2 è E1 con posizioni di bit E2 spostate a destra. Se E1 ha un tipo senza segno o se E1 ha un tipo firmato e un valore non negativo, il valore del risultato è la parte integrale del quoziente di E1 diviso per la quantità, 2 elevato alla potenza E2. Se E1 ha un tipo firmato e un valore negativo, il valore risultante è definito dall'implementazione.

Così:

x = y << z;

"<<": y × 2 z ( indefinito se si verifica un overflow);

x = y >> z;

">>": definito dall'implementazione per la firma (molto spesso il risultato dello spostamento aritmetico: y / 2 z ).




Ci sono molti casi su questo.

  1. Molte MPU ad alta velocità hanno un cambio elettronico a barilotto, un circuito elettronico simile a un multiplexer che esegue qualsiasi spostamento in tempo costante.

  2. Se MPU ha solo 1 bit di spostamento x << 10 normalmente sarà più lento, come per lo più fatto con 10 turni o copiatura a byte con 2 turni.

  3. Ma esiste un caso comune in cui x << 10 sarebbe ancora più veloce di x << 1 . Se x è 16 bit, solo 6 bit più bassi di esso sono utili (tutti gli altri verranno spostati), quindi MPU deve caricare solo il byte inferiore, quindi rendere solo un singolo ciclo di accesso alla memoria a 8 bit, mentre x << 10 necessità due cicli di accesso. Se il ciclo di accesso è più lento dello spostamento (e cancella il byte inferiore), x << 10 sarà più veloce. Questo può essere applicato ai microcontrollori con una ROM di programma veloce integrata durante l'accesso alla RAM di dati esterni lenti.

  4. Come aggiunta al caso 3, il compilatore può interessare il numero di bit significativi in x << 10 e ottimizzare ulteriori operazioni a quelle di larghezza inferiore, come la sostituzione della moltiplicazione 16x16 con 16x8 (dato che il byte inferiore è sempre zero).

Nota, alcuni microcontrollori non hanno alcuna istruzione shift-left, usano invece add x,x invece.







Su alcune generazioni di CPU Intel (P2 o P3? Non AMD però, se ricordo bene), le operazioni di bitshift sono ridicolmente lente. Bitshift di 1 bit dovrebbe essere sempre veloce, dal momento che può solo utilizzare l'aggiunta. Un'altra questione da considerare è se i bithift di un numero costante di bit siano più veloci rispetto ai turni di lunghezza variabile. Anche se gli opcode hanno la stessa velocità, su x86 l'operando destrorso non costante di un bithift deve occupare il registro CL, che impone ulteriori vincoli sull'allocazione del registro e può rallentare il programma anche in questo modo.




Alcuni processori integrati hanno solo un'istruzione "shift-by-one". Su tali processori, il compilatore cambierebbe x << 3 in ((x << 1) << 1) << 1 .

Penso che il Motorola MC68HCxx sia stato una delle famiglie più popolari con questa limitazione. Fortunatamente, tali architetture sono ora piuttosto rare, la maggior parte ora include un barrel shifter con una dimensione variabile del cambio.

Anche l'Intel 8051, che ha molti derivati ​​moderni, non può spostare un numero arbitrario di bit.




Come sempre, dipende dal contesto del codice circostante : ad esempio stai usando x<<1 come indice di matrice? O aggiungendolo a qualcos'altro? In entrambi i casi, il conteggio dei turni di piccole dimensioni (1 o 2) può spesso ottimizzare ancora di più che se il compilatore finisse per dover semplicemente spostarsi. Per non parlare dell'intero throughput vs. latenza rispetto al compromesso dei collo di bottiglia front-end. Le prestazioni di un piccolo frammento non sono unidimensionali.

Una istruzione di shift hardware non è l'unica opzione del compilatore per la compilazione di x<<1 , ma le altre risposte lo assumono principalmente.

x << 1 è esattamente equivalente a x+x per i non firmati e per gli interi con segno del complemento a 2. I compilatori sanno sempre quale hardware hanno come target durante la compilazione, in modo che possano trarre vantaggio da trucchi del genere.

Su Intel Haswell , add ha un throughput di 4 volte, ma shl con un conteggio immediato ha solo un throughput di 2 per clock. (Vedi http://agner.org/optimize/ per le tabelle di istruzioni e altri collegamenti nel wiki dei tag x86 ). I turni vettoriali SIMD sono 1 per orologio (2 in Skylake), ma i numeri interi SIMD vettoriali sono 2 per orologio (3 in Skylake). La latenza è la stessa, però: 1 ciclo.

C'è anche una speciale codifica shift-by-one di shl cui il conteggio è implicito shl . 8086 non ha avuto turni di conteggio immediato, solo da uno e dal registro cl . Questo è per lo più rilevante per i turni di destra, perché puoi semplicemente aggiungere i turni a sinistra a meno che non stia modificando un operando di memoria. Ma se il valore è necessario in seguito, è meglio caricare prima un registro. Comunque, shl eax,1 o add eax,eax è un byte più corto di shl eax,10 , e la dimensione del codice può direttamente (colli di bottiglia di decodifica / front-end) o indirettamente (mancate cache del codice L1I) influenzare le prestazioni.

Più in generale, i piccoli conteggi di spostamento possono a volte essere ottimizzati in un indice scalato in una modalità di indirizzamento su x86. La maggior parte delle altre architetture di uso comune in questi giorni sono RISC e non hanno modalità di indirizzamento dell'indice in scala, ma x86 è un'architettura abbastanza comune da farne menzione. (egg se stai indicizzando un array di elementi a 4 byte, c'è spazio per aumentare il fattore di scala di 1 per int arr[]; arr[x<<1] ).

La necessità di copiare + spostare è comune in situazioni in cui è ancora necessario il valore originale di x . Ma la maggior parte delle istruzioni per interi x86 operano sul posto. (La destinazione è una delle fonti per istruzioni come add o shl .) La convenzione di chiamata System V x86-64 supera gli args nei registri, con il primo argomento in edi e il valore restituito in eax , quindi una funzione che restituisce x<<10 fa sì che il compilatore emetta copia + codice maiuscole.

L' istruzione LEA ti consente di spostare e aggiungere (con un numero di turni da 0 a 3, poiché utilizza la codifica della macchina in modalità di indirizzamento). Mette il risultato in un registro separato.

gcc e clang entrambi ottimizzano queste funzioni allo stesso modo, come si può vedere nel explorer del compilatore Godbolt :

int shl1(int x) { return x<<1; }
    lea     eax, [rdi+rdi]   # 1 cycle latency, 1 uop
    ret

int shl2(int x) { return x<<2; }
    lea     eax, [4*rdi]    # longer encoding: needs a disp32 of 0 because there's no base register, only scaled-index.
    ret

int times5(int x) { return x * 5; }
    lea     eax, [rdi + 4*rdi]
    ret

int shl10(int x) { return x<<10; }
    mov     eax, edi         # 1 uop, 0 or 1 cycle latency
    shl     eax, 10          # 1 uop, 1 cycle latency
    ret

LEA con 2 componenti ha una latenza di 1 ciclo e un throughput a 2 per clock sulle recenti CPU Intel e AMD. (Famiglia Sandybridge e Bulldozer / Ryzen). Su Intel, è solo 1 throughput di clock con latenza 3c per lea eax, [rdi + rsi + 123] . (Correlato: .com/questions/40354978/…

Ad ogni modo, copy + shift by 10 richiede un'istruzione mov separata. Potrebbe trattarsi di una latenza zero su molte CPU recenti, ma richiede ancora larghezza di banda e dimensioni del codice front-end. ( Il MOV di x86 può essere veramente "libero"? Perché non riesco a riprodurre questo? )

Anche in relazione: come moltiplicare un registro per 37 usando solo 2 istruzioni leal consecutive in x86? .

Il compilatore è anche libero di trasformare il codice circostante in modo che non ci sia uno spostamento effettivo, o che sia combinato con altre operazioni .

Per esempio if(x<<1) { } potrebbe usare un and per controllare tutti i bit tranne il bit più alto. Su x86, dovresti usare un'istruzione di test , come test eax, 0x7fffffff / jz .false invece di shl eax,1 / jz . Questa ottimizzazione funziona per qualsiasi numero di turni e funziona anche su macchine in cui i turni di conteggio elevato sono lenti (come il Pentium 4) o inesistenti (alcuni microcontrollori).

Molti ISA hanno istruzioni di manipolazione dei bit oltre il semplice spostamento. ad es. PowerPC ha molte istruzioni di estrazione / inserimento bit-field. Oppure ARM ha spostamenti di operandi sorgente come parte di qualsiasi altra istruzione. Quindi le istruzioni di spostamento / rotazione sono solo una forma speciale di move , utilizzando una sorgente spostata.

Ricorda, C non è linguaggio assembly . Guarda sempre l'output del compilatore ottimizzato quando stai ottimizzando il codice sorgente per la compilazione.




Potenzialmente dipende dalla CPU.

Tuttavia, tutte le moderne CPU (x86, ARM) utilizzano un "barrel shifter", un modulo hardware progettato specificamente per eseguire spostamenti arbitrari in tempo costante.

Quindi la linea di fondo è ... no. Nessuna differenza.




Le importazioni di massa sembrano avere un rendimento migliore se si riescono a modificare le istruzioni INSERT / UPDATE . Un valore di 10.000 circa ha funzionato bene per me su un tavolo con solo poche righe, YMMV ...





c++ c performance cpu low-level