Lock-Free Queue em C++ moderno: fila sem mutex de alta performance

O que é uma fila lock-free

Uma fila lock-free (ou fila sem bloqueio) e uma estrutura de dados concorrente que permite que múltiplas threads enfileirem e desenfileirem elementos simultaneamente, sem usar mutex ou semáforos. Em vez de bloquear as threads esperando o recurso ficar livre, ela usa operações atómicas da CPU para garantir consistência.

O termo "lock-free" tem uma definição técnica precisa: pelo menos uma thread sempre avança independentemente do que as outras estejam fazendo. Isso contrasta com estruturas protegidas por mutex, onde uma thread pode bloquear todas as outras indefinidamente se travar ou ser preemptada no momento errado.

Filas lock-free são fundamentais em sistemas de alta performance: jogos (thread de renderização e thread de simulação), sistemas de trading de alta frequência, processamento de áudio em tempo real, motores de eventos e qualquer sistema onde latência previsível e mais importante que throughput máximo. O artigo de Jay Smito no blog pessoal dele, que virou destaque no Hacker News, e um dos melhores guias práticos recentes sobre o assunto em C++ moderno.

Como funciona

A base de uma fila lock-free e a operação Compare-And-Swap (CAS), disponível como operação atómica na CPU. O CAS faz o seguinte atomicamente: se o valor em um endereço de memoria e igual ao esperado, substitui por um novo valor e retorna true. Se não e, não faz nada e retorna false.

Em C++ moderno (C++11 em diante), isso esta disponível via std::atomic e o método compare_exchange_weak/strong. A lógica básica do enqueue em uma fila lock-free e: carregar o ponteiro de cauda, tentar apontar o próximo do no atual para o novo no via CAS, e se o CAS falhar (outra thread chegou na frente), tentar novamente. Esse loop otimista e característico de algoritmos lock-free.

O algoritmo clássico de Michae e Scott (1996) e a base de quase todas as implementações de fila lock-free em uso hoje. O C++ moderno com memory ordering explicito permite implementar esse algoritmo de forma portátil e eficiente, sem depender de instruções específicas de arquitetura.

Principais componentes da implementação

Uma fila lock-free de alta performance em C++ moderno precisa de alguns elementos essenciais:

• Nos com contador de referências: gerenciar a vida útil dos nos e o problema mais difícil em estruturas lock-free, pois não ha secao crítica para proteger a liberação de memoria. Hazard pointers ou contagem atómica de referências são as soluções principais.
• Memory ordering correto: C++ oferece vários ordenamentos de memoria (relaxed, acquire, release, seq_cst). Usar o ordenamento mais fraco possível que ainda garante corretude e crítico para performance.
• Padding para evitar false sharing: colocar dados acessados por threads diferentes na mesma linha de cache causa false sharing, que destrói performance em sistemas multicore. alignas(std::hardware_destructive_interference_size) resolve isso.
• CAS loops com backoff exponencial: em alta contenção, fazer CAS em loop apertado aumenta contenção. Adicionar backoff exponencial (espera crescente) reduz colisões entre threads.

O artigo do Jay Smito detalhado no blog cobre cada um desses pontos com benchmarks comparando implementações diferentes, o que é raro em conteúdo sobre concorrência de baixo nível.

Como começar: implementação básica em C++

Veja uma implementação simplificada de fila lock-free SPSC (Single Producer Single Consumer), mais simples de implementar corretamente e suficiente para muitos casos de uso:

#include <atomic>
#include <array>
#include <optional>

template<typename T, std::size_t Cap>
class SPSCQueue {
    alignas(64) std::atomic<std::size_t> head_{0};
    alignas(64) std::atomic<std::size_t> tail_{0};
    std::array<T, Cap> buf_;

public:
    // Produtor: retorna false se a fila estiver cheia
    bool push(const T& val) {
        auto tail = tail_.load(std::memory_order_relaxed);
        auto next = (tail + 1) % Cap;
        if (next == head_.load(std::memory_order_acquire))
            return false; // fila cheia
        buf_[tail] = val;
        tail_.store(next, std::memory_order_release);
        return true;
    }

    // Consumidor: retorna nullopt se a fila estiver vazia
    std::optional<T> pop() {
        auto head = head_.load(std::memory_order_relaxed);
        if (head == tail_.load(std::memory_order_acquire))
            return std::nullopt; // fila vazia
        T val = buf_[head];
        head_.store((head + 1) % Cap, std::memory_order_release);
        return val;
    }
};

Para MPMC (Multiple Producer Multiple Consumer), a implementação e mais complexa e requer CAS para garantir exclusão mutua na atualização de head e tail.

Exemplo prático

