Spice: técnica de paralelismo refinado em Zig com overhead abaixo de nanossegundos

• Spice é um projeto de pesquisa que busca manter o overhead abaixo de 1 ns mesmo ao adicionar possibilidade de execução paralela a funções em Zig usando heartbeat scheduling
• O design central marca com fork um trabalho que outra thread pode processar, mas usa uma estrutura de fallback em que, se nenhuma thread pegar o trabalho, a thread atual o executa diretamente no join
• No benchmark de soma de árvore binária com 100 milhões de nós, o Rayon teve overhead de cerca de 15 ns com 1 thread e ficou em cerca de 4,5x o baseline com 16 threads, enquanto o Spice obteve quase intacto um ganho de cerca de 11x sobre o baseline com 16 threads
• Em tarefas de execução muito curta, como 1000 nós, o Rayon chegou a ficar 60 vezes mais lento com 32 threads, enquanto o Spice, ao julgar que não há necessidade de paralelismo, mantém as threads extras adormecidas e não inicia multithreading
• A implementação atual ainda carece de testes, documentação, suporte a arrays e slices, e benchmarks adicionais, usa bastante @panic, e o autor afirma que é preciso reconhecer muitas limitações antes de uso em produção

---

O problema que o Spice tenta resolver

• Spice é um projeto para implementar paralelismo muito granular em Zig com baixo overhead
• O objetivo é que o usuário não precise se preocupar o tempo todo se adicionar paralelização vai deixar o programa mais lento
• Para maximizar desempenho ainda são necessários benchmarks cuidadosos, mas, em geral, o Spice é projetado para que adicionar paralelismo traga quase nenhum overhead real
• O projeto é principalmente um projeto de pesquisa, e quem considerar uso em produção deve verificar as limitações primeiro
• Em uma atualização de setembro de 2024, foi apresentado Chili, um port dessa ideia para Rust

Forma de uso e API principal

• As funções paralelas do Spice recebem *spice.Task como parâmetro e o usam para coordenar o trabalho
• Chamadas recursivas ou chamadas a funções que podem ser paralelizadas não devem ser feitas diretamente, mas por meio de t.call
• fork define um trabalho que outra thread pode executar
• A função também deve continuar fazendo trabalho útil por conta própria após o fork
• join espera pela conclusão do trabalho por outra thread, mas pode retornar null
  • null sinaliza que nenhuma outra thread pegou aquele trabalho
  • Nesse caso, a thread atual deve executar esse trabalho diretamente

O design de “nem todo trabalho vem da fila”

• A ideia central do Spice é que nem todo trabalho começa na fila
• fork informa que existe trabalho que outra thread pode executar, mas, se as outras threads estiverem ocupadas, a thread atual processa tudo como em uma execução sequencial normal
• Quando não há possibilidade real de execução paralela, no hot path o Spice basicamente só faz push/pop na fila, sem inspecionar de fato os itens da fila
• A coordenação real com outras threads acontece em um heartbeat fixo
  • Aproximadamente a cada 100 microssegundos, a thread verifica sua fila de trabalho atual
  • Ela entrega o trabalho do topo da fila a outra thread que esteja esperando
  • Como a frequência do heartbeat é baixa, mesmo gastar algumas centenas de ns mantém o overhead total pequeno

Comparação com benchmarks do Rayon

• A soma de uma árvore binária de 100 milhões de nós é um caso em que a computação real é muito rápida, então o overhead do framework de paralelismo aparece com força
• Tanto o Rayon em Rust quanto o Spice são comparados em um formato de API fork/join fácil de ler e raciocinar
• No benchmark do Rayon, o overhead foi medido em cerca de 15 ns
  • Houve aumento de 7,48 ns para 22,99 ns
  • Com 4 threads, ele basicamente voltou ao nível do desempenho sequencial, mas usando 4 vezes mais CPU
  • Com 16 threads, teve cerca de 14x de aceleração em relação ao próprio baseline do Rayon, e cerca de 4,5x em relação ao baseline
• O Spice mostrou cerca de 11x de aceleração ao ir de 1 thread para 16 threads
  • A escalabilidade é um pouco pior que a do Rayon, mas, por causa do baixo overhead, o ganho sobre o baseline também se mantém quase intacto
