Journal Barrières mémoire et buffers circulaires - Un résultat inattendu

Sommaire

• Un peu de contexte
• Lock-free, qu'est-ce que c'est ?
• Première optimisation - Se débarrasser de la vilaine division
• Deuxième optimisation - Éviter le faux partage
• Troisième optimisation - Barrières mémoires - Dans le vif du sujet

Chère lectrice, cher lecteur,

Est-ce que tu saisis le concept de barrière mémoire ? Si oui, c'est très bien, parce que moi, pas vraiment. C'est pour cela que je vais t'expliquer jusqu'à ce que je comprenne.

Un peu de contexte

J'ai du écrire mon propre buffer circulaire lock-free en C++. C'est plutôt fun, pas le genre de chose que l'on fait tous les jours, et c'est pas franchement compliqué : un tableau, deux index qui pointent vers la prochaine case où écrire et la prochaine case où lire, un peu de logique pour éviter de se marcher dessus, et basta.

Pourquoi ne pas utiliser l'implémentation de quelqu'un d'autre, me diras-tu. En particulier, ce bon vieux MoodyCamel fait du très bon travail, et je l'utilise déjà à plusieurs endroits. Alors, sans rentrer dans les détails sordides, c'est dû à un objet assez particulier que je dois maintenir dans le buffer, qui est couteux à copier, et pour lequel la sémantique habituelle de push / pop fonctionne mal.

Je me suis lancé, en m'inspirant de plusieurs sources j'ai implémenté mon buffer et ajouté quelques optimisations afin que ça aille vite, aidé de quelques benchmarks. Les résultats ont été assez surprenants.

Lock-free, qu'est-ce que c'est ?