Veja como usar a fila SPSC em um cenário de produtor-consumidor típico, por exemplo em um motor de áudio onde a thread de callback de áudio consome amostras produzidas por outra thread:

#include <thread>
#include <iostream>

int main() {
    SPSCQueue<float, 1024> audioQueue;

    // Thread produtora (geração de sinal)
    std::thread producer([&] {
        float phase = 0.0f;
        while (true) {
            // Gera amostra de seno
            float sample = std::sin(phase);
            phase += 0.01f;

            // Tenta enfileirar; se cheia, descarta (trade-off de áudio)
            audioQueue.push(sample);
        }
    });

    // Thread consumidora (callback de áudio - latência crítica)
    std::thread consumer([&] {
        while (true) {
            if (auto sample = audioQueue.pop()) {
                // Envia para hardware de áudio
                // sem mutex, sem stall
                processAudio(*sample);
            }
        }
    });

    producer.join();
    consumer.join();
    return 0;
}

Comparação com alternativas

Quando usar cada abordagem:

• std::queue + std::mutex: a escolha padrão. Simples, correta, sem problemas de ABA ou gerenciamento de memoria. Use quando a latência do mutex e aceitável (microsegundos) e a contenção não e crítica. 95% dos casos de uso reais.
• Fila lock-free SPSC: ideal quando ha exatamente um produtor e um consumidor. Implementação muito simples, performance excelente, sem risco de ABA. Áudio, rendering pipeline, I/O assync.
• Fila lock-free MPMC: necessária quando ha múltiplos produtores e/ou consumidores. Muito mais complexa, mas oferece throughput superior ao mutex em alta contenção.
• Filas de bibliotecas (Folly, libcds, etc.): biblioteca Folly do Facebook (open source) tem implementações de fila lock-free battle-tested. Para produção, prefira uma biblioteca auditada a implementar do zero.
• Intel TBB concurrent_queue: implementação robusta para produção em ambientes Intel. Boa documentação e garantias de performance.

A regra prática: comece com mutex. Se os benchmarks mostrarem que o mutex e o gargalo real (não só suspeito), ai considere lock-free. Premature optimization com lock-free e uma fonte clássica de bugs sutis e difíceis de reproduzir.

Pontos positivos e limitações

Pontos positivos de filas lock-free:

• Latência muito mais previsível: sem risco de thread ficar bloqueada por tempo indeterminado
• Melhor throughput em alta contenção em sistemas com muitos cores
• Imunidade a deadlocks por definição (não ha locks para deadlock)
• Essencial para sistemas de tempo real onde stall e inaceitável

Limitações reais:

• Muito mais difícil de implementar corretamente do que estruturas com mutex
• Debugging e profiling são mais difíceis: bugs de concorrência lock-free são intermitentes e não-deterministas
• O problema ABA e uma armadilha clássica para implementações ingénuas
• Gerenciamento de memoria e complexo sem garbage collector
• Em baixa contenção, mutex pode ser mais rápido por evitar CAS loops retrying

Casos de uso reais

1. Motores de áudio: o callback de áudio roda em thread de tempo real com deadline fixo. Qualquer stall de mutex pode causar glitch audível. Filas SPSC lock-free são o padrão industrial para comunicação entre thread de processamento e thread de áudio.

2. Sistemas de trading de alta frequência: latência de microsegundos ou menos e requisito. Mutex com contenção pode adicionar dezenas de microsegundos imprevistos. Filas lock-free são parte fundamental da arquitetura de low-latency trading.

3. Game engines: comunicação entre thread de renderização (que não pode ser bloqueada) e thread de simulação de física/AI. SPSC lock-free e o padrão em engines como Unreal e motores proprietários de AAA.

4. Sistemas de logs de alta performance: gravar logs em thread separada sem bloquear a thread principal. Com SPSC, a thread principal empurra para a fila sem nunca bloquear; a thread de I/O consome e escreve em disco.

Dicas e boas práticas

Vale a pena implementar do zero?

Para aprendizado e para entender profundamente concorrência em C++, implementar uma fila lock-free do zero e valioso. Você vai aprender sobre memory ordering, o modelo de memoria do C++, ABA, false sharing e hazard pointers de forma muito mais concreta do que lendo apenas teoria.

Para produção, a resposta quase sempre e: use uma biblioteca. O custo de bugs sutis de concorrência em produção (que aparecem apenas sob carga específica em hardware específico) e muito maior que o custo de adicionar uma dependência auditada.

O próximo passo e ler o artigo original do Jay Smito em blog.jaysmito.dev/blog/04-fast-lockfree-queues, implementar a versão SPSC acima e testar com ThreadSanitizer. Depois, compare com std::queue + std::mutex em um benchmark real para ver se o delta justifica a complexidade no seu caso específico.