• O benchmark foi executado em uma instância Google Cloud c4-standard-16, em ambiente de 16 núcleos
• Não está claro por que o baseline em Zig foi cerca de 2 vezes mais rápido que o baseline em Rust
  • Segundo o compiled assembly, Rust salva 5 registradores na pilha e Zig salva 3

Comportamento em tarefas pequenas

• A soma de árvore binária com 1000 nós é uma tarefa muito curta, com tempo total de execução na faixa de poucos microssegundos
• Nesse caso, o Rayon mostrou overhead ainda maior, de cerca de 19 ns, e o desempenho piorou à medida que mais threads foram adicionadas
• Ao usar 32 threads em uma máquina de 16 núcleos, o tempo total de execução ficou 60 vezes mais lento
  • Isso não significa necessariamente que a mesma desaceleração ocorreria em uma máquina de 32 núcleos
  • Ainda assim, esse comportamento de escalabilidade é visto como preocupante
• O critério tradicional para paralelização costuma ser “só vale a pena quando há trabalho suficiente”
  • Pode ser necessário descobrir o que conta como “trabalho suficiente” por meio de benchmarks para cada entrada
  • Em entradas como árvores binárias, em que não dá para saber o tamanho total só olhando a raiz, é difícil decidir se o trabalho é pequeno
  • Se 90% da carga de trabalho for composta por entradas pequenas, uma desaceleração extrema pode virar problema
  • À medida que o programa evolui, o critério de trabalho suficiente também pode mudar
• No mesmo caso de 1000 nós, o Spice conclui que o tempo de execução é curto demais e não inicia multithreading
  • As threads extras permanecem dormindo
  • Os núcleos podem ser usados para executar outros programas

Diferença entre work-stealing e Spice

• O Spice fornece um modelo fork/join, normalmente implementado com work-stealing
• No work-stealing tradicional, cada thread tem sua fila local de trabalho e, quando a fila esvazia, rouba trabalho do fim da fila de outra thread
• As ineficiências do work-stealing são resumidas em três pontos
  • Todo trabalho vira uma forma genérica de “chamada dinâmica de função”, o que gera custo de dispatch dinâmico
  • A fila local, na prática, é uma fila da qual todas as threads podem roubar, exigindo operações atômicas
  • Em contenção de fila, ocorre spinning, o que em certas condições pode deixar tudo 10 a 100 vezes mais lento
• O Spice reduz diretamente essas ineficiências
  • O dispatch dinâmico da fila de trabalho só é usado quando o trabalho é enviado a outra thread
  • O trabalho executado dentro de uma única thread usa chamadas normais de função
  • O push na fila de trabalho é tratado com ponteiro de pilha, frame atual da pilha e salvamento de registradores, sem sincronização com outras threads
  • Não há loop while girando sem wait(), então não existe spinning

Detalhes de implementação

• Otimização com dispatch estático

  • O Spice parte do princípio de que a maioria dos trabalhos marcados com fork não será pega por outra thread, então duplica internamente esse caminho de execução dentro da função
  • Se o trabalho não for executado por outra thread, o programa se comporta como uma versão sequencial com apenas alguns branches previsíveis a mais
  • Essa estrutura favorece otimizações de código como inlining e também a execução pela CPU

• Sinal de heartbeat de baixo overhead

  • O heartbeat scheduling faz o agendamento localmente e com baixa frequência
  • Aproximadamente a cada 100 microssegundos, a thread olha sua fila local de trabalho e envia trabalho para outra thread
  • Se forem gastos 100 ns a cada 100 microssegundos, o overhead total fica em torno de 0,1%
  • Em vez de sinais do sistema operacional, usa-se uma abordagem cooperativa com chamadas a tick()
    • Ao usar o helper t.call, tick() é chamado automaticamente
    • Uma thread separada de heartbeat alterna periodicamente de false para true o valor atômico de heartbeat de cada thread
    • tick() lê esse valor e, quando ele está true, executa o código de heartbeat
  • A função de heartbeat deve ser marcada como cold; caso contrário, o overhead fica muito maior

• Mutex global sem contenção

  • O pool de threads do Spice tem um único mutex que pode ser travado de vários pontos
  • Um mutex global só vira problema quando as threads realmente ficam bloqueadas nele
  • No Spice, por causa do heartbeat, normalmente apenas uma thread executa o heartbeat por vez
  • Nenhum código do usuário é executado enquanto o lock está segurado; ele protege apenas leituras e escritas simples de memória que terminam em tempo constante

