Download atomic_queue - atomic_queue download do código -fonte

atomic_queue

C/C++

1.0.0

Baixar

atomic_queue

C ++ 14 Filas sem bloqueio de múltiplos produtores múltiplos consumidores com base em tampão circular e std::atomic .

Projetado com uma meta para minimizar a latência entre um thread empurrando um elemento em uma fila e outro fio que o pega da fila.

Foi desenvolvido, testado e comparado no Linux, mas deve suportar quaisquer plataformas C ++ 14 que implementem std::atomic . Relatado como compatível com o Windows, mas as integrações contínuas hospedadas pelo GitHub estão atualmente configuradas apenas para a plataforma x86_64 no Ubuntu-20.04 e Ubuntu-22.04. Puxe solicitações para estender as integrações contínuas para executar em outras arquiteturas e/ou plataformas são bem -vindas.

Princípios de design

Ao minimizar a latência, um bom design não é quando não há mais nada a acrescentar, mas quando não há mais nada a ser removido, pois essas filas exemplificam.

Minimizar a latência maximiza naturalmente a taxa de transferência. A baixa latência recíproca é alta através do sentido ideal de engenharia matemática e prática. A baixa latência é incompatível com qualquer atraso e/ou lotes, que destruam a ordem de tempo dos eventos originais (hardware) empurrada para uma fila por diferentes threads. A maximização da taxa de transferência, por outro lado, pode ser feita às custas da latência, atrasando e em lote várias atualizações.

O principal princípio do design que essas filas seguem é o minimalismo , o que resulta em opções de design como:

Mínimo de instruções atômicas. As funções de push e pop inline não podem ser mais baratas em termos de pressão do número da instrução / L1i Cache da CPU.
A contenção explícita/evitação de compartilhamento falso na fila e seus elementos.
Array linear de tamanho fixo de buffer de anel. Nenhuma alocações de memória de heap após a construção de um objeto de fila. Não recebe mais cache da CPU L1D ou TLB do que isso.
Semântica de valor. Significando que as filas fazem uma cópia/movimentação no push / pop , nenhuma referência/ponteiro para elementos na fila pode ser obtida.

O impacto de cada uma dessas pequenas opções de design por conta própria é quase mensurável, mas seu impacto total é muito maior que uma soma simples dos impactos dos constituintes, também conhecida como composta super escalar ou sinergia. A sinergia emergindo de combinar várias dessas pequenas opções de design é o que permite que as CPUs realizem em suas capacidades de pico menos impedidas.

Essas opções de design também são limitações:

O tamanho máximo da fila deve ser definido no tempo de compilação ou no tempo de construção. O tampão circular etapas laterais O problema de recuperação da memória inerente às filas baseadas na lista vinculada pelo preço do tamanho do buffer fixo. Consulte Recuperação de memória eficaz para estruturas de dados sem bloqueio em C ++ para obter mais detalhes. O tamanho do buffer fixo pode não ser uma grande limitação, pois uma vez que a fila fica maior que o tamanho máximo esperado que indica um problema que os elementos não são consumidos com rapidez suficiente e, se a fila continuar crescendo, pode eventualmente consumir toda a memória disponível que pode afetar todo o sistema, e não apenas o processo problemático. O único inconveniente aparente é que é preciso fazer um cálculo inicial sobre o que seria o maior número esperado/aceitável de elementos não consumidos na fila.
Não há funções de push/pop bloqueando o OS. Esta fila foi projetada para cenários ultra-baixa-latência e o uso de um Primitivo de Bloqueio do SO seria sacrificar a latência push-to-pop. Para a menor latência possível, não se pode dar ao ar livre no núcleo do sistema operacional, porque a latência de despertar de um fio bloqueado é de cerca de 1-3 microssegundos, enquanto o tempo de ida e volta dessa fila pode ser tão baixo quanto 150 nanossegundos.

Os aplicativos ultra-baixa de latência precisam exatamente disso e nada mais. O minimalismo compensa, consulte a taxa de transferência e os benchmarks de latência.

Modelos de papéis

