Est-ce que le décalage de bits est en O(1) ou en O(n) ?

Question

Les opérations de décalage sont-elles de complexité O(1) ou O(n) ?

A-t-il du sens que les ordinateurs nécessitent généralement plus d'opérations pour décaler de 31 places au lieu d'une place?

Ou a-t-il du sens que le nombre d'opérations requis pour le décalage est constant quel que soit le nombre de places que nous devons décaler?

PS : se demander si hardware est une balise appropriée..

Answer 1

Certains ensembles d'instructions sont limités à un décalage d'un bit par instruction. Et certains ensembles d'instructions vous permettent de spécifier n'importe quel nombre de bits à décaler en une seule instruction, ce qui prend généralement un cycle d'horloge sur les processeurs modernes (moderne étant un mot intentionnellement vague). Voir la réponse de dan04 à propos d'un shifter en cascade, un circuit qui décale plus d'un bit en une seule opération.

Tout se résume à l'algorithme logique. Chaque bit du résultat est une fonction logique basée sur l'entrée. Pour un simple décalage à droite, l'algorithme serait quelque chose comme :

• Si l'instruction est [décalage à droite] et que le bit 1 de l'entrée est 1, alors le bit 0 du résultat est 1, sinon le bit 0 est 0.
• Si l'instruction est [décalage à droite], alors le bit 1 = bit 2.
• etc.

Mais l'équation logique pourrait aussi bien être :

• Si l'instruction est [décalage à droite] et que l'opérande est de 1, alors le bit 0 du résultat = bit 1 décalé de l'entrée.
• si la quantité est de 2 alors le bit 0 = bit 2.
• et ainsi de suite.

Les portes logiques, étant asynchrones, peuvent faire tout cela en un seul cycle d'horloge. Cependant, il est vrai que le décalage unique permet un cycle d'horloge plus rapide et moins de portes à stabiliser, si tout ce que vous comparez sont ces deux variantes d'une instruction. Ou l'alternative est de laisser le temps de se stabiliser, donc l'instruction prend 2 ou 3 cycles d'horloge ou autre, et la logique compte jusqu'à 3 puis verrouille le résultat.