• Lista duplamente ligada sem branches

  • O Spice usa uma lista duplamente ligada para rastrear a fila de trabalho
  • fork() faz append no fim, join() faz pop do fim se ainda houver item, e o envio para um worker em segundo plano faz pop pela frente
  • Um append comum exigiria um branch para verificar se a lista está vazia
  • O Spice usa um nó sentinela de cabeça que sempre existe, de modo que a lista nunca fica vazia e push/pop podem ser feitos sem branches

• Uso mínimo de pilha

  • Future pode estar nos estados queued ou executing
  • O heartbeat converte um future queued em executing
  • O estado extra necessário para executing fica em uma struct separada alocada em pool, reduzindo o uso de pilha do future em estado queued
  • É usada uma forma manual de tagged union, distinguindo queued/executing pelo fato de o primeiro campo prev_or_null ser ou não null

• Passagem de valores por registradores

  • Task contém um ponteiro para o worker proprietário e um ponteiro para a cauda da fila de trabalho
  • Como o LLVM muitas vezes passa structs pela pilha, o Spice define callWithContext, que recebe worker e job_tail como parâmetros separados
  • Essa função é chamada de forma a sempre ser inline, fazendo com que os ponteiros sejam passados por registradores

Base de pesquisa e trabalhos relacionados

• O Spice foi criado com base em pesquisas sobre heartbeat scheduling
• “The best multicore-parallelization refactoring you've never heard of” é um artigo que apresenta brevemente o conceito de heartbeat scheduling; ele foca em um único caso de uso, mas explica a abordagem de forma generalizável
  • A solução do artigo transforma o código em continuation-passing style para alternar entre execução sequencial e paralela
  • O Spice começou como um experimento com essa abordagem, mas mostrou overhead acima de 10 ns
• “Heartbeat scheduling: provable efficiency for nested parallelism” é o artigo que apresentou heartbeat scheduling pela primeira vez
  • Ele é rico em informações conceituais, mas a implementação é baseada em integração com interpretador e o foco maior está nas garantias teóricas
• “Task parallel assembly language for uncompromising parallelism” é um trabalho posterior que melhorou o desempenho do heartbeat com linguagem assembly customizada e sinalização do SO
  • A avaliação é que seria difícil integrar isso a linguagens já existentes

Limitações atuais

• O Spice pode ter comportamentos bruscos quando usado incorretamente
  • Em especial, é sensível à forma como fork e join são usados
  • Isso deveria ser melhorado com verificações em tempo de compilação, assertions em modo debug e mudanças de API
• Há muito código de concorrência, mas a cobertura de testes é 0
• Não existe suporte nativo para processar cada elemento de arrays e slices, um caso de uso comum para paralelismo granular
• Faltam bons documentos explicando como usar
• No momento, ele foi testado principalmente com um único benchmark pequeno
  • O autor considera que esse benchmark deveria ser representativo, mas mais benchmarks são necessários para validar os resultados
• O tratamento de erros usa muito @panic
  • Para ser visto como uma biblioteca Zig adequada, seria preciso considerar melhor mais casos de erro
• São necessários mais benchmarks e testes para saber o quão bem ele funciona em ReleaseSafe do Zig
• A base de código inteira tem cerca de 500 linhas, e o autor atualmente não tem um plano ativo de desenvolvimento para melhorar o Spice por falta de tempo
• Melhorias por meio de forks ou reimplementações em outras linguagens são incentivadas

[GN⁺]

Comentários no Hacker News

• Esta implementação se baseia na linha de pesquisa recente de heartbeat scheduling, amortizando o custo de criar paralelismo para alcançar uma espécie de controle dinâmico automático da granularidade das tarefas
  Artigos relacionados:
  (2018) Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf
  (2021) Task Parallel Assembly Language for Uncompromising Parallelism. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
  (2024) Compiling Loop-Based Nested Parallelism for Irregular Workloads. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
  (2024) Automatic Parallelism Management. https://www.cs.cmu.edu/~swestric/24/popl24-par-manage.pdf

  • Isso é realmente interessante, e quando escrevi o Spice eu só conhecia os dois primeiros artigos
    Pretendo dar uma olhada nos dois últimos também

