xenium
v0.0.2: Merge pull request #19 from rbalint
xenium est une bibliothèque d'en-tête uniquement qui fournit une collection de structures de données simultanées et d'algorithmes de récupération de mémoire. Les structures de données sont paramétrées de manière à pouvoir être utilisées avec divers schémas de récupération (de la même manière que la STL permet la personnalisation des allocateurs).
La documentation fournit plus de détails.
Ce projet est basé sur mon travail précédent sur https://github.com/mpoeter/emr
# include < xenium/ramalhete_queue.hpp >
# include < xenium/reclamation/epoch_based.hpp >
struct msg { ... };
xenium::ramalhete_queue<
std::unique_ptr<msg>,
xenium::policy::reclaimer<xenium::reclamation::epoch_based<>>,
xenium::policy::entries_per_node< 2048 >
> queue;
queue.push(std::make_unique<msg>());
std::unique_ptr<msg> data;
if (queue.try_pop(data)) {
// do something with data
}Pour le moment, le nombre de structures de données fournies est plutôt faible puisque l'accent a été mis jusqu'à présent sur les schémas de récupération. Cependant, il est prévu d’ajouter plusieurs structures de données supplémentaires dans un avenir proche.
michael_scott_queue - une file d'attente multi-producteurs/multi-consommateurs illimitée et sans verrouillage proposée par Michael et Scott [MS96].ramalhete_queue - une file d'attente multi-producteurs/multi-consommateurs rapide, illimitée et sans verrouillage proposée par Ramalhete [Ram16].vyukov_bounded_queue - une file d'attente FIFO multi-producteurs/multi-consommateurs limitée basée sur la version proposée par Vyukov [Vyu10 ].kirsch_kfifo_queue - une file d'attente k-FIFO multi-producteurs/multi-consommateurs illimitée proposée par Kirsch et al. [KLP13].kirsch_bounded_kfifo_queue - une file d'attente k-FIFO multi-producteurs/multi-consommateurs limitée proposée par Kirsch et al. [KLP13].nikolaev_queue - une file d'attente multi-producteurs/multi-consommateurs illimitée proposée par Nikolaev [Nik19].nikolaev_bounded_queue - une file d'attente multi-producteurs/multi-consommateurs limitée proposée par Nikolaev [Nik19].harris_michael_list_based_set - un conteneur sans verrouillage qui contient un ensemble trié d'objets uniques. Cette structure de données est basée sur la solution proposée par Michael [Mic02] qui s'appuie sur la proposition originale de Harris [Har01].harris_michael_hash_map - une carte de hachage sans verrouillage basée sur la solution proposée par Michael [Mic02] qui s'appuie sur la proposition originale de Harris [Har01].chase_work_stealing_deque - un deque de vol de travail basé sur la proposition de Chase et Lev [CL05].vyukov_hash_map - une carte de hachage simultanée qui utilise un verrouillage à granularité fine pour les opérations de mise à jour. Cette implémentation est fortement inspirée de la version proposée par Vyukov [Vyu08].left_right - une implémentation générique de l'algorithme LeftRight proposé par Ramalhete et Correia [RC15].seqlock - une implémentation du verrouillage séquentiel (également souvent appelé « verrouillage séquentiel »). L'implémentation des schémas de récupération est basée sur une version adaptée de l'interface proposée par Robison [Rob13].
Les programmes de remise en état suivants sont mis en œuvre :
lock_free_ref_count [Val95, MS95]hazard_pointer [Mic04]hazard_eras [RC17]quiescent_state_basedgeneric_epoch_based - il s'agit d'un récupérateur généralisé basé sur une époque qui peut être configuré de plusieurs manières. Par souci de simplicité, les alias suivants sont prédéfinis pour les configurations correspondantes.epoch_based [Fra04]new_epoch_based [HMBW07]debra [Bro15]stamp_it [PT18a, PT18b] xenium est une bibliothèque uniquement d'en-tête, donc pour l'utiliser, il suffit d'inclure le dossier xenium dans votre liste de répertoires d'inclusion. Aucune autre bibliothèque tierce n'est requise. Cependant, l'implémentation utilise les fonctionnalités C++17, un compilateur avec une prise en charge suffisante de C++17 est donc requis. Les compilateurs suivants sont utilisés dans les versions CI et sont donc connus pour être pris en charge :
Le test unitaire nécessite googletest et les benchmarks nécessitent taocpp/json et taocpp/config . Ces dépendances sont incluses sous forme de sous-modules, les tests unitaires et/ou les benchmarks peuvent donc être construits comme suit :
git clone https://github.com/mpoeter/xenium.git && cd xenium
git submodule update --init --recursive
mkdir build && cd build
cmake ..
make gtest
make benchmark
| [Frère15] | Trevor Alexander Brown. Récupérer de la mémoire pour des structures de données sans verrouillage : il doit y avoir une meilleure solution. Dans Actes du Symposium ACM 2015 sur les principes de l'informatique distribuée (PODC) , pages 261-270. ACM, 2015. |
| [CL05] | David Chase et Yossi Lev. Deque de vol de travail circulaire dynamique. Dans Actes du 17e Symposium annuel de l'ACM sur le parallélisme dans les algorithmes et les architectures (SPAA) , pages 21 à 28. ACM, 2005. |
| [Fra04] | Keir Fraser. Liberté de verrouillage pratique . Thèse de doctorat, Laboratoire informatique de l'Université de Cambridge, 2004. |
| [Har01] | Timothy L. Harris. Une implémentation pragmatique de listes chaînées non bloquantes. Dans Actes de la 15e Conférence internationale sur l'informatique distribuée (DISC) , pages 300 à 314. Springer-Verlag, 2001. |
| [HMBW07] | Thomas E. Hart, Paul E. McKenney, Angela Demke Brown et Jonathan Walpole. Performance de récupération de mémoire pour une synchronisation sans verrouillage. Journal de l'informatique parallèle et distribuée, 67(12):1270-1285, 2007. |
| [KLP13] | Christoph Kirsch, Michael Lippautz et Hannes Payer. Files d'attente k-FIFO rapides, évolutives et sans verrouillage. Dans Actes de la Conférence internationale sur les technologies informatiques parallèles (PaCT) , pages 208 à 223, Springer-Verlag, 2013. |
| [Mic02] | Magé M. Michael. Tables de hachage dynamiques sans verrouillage hautes performances et ensembles basés sur des listes. Dans Actes du 14e Symposium annuel ACM sur les algorithmes et architectures parallèles (SPAA) , pages 73-82. ACM, 2002. |
| [Mic04] | Magé M. Michael. Indicateurs de danger : Récupération de mémoire sécurisée pour les objets sans verrouillage. Transactions IEEE sur les systèmes parallèles et distribués, 15(6):491-504, 2004. |
| [MS95] | Maged M. Michael et Michael L. Scott. Correction d'une méthode de gestion de mémoire pour les structures de données sans verrouillage. Rapport technique, Université de Rochester, 1995. |
| [MS96] | Maged M. Michael et Michael L. Scott. Algorithmes de file d'attente simultanés non bloquants et bloquants simples, rapides et pratiques. Dans Actes du 15e Symposium annuel de l'ACM sur les principes de l'informatique distribuée (PODC) , pages 267-275. ACM, 1996. |
| [Nik19] | Ruslan Nikolaev Une file d'attente fifo sans verrouillage évolutive, portable et économe en mémoire. Dans Actes du 33e Symposium international sur l'informatique distribuée (DISC) , 2019. |
| [PT18a] | Manuel Pöter et Jesper Larsson Träff. Brève annonce : Stamp-it, un système de récupération de mémoire simultanée plus efficace pour les threads dans le modèle de mémoire C++. Dans Actes du 30e Symposium annuel de l'ACM sur le parallélisme dans les algorithmes et les architectures (SPAA) , pages 355-358. ACM, 2018. |
| [PT18b] | Manuel Pöter et Jesper Larsson Träff. Stamp-it, un schéma de récupération de mémoire simultanée plus efficace pour les threads dans le modèle de mémoire C++. Rapport technique, 2018. |
| [Ram16] | Pedro Ramalhete. FAAArrayQueue - File d'attente sans verrouillage MPMC (partie 4 sur 4). Blogue, novembre 2016. |
| [RC15] | Pedro Ramalhete et Andreia Correia. Gauche-Droite - Une technique de contrôle de concurrence avec des lectures inconscientes de la population sans attente. Octobre 2015 |
| [RC17] | Pedro Ramalhete et Andreia Correia. Brève annonce : Ères de danger - récupération de mémoire non bloquante. Dans Actes du 29e Symposium annuel de l'ACM sur le parallélisme dans les algorithmes et les architectures (SPAA) , pages 367-369. ACM, 2017. |
| [Rob13] | Arch D. Robison. Conception basée sur des politiques pour une destruction en toute sécurité dans des conteneurs simultanés. Document du comité des normes C++, 2013. |
| [Val95] | John D. Valois. Structures de données sans verrouillage . Thèse de doctorat, Institut polytechnique Rensselaer, 1995. |
| [Vyu08] | Dmitri Vyukov. Carte de hachage évolutive. Publication sur Google Groupes, 2008. |
| [Vyu10] | Dmitri Vyukov. File d'attente MPMC délimitée simple et efficace. Publication sur Google Groupes, 2010. |