Vários outros recipientes bem estabelecidos e populares são usados para referência nos benchmarks:

std::mutex - um buffer de anel de tamanho fixo com std::mutex .
pthread_spinlock - um buffer de anel de tamanho fixo com pthread_spinlock_t .
boost::lockfree::spsc_queue -Uma fila de um produtor único sem espera da biblioteca Boost.
boost::lockfree::queue -Uma fila de consumidores de múltiplos produtores sem bloqueio sem bloqueio da biblioteca Boost.
moodycamel::ConcurrentQueue -Uma fila de consumidores de múltiplos produtores sem bloqueio sem bloqueio usada no modo não bloqueador. Esta fila foi projetada para maximizar a taxa de transferência às custas da latência e evitar a ordem de tempo global dos elementos empurrada para uma fila por diferentes encadeamentos. Não é equivalente a outras filas comparadas aqui a esse respeito.
moodycamel::ReaderWriterQueue -Uma fila de um produtor único sem bloqueio de bloqueio usado usado no modo não bloqueador.
xenium::michael_scott_queue -Uma fila de multi-produtor sem trava-multi-consumidor proposta por Michael e Scott (esta fila é semelhante ao boost::lockfree::queue que também é baseada na mesma proposta).
xenium::ramalhete_queue -Uma fila de multi-produtor sem trava-multi-consumidor proposta por Ramalhete e Correia.
xenium::vyukov_bounded_queue -uma fila de consumidor multi-produtor limitada com base na versão proposta por Vyukov.
tbb::spin_mutex - um buffer de anel fixo bloqueado com tbb::spin_mutex dos blocos de construção de encadeamento da Intel.
tbb::concurrent_bounded_queue - fila de mesmo nome usado no modo de bloqueio a partir de blocos de construção Intel Threading.

Usando a biblioteca

Os contêineres fornecidos são modelos de aula somente para cabeçalho, não é necessário edifício/instalação.

Instale no github

Clone o projeto:

 git clone https://github.com/max0x7ba/atomic_queue.git

Adicione atomic_queue/include diretório (use o caminho completo) aos caminhos de inclusão do seu sistema de construção.
#include <atomic_queue/atomic_queue.h> Na sua fonte C ++.

Instale usando o vcpkg

 vcpkg install atomic-queue

Instale usando Conan

Siga o tutorial oficial sobre como consumir pacotes Conan. Detalhes específicos para esta biblioteca estão disponíveis no Conancenter.

Referência de instruções de construção e execução

Os contêineres fornecidos são modelos de classe somente cabeçalho que exigem apenas #include <atomic_queue/atomic_queue.h> , nenhuma construção/instalação é necessária.

A construção é necessária para executar os testes e os benchmarks.

 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

A referência também exige que a biblioteca Intel TBB esteja disponível. Ele assume que está instalado em /usr/local/include e /usr/local/lib . Se estiver instalado em outro lugar, você poderá modificar cppflags.tbb e ldlibs.tbb no Makefile .

Biblioteca contemve

Filas disponíveis

AtomicQueue - Um buffer de anel de tamanho fixo para elementos atômicos.
OptimistAtomicQueue -Um buffer de anel fixo mais rápido para elementos atômicos que ocupam as ranhuras quando vazias ou cheias. É AtomicQueue usado com push / pop em vez de try_push / try_pop .
AtomicQueue2 -Um buffer de anel de tamanho fixo para elementos não atômicos.
OptimistAtomicQueue2 -Um buffer de anel fixo mais rápido para elementos não atômicos que ocupam as ranhuras quando vazias ou cheias. É AtomicQueue2 usado com push / pop em vez de try_push / try_pop .

Esses recipientes possuem AtomicQueueB correspondentes, OptimistAtomicQueueB , AtomicQueueB2 , OptimistAtomicQueueB2 versões em que o tamanho do buffer é especificado como um argumento para o construtor.

O modo totalmente ordenado é suportado. Nesse modo, os consumidores recebem mensagens na mesma ordem do FIFO, as mensagens foram publicadas. Este modo é suportado para funções push e pop , mas não para as versões try_ . Na Intel X86, o modo totalmente ordenado tem 0 custo, a partir de 2019.

