Apprendre à programmer avec C++14 et C++17 pour des codes plus rapides et performants

Exemples d'applications

Dan Levin

Traducteur

Sabine CHIESA

Ce tutoriel traite des standards modernes du C++, et en particulier des nouveautés du C++14. À travers ce tutoriel, nous allons apprendre à rendre nos codes plus rapides et performants en utilisant C++14 et C++17.

Commentez

- Titre : Apprendre à programmer avec C++14 et C++17 pour des codes plus rapides et performants

- Auteur : Dan Levin

- Traducteur : Sabine CHIESA

- Parution : 2 septembre 2016

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2016 Dan Levin. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Introduction

- II. Les transformées de Fourier rapides que l'on peut encore accélérer

- II-A. Exemple 1 : Spécialisation

- II-A-1. La fonction cswitch

- II-B. SIMD et C++

- III. Exemples complémentaires

- III-A. counter

- III-B. sequence

- IV. Conclusion

- V. Remerciements

I - Introduction

L'écriture de codes performants est toujours une tâche difficile. L'application directe des algorithmes théoriques « purs » n'est pas toujours suffisante dans les architectures du monde réel.

Lorsqu'on a commencé à améliorer la rapidité de ces algorithmes purs, on se trouve rapidement confronté à un dilemme : certaines implémentations s'avèrent relativement rapides sur une architecture, mais effroyablement lentes sur d'autres. Dans le même temps, dans certains contextes, une nouvelle implémentation va dépasser les performances de la première, mais perdre de la vitesse sur les autres calculs.

De nombreuses optimisations, grandes et petites, pour chacune des architectures prises en charge peuvent rapidement faire gonfler notre code et nous faire perdre du temps. Souvent, nous sommes donc ramenés à choisir entre deux options : un beau code trop lent, ou bien un code rapide mais illisible.

On peut donc se demander ce qu'il en est des optimisations des compilateurs modernes ?

De nos jours, les compilateurs font beaucoup de choses, mais clairement pas tout. Par exemple, les algorithmes décrits dans cet article ne peuvent pas vraiment être optimisés ni vectorisés du fait de leur complexité.

Dans ce tutoriel, je montre cependant comment le C++17 et le C++14 peuvent aider à obtenir un code rapide, condensé, et bien structuré.

II - Les transformées de Fourier rapides que l'on peut encore accélérer

La transformée de Fourier rapide (FFT) est un algorithme au cœur du traitement de signal numérique et a de nombreuses applications dans beaucoup d'autres domaines.

