xenium
v0.0.2: Merge pull request #19 from rbalint
xenium é uma biblioteca somente de cabeçalho que fornece uma coleção de estruturas de dados simultâneas e algoritmos de recuperação de memória. As estruturas de dados são parametrizadas para que possam ser utilizadas com vários esquemas de recuperação (semelhante à forma como o STL permite a customização de alocadores).
A documentação fornece mais detalhes.
Este projeto é baseado em meu trabalho anterior em 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
}Neste momento, o número de estruturas de dados fornecidas é bastante pequeno, uma vez que o foco até agora estava nos esquemas de recuperação. No entanto, o plano é adicionar várias outras estruturas de dados num futuro próximo.
michael_scott_queue - uma fila multiprodutor/multiconsumidor ilimitada e livre de bloqueio proposta por Michael e Scott [MS96].ramalhete_queue - uma fila multiprodutor/multiconsumidor rápida, ilimitada e sem bloqueio proposta por Ramalhete [Ram16].vyukov_bounded_queue - uma fila FIFO multiprodutor/multiconsumidor limitada baseada na versão proposta por Vyukov [Vyu10 ].kirsch_kfifo_queue - uma fila k-FIFO multiprodutor/multiconsumidor ilimitada proposta por Kirsch et al. [KLP13].kirsch_bounded_kfifo_queue - uma fila k-FIFO limitada de multiprodutor/multiconsumidor proposta por Kirsch et al. [KLP13].nikolaev_queue - uma fila ilimitada de multiprodutores/multiconsumidores proposta por Nikolaev [Nik19].nikolaev_bounded_queue - uma fila limitada de multiprodutores/multiconsumidores proposta por Nikolaev [Nik19].harris_michael_list_based_set - um contêiner sem bloqueio que contém um conjunto classificado de objetos exclusivos. Esta estrutura de dados é baseada na solução proposta por Michael [Mic02] que se baseia na proposta original de Harris [Har01].harris_michael_hash_map - um mapa hash sem bloqueio baseado na solução proposta por Michael [Mic02] que se baseia na proposta original de Harris [Har01].chase_work_stealing_deque - um deque de roubo de trabalho baseado na proposta de Chase e Lev [CL05].vyukov_hash_map - um mapa hash simultâneo que usa bloqueio refinado para operações de atualização. Esta implementação é fortemente inspirada na versão proposta por Vyukov [Vyu08].left_right - uma implementação genérica do algoritmo LeftRight proposto por Ramalhete e Correia [RC15].seqlock - uma implementação do bloqueio de sequência (também conhecido como "bloqueio sequencial"). A implementação dos esquemas de recuperação baseia-se numa versão adaptada da interface proposta por Robison [Rob13].
Os seguintes esquemas de recuperação são implementados:
lock_free_ref_count [Val95, MS95]hazard_pointer [Mic04]hazard_eras [RC17]quiescent_state_basedgeneric_epoch_based - este é um recuperador generalizado baseado em época que pode ser configurado de várias maneiras. Para simplificar, os seguintes aliases são predefinidos para as configurações correspondentes.epoch_based [Fra04]new_epoch_based [HMBW07]debra [Mano15]stamp_it [PT18a, PT18b] xenium é uma biblioteca apenas de cabeçalho, portanto, para utilizá-la basta incluir a pasta xenium em sua lista de diretórios de inclusão. Nenhuma outra biblioteca de terceiros é necessária. No entanto, a implementação usa recursos do C++17, portanto, é necessário um compilador com suporte suficiente ao C++17. Os seguintes compiladores são usados nas compilações de CI e, portanto, são conhecidos por serem suportados:
O teste de unidade requer googletest e os benchmarks requerem taocpp/json e taocpp/config . Essas dependências são incluídas como submódulos, portanto os testes unitários e/ou benchmarks podem ser construídos da seguinte forma:
git clone https://github.com/mpoeter/xenium.git && cd xenium
git submodule update --init --recursive
mkdir build && cd build
cmake ..
make gtest
make benchmark
| [Mano15] | Trevor Alexander Brown. Recuperando memória para estruturas de dados sem bloqueio: deve haver uma maneira melhor. Nos Anais do Simpósio ACM sobre Princípios de Computação Distribuída (PODC) de 2015 , páginas 261–270. ACM, 2015. |
| [CL05] | David Chase e Yossi Lev. Deque circular dinâmico de roubo de trabalho. Nos Anais do 17º Simpósio Anual ACM sobre Paralelismo em Algoritmos e Arquiteturas (SPAA) , páginas 21–28. ACM, 2005. |
| [Fra04] | Keir Fraser. Liberdade de bloqueio prática . Tese de doutorado, Laboratório de Computação da Universidade de Cambridge, 2004. |
| [Har01] | Timothy L. Harris. Uma implementação pragmática de listas vinculadas sem bloqueio. Nos Anais da 15ª Conferência Internacional sobre Computação Distribuída (DISC) , páginas 300–314. Springer-Verlag, 2001. |
| [HMBW07] | Thomas E. Hart, Paul E. McKenney, Angela Demke Brown e Jonathan Walpole. Desempenho de recuperação de memória para sincronização sem bloqueio. Jornal de Computação Paralela e Distribuída, 67(12):1270–1285, 2007. |
| [KLP13] | Christoph Kirsch, Michael Lippautz e Hannes Payer. Filas k-FIFO rápidas, escaláveis e sem bloqueios. Em Anais da Conferência Internacional sobre Tecnologias de Computação Paralela (PaCT) , páginas 208–223, Springer-Verlag, 2013. |
| [Mic02] | Maged M. Michael. Tabelas hash dinâmicas e sem bloqueio de alto desempenho e conjuntos baseados em lista. Nos Anais do 14º Simpósio Anual ACM sobre Algoritmos e Arquiteturas Paralelas (SPAA) , páginas 73–82. ACM, 2002. |
| [Mic04] | Maged M. Michael. Indicadores de perigo: Recuperação segura de memória para objetos sem bloqueio. Transações IEEE em Sistemas Paralelos e Distribuídos, 15(6):491–504, 2004. |
| [MS95] | Maged M. Michael e Michael L. Scott. Correção de um método de gerenciamento de memória para estruturas de dados sem bloqueio. Relatório técnico, Universidade de Rochester, 1995. |
| [MS96] | Maged M. Michael e Michael L. Scott. Algoritmos de fila simultânea simples, rápidos e práticos, sem bloqueio e bloqueio. Nos Anais do 15º Simpósio Anual ACM sobre Princípios de Computação Distribuída (PODC) , páginas 267–275. ACM, 1996. |
| [Nik19] | Ruslan Nikolaev Uma fila fifo escalonável, portátil e com uso eficiente de memória e sem bloqueio. Nos Anais do 33º Simpósio Internacional de Computação Distribuída (DISC) , 2019. |
| [PT18a] | Manuel Pöter e Jesper Larsson Träff. Breve anúncio: Stamp-it, um esquema de recuperação de memória simultânea mais eficiente em threads no modelo de memória C++. Nos Anais do 30º Simpósio Anual ACM sobre Paralelismo em Algoritmos e Arquiteturas (SPAA) , páginas 355–358. ACM, 2018. |
| [PT18b] | Manuel Pöter e Jesper Larsson Träff. Stamp-it, um esquema de recuperação de memória simultânea mais eficiente em threads no modelo de memória C++. Relatório técnico, 2018. |
| [Carneiro16] | Pedro Ramalhete. FAAArrayQueue - fila MPMC sem bloqueio (parte 4 de 4). Blog, novembro de 2016. |
| [RC15] | Pedro Ramalhete e Andreia Correia. Esquerda-Direita - Uma técnica de controle de simultaneidade com leituras inconscientes da população sem espera. Outubro de 2015 |
| [RC17] | Pedro Ramalhete e Andreia Correia. Breve anúncio: Eras de perigo - recuperação de memória sem bloqueio. Nos Anais do 29º Simpósio Anual ACM sobre Paralelismo em Algoritmos e Arquiteturas (SPAA) , páginas 367–369. ACM, 2017. |
| [Rob13] | Arco D. Robison. Design baseado em políticas para destruição segura em contêineres simultâneos. Artigo do comitê de padrões C++, 2013. |
| [Val95] | John D. Valois. Estruturas de dados sem bloqueio . Tese de doutorado, Instituto Politécnico Rensselaer, 1995. |
| [Vyu08] | Dmitry Vyukov. Mapa hash escalável. Postagem nos Grupos do Google, 2008. |
| [Vyu10] | Dmitry Vyukov. Fila MPMC limitada simples e eficiente. Postagem nos Grupos do Google, 2010. |
