Catégorie : Dilemme

Article original : Duff’s device in 2021 | Belay the C++ (belaycpp.com)
Traductrice : Chloé Lourseyre

Cette année à la CppCon, Walter E. Brown a donné un Lightning Talk (un conférence-éclair) sur l’appareil de Duff (je mettrais un lien YouTube vers la vidéo correspondante dès qu’elle sortira).

L’appareil de Duff est un modèle assez vieux et je me suis dit : « À quel point est-il encore utile en 2021, avec le C++20 et tout ? ».

Ainsi naquit cet article

C’est quoi, l’appareil de Duff ?

Ce que j’appelle l’appareil de Duff renvoie à ce qu’on appelle Duff’s device en anglais. Ce mécanisme a été nommé d’après son créateur Tom Duff. Il correspond à une méthode de déroulage de boucle manuelle.

Le déroulage de boucle (ou loop unrolling) est une technique d’optimisation visant à réduire de temps d’exécution d’une boucle en « déroulant » manuellement son contenu afin de réduire le nombre de contrôle de boucle effectués. Le tout se fait au détriment de la taille du binaire généré.

Le principe de l’appareil de Duff est d’exécuter plusieurs fois le contenu de la boucle à la suite (généralement entre quatre et huit fois) au lieu d’une seule fois, ce qui permet de ne faire le contrôle de boucle qu’une fois toutes les quatre à huit computations.

Donc au lieu de faire ceci:

void execute_loop(int & data, const size_t loop_size)
{
    for (int i = 0 ; i < loop_size ; ++i)
    {
        computation(data);
    }
}

On cherche à faire quelque chose ressemblant un peu à cela:

void execute_loop(int & data, const size_t loop_size)
{
    for (int i = 0 ; i < loop_size/4 ; ++i)
    {
        computation(data);
        computation(data);
        computation(data);
        computation(data);
    }
}

Cependant, vous l’aurez peut-être remarqué, mais si loop_size n’est pas un multiple de 4, alors le nombre de computation() effectué n’est pas le bon. Pour palier à ce problème, l’appareil de Duff utilise la capacité du switch à « passer à travers » (ce qu’on appelle le switch fallthrough et qui ne peut pas avoir de traduction satisfaisante). Concrètement, ça ressemble à ceci:

void execute_loop(int & data, const size_t loop_size)
{
    size_t i = 0;
    switch(loop_size%4)
    {
        do{
            case 0: computation(data);
            case 3: computation(data);
            case 2: computation(data);
            case 1: computation(data);
            ++i;
        } while (i < (loop_size+3)/4);
    }
}

Ce code est un peu plus étrange que ce que vous avez l’habitude de voir, alors laissez-moi l’expliquer.

Au début de la fonction, on entre dans le switch et on vérifie alors le modulo de loop_size. En fonction du résultat, on arrive dans un des quatre case. Puis, grâce à ce « passage à travers », on fait un nombre de computation() différent en fonction du case dans lequel on est tombés. Cela permet de rectifier le problème de divisibilité par 4 qu’on a rencontré juste avant.

Ensuite, on arrive sur le while. Comme techniquement le switch nous a envoyé dans une boucle do while(), alors l’exécution retourne au do et on continue la boucle normalement.

Après la première occurrence, les labels de type case N sont ignorés, donc ça fait comme si on passait à travers à chaque fois.

Vous pouvez vérifier les calculs : cela fait qu’on réalise exactement loop_size computations.

Est-ce que l’appareil de Duff en vaut la peine ?

L’appareil de Duff vient d’une autre époque, d’une autre ère (et même d’un autre langage), donc ma première réaction a été : « Ce genre de mécanisme est probablement contre-productif, autant laisser le compilateur optimiser lui-même les boucles. »

Mais je voulais une preuve tangible que cette approche était la bonne. Quoi de mieux que quelques benchmarks pour obtenir une telle preuve ?

Benchmarks

Pour faire ce benchmark, j’ai utilisé le code suivant : Quick C++ Benchmarks – Duff’s device (quick-bench.com).

Voici les résultats¹ :

Dans cette situation, on peut voir que la différence est insignifiante (3.5% sur un benchmark c’est peu, dans un code intégré cette différence serait diluée dans le reste du code). De plus, le côté duquel penche la balance varie d’un compilateur et d’une option à l’autre.

Après cela, j’ai utilisé une version plus simple du computation(), plus facile à optimiser pour le compilateur.

