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

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Éviter les branchements conditionnels grâce aux opérateurs bitwise


Sujet :

C

  1. #1
    Membre à l'essai
    Profil pro
    Inscrit en
    octobre 2010
    Messages
    36
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : octobre 2010
    Messages : 36
    Points : 19
    Points
    19
    Par défaut Éviter les branchements conditionnels grâce aux opérateurs bitwise
    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.

  2. #2
    Inactif  


    Homme Profil pro
    Doctorant sécurité informatique — Diplômé master Droit/Économie/Gestion
    Inscrit en
    décembre 2011
    Messages
    9 013
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 28
    Localisation : France, Loire (Rhône Alpes)

    Informations professionnelles :
    Activité : Doctorant sécurité informatique — Diplômé master Droit/Économie/Gestion
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2011
    Messages : 9 013
    Points : 22 975
    Points
    22 975
    Par défaut
    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?^^

  3. #3
    Membre à l'essai
    Profil pro
    Inscrit en
    octobre 2010
    Messages
    36
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : octobre 2010
    Messages : 36
    Points : 19
    Points
    19
    Par défaut
    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.

  4. #4
    Expert éminent sénior
    Avatar de diogene
    Homme Profil pro
    Enseignant Chercheur
    Inscrit en
    juin 2005
    Messages
    5 761
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Enseignant Chercheur
    Secteur : Enseignement

    Informations forums :
    Inscription : juin 2005
    Messages : 5 761
    Points : 13 724
    Points
    13 724
    Par défaut
    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
    Publication : Concepts en C

    Mon avatar : Glenn Gould

    --------------------------------------------------------------------------
    Une réponse vous a été utile ? Remerciez son auteur en cliquant le pouce vert !

  5. #5
    Membre du Club
    Profil pro
    Inscrit en
    octobre 2011
    Messages
    25
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : octobre 2011
    Messages : 25
    Points : 68
    Points
    68
    Par défaut
    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 :

    Citation Envoyé par C11 (n1570) § 6.5.7 al 5 p 95
    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;

  6. #6
    Membre éclairé

    Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    juillet 2010
    Messages
    355
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : Industrie

    Informations forums :
    Inscription : juillet 2010
    Messages : 355
    Points : 778
    Points
    778
    Par défaut
    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?

  7. #7
    Membre éclairé
    Profil pro
    Inscrit en
    septembre 2009
    Messages
    1 703
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2009
    Messages : 1 703
    Points : 850
    Points
    850
    Par défaut
    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

Discussions similaires

  1. Réponses: 8
    Dernier message: 22/11/2011, 16h13
  2. Réponses: 0
    Dernier message: 09/06/2011, 13h37
  3. Réponses: 3
    Dernier message: 10/05/2011, 21h41
  4. Remplacer les sous requêtes grâce aux jointures
    Par onizuka_metal dans le forum Requêtes
    Réponses: 6
    Dernier message: 25/09/2009, 17h48
  5. [SimpleXML] Trier les résultats grâce aux attributs
    Par Zaki_SDwin dans le forum Bibliothèques et frameworks
    Réponses: 5
    Dernier message: 26/09/2008, 01h48

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo