atomic_queue
1.0.0
C ++ 14 Files d'attente sans verrouillage -consommateur multipro-producteur basées sur un tampon circulaire et std::atomic .
Conçu dans un objectif pour minimiser la latence entre un fil qui pousse un élément dans une file d'attente et un autre fil qui le fait sortir de la file d'attente.
Il a été développé, testé et comparé sur Linux, mais devrait prendre en charge toutes les plates-formes C ++ 14 qui implémentent std::atomic . Signalé comme compatible avec Windows, mais les intégrations continues hébergées par GitHub sont actuellement configurées uniquement pour la plate-forme x86_64 sur Ubuntu-20.04 et Ubuntu-22.04. Les demandes de traction pour étendre les intégrations continues pour s'exécuter sur d'autres architectures et / ou plates-formes sont les bienvenues.
Lors de la minimisation de la latence, une bonne conception n'est pas lorsqu'il n'y a plus rien à ajouter, mais plutôt quand il n'y a plus rien à supprimer, car ces files d'attente illustrent.
La minimisation de la latence maximise naturellement le débit. La faible latence réciproque est élevée à travers, dans un sens de génie mathématique et pratique idéal. La faible latence est incompatible avec tous les retards et / ou lots, qui détruisent l'ordre des événements mondiaux d'origine (matériel) poussé dans une file d'attente par différents threads. La maximisation du débit, en revanche, peut être effectuée à des dépens de latence en retardant et en regroupant plusieurs mises à jour.
Le principal principe de conception que ces files d'attente suivent est le minimalisme , ce qui se traduit par des choix de conception tels que:
push / pop , aucune référence / pointeur vers les éléments dans la file d'attente ne peut être obtenue.L'impact de chacun de ces petits choix de conception par eux-mêmes est à peine mesurable, mais leur impact total est beaucoup plus élevé qu'une simple somme des impacts des constituants, alias composé ou synergie super-échelle. La synergie émergeant de la combinaison de multiples de ces petits choix de conception ensemble est ce qui permet aux processeurs de fonctionner à leurs capacités de pointe les moins entravés.
Ces choix de conception sont également des limitations:
Les applications à ultra-laté ont besoin de cela et rien de plus. Le minimalisme est payant, voir le débit et les références de latence.
Plusieurs autres conteneurs de filetage bien établis et populaires sont utilisés pour référence dans les repères:
std::mutex - Un bouffon d'anneau de taille fixe avec std::mutex .pthread_spinlock - un bouffère de ring de taille fixe avec pthread_spinlock_t .boost::lockfree::spsc_queue - Une file d'attente à consommation unique sans producteur de Boost Library.boost::lockfree::queue - une file d'attente de consommation multipro-productrice sans verrouillage de la bibliothèque Boost.moodycamel::ConcurrentQueue - une file d'attente de consommation multipro-productrice sans serrure utilisée en mode non bloquant. Cette file d'attente est conçue pour maximiser le débit au détriment de la latence et éviter l'ordre de temps mondial des éléments poussés dans une file d'attente par différents fils. Il n'est pas équivalent à d'autres files d'attente comparées ici à cet égard.moodycamel::ReaderWriterQueue - Une file d'attente de consommation unique sans serrure utilisée en mode non bloquant.xenium::michael_scott_queue - Une file d'attente multi-productrice-productrice sans serrure proposée par Michael et Scott (cette file d'attente est similaire à boost::lockfree::queue qui est également basée sur la même proposition).xenium::ramalhete_queue - Une file d'attente multi-productrice-productrice sans serrure proposée par Ramalhete et Correia.xenium::vyukov_bounded_queue - Une file d'attente multi-productrice-multi-consommation bornée basée sur la version proposée par Vyukov.tbb::spin_mutex - Un bouffon d'anneau à taille fixe verrouillée avec tbb::spin_mutex à partir des blocs de construction Intel.tbb::concurrent_bounded_queue - Fitre éponyme utilisée en mode non bloquant à partir des blocs de construction Intel.Les conteneurs fournis sont des modèles de classe uniquement en tête, aucun bâtiment / installation n'est nécessaire.
git clone https://github.com/max0x7ba/atomic_queue.git
atomic_queue/include (utilisez le chemin complet) sur les chemins d'inclusion de votre système de construction.#include <atomic_queue/atomic_queue.h> dans votre source C ++. vcpkg install atomic-queue
Suivez le tutoriel officiel sur la façon de consommer des packages Conan. Les détails spécifiques à cette bibliothèque sont disponibles dans Conopenter.
Les conteneurs fournis sont des modèles de classe uniquement en tête qui ne nécessitent que #include <atomic_queue/atomic_queue.h> , aucun bâtiment / installation n'est nécessaire.
Le bâtiment est nécessaire pour exécuter les tests et les références.
git clone https://github.com/cameron314/concurrentqueue.git
git clone https://github.com/cameron314/readerwriterqueue.git
git clone https://github.com/mpoeter/xenium.git
git clone https://github.com/max0x7ba/atomic_queue.git
cd atomic_queue
make -r -j4 run_benchmarks
La référence nécessite également une bibliothèque Intel TBB pour être disponible. Il suppose qu'il est installé dans /usr/local/include et /usr/local/lib . S'il est installé ailleurs, vous aimerez peut-être modifier cppflags.tbb et ldlibs.tbb dans Makefile .
AtomicQueue - Un bouffon d'anneau de taille fixe pour les éléments atomiques.OptimistAtomicQueue - Un bouffon d'anneau de taille fixe plus rapide pour les éléments atomiques qui sont occupés lorsqu'ils sont vides ou pleins. Il est AtomicQueue utilisé avec push / pop au lieu de try_push / try_pop .AtomicQueue2 - Un bouffon d'anneau de taille fixe pour les éléments non atomiques.OptimistAtomicQueue2 - Un bouffon d'anneau de taille fixe plus rapide pour les éléments non atomiques qui sont occupés lorsqu'ils sont vides ou pleins. Il est AtomicQueue2 utilisé avec push / pop au lieu de try_push / try_pop . Ces conteneurs ont AtomicQueueB correspondant, OptimistAtomicQueueB , AtomicQueueB2 , OptimistAtomicQueueB2 versions où la taille du tampon est spécifiée comme argument au constructeur.
Le mode totalement commandé est pris en charge. Dans ce mode, les consommateurs reçoivent des messages dans la même commande FIFO, les messages ont été publiés. Ce mode est pris en charge pour les fonctions push et pop , mais pas pour les versions try_ . Sur Intel x86, le mode totalement commandé a 0 coût, en 2019.
Le mode de consommation unique unique est pris en charge. Dans ce mode, aucune instruction de CPU à modernes de lecture atomique coûteuse n'est nécessaire n'est nécessaire, seules les charges et les magasins atomiques les moins chers. Cela améliore considérablement le débit de file d'attente.
Les types d'éléments de file d'attente déplacés sont entièrement pris en charge. Par exemple, une file d'attente de std::unique_ptr<T> serait AtomicQueue2B<std::unique_ptr<T>> ou AtomicQueue2<std::unique_ptr<T>, CAPACITY> .
Les modèles de classe de file d'attente fournissent les fonctions membres suivantes:
try_push - ajoute un élément à la fin de la file d'attente. Retourne false lorsque la file d'attente est pleine.try_pop - supprime un élément de l'avant de la file d'attente. Retourne false lorsque la file d'attente est vide.push (Optimist) - ajoute un élément à la fin de la file d'attente. Les attentes occupées lorsque la file d'attente est pleine. Plus rapide que try_push lorsque la file d'attente n'est pas pleine. FIFO Producer FIFO FIFOT et commande totale.pop (Optimist) - supprime un élément de l'avant de la file d'attente. Les attentes occupées lorsque la file d'attente est vide. Plus rapide que try_pop lorsque la file d'attente n'est pas vide. FIFO FIFO FIFO FIFO et commande totale.was_size - renvoie le nombre d'éléments non consommés pendant l'appel. L'État peut avoir changé au moment où la valeur de retour est examinée.was_empty - Renvoie true si le conteneur était vide pendant l'appel. L'État peut avoir changé au moment où la valeur de retour est examinée.was_full - Renvoie true si le conteneur était plein pendant l'appel. L'État peut avoir changé au moment où la valeur de retour est examinée.capacity - Renvoie le nombre maximum d'éléments que la file d'attente peut éventuellement retenir. Les éléments atomiques sont ceux, pour lesquels std::atomic<T>{T{}}.is_lock_free() Renvoie true , et, lorsque les fonctionnalités C ++ 17 sont disponibles, std::atomic<T>::is_always_lock_free évalue à true au moment de la compilation. En d'autres termes, le CPU peut charger, stocker et comparer et échanger de tels éléments atomiquement nativement. Sur x86-64, ces éléments sont tous les types arithmétiques et pointeurs standard C ++.
Les files d'attente pour les éléments atomiques réservent une valeur pour servir de marqueur d'élément vide NIL , sa valeur par défaut est 0 . La valeur NIL ne doit pas être poussée dans une file d'attente et il y a une instruction assert dans les fonctions push pour se prémunir contre celle des builds de mode de débogage. Pousser NIL Element dans une file d'attente en mode de libération se traduit par un comportement non défini, tels que des impasses et / ou des éléments de file d'attente perdus.
Notez que l'optimisme est un choix d'un flux de contrôle de l'opération de modification de file d'attente, plutôt qu'un type de file d'attente. Une push optimiste est la plus rapide lorsque la file d'attente n'est pas pleine la plupart du temps, une pop optimiste - lorsque la file d'attente n'est pas vide la plupart du temps. Les opérations optimistes et non pas peuvent être mélangées sans restrictions. Les OptimistAtomicQueue dans les repères utilisent uniquement push et pop optimistes .
Voir exemple.cc pour un exemple d'utilisation.
Les opérations push et try_push se synchronisent avec (comme défini dans std::memory_order ) avec toute opération pop ou try_pop ultérieure du même objet de file d'attente. Ce qui signifie que:
push / try_push , qui est une opération memory_order::release . Même ordre mémoire que celui de std::mutex::unlock .pop / try_pop , qui est une opération memory_order::acquire . Même ordre mémoire que celui de std::mutex::lock .push / try_push d'un élément dans une file d'attente deviennent visibles dans le fil du consommateur qui pop / try_pop cet élément particulier. Les files d'attente disponibles ici utilisent un tableau de bouffée pour stocker des éléments. La capacité de la file d'attente est fixée à l'heure de compilation ou à l'heure de construction.
Dans une production, un scénario de consommation multiple multipro-producteur, la capacité de rogne devrait être réglée sur la taille maximale de la file d'attente attendue. Lorsque la bague se rassasie, cela signifie que les consommateurs ne peuvent pas consommer les éléments assez rapidement. Une solution pour cela est de:
push et pop entraînent toujours des cycles de CPU coûteux pour maintenir l'intégrité de l'état de file d'attente de manière atomique / cohérente / isolée par rapport à d'autres fils et ces coûts augmentent super linéairement à mesure que la file d'attente augmente. Le lot de producteur de plusieurs petits éléments ou éléments résultant d'un événement à un message de file d'attente est souvent une solution raisonnable.L'utilisation d'une taille de tableau de bouffée Power-of-2 permet de quelques optimisations importantes:
% SIZE de l'opérateur binaire reste. L'opérateur binaire restant % génère normalement une instruction de CPU de division qui n'est pas bon marché, mais l'utilisation d'une taille de puissance de 2 tourne cet opérateur reste en une instruction binaire and CPU bon marché et c'est aussi rapide que possible.N producteurs ainsi que des consommateurs M rivaliers sur des éléments ultérieurs dans la même ligne de cache d'anneau dans le pire des cas, ce n'est qu'un producteur en concurrence avec un consommateur (pédantiquement, lorsque le nombre de processeurs n'est pas plus élevé que le nombre d'éléments qui peuvent tenir dans une ligne de cache). Cette optimisation évolue mieux avec le nombre de producteurs et de consommateurs et la taille des éléments. Avec un faible nombre de producteurs et de consommateurs (jusqu'à environ 2 de chacun dans ces repères), la désactivation de cette optimisation peut produire un meilleur débit (mais une variance plus élevée entre les cycles). Les conteneurs utilisent un type unsigned pour la taille et les index internes. Sur la plate-forme X86-64 unsigned , 32 bits de large, tandis que size_t est de large de 64 bits. Les instructions 64 bits utilisent un préfixe d'instructions d'octet supplémentaire entraînant un peu plus de pression sur le cache d'instructions du CPU et le frontal. Par conséquent, des indices unsigned 32 bits sont utilisés pour maximiser les performances. Cela limite la taille de la file d'attente à 4 294 967 295 éléments, ce qui semble être une limite difficile raisonnable pour de nombreuses applications.
Bien que les files d'attente atomiques puissent être utilisées avec tous les types d'éléments mobiles (y compris std::unique_ptr ), pour le meilleur débit et la latence, les éléments de file d'attente doivent être bon marché à copier et sans verrouillage (par exemple, unsigned ou T* ), de sorte que les opérations push et pop les plus rapides sont les plus rapides.
Conceptuellement , une opération push ou pop fait deux étapes atomiques:
head , des consommateurs incrémentant l'indice tail . Chaque créneau est accessible par un producteur et un threads de consommation uniquement.NIL , le chargement des consommateurs à partir d'une machine à sous modifie son état de NIL . La fente est un spinlock pour son seul producteur et un threads de consommation. Ces files d'attente prévoient qu'un fil faisant push ou pop peut terminer l'étape 1, puis être préempté avant de terminer l'étape 2.
Un algorithme est sans serrure s'il existe des progrès garantis à l'échelle du système. Ces files d'attente garantissent les progrès à l'échelle du système par les propriétés suivantes:
push est indépendante de toute push précédente. Une push incomplète (préemptée) par un fil de producteur n'affecte pas push d'un autre fil.pop est indépendante de tout pop précédent. Une pop incomplète (préemptée) par un fil de consommation n'affecte pas pop d'un autre fil.push incomplète (préemptée) à partir d'un fil de producteur n'affecte qu'un seul fil de consommateur pop de faire un élément de cette fente de file d'attente particulière. Tous les autres threads pop S ne sont pas affectés.pop incomplète (préemptée) d'un fil de consommation affecte un seul fil de producteur push un élément dans cette fente de file d'attente particulière tout en s'attendant à ce qu'il ait été consommé il y a longtemps, dans le scénario plutôt improbable que les producteurs ont enroulé autour de l'ensemble du rogue tandis que ce consommateur n'a pas terminé sa pop . Tous les autres threads push et pop s ne sont pas affectés. La préemption du thread de planificateur de tâches Linux est quelque chose qu'aucun processus d'espace utilisateur ne devrait être en mesure d'affecter ou d'échapper, sinon toute application malveillante exploiterait cela.
Pourtant, il y a quelques choses que l'on peut faire pour minimiser la préemption de la mission Critical Application Threads:
SCHED_FIFO en temps réel pour vos threads, par exemple chrt --fifo 50 <app> . Un thread SCHED_FIFO ou un gestionnaire d'interruption du noyau plus élevé peut toujours préempter vos threads SCHED_FIFO .SCHED_OTHER avec ses priorités ajustées dynamiquement va à la défaite de l'utilisation de ces files d'attente.SCHED_FIFO d'être étranglés.taskset . Les gens proposent souvent de limiter l'attention occupée avec un appel ultérieur à std::this_thread::yield() / sched_yield / pthread_yield . Cependant, sched_yield est un mauvais outil pour le verrouillage car il ne communique pas au noyau OS ce que le thread attend, afin que le planificateur de threads OS ne puisse jamais planifier le thread d'appel pour reprendre au bon moment lorsque l'état partagé a changé (sauf s'il n'y a pas d'autres threads qui peuvent fonctionner sur ce noyau CPU, afin que l'appelant ait changé immédiatement). Voir la section des notes dans man sched_yield et un thread de noyau Linux sur sched_yield et spinlocks pour plus de détails.
Dans Linux, il y a un type mutex PTHREAD_MUTEX_ADAPTIVE_NP qui porte occupé un mutex verrouillé pour un certain nombre d'itérations, puis fait un système de blocage dans le noyau pour deschedule le fil d'attente. Dans les références, c'était le pire interprète et je n'ai pas pu trouver un moyen de le rendre meilleur, et c'est la raison pour laquelle il n'est pas inclus dans les repères.
Sur Intel CPU, on peut utiliser les 4 registres de contrôle de débogage pour surveiller la région de la mémoire Spinlock pour l'accès en écriture et attendre dessus en utilisant select (et ses amis) ou sigwait (voir perf_event_open et uapi/linux/hw_breakpoint.h pour plus de détails). Un serveur Spinlock pourrait se suspendre avec select ou sigwait jusqu'à ce que l'état de Spinlock soit mis à jour. Mais il n'y a que 4 de ces registres, de sorte qu'une telle solution ne s'allonge pas.
Voir les graphiques de référence du débit et de latence.
Il y a quelques comportements de système d'exploitation qui compliquent l'analyse comparative:
SCHED_FIFO Priority 50 en temps réel soit utilisé pour désactiver l'expiration du temps de temps du planificateur et rendre les threads non préemptables par des processus / threads de priorité inférieurs.benchmarks est exécuté au moins 33 fois. Les graphiques de référence affichent des valeurs moyennes. L'infiltration du graphique affiche également l'écart type, les valeurs minimales et maximales. Les performances de référence des files d'attente de consommation de consommation unique à un seul producteur boost::lockfree::spsc_queue , moodycamel::ReaderWriterQueue et ces files d'attente en mode de consommation unique à producteur unique devraient être identiques car ils mettent exactement le même algorithme en utilisant exactement le même chargement atomique et des instructions de stockage. boost::lockfree::spsc_queue Implémentation Benchmarked à ce moment-là n'avait aucune optimisation pour minimiser les affirmations de cache L1D, une mauvaise prédiction de la branche froide ou des stands de pipeline à partir de problèmes subtiles notables uniquement dans le code d'assemblage généré.
Je n'ai accès qu'à quelques machines x86-64. Si vous avez accès à différents matériels, n'hésitez pas à soumettre le fichier de sortie de scripts/run-benchmarks.sh et je inclurai vos résultats dans la page Benchmarks.
Lorsque des pages énormes sont disponibles, les repères utilisent des pages énormes de 1x1 Go ou 16x2 Mo pour les files d'attente afin de minimiser les ratés TLB. Pour activer d'énormes pages, faites l'une des:
sudo hugeadm --pool-pages-min 1GB:1
sudo hugeadm --pool-pages-min 2MB:16
Alternativement, vous aimerez peut-être activer les immenses pages transparentes dans votre système et utiliser un allocateur conscient de la page ÉNORME, comme TCMALLOC.
Par défaut, le planificateur Linux efface les fils en temps réel de la consommation de 100% de CPU et ce qui est préjudiciable à l'analyse comparative. Tous les détails peuvent être trouvés dans la planification de groupe en temps réel. Pour désactiver la limite de fil en temps réel, faites:
echo -1 | sudo tee /proc/sys/kernel/sched_rt_runtime_us >/dev/null
N Les fils de producteur poussent un entier de 4 octets dans une même file d'attente, n les fils de consommation font éclater les entiers de la file d'attente. Tous les producteurs publient 1 000 000 de messages au total. Le temps total pour envoyer et recevoir tous les messages est mesuré. La référence est exécutée pour 1 producteur et 1 consommateur jusqu'à (total-number-of-cpus / 2) producteurs / consommateurs pour mesurer l'évolutivité des différentes files d'attente.
Un thread affiche un entier à un autre fil à travers une file d'attente et attend une réponse d'une autre file d'attente (2 files d'attente au total). Les repères mesurent le temps total de 100 000 ping-pongs, le meilleur des 10 points. L'affirmation est minime ici (1 producteur-1-consommateur, 1 élément dans la file d'attente) pour pouvoir atteindre et mesurer la latence la plus faible. Rapporte le temps aller-retour moyen.
Les contributions sont plus que les bienvenues. .editorconfig et .clang-format peuvent être utilisés pour faire correspondre automatiquement le formatage du code.
Quelques livres sur le sujet de la programmation multithread que j'ai trouvé assez instructif:
Copyright (C) 2019 Maxim Egorushkin. Licence MIT. Voir la licence complète dans la licence de fichier.