• Não li o código em detalhe, mas a expressão overhead abaixo de 1 nanossegundo parece um slogan de marketing passível de induzir ao erro
  À primeira vista, parece uma medição complicada de “tempo por tarefa” calculada em uma situação em que o número de threads é muito menor que o número de “tarefas”

  • Sou o autor
    Eu já imaginava que parte das pessoas reagiria negativamente a essa expressão, mas a intenção era ajudar a entender melhor exatamente quando e como usar Spice e Rayon
    Recomendo ler a documentação de benchmark: https://github.com/judofyr/spice/blob/main/bench/README.md
    Normalmente, ao comparar código paralelo, as pessoas só comparam uma implementação sequencial/de referência com uma implementação paralela usando todas as threads (16). No caso de 100M, os números do Rayon foram 7.48ns para a versão sequencial e 1.64ns para o Rayon, então é fácil encerrar dizendo “o Rayon foi 4,5 vezes mais rápido neste problema, mas usou 16 threads, então a comparação não se encaixa bem”. Isso está correto, mas fica difícil aprender como aplicar isso a outros tipos de problema
    Quando se executa o mesmo benchmark com diferentes quantidades de threads, aparece algo mais interessante. O scheduler do Rayon é bastante bom em distribuir trabalho para threads separadas, mas o mecanismo geral de execução das tarefas tem um overhead de cerca de 15ns. Mesmo que este programa seja um exemplo completamente inútil, ainda dá para aprender algo que pode ser aplicado depois: para usar Rayon, a menor unidade de trabalho provavelmente precisa ser maior que aproximadamente 7ns. A menos, claro, que reduzir a latência total seja mais importante do que sacrificar o throughput total
    A documentação do Rayon não dá números e apenas diz: “conceitualmente, uma chamada a join() é parecida com criar duas threads para executar uma closure cada, mas a implementação é bem diferente e tem overhead muito baixo”: https://docs.rs/rayon/latest/rayon/fn.join.html
    Se eu quisesse induzir ao erro, teria dito “o Spice dá ganho de 10x e o Rayon 4,5x, então o Spice é duas vezes mais rápido que o Rayon”
  • Para que “overhead abaixo de 1 nanossegundo” fosse um slogan de marketing enganoso, Spice com 1 thread - implementação de referência não paralela teria de ser maior que 1ns
    Os resultados dos testes sustentam a afirmação: https://github.com/judofyr/spice/tree/main/bench
  • Acho que isso também corresponde ao nicho ecológico do Rayon citado aqui
    É uma estrutura em que você precisa processar de milhares a milhões de tarefas, quer paralelizar ao máximo dentro de algumas dezenas de núcleos e não quer que o overhead de scheduling consuma tudo, então faz sentido olhar o overhead por tarefa
  • Quando isso apareceu no Reddit ontem, eu manifestei preocupação com os benchmarks
    Os benchmarks afirmam 0.36ns de overhead por chamada, mas incluem apenas a função de cálculo. Há uma segunda thread fazendo o scheduling, e isso não entra no número de overhead. Parece ter sido executado em uma máquina com hyperthreading, 8 núcleos, ou seja, 16 threads, e assumindo 3GHz isso literalmente dá um overhead de um ciclo
    O overhead aumenta com cada thread adicional por causa da contenção de locks. Em 16 threads, sobe para 3.6ns, um aumento de 10x. É uma suposição, mas se for isso, então os 0.36ns de overhead incluem locks sem contenção, o que é impossível. Também há mais coisas estranhas nos dados do benchmark. Pode ser que eu não esteja entendendo o que realmente está sendo medido, ou pode haver um bug no código do benchmark
    Multiplicando todos os valores, parece que o tempo está sendo medido em milissegundos. Quando o tempo de execução é calculado e convertido para milissegundos, o resultado cai em valores inteiros. Normalmente, quem faz benchmark não usa precisão melhor do que isso? Pode ser que tenham usado apenas time prog, então os dados ficaram muito ruidosos, ou que tenham escolhido uma métrica totalmente inútil para esse objetivo
  • Lendo o README, acho que a afirmação do título é explicada com muita precisão quanto ao que exatamente significa
    Não existe título totalmente livre de ambiguidade, e este está ok. O que eu entendi foi apenas que se trata de uma biblioteca com latência extremamente baixa segundo algum critério de medição, e bastou verificar no README qual era esse critério. Está bem claro.