O modo de consumidor único de produtor único é suportado. Nesse modo, não são necessárias instruções caras de CPU de leitura atômica de leitura-escreva, apenas as cargas e lojas atômicas mais baratas. Isso melhora significativamente a taxa de transferência da fila.

Os tipos de elementos de fila somente para movimentos são totalmente suportados. Por exemplo, uma fila de std::unique_ptr<T> ele seria AtomicQueue2B<std::unique_ptr<T>> ou AtomicQueue2<std::unique_ptr<T>, CAPACITY> .

API da fila

Os modelos de classe da fila fornecem as seguintes funções de membro:

try_push - anexa um elemento ao final da fila. Retorna false quando a fila está cheia.
try_pop - remove um elemento da frente da fila. Retorna false quando a fila estiver vazia.
push (otimista) - anexa um elemento ao final da fila. Aguarda ocupada quando a fila está cheia. Mais rápido que try_push quando a fila não está cheia. FILO OPCIONAL FILO FILHEING E ORDEM TOTAL.
pop (otimista) - remove um elemento da frente da fila. Espera ocupado quando a fila está vazia. Mais rápido que try_pop quando a fila não está vazia. FIFO Opcional FILO Fila e ordem total.
was_size - Retorna o número de elementos não consumidos durante a chamada. O estado pode ter alterado quando o valor de retorno for examinado.
was_empty - retorna true se o contêiner estivesse vazio durante a chamada. O estado pode ter alterado quando o valor de retorno for examinado.
was_full - retorna true se o contêiner estiver cheio durante a chamada. O estado pode ter alterado quando o valor de retorno for examinado.
capacity - Retorna o número máximo de elementos que a fila pode manter.

Os elementos atômicos são aqueles, para os quais std::atomic<T>{T{}}.is_lock_free() retorna true e, quando os recursos C ++ 17 estiverem disponíveis, std::atomic<T>::is_always_lock_free avalia true o tempo de compilação. Em outras palavras, a CPU pode carregar, armazenar e comparar e trocar esses elementos atomicamente nativamente. No x86-64, esses elementos são todos os tipos de aritmética padrão e ponteiro C ++.

As filas dos elementos atômicos reservam um valor para servir como um marcador de elemento vazio NIL , seu valor padrão é 0 . O valor NIL não deve ser empurrado para uma fila e há uma declaração assert nas funções push para se proteger contra a criação do modo de depuração. Empurrar o elemento NIL em uma fila no modo de liberação construi resulta em comportamento indefinido, como impasse e/ou elementos de fila perdidos.

Observe que o otimismo é a escolha de um fluxo de controle de operação de modificação da fila, em vez de um tipo de fila. Um push otimista é mais rápido quando a fila não está cheia na maioria das vezes, um pop otimista - quando a fila não está vazia a maior parte do tempo. Otimistas e não para que as operações possam ser misturadas sem restrições. Os OptimistAtomicQueue nos referências usam apenas push e pop otimistas .

Consulte o exemplo.cc para um exemplo de uso.

Notas de implementação

Ordem de memória de cargas e lojas não atômicas

Operações push e try_push sincronize-with (conforme definido em std::memory_order ) com qualquer operação pop ou try_pop subsequente do mesmo objeto de fila. Significando isso:

Nenhuma carga / loja não atômica é reordenada após push / try_push , que é uma operação memory_order::release . A mesma ordem de memória que a de std::mutex::unlock .
Nenhuma carga / loja não atômica é reordenada antes do pop / try_pop , que é uma operação memory_order::acquire . A mesma ordem de memória que a de std::mutex::lock .
Os efeitos das lojas não atômicas de um thread de um produtor seguidas de push / try_push de um elemento em uma fila se tornam visíveis no thread do consumidor que pop / try_pop esse elemento em particular.

Capacidade de buffer de anel

As filas disponíveis aqui usam uma matriz de buffer de anel para armazenar elementos. A capacidade da fila é fixada no tempo de compilação ou no tempo de construção.