Le MSP430, par exemple, n'a que des instructions de rotation d'un seul bit vers la droite (car vous pouvez effectuer un décalage d'un seul bit ou une rotation à gauche avec une autre instruction, que je laisse au lecteur le soin de comprendre).

L'ensemble d'instructions ARM permet des rotations multibits basées à la fois sur un registre et immédiates, des décalages arithmétiques et logiques. Je pense qu'il n'y a qu'une seule instruction de rotation réelle et le reste est un alias, car tourner à gauche de 1 est la même chose qu'une rotation à droite de 32, il vous suffit d'un shifter en cascade dans une direction pour implémenter un décalage multibit.

SHL dans le x86 permet plus d'un bit par instruction, mais cela prenait plus d'un cycle autrefois.

et ainsi de suite, vous pouvez facilement examiner n'importe lequel des ensembles d'instructions disponibles.

La réponse à votre question est que ce n'est pas fixe. Parfois c'est une opération, un cycle, une instruction. Parfois c'est une instruction, plusieurs cycles d'horloge. Parfois ce sont plusieurs instructions, plusieurs cycles d'horloge.

Les compilateurs optimisent souvent pour ce genre de choses. Disons que vous avez un ensemble d'instructions de registres de 16 bits avec une instruction d'échange de byte et une instruction AND avec une valeur immédiate, mais un seul décalage de bit. Vous pourriez penser qu'un décalage de 8 bits nécessiterait 8 cycles d'instructions de décalage, mais vous pourriez simplement échanger les bytes (une instruction) et ensuite effectuer un ET avec la moitié inférieure mise à zéro (ce qui pourrait prendre deux instructions, ou pourrait être une instruction de longueur variable de deux mots, ou pourrait être encodée en une seule instruction) donc cela ne prend que 2 ou 3 cycles d'instructions/d'horloge au lieu de 8. Pour un décalage de 9 bits, vous pouvez faire la même chose et ajouter un décalage, ce qui le rendrait de 9 cycles contre 3 ou 4. De plus, sur certaines architectures, il est plus rapide de multiplier par 256 que de décaler de 8 bits, etc., etc. Chaque ensemble d'instructions a ses propres limites et astuces.

Ce n'est même pas le cas que la plupart des ensembles d'instructions fournissent du multi bit ou limitent à un bit. Les processeurs qui entrent dans la catégorie "informatique", comme X86, ARM, PowerPC et MIPS, pencheront vers une opération de décalage. En élargissant à tous les processeurs mais pas nécessairement les "ordinateurs" couramment utilisés aujourd'hui, le tendance s'inverse, je dirais que la plupart d'entre eux sont à un seul bit plutôt que multi bits, donc plusieurs opérations sont nécessaires pour réaliser un décalage multibits.

Answer 2

Un barrel shifter permet d'effectuer la translation en O(log n) passes - ce qui peut être fait dans le même cycle d'horloge, rendant le décalage une opération O(1).

Answer 3

Comme déjà noté, un décaleur de barillet peut décaler un opérande à une distance arbitraire en temps constant. Un décaleur de barillet, cependant, consomme une quantité importante d'espace sur une puce de CPU, donc ils ne sont pas inclus dans tous les conceptions de CPU.

Juste pour un exemple assez bien connu, l'Intel Pentium III inclus un décaleur de barillet - mais le Pentium IV ne l'a pas inclus. Le code écrit pour un Pentium III en supposant qu'un décaleur de barillet était présent ralentissait parfois considérablement sur un Pentium IV. J'avais un code de cryptage (qui inclut beaucoup de décalages et rotations) qui fonctionnait environ 4 fois plus vite sur un Pentium III 1.2 GHz que sur un Pentium IV 2.8 GHz.

Answer 4

Le décalage de bits est en O(1) sur pratiquement tous les processeurs actuels.

Jetez un œil, par exemple, à l'instruction "shrw" x86. Le premier opérande (en syntaxe AT&T) est le nombre de bits à décaler. La façon dont un compilateur implémente le décalage dépend du compilateur, mais il serait ridicule de mettre des décalages dans une boucle quand un processeur peut décaler N bits en une seule fois.

Addendum : Re : "Nécessitent-ils plus d'opérations pour décaler de 31 places vers la gauche ?" Il existe différents types de décalages (si vous vous demandez pourquoi, pensez à ce qu'il faut faire avec les bits qui sont décalés hors du registre), mais la plupart des processeurs peuvent effectuer un décalage en un seul instruction , autant de bits que le GPR peut stocker. Pour effectuer un décalage de 40 bits sur un registre 32 bits, il serait nécessaire de décaler à travers plusieurs registres (en supposant qu'un nombre de 64 bits soit stocké sur 2 registres de 32 bits), ce qui, sur tous les processeurs que je connais, nécessitera davantage d'instructions. Ce serait toujours O(1), mais probablement pas en un cycle. Fait intéressant, le processeur Pentium IV est étonnamment lent pour les décalages de bits. Cela est ironique car Intel a historiquement recommandé l'optimisation des divisions et multiplications par ^2 en passant par le décalage de bits. Voir : ce PDF et rechercher plus d'informations sur Google si intéressé.

Answer 5

Ahem, j'ai testé cela par curiosité en c# et obtenu des résultats amusants.

var sw = Stopwatch.StartNew();
long l = 1;
for (long i = 0; i < 20000000; i++) {
    l = l << 60; l = l >> 60;
    l = l << 60; l = l >> 60;
    l = l << 60; l = l >> 60;
    //...
    // 50 de ^eux^ au total

}
Console.WriteLine(l + " " + sw.Elapsed);

Cela prend 1.2 secondes sur mon PC. Mais si je remplace

l = l << 60; l = l >> 60;

avec

l = l << 1; l = l >> 1;

alors le temps augmente à 2.0 secondes. Je n'ai aucune idée des optimisations en jeu ici, mais cela semble étrange.