Discussion :

[lucas-84]

Bonsoir,

Il y a peu de temps, je me suis dit que j'allais me remettre aux opérateurs bit à bit. Après avoir lu quelques billets de blog sur les effets néfastes des branchements conditionnels, j'ai essayé de reproduire ce mécanisme de condition avec ces opérateurs bas niveaux.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdint.h>
 
/*
 * Evaluate the expression `expr'. If it's true, return `a' ; else, return `b'.
 * This function doesn't use any conditionnal or unconditionnal branches,
 * therefore it should go faster than an habitual function-like if the macro
 * `CODE_OPTIMIZE' is defined.
 */
static inline uint32_t test(_Bool expr, uint32_t a, uint32_t b)
{
#ifdef CODE_OPTIMIZE
	uint32_t mask = (uint32_t)(((int32_t) -expr) >> 31);
	return (a & mask) | (b & ~mask);
#else
	return expr ? a : b;
#endif
}

Si on met de côté les commentaires dans mon anglais grisonnant ainsi que la relative illisibilité du code, je me retrouve quand même avec des résultats probants sur plusieurs benchmark.

Ce sujet n'est donc pas réellement une question, mais plutôt une demande de confirmation, voire d'améliorations de ce code qui semble aller plus vite lorsque la constante CODE_OPTIMIZE est définie.

Et, sinon, dans ce cas-là, pourquoi utiliser les ternaires par exemple (qui a beau être une implémentation native du langage...), dont on pourrait, par exemple, recoder le fonctionnement grâce à des macros hideuses de génération de code. (mis à part le problème de flexibilité dû à l'utilisation des entiers de taille fixe, qui peut être contourné)

Bonne soirée à vous et merci pour votre lecture et/ou pour votre participation.

[Neckara]

les effets néfastes des branchements conditionnels

Pourrais-tu nous en dire un peu plus à ce propos ou nous donner un lien pour que les éventuels lecteurs (comme moi) sache de quoi tu parles?^^

[lucas-84]

Bah en gros, les branchements conditionnels (ce qui comprend conditions, aiguillages et boucles) sont coûteux, notamment sur certains processeurs (du genre PowerPC). Ce code en est peut-être la preuve (chez, moi, bien que je ne sois pas équipé d'un tel processeur), semble aller plus vite qu'une utilisation basique des ternaires.

Exemple de citation (mais il y en a d'autres) du guide d'écriture du compilateur pour IBM PowerPC §3.1.5 :

Branching, both conditional and unconditional, slows most implementations.

[diogene]

A noter que ces expressions ne constituent pas vraiment une équivalence à l'opérateur ternaire :
L'opérateur ternaire spécifie que exp est évalué et que selon le résultat (Vrai, Faux), l'opérande a ou l'opérande b sera évalué et que l'autre ne le sera pas.
Dans le code alternatif, a & mask et b & ~mask seront évalués, donc a et b seront tous deux évalués.
Ceci peut avoir de l'importance si on a des effets de bords sur l'évaluation de a ou b ce qui peut se produire sur une macro. Par exemple, pour illustrer :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
#define Mask(expr) (uint32_t)(((int32_t) -(expr)) >> 31)
#define Ternaire(expr,a,b) ((a) & Mask(expr)) | ((b) & ~Mask(expr))
// ces deux expressions ne donneront pas le même résultat si expr==false
 A = Ternaire(expr,a++,b);
 A = expr ? a++ : b;

Il faut donc prendre des précautions dans le cas d'une macro

[Taurre]

Salut,

Comme cela a été dit par diogene, le problème est que dans ce cas tu n'auras pas de point de séquence entre l'évaluation de la condition et l'un des deux derniers opérandes. Sinon, l'instruction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

uint32_t mask = (uint32_t)(((int32_t) -expr) >> 31);

me semble inutilement complexe et à un comportement dépendant de l'implantation :

The result of E1 >> E2 is E1 right-shifted E2 bit positions.
If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2.
If E1 has a signed type and a negative value, the resulting value is implementation-defined.

Chez moi l'application de l'opérateur de décalage >> sur un nombre négatif n'a aucun effet. Étant donné que les types de tailles fixes comme uint32_t sont garantis d'être stocké en complément à deux, cette ligne peut être simplifiée en :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

uint32_t mask = (uint32_t)-expr;

Aussi, cette technique fonctionne avec des expressions entières, mais quid de pointeurs, de nombres flottants, de nombres complexes, de structures ou unions ou encore d'expressions de type void comme celle-ci ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(ptr != NULL) ? free(ptr) : (void)0;

[mith06]

Salut,

J'ai pensé à ca:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
static inline uint32_t test(_Bool expr, uint32_t a, uint32_t b)
{
	uint32_t mux_a = expr & 1;	//vaut 1 si expr, 0 sinon
	uint32_t mux_b = (!expr) & 1;//vaut 0 si expr, 1 sinon
	return a*mux_a + b*mux_b;
}

Ca peut valoir le coup si la multiplication entière est effectuée en 1 cycle.
Ce bout de code doit consommer 6 cycles machines.

Si on considère le cas où TRUE est TOUJOURS représenté par la valeure entière 1.

Alors on pourrait directement faire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

return a*expr + b*(!expr);

Qu'en pensez-vous?

[boboss123]

salut,

Pour vraiment comprendre pourquoi ça te semble aller plus vite, je te conseille d'analyser le code assembleur (remarque: les commandes de saut peuvent prendre plusieurs cycles)... l'optimisation peut dépendre du compilateur utilisé (et de sa configuration) et du hardware...

Aussi là ou tu peux optimiser, c'est sur la taille des variables : si tu travailles avec des variables de la taille de ton CPU. En général ça correspond au type '(unsigned) int' (ex: CPU 32bit => variable 4 octets), ça ira beaucoup plus vite car il y aura plein d'étapes en moins.
=> par exemple si tu fais des additions sur des uchar, ça ira moins vite que sur des unsigned int