Engine Peredvizhnikov: um motor de jogo lock-free escrito em C++20

 (github.com/eduard-permyakov)
4 pontos por GN⁺ 2023-09-11 | 1 comentários | Compartilhar no WhatsApp
  • Um motor de jogo totalmente lock-free escrito em C++20, que implementa o modelo de atores para computação concorrente sobre as primitivas de corrotina da linguagem
  • Usando a abstração de modelo de atores, é possível desenvolver lógica paralela complexa isolada dos detalhes de sincronização entre threads
  • A implementação totalmente lock-free oferece garantia de progresso mesmo em casos de encerramento arbitrário de threads, prevenção de deadlocks, latência previsível para reação a eventos críticos e tolerância a falhas
  • Também garante que o motor continue em execução mesmo que uma das threads de trabalho seja encerrada de forma assíncrona
  • A implementação inclui Software Transactional Memory, filas lock-free, primitivas de serialização lock-free, std::atomic_shared_ptr, scheduler lock-free, alocador de memória lock-free e DAG em tempo de compilação
  • Os algoritmos lock-free, a justificativa de design e os benchmarks são abordados no documento Peredvizhnikov Engine: Design and Implementation of a Completely Lock-Free Scheduler
  • Para ajudar no design orientado a dados, implementa um banco de dados em memória otimizado para acesso por componente e com suporte a grandes conjuntos de dados
  • O banco de dados em memória é baseado nas estruturas Flat Hash Map e Bitwise Trie with Bitmap
  • No momento, a única plataforma suportada é Linux, e a compilação do código-fonte requer Clang++ 16
  • O código-fonte é fornecido sob a licença GPLv3, e permissões para usar parte ou todo o código sob outras licenças podem ser concedidas caso a caso

Leituras relacionadas