Cela donne ce résultat :

C’est intéressant, car on observe que Clang peut, de lui-même, grandement optimiser la boucle simple sans arriver à optimiser de la même manière l’appareil de Duff (avec les options -O2 et -O3 la boucle simple est 30 000 fois plus rapide ; c’est parce que la boucle est entièrement optimisée en une simple addition, mais considère que l’appareil de Duff est trop complexe pour être optimisé de la sorte).

D’un autre côté, GCC n’arrive pas à réduire la boucle simple plus qu’il ne réduit l’appareil de Duff. Même si à -O1 la boucle simple est plus de cinq fois plus rapide, à -O3 c’est l’appareil de Duff qui est 23% meilleur (ce qui est significatif)².

Lisibilité et sémantique

Au premier coup d’œil, l’appareil de Duff est une congruence très difficile à appréhender. Cependant, c’est aujourd’hui un mécanisme assez connu (surtout parmi les plus vieux développeur·se·s C et C++). De plus, il a un déjà un nom et qu’il possède une page Wikipedia qui explique son fonctionnement.

Tant que vous l’identifiez comme tel dans les commentaires de votre code, je pense qu’il n’est pas malsain de l’utiliser, mais si vos confrères et consœurs ne le connaissent pas (au pire, vous pouvez mettre un lien vers sa page Wikipedia directement dans les commentaires !).

Chercher un cas plus spécifique

Principe

Le déroulage de boucle cherche spécifiquement à réduire le nombre d’évaluation de la structure de contrôle de votre boucle. Du coup, j’ai construit un cas spécifique où ce contrôle est particulièrement lourd à évaluer, pour voir si ça permet à l’appareil de Duff d’avoir un impact significatif.

Du coup, à la place d’utiliser un entier comme index de boucle, j’ai utilisé cette classe :

struct MyIndex
{
  int index;
   
  MyIndex(int base_index): index(base_index) {}
   
  MyIndex& operator++() 
  {  
    if (index%2 == 0)
      index+=3;
    else
      index-=1;
    return *this;
  }
 
  bool operator<(const MyIndex& rhs)
  {
    if (index%3 == 0)
      return index < rhs.index;
    else if (index%3 == 1)
      return index < rhs.index+2;
    else
      return index < rhs.index+6;
  }
};

À chaque fois qu’on incrémente ou compare MyIndex, on évalue un modulo (qui est une opération arithmétique assez lente).

Et j’ai fait des benchmarks dessus.

Benchmarks

J’ai donc utilisé le code suivant : Quick C++ Benchmarks – Duff’s device with strange index (quick-bench.com).

Cela m’a donné les résultats suivants :

Ici, on peut voir que l’appareil de Duff est meilleur que la boucle simple dans les plus basses couches d’optimisation, mais jamais significativement à -O3. Cela signifie que le compilateur réussit à optimiser la boucle simple aussi bien que l’appareil de Duff l’est. C’est significativement différent des résultats précédents.

Pourquoi les résultats sont aussi inconsistants ?

Les benchmarks montrent des résultats très peu consistants : par exemple, comment cela se fait-il que dans d’une computation() simple, avec GCC et -O1, la boucle simple est plus de cinq fois plus rapide que l’appareil de Duff, alors qu’avec -O3, c’est l’appareil de Duff qui est 23% meilleur ? Comment se fait-il que pour le même code, Clang montre des résultats totalement différents de GCC et montre que la boucle simple est trente mille fois plus rapide avec -O2 et -O3 ?

C’est parce que chaque compilateur a ses propres manières d’optimiser ces genres de boucles à différents niveaux d’optimisation.

Si vous voulez regarder cela de plus près, vous pouvez comparer le code assembleur généré par chaque compilateur, comme dans cet exemple : Compiler Explorer (godbolt.org) où les versions Clang et GCC (à -O3) sont mises côte-à-côte.

J’aurais beaucoup aimé détailler tout cela ici, mais il faudrait largement plus d’un article dédié pour tous les couvrir. Si vous, lecteur·rice, voulez prendre le temps de le faire et effectuer ces analyses vous-même, je serai plus que contente de publier vos résultats sur ce blog (vous pouvez me contacter ici).

Conclusion

Voici un résumé des résultats, qui indique pour chaque implémentation quel appareil est meilleur :

Comment interpréter ces résultats ?

Premièrement, quand on a une computation complexe et une structure de contrôle triviale, il n’y a pas de différence significative entre les deux.

