L’appareil de Duff en 2021

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.