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.
# C++ c'est trop gros
Posté par meumeul . Évalué à 9 (+9/-0).
Merci pour ce partage. J'ai codé des choses qui ressemblent il y a quelque temps pour une machine d'acquisition sur laquelle on doit garantir un latence "faible" pendant pas mal de temps.
J'aurais pu largement me simplifier la vie avec ces primitives !
Je me suis retrouvé à jongler avec des entiers 8 bits (volatile) pour 'garantir' l'atomicité au niveau processeur. Un peu galère mais chouette à faire !
# La méthode
Posté par Julien Jorge (site web personnel) . Évalué à 7 (+5/-0). Dernière modification le 03 octobre 2025 à 09:00.
Journal très intéressant, merci :)
Quel genre de benchmark fais-tu et sur quel type de machine ? Perso je n'ai jamais vu de gain ni de perte en jouant avec
std::memory_order
mais je n'ai fait que des benchmarks sur la solution complète, pas de micro benchmark. Sans avoir creusé, je soupçonne que le coût lié aux atomics soit complètement dilué dans le reste (dans mon cas ils interviennent surtout comme gardien pour des sections algorithmiques intenses), à moins que ce ne soit des machines trop puissantes (des trucs avec une centaine de cœurs à 4 GHz répartis sur deux nœuds numa).[^] # Re: La méthode
Posté par Nicolas Boulay (site web personnel) . Évalué à 5 (+2/-0).
Normalement, cela se voit bien sur des machines puissantes car la hiérarchie mémoire est complexe et le moindre "false sharing" coute très chère (imagines une barrière mémoire sur le ring de connexion entre socket).
"La première sécurité est la liberté"
[^] # Re: La méthode
Posté par small_duck (site web personnel) . Évalué à 3 (+1/-0).
Le benchmark le plus remarquable a été celui que j'appelle "la poursuite", on a un thread qui écrit en boucle n éléments à toute blinde, l'autre thread qui lit n éléments en boucle à toute blinde, et on voit quand ils ont terminé tous les deux. Probablement pas représentatif du tout d'un usage normal !
Question machines, on tourne sur le genre de monstre que tu décris - Comme le dit Nicolas, sur ce genre de très grosse machines avec beaucoup de cœurs, on s'attend à ce que les flush coutent beaucoup?
[^] # Re: La méthode
Posté par KaminariNoHime . Évalué à 5 (+5/-0). Dernière modification le 04 octobre 2025 à 21:44.
Le cas de "poursuite" existe réellement. J'ai un client qui doit souhaite détecter des déformations mécaniques de pièces mécaniques. Le système d'acquisition repose sur 6 caméras dont les sorties sont déposées dans un buffer circulaire pour un modèle producteur-consommateur. Et on arrive très rapidement à cette situation de remplissage rapide et dé-remplissage rapide.
On s'attend à ce que les accès mémoires soient sources de bottleneck que ce soit en lecture et écriture. Avec du NUMA, il faut prêter attention à ce que les accès mémoires demandaient par un processeur soit associés avec "ses" barettes de RAM. Dans le cas contraire, il doit aller chercher l'information à l'autre processeur (cas d'une machine à deux sockets ou plus) ou de l'autre ensemble de cores (cas de chiplets ayant un ring pour communiquer) pour obtenir celle-ci, et donc un stall significatif.
# Merci
Posté par reno . Évalué à 8 (+6/-0).
C'est très intéressant comme article, quand on voit pas mal de blog sur Internet qui oublient de stocker les index dans des lignes de caches séparées..
Connais-tu un article qui explique les memory order car là j'avoue que j'ai du mal..
[^] # Re: Merci
Posté par small_duck (site web personnel) . Évalué à 5 (+3/-0).
Je me suis inspiré de la page Wikipedia en anglais sur le sujet, et de la doc C++, assez complète mais touffue.
[^] # Re: Merci
Posté par pushmepullme . Évalué à 2 (+1/-0).
Oui superbe article merci :) Je ne connaissais aucune de ces techniques.
Il me fait me rappeler qu'il n'y a toujours pas de tels conteneurs dans la stdc++. Mais y en aura-t-il un jour ? Il semble y avoir autant de besoins que d'implémentations possibles.
[^] # Re: Merci
Posté par pushmepullme . Évalué à 1 (+0/-0).
Je rappelle l'existence de godbolt pour ceux et celles qui ne connaissent pas. Sans être un expert en assembleur, il peut orienter certaines décisions d'implémentations.
https://godbolt.org/
[^] # Re: Merci
Posté par pulkomandy (site web personnel, Mastodon) . Évalué à 4 (+1/-0).
Il y a des choses dans Boost mais je n'ai pas eu l'occasion de mesurer les performances ou de regarder l'implémentation de près (l'idée d'utiliser une file lockless a été évoquée dans un projet, mais n'a pas été retenue pour d'autrs raisons, avant d'en arriver à ce stade).
[^] # Re: Merci
Posté par reno . Évalué à 2 (+0/-0).
Il y a déjà au moins 4 configurations possible en prenant en compte, les variantes possibles entre écrivain ou lecteur simple/multiples..
# Super intéressant
Posté par ajeandet . Évalué à 5 (+5/-0).
Merci pour l'article détaillé, c'est super intéressant! Le code associé est en ligne?
Sinon dans pour approfondir, je conseille vivement ce talk de la cppcon 2024.
Envoyer un commentaire
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.