Deuxièmement, quand la computation est triviale, c’est plus souvent la boucle simple qui l’emporte.

Troisièmement, conformément à nos éventuelles attentes, l’appareil de Duff est meilleur dans le cas d’une computation triviale mais d’un contrôle de boucle complexe.

Et pour finir, les résultats vont presque toujours dépendre de votre implémentation. En faisant mes recherches pour cet article, j’ai testé différentes implémentations de l’appareil de Duff et je me suis souvent rendue compte que la plus petite modification dans le code pouvait renverser les résultats des benchmarks.

Ce que je veux dire, c’est que l’appareil de Duff vaut, encore aujourd’hui, la peine d’être pris en considération³, mais vous devrez faire vos propres benchmarks pour vous assurer que, dans votre cas spécifique, il est effectivement plus efficace.

Merci de votre attention et à la semaine prochaine !

ticle original : Duff’s device in 2021 | Belay the C++ (belaycpp.com)
Traductrice : Chloé Lourseyre

Addendum

Notes

1. Le « cpu_time » indiqué est une unité abstraite de mesure, affichée par Quick-bench. Elle n’a par elle-même pas de sens, elle sert juste à être comparée à elle-même dans les différentes implémentations benchmarkées.
2. Ces résultats dépendent aussi de l’implémentation de chaque compute_*(). Par exemple, si vous évaluez (loop_size+3/4) à chaque passage de boucle au lieu de la mettre dans une constante, les résultats sous GCC vont être très différent et l’appareil de Duff ne sera plus significativement meilleur avec -O3.
3. J’écris cette note juste pour vous rappeler une règle triviale : l’optimisation de temps d’exécution n’a de sens que si votre code est, en terme de temps d’exécution, particulièrement sensible. Si votre code n’est pas un goulot d’étranglement, vous ne devriez même pas considérer utiliser l’appareil de Duff. Restez simples et n’oubliez pas la règles des 80-20.

Article original : Pragma: once or twice? | Belay the C++ (belaycpp.com)
Traductrice : Chloé Lourseyre

Contexte

Les header guards

Les header guards (littéralement : protections de header) sont une méthode très répandue pour protéger les fichiers header des inclusions multiples, et ainsi de ne pas avoir plusieurs fois la même définition de variable, fonction ou classe.

Normalement, tous les développeurs C++ se sont vus enseigner cette méthode.

En voici un exemple :

#ifndef HEADER_FOOBAR
#define HEADER_FOOBAR

class FooBar
{
    // ...
};

#endif // HEADER_FOOBAR

Pour ceux qui ne sont pas familiers avec son fonctionnement, voici ce qui se passe : la première fois que le fichier est inclus, la macro HEADER_FOOBAR n est pas définie. Nous entrons donc dans la directive de contrôle #ifndef. Dedans, on définit la macro HEADER_FOOBAR et la classe FooBar. Plus tard, si on inclut de nouveau ce fichier, puisque la macro HEADER_FOOBAR est désormais définie, on ne rentre pas dans le #ifndef, du coup la classe FooBar n’est pas redéfinie.

#pragma once

#pragma est une directive de précompilation qui prodigue des informations additionnelles au compilateur, au-delà de ce que fournit déjà le langage lui-même.

Tout compilateur est libre d’interpréter les directives #pragma comme il l’entend. Cependant, au fil des années, certaines directives ont acquis plus de popularité que les autres et sont maintenant presque des standards (comme #pragma once, qui est le sujet de cet article, ou encore #pragma pack).

#pragma once est une directive qui indique au compilateur d’inclure le fichier où elle est présente une seule fois. C’est au compilateur de gérer comment il fait ça.

Du coup, instinctivement, on pourrait se dire que #pragma once fait le même travail qu’un header guard, mais en mieux puisqu’il fait ça en une ligne au lieu de trois, et sans avoir à réfléchir à un nom de macro.

Aujourd’hui ?

Autrefois, #pragma once n’était pas implémentée sur tous les compilateurs, elle était donc moins portable que les header guards.

Mais aujourd’hui, en C++, il n’y a (à ma connaissance) aucun compilateur qui ne l’implémente pas.

Donc pourquoi continuer à utiliser les header guards ? Réponse : à cause du problème que je vais détailler dans la section suivante.

Un problème bizarre avec #pragma once

La problématique que je m’apprête à décrire ne peut pas arriver avec des header guards, ce qui rend #pragma once particulièrement problématique.

