IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous
Identifiant
Mot de passe
Mot de passe oublié ?
Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

Apprendre à compacter des valeurs booléennes
Un tutoriel de Bartlomiej Filipek traduit par l'équipe de rédaction

Le , par Community Management

55PARTAGES

18  0 
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++

Une erreur dans cette actualité ? Signalez-nous-la !

Avatar de dorian833
Membre averti https://www.developpez.com
Le 25/04/2019 à 9:53
En 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 : Sélectionner tout
1
2
3
arrayLength / 8 = 4
(arrayLength / 8) * 8 = 32
Le résultat est effectivement identique.

Par contre, si l'on prend 'arrayLength = 34' :
Code : Sélectionner tout
1
2
3
arrayLength / 8 = 4
(arrayLength / 8) * 8 = 32
C'est ici que l'on se rend compte de l'intérêt d'une telle ligne.

On rencontre souvent du code assez proche pour calculer le stride d'une image.
4  0 
Avatar de camboui
Membre éprouvé https://www.developpez.com
Le 27/04/2019 à 16:46
Ceci est tellement plus direct
Code : Sélectionner tout
const int64_t lenDivBy8 = arrayLength & ~7;
Sauf que, ~7 est-il 32 ou 64 bits ? Telle est la question...
2  0 
Avatar de camboui
Membre éprouvé https://www.developpez.com
Le 24/04/2019 à 10:46
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...
1  0 
Avatar de Bousk
Rédacteur/Modérateur https://www.developpez.com
Le 25/04/2019 à 14:23
Par 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.
1  0 
Avatar de jmricher49
Membre à l'essai https://www.developpez.com
Le 05/05/2019 à 14:07
J'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 lit
le ième bit du tableau est mis à 1 lorsque la ième valeur du tableau d’entiers est supérieure au seuil donné

ce n'est plus très évident pour le lecteur.

De même le pseudo-code est beaucoup plus explicite comme cela :

Code : Sélectionner tout
1
2
3
for (int i=0; i<N; ++i) { 
	if (input_data[i] > threshold) output_data[i] = 1; 
}
pour ensuite passer à la version compacte.

Dans la partie IX. Améliorations dire
ce n’est pas très efficace, car on utilise très peu l’architecture du processeur

est faux. Il faudrait à la rigueur reprendre les termes de l'auteur qui parle d'
instruction pipelining

, mais en fait il s'agit d'un dépliage de boucle.

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 suivant

Code : Sélectionner tout
1
2
3
4
5
void procedure(u8 *x, u8 *y, u32 size) { 
	for (u32 i = 0; i < size; ++i) { 
		y[i] = (x[i] > threshold) ? 1 : 0; 
	} 
}
car le compilateur pourra vectoriser le code sans trop de problème.
Avec ici u8 est en caractère non signé donc un byte et u32 en entier non signé
1  0 
Avatar de jmricher49
Membre à l'essai https://www.developpez.com
Le 05/05/2019 à 14:16
Citation Envoyé par darkman19320 Voir le message
Merci pour ce tutoriel très bien expliqué.

J'ai cependant une petite question: à quoi sert cette ligne (paragraphe IX)?
Code : Sélectionner tout
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?
En fait la formule exacte pour trouver la longueur du tableau compacté est

Code : Sélectionner tout
(arrayLength + 7)/8
par exemple si arrayLength = 15, il faut deux octets et arrayLength+7 = 22, qui divisé par 8 (division entière) donne 2
1  0 
Avatar de darkman19320
Membre éclairé https://www.developpez.com
Le 25/04/2019 à 8:25
Merci pour ce tutoriel très bien expliqué.

J'ai cependant une petite question: à quoi sert cette ligne (paragraphe IX)?
Code : Sélectionner tout
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?
0  0