Em um cenário de produção múltipla de produtores múltiplos, a capacidade do buffer de anel deve ser definida com o tamanho máximo de fila esperado. Quando o buffer de anel fica cheio, significa que os consumidores não podem consumir os elementos com rapidez suficiente. Uma correção para isso é qualquer:

Aumente a capacidade da fila para lidar com picos temporários de elementos pendentes na fila. Isso normalmente requer reiniciar o aplicativo após a re-configuração/recompilação da reconfiguração.
Aumente o número de consumidores para drenar a fila mais rapidamente. O número de consumidores pode ser gerenciado dinamicamente, por exemplo: quando um consumidor observa que o número de elementos pendentes na fila continua crescendo, que exige a implantação de mais threads de consumidores para drenar a fila a uma taxa mais rápida; As chamadas de fila principalmente vazias para suspender/rescindir threads em excesso de consumidores.
Diminuir a taxa de empurrar elementos para a fila. As chamadas push e pop sempre incorrem em alguns ciclos caros da CPU para manter a integridade do estado da fila de maneira atômica/consistente/isolada em relação a outros threads e esses custos aumentam super-linearmente à medida que a contenção da fila cresce. O lote do produtor de vários elementos ou elementos pequenos resultantes de um evento em uma mensagem de fila geralmente é uma solução razoável.

O uso de um tamanho de matriz de buffers de potência de 2 anel permite algumas otimizações importantes:

Os índices de escritor e leitor são mapeados no índice de matriz de buffer de anel usando % SIZE do operador binário restante. O operador binário restante % normalmente gera uma instrução de CPU de divisão que não é barata, mas o uso de um tamanho de 23 gira que o operador restante em uma instrução binária and CPU barata e isso é o mais rápido possível.
O índice de elementos dentro da linha de cache é trocado pelo índice da linha de cache , para que os elementos consecutivos da fila residam em diferentes linhas de cache. Isso reduz massivamente a contenção de linha de cache entre vários produtores e vários consumidores. Em vez de N produtores, juntamente com M consumidores que competem nos elementos subsequentes na mesma linha de cache do anel-buffer no pior dos casos, é apenas um produtor competindo com um consumidor (pedanteicamente, quando o número de CPUs não é maior que o número de elementos que podem caber em uma linha de cache). Essa otimização é melhor com o número de produtores e consumidores e o tamanho do elemento. Com baixo número de produtores e consumidores (até cerca de 2 de cada um nesses referências) desativando essa otimização pode produzir melhor taxa de transferência (mas uma variação mais alta entre as execuções).

Os contêineres usam tipo unsigned para tamanho e índices internos. Na plataforma x86-64, unsigned tem 32 bits de largura, enquanto size_t tem 64 bits de largura. As instruções de 64 bits utilizam um prefixo de instrução de bytes extra, resultando em um pouco mais de pressão no cache de instruções da CPU e no front-end. Portanto, índices unsigned 32 bits são usados para maximizar o desempenho. Isso limita o tamanho da fila a 4.294.967.295 elementos, o que parece ser um limite rígido razoável para muitas aplicações.

Embora as filas atômicas possam ser usadas com quaisquer tipos de elementos móveis (incluindo std::unique_ptr ), para a melhor taxa de transferência e latência, os elementos da fila devem ser baratos para copiar e travar (por exemplo, unsigned ou T* ), para que as operações push e pop completas mais rápidas.

Garantias sem trava

Conceitualmente , uma operação push ou pop faz duas etapas atômicas:

Atomicamente e exclusivamente reivindica o índice de slot da fila para armazenar/carregar um elemento de/de. Isso é os produtores que incrementam o índice head , os consumidores incrementando o índice tail . Cada slot é acessado por um produtor e apenas threads de consumidores.
Armazene/carregue atomicamente o elemento em/a partir do slot. O produtor armazenado em um slot altera seu estado para não ser NIL , o carregamento do consumidor de um slot altera seu estado para ser NIL . O slot é um spinlock para seu único produtor e um threads de consumo.

