[C++] Qual è più veloce: x << 1 o x << 10?


Answers

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.

Question

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. :)




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.




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 ).




Su ARM, questo può essere fatto come un effetto collaterale di un'altra istruzione. Quindi, potenzialmente, non c'è nessuna latenza per nessuno di essi.