En quelques mots, la FFT fait passer les données (le signal) du domaine temporel (chaque échantillon représente le signal à un temps donné) au domaine des fréquences (chaque échantillon représente la puissance d'une fréquence donnée).

La performance d'une implémentation de transformée de Fourier impacte souvent sur la performance globale d'une application, du fait du grand nombre de transformations effectuées. Dans le KFR Framework, certaines parties de l'implémentation de la FFT ont été grandement améliorées par l'utilisation du C++14, comme illustré en Figure 1.

Note du traducteur : La figure 1 ci-dessous illustre une étude de cas de vitesse pour une FFT par Dan Levin sous GitHub.

Figure 1 : Résultats d'une étude de cas pour une FFT de taille comprise entre 1024 et 16 777 216.

II-A - Exemple 1 : Spécialisation

Pour atteindre sa vitesse maximale, la FFT doit être spécialisée quand on l'applique à des vecteurs de petite taille, par exemple 2, 4, 8, 16, 32, 64, 128, 256. L'exemple suivant montre comment sélectionner une taille, connue uniquement à l'exécution (au runtime).

Version C++14 (source code on GitHub) :

1. cswitch(csizes<1, 2, 3, 4, 5, 6, 7, 8>, log2n,

2. [&](auto log2n) { // si log2n a été trouvé dans la liste, créer une étape spécialisée

3. add_stage<internal::fft_specialization_t<T, val_of(log2n), false>::template type>(size, type);

4. },

5. [&]() { // si log2n n'a pas été trouvé dans la liste, créer une étape générique

6. // l'étape générique a deux spécialisations pour les valeurs paires et impaires de log2n, donc on sélectionne la bonne

7. cswitch(cfalse_true, is_even(log2n), [&](auto is_even) {

8. make_fft(size, type, is_even, ctrue);

9. add_stage<internal::fft_reorder_stage_impl_t<T, val_of(is_even)>::template type>(size, type);

10. });

11. });

Ci-dessus, j'utilise cswitch, cif et d'autres fonctions de la bibliothèque CoMeta C++14 Metaprogramming library (licence MIT), écrit lors du développement du KFR Framework.

Le code précédent est équivalent à ce code, écrit en C++03 ou bien C++11 :

1. switch(log2n)

2. {

3. case 1:

4. add_stage<internal::fft_specialization_t<T, 1, false>::template type>(size, type);

5. break;

6. case 2:

7. add_stage<internal::fft_specialization_t<T, 2, false>::template type>(size, type);

8. break;

9. case 3:

10. add_stage<internal::fft_specialization_t<T, 3, false>::template type>(size, type);

11. break;

12. case 4:

13. add_stage<internal::fft_specialization_t<T, 4, false>::template type>(size, type);

14. break;

15. case 5:

16. add_stage<internal::fft_specialization_t<T, 5, false>::template type>(size, type);

17. break;

18. case 6:

19. add_stage<internal::fft_specialization_t<T, 6, false>::template type>(size, type);

20. break;

21. case 7:

22. add_stage<internal::fft_specialization_t<T, 7, false>::template type>(size, type);

23. break;

24. case 8:

25. add_stage<internal::fft_specialization_t<T, 8, false>::template type>(size, type);

26. break;

27. default:

28. if(is_even(log2n))

29. {

30. make_fft(size, type, cbool<true>, ctrue);

31. add_stage<internal::fft_reorder_stage_impl_t<T, true>::template type>(size, type);

32. }

33. else

34. {

35. make_fft(size, type, cbool<false>, ctrue);

36. add_stage<internal::fft_reorder_stage_impl_t<T, false>::template type>(size, type);

37. }

38. }

Une autre façon d'obtenir ce résultat avec C++11 consiste à extraire le code vers un nouveau foncteur, rendre générique l'opérateur d'appel (operator()) de ce nouveau foncteur (afin de pouvoir accéder aux valeurs pendant la compilation), et lui passer en entrée toutes les variables locales. Mais ceci introduit une complexité indésirable dans le code et dans tous les cas n'est pas plus aisé que l'utilisation de cswitch en C++14.

II-A-1 - La fonction cswitch

Cette fonction est utilisée lorsqu'une valeur connue en cours d'exécution doit apparaître dans une liste d'arguments d'un template. Il n'y a qu'une seule façon d'y arriver en interne : il faut comparer la valeur renvoyée par le code à chacune des valeurs de la liste prédéfinie, et appeler l'instance de template associée. Mais le C++14 nous aide bien dans cette situation et nous n'avons plus à écrire à la main chacune des comparaisons. Concrètement, la lambda générique est la clef qui fait fonctionner le code.

Ci-dessous le code de cswitch (source GitHub) :

1. template <typename T, T... vs, typename U, typename Function, typename Fallback = DoNothing>

2. void cswitch(cvals_t<T, vs...>, const U& value, Function&& function, Fallback&& fallback = Fallback())

3. {

4. bool result = false;

5. swallow{ (result = result || ((vs == value) ? (function(cval<T, vs>), void(), true) : false), void(), 0)... };

6. if(!result)

7. fallback();

8. }

Comme on peut le constater, la fonction fallback est optionnelle.

Lors de l'instanciation, le code sera développé comme une séquence de comparaisons.

1. bool result = false;

2. result = result || ((vs == value) ? (function(cval<T, vs>), void(), true) : false);

3. result = result || ((vs == value) ? (function(cval<T, vs>), void(), true) : false);

4. ...

5. result = result || ((vs == value) ? (function(cval<T, vs>), void(), true) : false);

6. if(!result)

7. fallback();

swallow est une structure avec un constructeur qui accepte initializer_list.

La liste d'initialisation est utilisée pour s'assurer que les arguments sont évalués dans l'ordre où ils apparaissent. La version C++17 à venir introduira les fold expressions (expressions repliées) qui peuvent être utilisées pour obtenir le même effet sous une forme plus élégante.

II-B - SIMD et C++

La FFT est constituée de courtes routines appelées papillons qui gagneront fortement à être optimisées en termes d'utilisation des registres SIMD. Le total des spécialisations nécessaires pour un algorithme des FFT est donné par :

1. Deux types de données : float et double, donc on démarre par deux spécialisations.

2. Le code est à optimiser pour SSE.x et AVX.x qui occupent des tailles de registre SIMD différentes : 4.

3. Le x86 possède 8 registres SIMD (même sur les AVX), tandis que le x86-64 en possède 16. En x86-64 on peut doubler la quantité de calculs réalisés en une étape grâce à l'utilisation de deux registres à la place d'un seul.
On ne peut pas décemment laisser passer cette opportunité, ce qui double notre nombre de spécialisations.
On a donc à présent 8 spécialisations.

4. Afin de pouvoir appliquer à la fois les opérations de FFT et leur inverse, en utilisant les mêmes données précalculées (la TF inverse utilise exactement le même algorithme que la TF directe, mais elle fonctionne avec les coefficients conjugués), il nous faut modifier tous nos papillons : 16.

5. L'une des étapes de la FFT multiplie systématiquement les données d'entrées par 1.0, en conséquence, on peut (et on doit, si l'on veut atteindre notre objectif de performance) totalement retirer cette étape de multiplication.
Le nombre de spécialisations devient 32.

6. Les données peuvent être alignées ou pas.
Les accès à des données alignées en utilisant des instructions non alignées seront lents sur les SSE.
Les accès à des données non alignées en utilisant des instructions alignées amèneront toujours à une segfault.
Il en résulte qu'on doit compter sur 48 spécialisations.

Une fois de plus, 48 spécialisations sont ainsi obtenues pour le papillon radix-4. Certaines de ces spécialisations sont redondantes, mais un comptage global des implémentations optimisées nous amène bien au-delà de 20.
En C, nous aurions eu à écrire et maintenir l'ensemble de ces fonctions.

Et si je vous disais que toutes ces spécialisations ont une syntaxe de code unique dans C++14 ? Toutes ces différentiations nécessaires pour atteindre les meilleurs résultats dans chacune des configurations peuvent être passées en tant qu'arguments template.

1. template <size_t width, bool use_br2, bool inverse, bool aligned, typename T>

2. inline void radix4_body(

3. size_t N,                   // dimension du vecteur fft

4. csize_t<width>,             // largeur de la SIMD

5. cfalse_t,

6. cfalse_t,

7. cfalse_t,

8. cbool_t<use_br2>,           // appliquer une permutation par renversement de bits (« bit-reversal »)

9. cbool_t<inverse>,           // vrai dans le cas de la FFT inverse

10. cbool_t<aligned>,           // vrai si on a des accès alignés

11. complex<T>* out,

12. const complex<T>* in,

13. const complex<T>* twiddle)

14. {

15. const size_t N4 = N / 4;

16. cvec<T, width> w1, w2, w3;

18. cvec<T, width> sum02, sum13, diff02, diff13;

20. cvec<T, width> a0, a1, a2, a3;

21. a0    = cread<width, aligned>(in + 0);

22. a2    = cread<width, aligned>(in + N4 * 2);

23. sum02 = a0 + a2;

25. a1    = cread<width, aligned>(in + N4);

26. a3    = cread<width, aligned>(in + N4 * 3);

27. sum13 = a1 + a3;

29. cwrite<width, aligned>(out, sum02 + sum13);

30. w2 = sum02 - sum13;

31. cwrite<width, aligned>(

32. out + N4 * (use_br2 ? 1 : 2),

33. radix4_apply_twiddle(csize<width>, cfalse, cbool<inverse>, w2, cread<width, true>(twiddle + width)));

34. diff02 = a0 - a2;

35. diff13 = a1 - a3;

36. if (inverse)

37. {

38. diff13 = (diff13 ^ broadcast<width * 2, T>(T(), -T()));

39. diff13 = swap<2>(diff13);

40. }

41. else

42. {

43. diff13 = swap<2>(diff13);

44. diff13 = (diff13 ^ broadcast<width * 2, T>(T(), -T()));

45. }

47. w1 = diff02 + diff13;

49. cwrite<width, aligned>(

50. out + N4 * (use_br2 ? 2 : 1),

51. radix4_apply_twiddle(csize<width>, cfalse, cbool<inverse>, w1, cread<width, true>(twiddle + 0)));

52. w3 = diff02 - diff13;

53. cwrite<width, aligned>(out + N4 * 3, radix4_apply_twiddle(csize<width>, cfalse, cbool<inverse>, w3,

54. cread<width, true>(twiddle + width * 2)));

55. }

De plus, le papillon opère sur le type vec<T, width> qui n'affiche plus tous les détails d'implémentation et présente une interface publique unifiée.

C++ possède bien plus d'avantages que le C en termes de réutilisation du code.
Mais C++14 va encore plus loin.

III - Exemples complémentaires

Ces quelques fonctions tirent avantage du C++11 ou bien du C++14.

III-A - counter

Probablement la plus simple des fonctions du KFR Framework.

counter est un générateur, qui renvoie séquentiellement les valeurs à partir de 0 (GitHub).

1. inline auto counter()

2. {

3. return lambda([](cinput_t, size_t index, auto x) {

4. return enumerate(x) + index;

5. });

6. }

cinput_t indique que nous lisons dans une expression et non pas que nous y écrivons. Ce type est utilisé pour faire la distinction entre ce que l'on veut faire lorsqu'un objet implémente des operator() à la fois d'entrée et de sortie.
index prend sa valeur de la variable de boucle for lorsque l'expression template est exécutée.
x contrôle le type du résultat renvoyé par cette fonction.
lambda encapsule la lambda dans un objet-expression.

Sans l'utilisation des lambda génériques, nous aurions à écrire un foncteur avec un operator() générique.

III-B - sequence

Cette fonction renvoie des valeurs données dans une séquence et retourne à son point de départ lorsqu'elle arrive à la fin.

Cette fonction utilise l'initialisation des captures de lambda, la déduction du type de retour pour une fonction normale et les lambda génériques, qui sont tous dans le standard C++14.

1. template <typename... Ts, typename T = common_type<Ts...>>

2. inline auto sequence(const Ts&... list)

3. {

4. return lambda([seq = std::array<T, sizeof...(Ts)>{ list... }](size_t index) {

5. return seq[index % seq.size()];

6. });

7. }

IV - Conclusion

Les standards modernes de C++ sont bien plus que de simples révisions de syntaxe ou bien de nouvelles fonctions et types de variables.

Ils présentent de nombreuses améliorations concrètes, y compris quand il s'agit d'implémenter un logiciel dédié à la haute performance, et aident à gérer explicitement les optimisations et la vectorisation dans le but d'obtenir les performances optimales tout en conservant du code léger.

Avec les standards modernes de C++, les codes peuvent être tout à la fois rapides, beaux, ajustables et maintenables.

V - Remerciements

Note de la traduction : l'article original (en anglais) a été écrit par Dan Levin.

Nous tenons à remercier scsab pour la traduction, JolyLoic pour sa relecture technique, Winjerome pour la mise au gabarit et f-leb pour la relecture orthographique.