Avantages de la manipulation de bits ?

[Dalini71]

Bonjour à tous,

J'entends beaucoup parler (surtout dans le secteur du jeux vidéo) de l'utilisation intensive des opérateurs bits à bits à des fins de performance.

Je n'ais pas trouvé de benchmarks sur le net, ces gains sont-ils vraiment significatifs ? Les compilateurs ne sont-ils pas capables de faire eux mêmes ces optimisations ?

Merci d'avance

Ca sert à plein de choses... en fait les opérations sur les bits c'est ce que fait ta machine et il y'a des cas où c'est utile, plus rapide, voir obligatoire, de tripoter directement les bits au lieu d'utiliser les maths classiques

En 3d c'est très utilisé pour optimiser le poids des listes d'index de triangles, de points, etc.

Imagine que ton objet a 400 000 vertices. Tu souhaites faire un tableau d'index de vertices pour faire un calcul sur un nombre limité de vertices. Si ce nombre est plafonné à une petite quantité de points ça ne sert à rien d'optimiser avec des bits, par contre si ce tableau peut contenir la totalité des verts tu vas donc avoir un tableau qui peut faire 4octets * 400 000 = 1 600 000 octets. si maintenant tu utilises un tableau de bits à la place ça donne 400 000 bit / 8 = 50 000 octets, tu as divisé le poids par 32.

Ca sert également à simplifier beaucoup de calculs. Par exemple si tu veux trouver les index communs entre deux listes il suffit de faire une opération bitmask (&) au lieu de te taper des parcours de tableau avec de la force brute.


En 2d les opérations binaires ça sert aussi pour simplifier les opérations sur les pixels ou les grilles (c'est pour ça que les cartes vidéo ont des dimensions d'image puissance 2 ça permet de faire des calculs plus rapides dedans avec des opérations binaires)

Par exemple ta carte doit trouver l'adresse du pixel aux coordonnées x,y sur une texture, plutôt que de faire l'opération adressepremierpixel + y * largeur + x, la carte va faire adresseprempixel + ( y << bitShiftDelaLargeur ) + x, tu remplaces une multiplication par un bitshift et c'est beaucoup plus rapide.

On s'en sert aussi pour la répétition du tracé d'une image avec l'opérateur bitmask "&", là il n'y a aucun équivalent propre pour faire cette opération avec des calculs plus "math".

Les opérations binaires permettent aussi de remplacer les divisions par un bitshift qui va dans l'autre sens quand par exemple tu cherches la case contenant un point sur une grille, c'est ce qui permet par exemple de rendre une tilemap en rendu-cpu ou avec un shader pixel. et pour trouver la position du point à l'intérieur de la case tu as besoin de l'opérateur bitmask ensuite.

Ca sert aussi à optimiser le poids du stockage des données booléennes, au lieu d'utiliser un octet par booléen on utilise un seul bit et on range tout ça dans un objet flags qui est un bête nombre contenant autant de bits que tu veux.

Donc déjà les gains sont vraiment significatifs oui, les opérations sur les bits sont bien plus rapides que les calculs de type multiplication, division, modulo, ou que les parcours de listes d'index, et il y'a des cas où ça permet une très bonne compression des données. Mais en plus il y'a des cas où on est obligés d'utiliser ces opérateurs, notemment le bitmask qui n'a pas un équivalent exact avec le modulo.

Ca servait aussi à encoder et lire des pixels avec un poids inférieur à 8 bits mais ça je suis pas sûr que ça soit encore utilisé à part dans les émulateurs d'antiquités... par contre on utilise toujours ces opérations pour extraire les 4 couches d'un pixel codé sur 32 bit: couchebleue = couleur & 255 , couchevert = (couleur>>8) & 255 coucherouge = (couleur>>16) & 255 et couchealpha = (couleur>>24) & 255 .. ou pour recomposer cette couleur à partir de ses 4 couches: couleur = bleu | (vert<<8) | (rouge<<16) | (alpha<<24)

Donc dans les jeux les opérations binaires on s'en sert partout. c'est des calculs qui n'ont rien de compliqué faut juste comprendre ce que font les opérateurs binaires

j'en connais que 6 je sais pas s'il y'en a plus

deux opérateurs bitshift:

<< = bitshift gauche (tu décales ton nombre binaire de x bit sur la gauche, donc 0001 bitshift 2 va devenir 0100 ... soit 1<<2 donne 8 et ça donne une multiplication par une puissance de 2)
>> = bitshift droit, pareil mais vers la droite et ça fait une division donc

quatre opérateurs bitwise:

& = bitmask/intersection. ça fait une opération "and" entre tous les bits de deux nombres
| = union. pareil avec une opération "or"
^ = pareil avec une opération xor le sherif de l'espace
~ = fait une opération "not" sur tous les bits du nombre

[Dalini71]

Merci beaucoup pour ta réponse bien complète, je vais aller potasser tout ça

Un bon entrainement pour se familiariser avec ces trucs là c'est de t'amuser à faire un petit jeu ringard en tuiles genre un tetris ou un casse-briques, y'a du calcul binaire dans tous les coins... c'est plus simple de s'exercer à faire du rendu-cpu avant de passer au pixels shaders

