Apprendre à compacter des valeurs booléennes
Un tutoriel de Bartlomiej Filipek traduit par l'équipe de rédaction
Le 2019-04-24 09:26:08, par Community Management, Community Manager
Chers membres du club,
J'ai le plaisir de vous présenter ce tutoriel de Bartlomiej Filipek dont l'objectif est de vous apprendre à compacter des valeurs booléennes.
« J’ai commencé la rédaction de ce billet, car j’ai rencontré un problème similaire dans le cadre de mon travail il y a quelques temps. Le code d’une zone de notre système compactait des résultats booléens de conditions en bits. Je me demandais s'il était possible d’optimiser ce processus. Cet algorithme n’est pas des plus complexes, mais comme à l’accoutumée, il ouvre la réflexion sur des détails et solutions intéressantes. Alors j’ai décidé de partager cette réflexion avec mes lecteurs. »
Bonne lecture .
Retrouvez les meilleurs cours et tutoriels pour apprendre la programmation C++
J'ai le plaisir de vous présenter ce tutoriel de Bartlomiej Filipek dont l'objectif est de vous apprendre à compacter des valeurs booléennes.
« J’ai commencé la rédaction de ce billet, car j’ai rencontré un problème similaire dans le cadre de mon travail il y a quelques temps. Le code d’une zone de notre système compactait des résultats booléens de conditions en bits. Je me demandais s'il était possible d’optimiser ce processus. Cet algorithme n’est pas des plus complexes, mais comme à l’accoutumée, il ouvre la réflexion sur des détails et solutions intéressantes. Alors j’ai décidé de partager cette réflexion avec mes lecteurs. »
Bonne lecture
-
dorian833Membre avertiEn fait non, pas forcément car c'est une division entière. En gros, le code permet d'avoir la valeur de 'arrayLength' arrondie au multiple de 8 directement égal ou inférieur.
Par exemple pour 'arrayLength = 32' :
Code : 1
2
3arrayLength / 8 = 4 (arrayLength / 8) * 8 = 32
Par contre, si l'on prend 'arrayLength = 34' :
Code : 1
2
3arrayLength / 8 = 4 (arrayLength / 8) * 8 = 32
On rencontre souvent du code assez proche pour calculer le stride d'une image.le 25/04/2019 à 9:53 -
cambouiMembre éprouvéCeci est tellement plus direct
Code : const int64_t lenDivBy8 = arrayLength & ~7;
le 27/04/2019 à 16:46 -
cambouiMembre éprouvéComme souligné dans l'article, std::vector<bool> est sensé être "compacté". C'est toujours bon à prendre dans de nombreux cas
(même si pas recommandé à cause de défauts dont il faut être conscient).
Ceci me rappelle qu'il y a une bonne 20aine d'années j'avais implémenté un tableau dynamique de bits. Je ne l'ai plus utilisé depuis 15 ans...le 24/04/2019 à 10:46 -
BouskRédacteur/ModérateurPar contre je ferais attention à ce genre de code.
J'ai implémenté un système similaire, et avec des calculs de ce genre le compilateur les optimisait en release ce qui donnait des résultats incorrects..
Après c'était sur des constexpr et non des variables, peut-être que ça importe.le 25/04/2019 à 14:23 -
jmricher49Membre à l'essaiJ'ai pu noter plusieurs problèmes à la lecture de cet article.
D'une part l'explication du traitement même si très simple est mal exprimée dans la partie "II Algorithme". Il faut donner un nom au tableau en entrée et un nom au tableau en sortie pour pouvoir les différencier
car lorsqu'on litle ième bit du tableau est mis à 1 lorsque la ième valeur du tableau d’entiers est supérieure au seuil donné
De même le pseudo-code est beaucoup plus explicite comme cela :Code : 1
2
3for (int i=0; i<N; ++i) { if (input_data[i] > threshold) output_data[i] = 1; }
Dans la partie IX. Améliorations direce n’est pas très efficace, car on utilise très peu l’architecture du processeur
instruction pipelining
Dans la partie X. Résultats on ne sait pas quelles sont les options de compilation utilisées. Un "-O2" ou un "-O3" produisent des résultats parfois très différents la dernière option étant préférable et il faudrait spécifier l'utilisation de la vectorisation avec un "-mavx2" par exemple avec gcc/c++
Il est évident que la version sans compactage sera beaucoup plus rapide car il n'y a pas d'instruction qui permet de manipuler les bits comme on le voudrait ici.La version la plus rapide correspond au code suivantCode : 1
2
3
4
5void procedure(u8 *x, u8 *y, u32 size) { for (u32 i = 0; i < size; ++i) { y[i] = (x[i] > threshold) ? 1 : 0; } }
Avec ici u8 est en caractère non signé donc un byte et u32 en entier non signéle 05/05/2019 à 14:07 -
jmricher49Membre à l'essaiEn fait la formule exacte pour trouver la longueur du tableau compacté est
Code : (arrayLength + 7)/8
le 05/05/2019 à 14:16 -
darkman19320Membre éclairéMerci pour ce tutoriel très bien expliqué.
J'ai cependant une petite question: à quoi sert cette ligne (paragraphe IX)?
Code : const int64_t lenDivBy8 = (arrayLength / 8) * 8;
Si on divise par 8 puis multiplie par 8 ensuite, un nombre entier, on n'est pas sensé obtenir la même chose?le 25/04/2019 à 8:25