Je veux que mon buffer, qui représente en fait une file de messages, puisse avoir un producteur et un consommateur qui tournent depuis des threads différents : en gros, mon producteur lit ce qu'il trouve sur le réseau, l'ajoute à la file. Le consommateur lit depuis la file, et écrit sur le disque (il y a des transformations en chemin, mais conceptuellement, c'est ça). Pour éviter les problèmes, il faut protéger les variables partagées, en l’occurrence mes index d'écriture et de lecture, par des routines de synchronisation. Les plus simples sont les mutex, mais ceux-ci peuvent être couteux : en effet, tenter d'acquérir un mutex déjà possédé par un autre thread, et on se prend un appel système qui arrête l'exécution, et laisse à l'ordonnanceur du noyau la tâche de nous remettre sur les rails quand le mutex a été relâché. L'on peut regarder du côté des spinlocks, qui tentent d’acquérir un mutex en boucle, mais il existe une technique encore plus intéressante, le lock free.

Cette technique s'appuie sur des routines atomiques plutôt que des mutex, avec comme principe de ne jamais se faire sortir par l'ordonnanceur. Toutes les structures de données ne peuvent pas nécessairement être implémentées en lock-free (c'était d'ailleurs un sujet phare de la recherche en informatique, même si on en entend beaucoup moins parler), mais dans mon cas, la file de messages avec un seul producteur et un seul consommateur est justement assez trivial à faire en lock-free : il suffit de transformer nos index de lecture et d'écriture en entiers atomiques, std::atomic en C++, et basta, ça marche.

Première optimisation - Se débarrasser de la vilaine division

Ce n'est pas une optimisation liée à la programmation concurrente, mais c'est intéressant quand même, alors j'en parle.

Nous avons affaire à un buffer circulaire, ce qui veut dire qu'il faut à chaque incrément de notre index de lecture ou d'écriture se demander si l'on est arrivé en bout de buffer pour repartir au début. Et c'est quelque chose de plutôt cher : soit on utilise une condition, et c'est cher, soit on utilise une division modulaire, et c'est cher aussi.

Le truc, c'est que ma dernière déclaration n'est pas complètement vraie : le modulo par un entier quelconque est effectivement cher, mais il existe des entiers pour lesquels c'est très efficace : les puissances de 2. En effet, le modulo de la divison d'une puissance de 2, c'est le masque binaire de l'entier inférieur, de la même manière que le modulo d'une puissance de 10 est trivialement calculable en gardant simplement le nombre de chiffres correspondant à la puissance. Autrement dit, à l'initialisation de ma file, je peux faire ceci:

• Je détermine la taille réelle de ma file comme étant l'arrondi à la puissance de 2 supérieure (std::bit_ceil le fait gentiment)
• Je calcule un masque comme étant la taille de la queue moins 1
• J'incrémente mes index comme ceci: index = (index + 1) & masque

L'on obtient des performances améliorées de 10 à 20% par rapport à une division modulaire classique, et de quelques pourcents avec un opérateur ternaire (la prédiction de branche est quand même rudement efficace).

Deuxième optimisation - Éviter le faux partage

Nos deux index atomiques sont indépendants l'un de l'autre. Mais comme ils sont physiquement proches dans la mémoire, il est probable qu'ils se retrouvent à partager la même ligne de cache CPU. Lorsque l'un est modifié, et que sa nouvelle valeur est passée à la mémoire principale et va invalider les caches des autres CPU, il en sera de même pour l'autre, même si ce n'est pas nécessaire, et cela induit une baisse de performances. Par conséquent, il est pertinent de les séparer suffisamment. Heureusement, dans sa grande bonté, le C++ nous fournit des directives pour aligner nos attributs. L'on déclarera donc ainsi les attributs dans notre classe:

alignas(std::hardware_destructive_interference_size) std::atomic<size_t> _lecture;
alignas(std::hardware_destructive_interference_size) std::atomic<size_t> _ecriture;

Le bénéfice ici est limité, quelques pourcents, parce que les deux threads ont finalement besoin d'accéder très souvent aux deux atomiques en même temps. Dans d'autres cas, l'amélioration peut être bien plus élevée.

Troisième optimisation - Barrières mémoires - Dans le vif du sujet

C'est là que ça se complique. On va y aller doucement.

Les primitives de synchronisation comme les mutex et les atomic ne se contentent pas de prévenir un accès concurrent à une zone mémoire et à faire un flush des caches - Elles empêchent également au compilateur et au CPU de ré-ordonner les instructions autour de la primitive. Cela s'appelle une barrière mémoire, et il s'agit donc à la fois d'une instruction CPU qui prévient celui-ci qu'il doit accéder à la mémoire de manière plus stricte, et une routine qui empêche le compilateur de trop optimiser le code. En effet, le compilo est libre de réordonner les instructions à sa sauce afin d'optimiser par exemple la vectorisation ou le pipeline d'instructions. Nous parlerons principalement de l'ordre des instructions telles que définies par le compilateur, mais gardons à l'esprit que cela s'applique également au niveau du micro-code au sein du CPU.

Prenons le programme suivant:

int a = 0;
int b = 0;
for (int i = 0; i < 20; ++i)
{
  ++a;
  ++b;
}

Si un autre thread lit en permanence les valeurs a et b, on peut s'attendre à les voir s'incrémenter au fur et à mesure, et à a d'être systématiquement 0 ou 1 de plus que b. Sauf qu'en l'absence de primitives de synchronisation et donc de barrières mémoire, le compilo peut décider d'inverser les incréments, ou d'incrémenter d'abord a jusqu'à 20, puis b jusqu'à 20, ou encore d'assigner directement la valeur 20 à a et b. Une optimisation invisible pour le thread principal devient très visible et peut violer des invariants dans un thread différent. Mais si a et b sont atomiques, alors les barrières mémoires émises vont empêcher l'optimisation, et un thread séparé verrait effectivement a et b soit à la même valeur, soit avec a valant 1 de plus, en fonction de l'endroit où était le thread principal lorsque le thread secondaire a regardé.

Super pour la cohérence des données, mais nettement moins super pour la performance. Sauf que… Une barrière mémoire par défaut empêche de réordonner les instructions dans les deux sens : celles qui sont avant restent avant, celles qui sont après restent après. Et bien souvent, on peut relâcher certaines de ces contraintes. On parle typiquement d'acquérir la mémoire quand on veut éviter que les instructions qui sont après la barrière puissent être exécutées avant, et de la relâcher lorsque l'on veut éviter que les instructions qui sont avant la barrière ne puissent passer après. L'on peut même complètement relaxer l'ordre, s'assurant de l'atomicité de l'opération mais permettant de réordonner les instructions dans tous les sens.

Mais pourquoi donc? Voyons un exemple. Prenons ce programme:

std::atomic<bool> regarde = false;
int valeur = 0;

// Thread 1
valeur = 1
regarde = true;
valeur = 2

// Thread 2
while(!regarde) {}
print(valeur);

On peut voir que ce programme affichera 1 ou 2, mais jamais 0. Maintenant, regardons le moment où l'on met l'atomique "regarde" à vrai. Si l'on autorise les instructions qui sont avant à passer après, l'on change la sémantique du programme : l'on pourra voir 0, 1 ou 2. On ne peut pas donc permettre cela. En revanche, si l'on fait remonter l'instruction qui est après, valeur sera à 2 avant le changement de l'atomique, et le programme n'affichera que 2 : ce n'est pas un changement de sémantique, puisque cela aura été possible de toutes façons. Par conséquent, l'on peut changer notre assignation comme cela:

regarde.store(true, std::memory_order_release)

Et l'on donne des clés au compilo pour optimiser le code de manière plus poussée.

Dans mon code, j'incrémente l'index d'écriture ainsi:

ecriture.store((ecriture.load(std::memory_order_relaxed) + 1) & masque, std::memory_order_release);

• Le load se fait en std::memory_order_relaxed : en effet, aucun autre thread que le producteur ne modifie cet atomic. On a donc pas besoin de barrière mémoire.
• En revanche, le store se fait avec un memory order release - les instructions avant le store ne doivent pas passer après

Et là, pour le coup, la performance explose - Dans certains benchmarks, j'ai mesuré une augmentation de performance d'un facteur 10 ! Sur d'autres benchmarks, on se contente de 30% à 50% d'augmentation. C'est considérable, et je ne m'y attendais pas du tout.

L'approche qui fonctionne semble donc être:
* Utiliser "load" avec std::memory_order_acquire si un autre thread peut écrire la valeur, et std::memory_order_relaxed sinon
* Utiliser "store" avec std::memory_order_release

Et admirer les perfs qui s'envolent.