1 comentários

 
GN⁺ 2023-09-11
Opiniões no Hacker News

  • No framework de actors, usa-se um std::deque comum como fila de ponteiros para métodos, e ao colocar mensagens na fila o bloqueio é feito no estilo Benaphore
    Originalmente, como um Futex, ele usa operações atômicas junto com primitivas de bloqueio, mas a minha primitiva de bloqueio funciona como uma combinação de spinlock/mutex conforme o número de tentativas. Nos benchmarks, é muito raro a função de push de mensagens bloquear, e a chance de troca de contexto pelo sistema operacional também é baixa; portanto, mesmo que ocasionalmente uma thread bloqueada seja retirada da CPU, isso não acontece com frequência suficiente para justificar o custo de um algoritmo lock-free
    Em resumo, uma fila não lock-free é muito mais rápida do que uma fila lock-free, mas é preciso aceitar que, muito raramente, haverá uma longa latência por causa de uma troca de contexto em que ninguém consegue adquirir o lock. Em hardware moderno, é possível enfileirar 10 milhões de mensagens por segundo por thread worker

    • Você disse “originalmente Futex”, mas Benaphore é uma ideia bastante antiga, e Futex não é simplesmente um “Benaphore ao estilo Linux”
      O ponto central é que um objeto do kernel, isto é, uma primitiva de bloqueio separada, na verdade não é necessária. É aí que a ideia deixa de ser “um jeito que todo mundo conhece” e passa a ser “um recurso que precisa entrar no sistema operacional agora”
      No design do Futex, em vez de um objeto de sincronização do sistema operacional para lidar com colisões, o sistema operacional mantém uma lista de mapeamentos endereço→thread. Se a thread T dorme em um futex no endereço X, a lista passa a registrar que X aponta para T; quando chega uma solicitação para acordar o futex X, o sistema operacional percorre a lista e acorda T
      A diferença aparece nas limitações. Algo como um Benaphore era um recurso caro de todo o sistema, e lembro que o BeOS permitia algo como 65.536 por máquina. Já um Futex é apenas memória, então não há motivo para impor esse tipo de limite
    • Em um texto interessante como esse, deveria haver link para o código. Isso comprovaria as afirmações, e gente como eu acharia a ideia interessante e iria querer ver a implementação imediatamente
    • Varia muito conforme os detalhes da situação. Se houver muita contenção, o desempenho cai drasticamente, e até instruções atômicas podem virar gargalo (https://stackoverflow.com/q/2538070)
      Acho correta a observação de que, em muitos casos, basta usar locks e não se preocupar. Mas também há aplicações ou situações em que dá para fazer melhor. Com cuidado, um consumidor pode retirar todos os itens da fila com uma única operação de lock, enquanto os produtores sinalizam o consumidor, aumentando a eficiência e a vazão da fila. Por exemplo, não se deve sinalizar a cada item inserido, mas apenas quando a fila estava vazia e deixa de estar
    • Estruturas de dados lock-free não fazem mais sentido para reduzir o impacto da contenção do que para aumentar a vazão quando há pouca contenção?
    • Esse “custo aceitável” é uma exceção para pessoas com requisitos fortes segundo os quais as longas latências imprevisíveis e raras mencionadas simplesmente não podem acontecer

  • O escalonador lock-free certamente parece interessante, e a linearizabilidade do broadcast de eventos chama atenção em especial. Dito isso, nos benchmarks do artigo, o melhor resultado com 12 pares de actors (e 12 núcleos?) é de 43.500 mensagens por segundo, e o gráfico de núcleo único também fica em cerca de 5.000 mensagens por segundo, o que é surpreendentemente baixo para esse tipo de benchmark
    Ainda não consegui reproduzir, porque o engine exige Linux e, mais importante, x86 (por causa das instruções em assembly), mas eu esperaria pelo menos cerca de 1 milhão de requisições por segundo por par de actors. Pensando em casos como Erlang, qualquer valor abaixo disso torna o overhead proibitivamente alto
    Este engine se concentra na passagem de mensagens, mas, pela minha experiência, esse modelo é muito difícil de lidar. Máquinas de estados são difíceis, e ficam ainda mais difíceis ao trabalhar com vários sub-actors. No fundo, vejo actors mais como uma forma de isolar estado sem locks do que como passagem de mensagens. Acho que os actors do Swift acertaram: usar chamadas de método em vez de mensagens não só facilita o raciocínio, como também explicita pontos adicionais em que o contexto pode mudar em tempo de execução, sem necessariamente envolver o escalonador. Estado compartilhado é lento e prejudica a escalabilidade
    Recentemente, criei uma biblioteca header-only com corrotinas de C++20 que implementa algo parecido com os actors do Swift. Se houver interesse, procure por “coroactors”. Sem contenção, cerca de 10 milhões de requisições por segundo; com contenção e dependência do escalonador, até 1 milhão a 3 milhões de requisições por segundo me pareceram overhead alto demais. Especialmente em comparação com chamadas comuns de métodos sobre estado compartilhado protegido por mutex. Corrotinas tendem a ser contagiosas: cada vez mais funções viram corrotinas async, e em codebases não triviais há muitas chamadas de corrotina ou passagem de mensagens. Por isso, o overhead precisa ser o menor possível; caso contrário, passa-se mais tempo trocando de tarefa do que fazendo trabalho útil

  • Diz que é baseado em actors, e explica que enviar uma mensagem a um actor é equivalente a executar a função do actor sob um mutex. Ou seja, mesmo que N threads enviem mensagens, só 1 thread executa o código do actor, então ele é serializado como com um mutex
    Portanto, tecnicamente pode até ser “totalmente lock-free”, mas, enquanto usar actors, não há melhoria de paralelização

    • Não necessariamente. Em um actor baseado em mutex, se a thread do actor for suspensa, esse mutex — ou seja, o código do actor — permanece bloqueado até a thread original ser retomada. Como o mutex pertencente à thread suspensa está travado, mesmo que haja mais paralelismo, não dá para “reiniciar” ou “retomar” aquele código do actor
      Esta implementação depende bastante de funções reiniciáveis, para permitir que o trabalho de um actor que já estava em andamento, mas foi suspenso, seja pego e continuado por outra thread paralela. Vale ver a página 3 do excelente documento de design: https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...
      Então, estritamente falando, talvez não seja “mais paralelo” (já que o número de actors é o mesmo), mas parece aproveitar melhor mais paralelismo para concluir o mesmo conjunto de tarefas
    • Onde está escrito que “enviar uma mensagem a um actor é equivalente a executar a função do actor sob um mutex”? Pelo que entendo, o modelo de actors significa passagem de mensagens e execução assíncrona. Pelo contrário: se houver N actors, N threads podem executar em paralelo
    • Está certo dizer que não há melhoria de paralelização, mas isso também não reduz o paralelismo. É uma forma diferente de pensar em concorrência e, na minha opinião, mais fácil
      Se for mais fácil raciocinar, também fica mais claro onde haverá contenção sobre os mesmos recursos, o que na prática ajuda a melhorar o paralelismo potencial. Se você notar uma oportunidade específica para o SMP acelerar as coisas, pode se afastar um pouco do modelo de actors e fazer com que várias threads consumam a fila de mensagens; se isso não for possível, basta adicionar mais actors e dividir melhor os dados

  • Alguém já depurou ou fez profiling de uma seção crítica com alta contenção em STM, comparando com uma implementação tradicional com mutex? No fim, é preciso haver algo que arbitre o acesso concorrente à memória compartilhada, e não existe almoço grátis. Mutexes são muito bem otimizados, perfilados e compreendidos
    Já quanto a STM, não sei se está no mesmo nível. Uma transação não poderia ser tentada novamente indefinidamente(?)?

    • Neste caso, o árbitro é o scheduler. Na prática, é ele que chama o bloco assíncrono e, se falhar, potencialmente tenta de novo. No código do post original há blocos atômicos, execução sequencial de blocos e blocos com estado para garantir um acesso por vez
      O ponto central é scheduler.cpp, que usa std::coroutines
      É parecido com async/await em outras linguagens. O scheduler tem uma fila de tarefas (corrotinas) e um pool de threads (N>0) para executá-las
      Aqui, tarefas que contêm dados trocam mensagens entre si. Em troca de maior uso de memória, não é necessário bloqueio
    • Na prática, em uma STM sem starvation, o número de tentativas de uma transação é limitado. Um exemplo é 2PLSF, e há vários outros métodos também https://zenodo.org/record/7886718

  • Isso lembra BEAM, não?
    https://youtu.be/bo5WL5IQAd0?feature=shared

  • Não vi menção a quão difícil é depurar um engine desses

  • Não tenho tempo para ler a implementação, mas, só pelo README, soa como um sistema distribuído clássico entre threads de jogo. Imagino que padrões como retry/backoff sejam comuns

  • “Lock-free” soa legal, mas acho que qualquer código que use operações atômicas em um nível significativo deveria vir acompanhado de uma prova formal e, se possível, verificada por máquina. É difícil demais usar corretamente ordenações atômicas que não sejam consistência sequencial. Já vi código escrito errado várias vezes, e os bugs que surgem disso são os piores

  • Onde está a demo de jogo? Hoje em dia, para ser considerado um game engine, também precisa de ferramentas reais, exporters para Maya ou 3DSMax, e coisas como ferramentas de colaboração, métricas e alertas

    • Discordo. “Game engine” não significa necessariamente “algo capaz de substituir Unity ou Unreal”

  • Dizem que é “lock-free”, mas ainda não parece ser
    export std::mutex iolock{};
    export std::mutex errlock{};
    SDL_PollEvent