[dancingmad]

Envoyé par Dalini71

Les compilateurs ne sont-ils pas capables de faire eux mêmes ces optimisations ?

Oui et non. Aujourd'hui, les compilateurs sont assez intelligents pour optimiser certains bouts de code, comme par exemple transformer :

Code :

entier /= 2;

en :

Code :

entier >>= 1;

ou encore :

Code :

entier %= 4;

en :

Code :

entier &= 0x3;

Cependant, comme le dit punkcoders, si tu utilise un tableau de int au lieu d'un tableau de bits pour indexer les vertices, le compilateur ne va rien optimiser du tout ! C'est à toi de choisir les bonnes structures de données, car d'une manière générale le compilo n'y touchera pas.

[LLB]

Oui, le compilo est malin... mais il ne sait pas tout. Le compilo a aussi une contrainte : il n'optimise que quand il est certain à 100% que le résultat sera correct, c'est-à-dire qu'il doit prendre en compte toutes les possibilités. L'optimisation de code, c'est utiliser les infos que tu as et que le compilo n'a pas.

Bien sûr, avant d'optimiser ton code, vérifie que tu optimises la bonne partie du code (avec un profiler), vérifie que tu as fait toutes les optimisations de plus haut niveau (complexité des algos, structures de données adaptées). Et après tout changement, benchmark pour vérifier que ça a eu un impact mesurable.

Par exemple, si tu sais que n est toujours une puissance de 2, et que x est positif, tu peux remplacer "x % n" par "x & (n - 1)" (je te laisse réfléchir pourquoi). Ça, c'est un truc que le compilo ne pourra généralement pas deviner.

Tu peux regrouper plusieurs valeurs, des petits entiers ou des booléens, sur un char ou un int. Le compilo utilise souvent un octet pour un booléen. Il fait ça parce que ça permet un accès direct à la valeur. D'un autre côté, ça peut faire grossir tes objets, utiliser plus de ram et mener à des cache-miss. C'est à toi de voir ce qui vaut mieux pour ton appli.

dancingmad : non, "x /= 2" et "x >>= 2" ne sont pas équivalents !
Et "entier %= 4" est différent de "entier &= 0x3" !

Code :

1
2
3
4
5
6
7
8
9
10
11
12
$ cat a.c
#include <stdio.h>
 
int main() {
  int a = -5;
  a /= 2;
  int b = -5;
  b >>= 1;
  printf("%d, %d\n", a, b);
}
$ gcc a.c && ./a.out
-2, -3

Bref, quand on sait que certains nombres seront positifs, on peut faire des optimisations que le compilo n'osera pas faire, car il doit prendre en compte tous les cas particuliers.

Pour aller plus loin, plein de bouts de code intéressants : http://www-graphics.stanford.edu/~seander/bithacks.html

[Dalini71]

Tu peux regrouper plusieurs valeurs, des petits entiers ou des booléens, sur un char ou un int

Comment fait-on ça ?

[dancingmad]

Envoyé par LLB

dancingmad : non, "x /= 2" et "x >>= 2" ne sont pas équivalents !
Et "entier %= 4" est différent de "entier &= 0x3" !

Ah, en effet je n'avais pas pensé aux valeurs négatives ! Merci pour la correction.

[dancingmad]

Envoyé par Dalini71

Comment fait-on ça ?