Disons, par exemple, que votre fichier header est dupliqué pour une raison qui vous échappe. Cela peut être parce que:

• Vous avez raté un merge, et votre gestionnaire de version a gardé une version de chaque fichier.
• Votre gestionnaire de version a mal géré le déplacement d’un fichier.
• Votre système de fichier possède plusieurs points de montage sur le même disque, ce qui fait que chaque fichier peut-être accéder par deux chemins différents, ce que le compilateur comprend comme étant deux fichiers différents.
• Quelqu’un a copié-collé un des fichiers du projet pour son usage personnel à un autre endroit du projet, sans renommer quoique ce soit (c’est très malpoli, mais ça peut arriver).

(notez que j’ai déjà rencontré chacun de ces problèmes sur des projets réels.)

Quand ce genre de cas de figure survient, les #pragma once et les header guards ne se comportent pas de manière identique:

• Comme les macros qui protègent les headers dupliqués ont le même nom, les header guards fonctionnent parfaitement bien et un seul des fichiers dupliqués est inclus.
• Comme le FS indique qu’il s’agit de fichiers différents, le #pragma once protège chaque duplicata indépendamment, ce qui mène fatalement à une collision de nom.

Des problèmes avec les header guards ?

Les header guards on des problèmes qui leur sont spécifiques également. Par exemple, s’il y a une typographie dans la macro de protection, alors le header guard ne fonctionnera pas. De plus, si les conventions de nom sont mal formulées, certains header guards peuvent avoir le même nom (alors qu’ils protègent des fichiers différents).

Cependant, éviter ces deux problèmes est trivial (les typos sont faciles à voir et si vous avez une convention de nommage correcte, tout ira bien).

Avec un gros avantage !

Il existe aussi un avantage non négligeable aux header guards dans le cadre d une stratégie de test.

Disons que vous voulez tester la classe Foo (dans Foo.h) qui utilise la classe Bar (dans Bar.h). Mais, pour des raisons de test, vous voulez bouchonner Bar.

Une possibilité que vous permet les header guards est de créer votre propre bouchon de Bar (dans le fichier BarMock.h). Si le bouchon utilise les mêmes header guards que l’original, alors vous pouvez inclure BarMock.h puis Foo.h sans que le header Bar.h ne soit inclus (puisque les protections ont déjà été levée dans BarMock.h).

Du coup, dois-je utiliser #pragma once ou des header guards?

Cette question dont il est un peu complexe de répondre. Voici les possibilités qui s’offrent à vous :

• #pragma once est non standard et cause des problèmes majeurs quand vous tombez dans un environnement dégradé.
• Les header guards peuvent causer des problèmes si elles ne sont pas utilisées correctement.

D’après moi, les directives #pragma sont à éviter dès que possible. Si, en pratique, elles fonctionnent, elles ne sont pas formellement standards.

Cher C++20, quid des Modules ?

Les Modules, une des « big four » fonctionnalités du C++20, change notre approche du processus de build des projets. À la place d’avoir des fichiers source et header, on peut maintenant avoir des fichiers module. Ils dépassent complètement les restrictions des headers, augmentent la vitesse de compilation, réduisent les violations de la règle de One-Time-Definition et, surtout, permettent de se dispenser de directives de préprocesseur.

Grâce aux modules, on peut dire que les dilemmes de #pragma once et des header guards sont de l’histoire ancienne.

Pour en apprendre plus sur les module, allez-voir les articles suivants :

• Modules (since C++20) – cppreference.com
• C++20: The Advantages of Modules – ModernesCpp.com

En conclusion

Cet article, parlant surtout des directives #pragma et des header guards concerne les projets qui sont sur une version antérieure au C++20. Si vous hésitez encore entre les #pragma once et les header guards, peut-être devriez-vous passer au C++20 ?

Si vous ne pouvez pas migrer aussi facilement que ça (ce qui est le cas de la plupart des projets industriels), alors choisissez méticuleusement entre #pragma once et les header guards,

Merci de votre attention et à la prochaine!

Article original : Pragma: once or twice? | Belay the C++ (belaycpp.com)
Traductrice : Chloé Lourseyre

Addendum

Sources

• Pragmas (The C Preprocessor) (gnu.org)
• Modules (since C++20) – cppreference.com
• C++20: The Advantages of Modules – ModernesCpp.com
• C++20: A Simple math Module – ModernesCpp.com