Essas filas antecipam que um thread que faz push ou pop pode completar a etapa 1 e depois ser antecipado antes de concluir a etapa 2.

Um algoritmo é livre de bloqueio se houver progresso garantido em todo o sistema. Essas filas garantem o progresso em todo o sistema pelas seguintes propriedades:

Cada push é independente de qualquer push anterior. Um push incompleto (antecipado) por um thread do produtor não afeta push de nenhum outro thread.
Cada pop é independente de qualquer pop anterior. Um pop incompleto (antecipado) por um thread de consumidor não afeta pop de nenhum outro thread.
Um push incompleto (antecipado) de um thread do produtor afeta apenas um thread do consumidor que pop um elemento a partir deste slot de fila específico. Todos os outros threads pop s não são afetados.
Um pop incompleto (antecipado) de um thread de consumidor afeta apenas um fio produtor push um elemento para esse slot de fila específico, enquanto espera que ele tenha sido consumido há muito tempo, no cenário improvável que os produtores envolveram todo o buffer de anel enquanto esse consumidor não concluiu seu pop . Todos os outros threads push e pop não são afetados.

Preempção

A preempção do encadeamento do agendamento de tarefas do Linux é algo que nenhum processo de espaço do usuário deve poder afetar ou escapar, caso contrário, qualquer aplicativo malicioso exploraria isso.

Ainda assim, há algumas coisas que se pode fazer para minimizar a preempção dos threads de aplicativos de missão crítica:

Use aula de agendamento de SCHED_FIFO em tempo real para seus threads, por exemplo, chrt --fifo 50 <app> . Um thread de maior prioridade SCHED_FIFO ou manipulador de interrupção do kernel ainda pode antecipar seus threads SCHED_FIFO .
Use a mesma prioridade fixa de agendamento em tempo real para todos os threads acessando os mesmos objetos de fila. Os tópicos em tempo real com diferentes prioridades de agendamento que modificam um objeto de uma fila podem causar inversão prioritária e impasse. Usando a classe de agendamento padrão SCHED_OTHER com suas prioridades ajustadas dinamicamente derrota o objetivo de usar essas filas.
Desative a aceleração do tópico em tempo real para impedir que os threads SCHED_FIFO em tempo real sejam acelerados.
Isole os núcleos da CPU, para que nenhum manipulador ou aplicativos de interrupção seja executado nele. Os aplicativos de missão crítica devem ser explicitamente colocados nesses núcleos isolados com taskset .
PIN Threads em núcleos específicos, caso contrário, o agendador de tarefas continua movendo os threads para outros núcleos de CPU ociosos para nivelar os núcleos da CPU de tensão/tear induzidos pelo calor. Manter um encadeamento em execução em um mesmo núcleo da CPU maximiza a taxa de acerto do cache da CPU. Mover um thread para outro núcleo da CPU incorre, caso contrário, o cache da CPU se debate.

As pessoas geralmente propõem limitar a espera ocupada com uma chamada subsequente para std::this_thread::yield() / sched_yield / pthread_yield . No entanto, sched_yield é uma ferramenta errada para bloqueio, pois não se comunica com o kernel do sistema operacional, o que o thread está esperando, para que o agendador de threads do sistema operacional nunca possa agendar o thread de chamada para retomar no momento certo quando o estado compartilhado mudou (a menos que não haja outros threads que possam ser executados nesse núcleo da CPU, para que o chamador resuma imediatamente). Consulte a seção Notas em man sched_yield e um tópico do kernel Linux sobre sched_yield e spinlocks para obter mais detalhes.

No Linux, existe o tipo mutex PTHREAD_MUTEX_ADAPTIVE_NP , que ocupam um mutex bloqueado para várias iterações e depois faz um syscall bloqueador no kernel para desschedule o segmento de espera. Nos benchmarks, era o pior desempenho e não consegui encontrar uma maneira de fazê -lo melhor, e é por isso que não está incluído nos benchmarks.