Et bien par exemple, si tu as un booléen et un entier non signé dont tu sais que la valeur est toujours comprise entre 0 et 15, la représentation mémoire doit prendre au moins 5 bits (1 bit pour le booléen, 4 bits pour l'entier). Au lieu de stocker ces deux variables dans un structure qui contient un char et un int (en général 5 octets), tu va regrouper les valeurs dans un seul octet, les 4 premiers bits de poids faibles représentant ton entier et le 5e bit de poids faible représentant ton booléen. Tu auras gagné 4 octets dans l'affaire.

Plus précisément, au lieu de faire :

Code :

1
2
3
4
5
6
7
8
9
10
struct exemple
{
    unsigned char monBool;
    unsigned int monInt;
}
 
typedef struct exemple exemple;
 
unsigned char get_monBool( exemple* s ) { return s->monBool; }
unsigned int get_monInt( exemple* s ) { return s->monInt; }

on écrit :

Code :

1
2
3
4
typedef uint8_t exemple;
 
unsigned char get_monBool( exemple* s ) { return ( char ) ( ( s & 0x10 ) >> 4 ); }
unsigned int get_monInt( exemple* s ) { return ( int ) ( s & 0xf ); }

ps : Au passage, tu remarquera que les signatures des fonctions get_monBool et get_monInt sont identiques dans les exemples 1 et 2 : l'interface est indépendante de la représentation mémoire.

[Neckara]

Envoyé par dancingmad

Et bien par exemple, si tu as un booléen et un entier non signé dont tu sais que la valeur est toujours comprise entre 0 et 15, la représentation mémoire doit prendre au moins 5 bits (1 bit pour le booléen, 4 bits pour l'entier). Au lieu de stocker ces deux variables dans un structure qui contient un char et un int (en général 5 octets), tu va regrouper les valeurs dans un seul octet, les 4 premiers bits de poids faibles représentant ton entier et le 5e bit de poids faible représentant ton booléen. Tu auras gagné 4 octets dans l'affaire.

Plus précisément, au lieu de faire :

Code :

on écrit :

Code :

ps : Au passage, tu remarquera que les signatures des fonctions get_monBool et get_monInt sont identiques dans les exemples 1 et 2 : l'interface est indépendante de la représentation mémoire.

Ne peux-t-on pas se contenter de :

Code :

1
2
3
4
5
struct
{
           unsigned bit:1;
           signed entier:4;
};

Sinon :

Au lieu de stocker ces deux variables dans un structure qui contient un char et un int (en général 5 octets)

Pourquoi un int? Autant utiliser un signed char pour l'entier (donc 1+1 octets). Il ne faut pas oublier qu'un char est un entier comme les (unsigned) short, int, long int et long long int.

[Dalini71]

Envoyé par Neckara

Ne peux-t-on pas se contenter de :

Code :

Je suis assez d'accord, de ce que j'ai compris l'objectif est d’économiser de la place, mais c'est bien plus lisible de cette manière à mon goût.

[Mat.M]

Envoyé par punkcoders

Imagine que ton objet a 400 000 vertices. Tu souhaites faire un tableau d'index de vertices pour faire un calcul sur un nombre limité de vertices. Si ce nombre est plafonné à une petite quantité de points ça ne sert à rien d'optimiser avec des bits, par contre si ce tableau peut contenir la totalité des verts tu vas donc avoir un tableau qui peut faire 4octets * 400 000 = 1 600 000 octets. si maintenant tu utilises un tableau de bits à la place ça donne 400 000 bit / 8 = 50 000 octets, tu as divisé le poids par 32.

cette logique est exacte et bonne.
1-mais cela me semble inutile; un mesh 3d c'est un objet composé de sommets et de triangles qui définissent les polygones donc.
Les sommets sont codés sur des float en C++ ou nombres réels à virgules flottantes donc je ne vois vraiment pas l'intérêt de faire des opérations bit-à-bits
C'était valable du temps de la programmation sous Dos avec un Dos Extender et lorsque tu faisais des calculs en virgule fixes et entiers
Maintenant avec les cartes graphiques actuelles performantes


2 dans la réalité si tu conçois un jeu 3d afficher un objet de 400 000 sommets, ce qui représente un certain nombre de polygones, tu auras des difficultés pour l'afficher et des problèmes de fluidité...
si tu veux gérer 400 000 sommets il vaut mieux faire du code GPU carrément
Ensuite une scène 3d avec des objets si complexes ça risque de ramer à l'affichage ; la technique généralement utilisée c'est d'afficher le même objet en "low polygon" lorsqu'il est plus loin et avec tous ses polygones au premier plan
Il y a une méthode avec D3d9 qui permet de réduire le nombre de polygones d'un objet sans doute aussi avec OpenGL

Envoyé par Mat.M

mais cela me semble inutile; un mesh 3d c'est un objet composé de sommets et de triangles qui définissent les polygones donc.
Les sommets sont codés sur des float en C++ ou nombres réels à virgules flottantes donc je ne vois vraiment pas l'intérêt de faire des opérations bit-à-bits
C'était valable du temps de la programmation sous Dos avec un Dos Extender et lorsque tu faisais des calculs en virgule fixes et entiers
Maintenant avec les cartes graphiques actuelles performantes

C'est vrai tout ce que tu as écrit à propos des vecteurs Mat, et effectivement on ne se sert pas du binaire pour coder des vecteurs, mais il y'a malentendu dès de départ car je ne parlais pas des vecteurs.

Si tu relis mon texte tu verras que je ne parle pas des vecteurs mais des indexes d'entités (points, triangles, ngons, courbes, zones etc), et aussi j'ai expliqué à quoi ça sert de faire ça avec des bits.

Ce sont des opérations utilisées côté calculs processeur, pas gpu. Le gpu tu lui as rentré des vertbuffer dedans et puis tu lui dis lesquels afficher avec quelle matrice, ça c'est les calculs gpu. Mais d'abord il y'a des indexes d'objets à touver en amont, et ça, il y'a des cas de figure où ça marche mieux avec des bits.

Dans un logiciel de modeling comme 3dsmax les bits c'est utilisé partout notemment pour les selections d'entités (vert, face, etc). Dans un moteur de jeu ça peut donc également être très utilisé côté éditeur et pour les mêmes raisons.
Et côté jeu, ça s'utilise moins c'est vrai mais y'a quand même des cas où ça sert. Les listes de bits par exemple c'était utilisé par les versions 2 et 3 du quake engine pour précalculer les zones occluses.

Et sinon les calculs sur les bits au niveau des nombres on peut faire beaucoup de choses aussi avec, notemmement accélérer tout un tas d'opérations