• Não sou muito familiarizado com esta área, mas gostei do modelo de concorrência apresentado aqui.
  O README também foi muito bem escrito, e só de ler já dá para ter uma boa ideia do que está acontecendo. Ainda assim, houve alguns pontos que me deixaram com uma pulga atrás da orelha. Felizmente, o código é bem fácil de ler.

  • Ao compilar em modo Debug com zig build, obtive Baseline,3.92809172 e Spice 1 thread,19.1012624.
    Ao compilar em modo ReleaseSafe com zig build --release=safe, obtive Baseline,3.264224280000001 e Spice 1 thread,3.78043278.
    Então, o Spice sofre uma perda de desempenho considerável se não for um build de release. A implementação de referência não fica tão lenta assim no modo Debug do Zig.
    A versão usada é zig 0.13.0.

• É um trabalho de pesquisa interessante, e não só o código em si, mas também a justificativa das decisões é boa, além de a documentação estar bem escrita.
  O artigo de 2018 sobre heartbeat scheduling também vale a leitura: https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf

• Lista de limitações do projeto: https://github.com/judofyr/spice?tab=readme-ov-file#limitati...

  • Este projeto é excelente, e o autor merece muito crédito por ter investido tempo para fazê-lo funcionar e compartilhá-lo com a comunidade do HN.
    O HN também é conhecido por, em geral, reagir com críticas ou pessimismo em excesso.
    Também é positivo que o autor reconheça as limitações do próprio projeto, o que acaba bloqueando de antemão boa parte do cinismo habitual.
    Na parte que diz “Falta de testes: o Spice tem muito código de concorrência complicado, mas a cobertura de testes é 0. Isso precisa melhorar para que o Spice possa ser usado com responsabilidade em trabalhos importantes”, penso que, deixando de lado o teste da correção de execução para tarefas importantes, uma biblioteca que implementa código de concorrência complicado deveria ao menos ter testes de regressão.
    Do ponto de vista do usuário final, fico me perguntando qual é a garantia de que algo que funciona hoje não vai quebrar amanhã por causa de uma regressão sutil e traiçoeira.
    O SQLite tem 590 vezes mais código de teste e scripts de teste do que código-fonte C puro https://www.sqlite.org/testing.html. Além de estabilidade e portabilidade, esse também é um dos vários motivos pelos quais o SQLite se tornou o banco de dados embarcado padrão de fato no mundo todo.
    É um exemplo meio forçado, comparando coisas bem diferentes, mas a ideia geral continua válida. Testes de regressão geram estabilidade e confiança em um projeto.
    Onde eu trabalho, se realmente for inevitável adiar testes básicos de regressão, normalmente criamos um ticket de acompanhamento dentro do mesmo épico para garantir que eles sejam escritos pelo menos antes do lançamento da funcionalidade/épico.

• Segundo a explicação, usa-se busy waiting nos workers para obter latência na casa dos nanossegundos.
  Fico pensando o quão realista é o busy waiting em aplicações grandes com dezenas de milhares de tarefas. Se as tarefas não forem baseadas em threads, mas assíncronas, talvez isso seja viável, já que haveria apenas N esperadores, onde N é o tamanho do pool de threads do executor. De qualquer forma, uma estrutura assim certamente consumiria mais energia.
  Relacionado a isso, há muito tempo me pergunto se existe alguma forma de o produtor de tarefas acordar o consumidor mais rápido sem busy waiting. Por exemplo, já pensei se seria possível executar o consumidor dentro da fatia de tempo do produtor.
  Ainda nessa linha, também me pergunto se operações FUTEX_WAKE em espaço de usuário poderiam reduzir o custo de acordar consumidores à metade do normal, isto é, apenas ao custo do lado do consumidor.

• Há links para artigos bons e bem organizados.
  Só gostaria que a comparação tivesse sido com tarefas do OpenMP. Já ouvi dizer que o Rayon tem fama de ser meio lento.

• Escalonamento cooperativo é a base de muitos padrões que apresentam métricas excelentes.

  • Mas não se trata de escalonamento cooperativo no sentido de as tarefas cederem umas às outras.
    Trata-se principalmente de cooperar para permitir que algumas tarefas sejam passadas para outras threads, e isso também não acontece o tempo todo, apenas uma vez por heartbeat. Como o escalonamento acontece com pouca frequência, o custo amortizado é baixo.

• O README em bench também vale a pena: https://github.com/judofyr/spice/blob/main/bench/README.md