Nos CPUs Intel, pode -se usar os 4 registros de controle de depuração para monitorar a região de memória spinlock para acesso a gravar e esperar usando -o select (e seus amigos) ou sigwait (consulte perf_event_open e uapi/linux/hw_breakpoint.h para obter mais detalhes). Um garçom de spinlock poderia se suspender com select ou sigwait até que o estado de spinlock seja atualizado. Mas existem apenas 4 desses registros, para que essa solução não escalasse.

Benchmarks

Visualize os gráficos de rendimento e referência de latência.

Metodologia

Existem alguns comportamentos do sistema operacional que complicam o benchmarking:

O agendador da CPU pode colocar threads em diferentes núcleos da CPU a cada execução. Para evitar que os threads sejam fixados em núcleos específicos da CPU.
O agendador da CPU pode antecipar tópicos. Para evitar que a prioridade SCHED_FIFO em tempo real 50 seja usada para desativar a expiração quântica do horário do agendador e tornar os threads não preventáveis por processos/threads prioritários mais baixos.
Trema de thread em tempo real desativada.
A randomização do espaço de endereço adverso pode causar conflitos extras de cache da CPU, bem como outros processos em execução no sistema. Para minimizar os efeitos desse benchmarks executável, é executado pelo menos 33 vezes. Os gráficos de referência exibem valores médios. A dica de ferramenta do gráfico também exibe os valores de desvio padrão, mínimo e máximo.

Desempenho de referência das filas de um produtor único boost::lockfree::spsc_queue , moodycamel::ReaderWriterQueue e essas filas no modo de produtor único-consumidor deve ser idêntico porque implementam exatamente o mesmo algoritmo usando exatamente a mesma carga atômica e as instruções atômicas. boost::lockfree::spsc_queue A implementação reencomatada naquele momento não tinha otimizações para minimizar a contenção de cache L1D, a maleta de ramificação a frio ou as barracas de pipeline de questões mais sutis notáveis apenas no código de montagem gerada.

Eu só tenho acesso a algumas máquinas X86-64. Se você tiver acesso a hardware diferente, sinta-se à vontade para enviar o arquivo de saída de scripts/run-benchmarks.sh e incluirei seus resultados na página de referência.

Páginas enormes

Quando estão disponíveis páginas enormes, os benchmarks usam páginas enormes de 1x1 GB ou 16x2MB para as filas para minimizar as perdas do TLB. Para ativar páginas enormes, faça uma de:

 sudo hugeadm --pool-pages-min 1GB:1
sudo hugeadm --pool-pages-min 2MB:16

Como alternativa, você pode ativar o enorme Páginas transparentes em seu sistema e usar um alocador de consciência da enorme página, como o TCMalloc.

Trenação de threads em tempo real

Por padrão, o Linux Scheduler acelera os threads em tempo real do consumo de 100% da CPU e isso é prejudicial ao benchmarking. Detalhes completos podem ser encontrados na programação em grupo em tempo real. Para desativar a limitação de threads em tempo real:

 echo -1 | sudo tee /proc/sys/kernel/sched_rt_runtime_us >/dev/null

Referência de taxa de transferência e escalabilidade

N Tópicos produtores empurram um número inteiro de 4 bytes para a mesma fila, n threads de consumidores recebem os números inteiros da fila. Todos os produtores publicam 1.000.000 de mensagens no total. O tempo total para enviar e receber todas as mensagens é medido. O benchmark é executado de 1 produtor e 1 consumidor até (total-number-of-cpus / 2) produtores / consumidores para medir a escalabilidade de diferentes filas.

Referência de pingue-pongue

Um tópico publica um número inteiro para outro tópico através de uma fila e aguarda uma resposta de outra fila (2 filas no total). Os benchmarks mede o tempo total de 100.000 pingue-pongue, o melhor de 10 corridas. A contenção é mínima aqui (1-produtor-1-consumidor, 1 elemento na fila) para conseguir e medir a menor latência. Relata o tempo médio de ida e volta.

Contribuindo

As contribuições são mais do que bem -vindas. .editorconfig e .clang-format podem ser usados para corresponder automaticamente a formatação de código.