Coleta de lixo para programadores de sistemas (2023)
(bitbashing.io)- Mesmo em código em que desempenho e concorrência são importantes, como kernel e drivers, liberar memória não termina com uma simples chamada a
free(), e técnicas de compartilhamento sem lock podem se tornar necessárias - RCU(Read, Copy, Update) copia dados que são lidos com frequência e mudam raramente, depois troca o ponteiro de forma atômica, sem bloquear o caminho de leitura
- Se a versão anterior for
deleteimediatamente, pode ocorrer use-after-free em uma thread que ainda esteja lendo; por isso, o RCU rastreia as regiões de leitura e adia a liberação até um momento seguro - O RCU é usado dezenas de milhares de vezes no Linux, também está presente na biblioteca Folly C++ e no
crossbeam-epochdo Rust, e tem uma forma semelhante à de um GC por fazer a limpeza depois, dependendo de o objeto ainda estar em uso - A dicotomia de que gerenciamento manual de memória é sempre mais rápido e previsível é fraca; como
free(), contagem de referências e o comportamento de memória do SO também têm custos e incertezas, o GC moderno também pode ser uma ferramenta de programação de sistemas
Por que código de kernel usa técnicas como RCU
- O sistema operacional está entre os programas executados diariamente com maior sensibilidade a desempenho
- Se o SO fica mais rápido, o usuário pode realizar mais computação, então desenvolvedores de kernel e drivers investem muito esforço em otimização de código
- O sistema operacional lida não só com processos e threads em espaço de usuário, mas também com várias threads do próprio kernel e até manipuladores de interrupção de hardware
- Como aumento de latência toma tempo do usuário, surgiram várias técnicas para compartilhar dados entre threads sem locks no código de kernel
Funcionamento básico do RCU
- RCU(Read, Copy, Update) é uma abordagem adequada para dados lidos com muita frequência, mas escritos raramente
- Um exemplo é o conjunto de dispositivos USB conectados no momento: quase não muda, mas pode mudar
- A alteração deve ocorrer de forma atômica e não pode bloquear leitores que já estejam lendo
- O escritor atualiza o estado compartilhado na seguinte ordem
- Lê os dados antigos a partir do ponteiro
- Copia os dados antigos e aplica as mudanças necessárias para criar uma nova versão
- Atualiza o ponteiro de forma atômica para apontar para a nova versão
- Como os leitores apenas leem o ponteiro compartilhado, o caminho de leitura é simples e funciona sem espera
- Essa abordagem é fácil de usar e wait-free, mas, se a versão anterior não for limpa, ocorre vazamento de memória
A versão anterior não pode ser liberada imediatamente
- Se o ponteiro for trocado para a nova versão e a anterior for
deletelogo em seguida, surge o risco de use-after-free - Como tudo funciona sem lock, o escritor não sabe se ainda existem leitores consultando a versão anterior
- Leitores podem marcar a seção crítica do lado da leitura com
rcu_read_lock()ercu_read_unlock()- Os leitores continuam sem ser bloqueados
- O escritor não remove os dados anteriores até que esses leitores saiam
rcu_synchronize()não precisa esperar todos os leitores desaparecerem, mas apenas até terminarem os leitores anteriores que ainda poderiam ver a versão antiga- Leitores que já viram o novo ponteiro usam a nova versão e, portanto, são irrelevantes para o tempo de vida da versão anterior
Liberação adiada e a forma de GC
- Mesmo que o escritor não espere dentro da função de atualização, o código continua correto se os dados antigos forem liberados com segurança em algum momento posterior
- Algo como
rcu_defer(old)permite liberarolda qualquer momento depois que os leitores atuais saírem da região crítica - Um formato em que uma thread dedicada limpa periodicamente versões antigas não referenciadas se parece com um GC geracional
- RCU não é um experimento mental, mas uma técnica amplamente usada na prática
- O Linux usa RCU dezenas de milhares de vezes
- O RCU é oferecido na Folly C++ library do Facebook
- Em Rust, ele aparece com o nome
crossbeam-epoche serve de base para bibliotecas populares de concorrência
- Mais importante do que discutir se RCU é ou não “GC de verdade” é que sua estrutura é igual à de um GC no ponto em que a memória é limpa depois, conforme se ainda está em uso ou não
Os custos ocultos da liberação manual
- A noção comum de que GC é intrinsecamente menos eficiente do que gerenciamento manual de memória enfraquece quando se observam os detalhes de implementação
-
free()não é de graça- Alocadores de memória de uso geral precisam gerenciar estado global interno, como páginas recebidas do kernel, divisão em buckets por tamanho e buckets em uso
- Pode haver contenção quando várias threads tentam travar o estado do alocador
- Mesmo com pools locais por thread, como em jemalloc, ainda é necessário código adicional para sincronizá-los
-
RAII e lifetime também não eliminam o custo do alocador
- Os lifetimes do Rust e o RAII do C++ ajudam na automação e na correção da liberação de memória, mas não removem a complexidade das estruturas internas do alocador
- Em muitos cenários, é preciso voltar para
shared_ptrouArc - Isso exige metadados extras na forma de contagem de referências, e esse valor pode ficar trafegando entre núcleos e caches, gerando custo
- Também pode haver vazamento em grafos de liveness com ciclos
-
Há otimizações que o GC também pode oferecer
- Um GC geracional móvel recompata periodicamente o heap
- A alocação pode se aproximar de um simples incremento de ponteiro, alcançando alta taxa de processamento
- A localidade da alocação sequencial melhora e pode ajudar também no desempenho de cache
Equívocos sobre controle do gerenciamento de memória
- Muitos desenvolvedores que se opõem ao GC estão construindo sistemas de tempo real brando
- Querem o máximo de velocidade possível, como no FPS de videogames ou no desempenho de compressão de codecs de streaming
- Mas não se trata de requisitos de latência rígidos em que, se ocasionalmente levar 1 milissegundo a mais, o sistema quebra ou alguém morre
- A crença de que o programador pode decidir quando o gerenciamento de memória acontece não é tão simples
- O sistema operacional abstrai a interação com o hardware
- No Linux, por padrão, quase nada acontece no pedido de memória; a memória pode só ser realmente fornecida quando você tenta usá-la
- Quando entram em cena
madvise(), I/O com mapeamento de memória e cache de sistema de arquivos, não existe resposta simples para “o que foi alocado e quando” - Em um dia ruim, um simples acesso a ponteiro pode acabar virando I/O de disco
- Também é limitada a crença de que o programador sempre sabe qual é o melhor momento para parar para gerenciar memória
- Existem casos claros, como a tela de carregamento de um videogame
- Em muito software, a única resposta é quando o sistema não está ocupado com tarefas mais importantes
- Código individual que usa
shared_ptreArcnão consegue saber de antemão se será o último dono e, portanto, quem ficará responsável pela limpeza
- A crença de que chamar
free()devolve imediatamente a memória ao SO também nem sempre está correta- A memória é alocada pelo SO em unidades de página
- Muitas vezes o alocador mantém as páginas até o fim do programa para reutilizá-las
- O SO também pode recuperar páginas por meio de swap
Por que o GC pode ser visto como uma ferramenta de programação de sistemas
- Nem todo software se beneficia de GC
- Mas, mesmo perto de 2024, discussões sobre GC entre programadores de sistemas ainda tendem a se perder em falsas dicotomias e em medo, incerteza e dúvida
- A ideia de que linguagens com GC são “obviamente” mais lentas do que linguagens com gerenciamento manual de memória é, na prática, mais próxima de uma ideologia do que de um fato
- Mesmo em equipes que constroem sistemas dos quais vidas dependem, houve casos de latência abaixo de microssegundo em linguagens com GC que alocam em quase todas as linhas
- Se uma parte do sistema realmente precisa executar dentro de
nciclos de clock, apenas essa parte específica pode ser isolada em código sem GC ou em hardware - GC não é uma solução mágica, mas uma das ferramentas na caixa de ferramentas que podem ser usadas sem medo
1 comentários
Comentários do Hacker News
Entre as promissoras técnicas modernas de coleta de lixo paralela, vale a pena olhar para MPL ou MaPLe e seu novo trabalho sobre Automatic Management of Parallelism
A essência, premiada com o POPL 2024 distinguished paper award e o ACM SIGPLAN dissertation award 2023, é dupla: a) coleta de lixo paralela comprovadamente eficiente com base em disentanglement, b) controle automático de granularidade comprovadamente eficiente
[1] MaPLe (MPL): https://github.com/MPLLang/mpl
[2] Automatic Parallelism Management: https://dl.acm.org/doi/10.1145/3632880
Há o artigo citado e também o MLKit, um dos primeiros usuários e pioneiros da gestão de memória baseada em regiões
Por exemplo, uma abordagem dessas poderia tornar a coleta de lixo do Go muito mais rápida, ou esbarraria em problemas do design já existente da linguagem?
Os casos de uso de RCU são convincentes, mas a experiência com coleta de lixo em outras situações não foi boa
Este texto soa menos como uma defesa de que tempos de vida estáticos são geralmente melhores que tempos de vida dinâmicos, e mais como uma defesa de que soluções personalizadas de gerenciamento de memória podem entregar o melhor desempenho
Não vejo
free()como algo que devolve memória ao sistema operacional, e sim ao alocador. Isso é muito melhor do que devolvê-la ao sistema operacional, e chamadas de sistema são lentas. Ainda assim, alocadores como o mimalloc também podem fazer com que a memória liberada não fique disponível imediatamente para o próximomalloc, mas apenas periodicamenteAo alocar 800 bytes e depois chamar
freeimediatamente, repetindo isso 1 milhão de vezes e contando o número de ponteiros únicos, o glibc malloc deu 1, o jemalloc deu 1, o mimalloc deu 4, e o coletor de lixo do Julia deu 6276762767, cerca de 48 MiB, não é tão ruim, mas ainda assim expulsa o cache L3 da minha máquina. Se você usa coleta de lixo, fica quase garantido que novas alocações virão da RAM em vez do cache, o que destrói o desempenho de código com muitas alocações. O importante não é só a velocidade do gerenciamento de memória em si, mas também quão rápido é possível trabalhar com a memória que ele entregou
Publiquei um benchmark mostrando isso em Julia: https://discourse.julialang.org/t/blog-post-rust-vs-julia-in...
malloc/free dá uma chance de a memória real de trabalho permanecer quente no cache, se ela for pequena o bastante. Alocadores como o mimalloc também são projetados para posicionar alocações consecutivas próximas umas das outras, como um coletor de lixo com compactação, e os 4 ponteiros únicos que vi no mimalloc estavam espaçados por 896 bytes
Se eu tivesse mais experiência com coletores de lixo com compactação, talvez minha visão fosse menos cínica, mas vejo a coleta de lixo como uma solução muito mais complexa do que algo como o verificador de empréstimos do Rust para gerenciamento seguro de memória. Essa complexidade é empurrada para desenvolvedores de compiladores e runtime, então para o usuário em geral tudo bem, e é uma troca aceitável ao escrever código que não é sensível a desempenho. RAII com tempos de vida estáticos também é uma troca razoável para código que não precisa de uma abordagem mais personalizada, e os exemplos do texto claramente são casos que exigem uma solução sob medida
Em programas de longa duração, um coletor de lixo com compactação quase sempre usa melhor o cache do que malloc, porque a fragmentação do heap desperdiça entradas do cache TLB e espaço entre objetos. O alocador bump de um coletor de lixo com compactação dá um ponteiro novo a cada alocação porque
freenão recupera a memória, mas essas alocações são sequenciais e, se o heap continua sendo consumido enquanto só os objetos mais recentes são acessados, elas ainda permanecem no cache. Fazer benchmark dos efeitos colaterais de alocadores e coletores de lixo é extremamente difícil, e quase sempre sou cético com benchmarks sintéticos desse tipoO que preocupa as pessoas é que o processo de descobrir se a memória não está mais em uso é menos eficiente e menos determinístico do que dizer diretamente ao alocador que o uso do recurso terminou. Nunca vi ninguém preocupado com o simples fato de o descarte ser adiado
Percorrer todo o conjunto vivo é algo raro, e 30 anos de melhorias em algoritmos de coleta de lixo nos trouxeram quase ao nível de consciência, mas essa frase ignora, intencionalmente ou não, o ponto que as pessoas realmente criticam. Quando surge um problema de coleta de lixo em produção, parece que é preciso chamar um xamã para ajustar coisas em todo canto e torcer para mandar a alma enfurecida de volta para o mundo das sombras
Se o mecanismo marca o lixo e avisa quando ele deixa de ser usado, todo esse processo desaparece. A alocação de memória sob coleta de lixo pode ser muito rápida, mas para uma comparação justa também é preciso amortizar e incluir o custo de marcação e compactação
Outro grande problema é que, para obter o mesmo desempenho, a coleta de lixo em geral exige muito mais memória do que o gerenciamento manual de memória. Também é preciso CPU extra para verificar repetidamente e de forma redundante se ainda existem referências, além de aceitar cópias adicionais de memória para compactação otimista
Por fim, o texto critica a necessidade de gerenciamento manual de memória como Arc/Rc do Rust quando o tempo de vida é incerto, mas ignora que, em linguagens com coleta de lixo, também não dá para confiar que finalizers serão chamados com certeza, então na prática se constrói uma infraestrutura quase idêntica para fechar recursos externos
Esse debate já foi repetido o bastante nos últimos 20 ou 30 anos, e este texto não parece trazer nada de novo além de descartar preocupações legítimas sobre coleta de lixo como se fossem memes. Memes são divertidos, então tudo bem, mas a resposta correta é que não existe resposta universal. Basta usar a ferramenta adequada para satisfazer as restrições de projeto do sistema
As outras alocações, que vivem mais, por definição são difíceis de controlar do ponto de vista do cache. Localidade é uma das grandes vantagens da coleta de lixo, e o único problema que conheço é stop-the-world com marcação/varredura. Sei que coletores de lixo modernos usam threads em segundo plano, mas ainda assim, pelo que sei, eventos de stop-the-world continuam acontecendo
free()devolve memória ao alocador, mas lidar com fragmentação de memória em servidores de longa duração não é nada agradávelEm especial a fragmentação interna de páginas gerenciadas por alocadores slab; não é um problema comum, mas é difícil de tratar
Felizmente, não existem muitas áreas em que a coleta de lixo precise competir com exemplos arrumados de forma tão conveniente quanto este
Exceto no caso especial em que toda a memória possa ser tratada facilmente como arena, um bom garbage collector de rastreamento já superou há muito tempo o gerenciamento manual de memória em throughput, e recentemente o impacto em latência também se tornou aceitável para a grande maioria das aplicações
O ZGC do OpenJDK costuma ter pausas na faixa de dezenas a centenas de microssegundos, e em taxas de alocação razoáveis quase nunca passa de 1 ms mesmo no pior caso, ficando em uma faixa parecida com pausas provocadas pelo sistema operacional
O verdadeiro trade-off importante é apenas o uso de memória. Tirando nichos especiais, onde arenas se encaixam bem em tudo e a pior latência fica na faixa baixa de microssegundos, a pergunta central é uma só: minha aplicação roda em um ambiente com restrição de memória, ou vale a pena sacrificar outras coisas para reduzir o uso de RAM?
Nesse tipo de código, rastrear o tempo de vida de cada objeto individualmente é exagero. No fim, gerenciamento de memória é sobre tempo de vida, e menos tempos de vida individuais é sempre melhor do que muitos. Há menos trabalho a fazer, seja manual ou automático
Não precisar pensar no tempo de vida dos objetos é extremamente conveniente, e é por isso que linguagens com garbage collection deram certo apesar da considerável complexidade interna de bons coletores
Também continuamos sujeitos a latências de cauda difíceis de prever e ao impacto de vários casos excepcionais
O ZGC parece ter menos pausas do que o Shenandoah e, por isso, parece fazer mais trabalho por pausa, mostrando desempenho um pouco melhor
Ainda precisamos testar em produção, mas até agora parece que, com ZGC — e com o ZGC geracional a partir do Java 21 — as pausas de garbage collection são em grande parte um problema resolvido
Como na visão do Jai, a alocação de memória pode ser dividida em quatro categorias por ordem de frequência: 1) coisas extremamente curtas, que podem ficar na stack da função, 2) coisas de vida curta e bem definida, que podem ficar em arenas de memória por frame/requisição, 3) coisas de vida longa e com dono bem definido, que podem ser gerenciadas em pools dedicados por subsistema, 4) coisas de vida longa e com dono pouco claro, que exigem gerenciamento dinâmico de memória
Para defender que garbage collection de rastreamento geralmente supera gerenciamento manual de memória, seria preciso comparar não com um sistema que chama malloc/free por toda parte, mas com um sistema escrito com essa perspectiva em mente. Comparar com práticas modernas de C++/Rust pode ser mais justo
Concordo que, na maioria dos sistemas, depender de garbage collection de rastreamento provavelmente é muito mais prático, mas isso é uma afirmação completamente diferente
O texto motiva RCU e depois faz uma guinada para começar a defender garbage collection de uso geral de forma ampla
Não chega a ser um cavalo de Troia, mas parece uma mudança bem brusca
Os objetos ficam em um de três estados e transitam o mais rápido possível: active, obsolete but alive for old readers, deallocated
Dependendo de como o código for escrito, talvez dê para reutilizar com segurança objetos “obsolete-but-alive” para novas alocações com
new, mas eu não analisei completamente o desempenhoComo é comum em discussões sobre garbage collection, é muito nebuloso quando exatamente se deve “recuar” para
shared_ptr/Arc. Na prática, o ponto central de um sistema sério baseado em contagem de referências é evitar a contagem de referências, ou seja, provar que a posse já existe ou evitar completamente a indireção. Não fazer nada é obviamente melhor do que o “fazer alguma coisa em algum momento” da garbage collectionNo software que eu escrevo, há dois casos. (1) caminhos quentes em que sempre se usa um alocador customizado e se evita alocação, (2) todo o resto
Em (1), com ou sem garbage collection, não faz diferença, porque eu vou escapar disso. Em (2), garbage collection é realmente confortável e correta
O trabalho que o Java fez com coletores modernos é impressionante, mas até eles reconhecem indiretamente, por meio do Valhalla, que há espaço para código sem alocação ou com pouca alocação
Há aqui uma pequena ressalva à observação de que sistemas operacionais modernos para uso geral, ou seja, sistemas operacionais que não sejam RTOS especiais, têm coleta de lixo embutida
Só que nós não chamamos isso assim; chamamos de gerenciamento de memória. E como chamamos linguagens com coleta de lixo embutida? Linguagens com gerenciamento de memória
Vemos isso com frequência em programas antigos em C executados de “cima para baixo”. Alocam, limpam recursos do sistema, mas não se preocupam com
free. Quando o programa termina, o sistema operacional recupera toda essa memória, então por que se dar ao trabalho?Há aqui uma oportunidade de criar um sistema operacional que trate recursos como um coletor de lixo em nível de sistema operacional, menos isolado do programa do que o coletor de lixo do runtime da linguagem. Mas, em geral, em linguagens com coleta de lixo, o coletor está entrelaçado de forma complexa com quase todas as linhas do runtime, então não é prático fazer uma distribuição para um único sistema operacional apenas para entregar esse controle ao sistema operacional
Ainda assim, é uma pena. Porque há muito espaço para melhorar problemas crônicos causados pelo isolamento artificial entre o gerenciamento de memória no nível do programa e no nível do sistema operacional
A única razão para liberar memória é, em aplicações de longa duração, reutilizá-la em outras alocações sem buscar mais memória nova do sistema operacional. Em ferramentas de linha de comando que executam uma vez e terminam, isso normalmente não é necessário
Se o processo for projetado para encerrar quando terminar seu trabalho, dá para usar o sistema operacional como se fosse um coletor de lixo
Mas nunca existiu uma forma de o sistema operacional saber, dentro de um programa em execução, qual memória não está mais sendo usada. Talvez algum sistema operacional obscuro de pesquisa seja exceção. Então, em vez de ser uma oportunidade perdida, eu diria que aquilo que teria sido “perdido” nem existe de forma significativa
Por outro lado, um estilo de programação que usa programas muito simples e de vida curta é totalmente legítimo. Ferramentas de CLI e linguagens de script que as automatizam funcionam assim, servidores web antigos também funcionavam assim via CGI e similares, e ainda hoje é uma abordagem perfeitamente razoável
(1) A transição de RCU para coleta de lixo por rastreamento de propósito geral parece um caso de trocar o argumento no meio da discussão
(2) Gerenciamento manual de memória não é apenas fazer chamadas de malloc/free, mas também trata de layout. Por exemplo, separar arrays de structs, inlining, offsets implícitos, empacotamento etc.
Parece que você quis dizer “array de structs”; isso pode ser feito com arrays de tuplas e, dependendo do alvo, é naturalmente achatado/normalizado. Ou seja, em alvos nativos isso vira um array de structs
Também é possível definir layouts exatos em nível de byte[1], usados principalmente para interoperar com outros softwares ou fazer parsing de formatos binários. Tipos de dados algébricos podem ser unboxed e, em breve, também será possível controlar a codificação exata dos tipos de dados algébricos
O Virgil usa coleta de lixo
[1] https://github.com/titzer/virgil/blob/master/doc/tutorial/La...
É verdade que linguagens gerenciadas modernas têm pouco controle de layout de memória, mas mesmo em linguagens de baixo nível isso está longe de ser perfeito, e certamente há maneiras de influenciar isso
Uma coisa que faltou neste texto é que async/await combina muito bem com coleta de lixo
Por motivos pessoais e idiossincráticos de estilo, eu não gosto de async/await, mas não vou me alongar nisso
Já usei bastante em TypeScript/JavaScript e também em Dart, e lá funciona como esperado
Também usei em Rust e, na minha opinião, é um desastre. Enfiar à força o tipo de gerenciamento de memória necessário para usar async/await em um runtime multithread é um inferno
https://doc.rust-lang.org/std/pin/index.html
Em muitos textos que defendem a coleta de lixo, há um ponto que costuma faltar, e este texto aparentemente é assim também: memória é apenas um tipo de recurso
Especialmente em programação de sistemas, código correto também precisa gerenciar recursos externos, como descritores de arquivo e sockets. A coleta de lixo resolve apenas a parte da memória da aplicação, então não ajuda em nada com esses recursos externos. Na verdade, pode até tornar isso bem mais complexo, e basta ver o que é necessário para implementar corretamente um
IDisposablenão trivial no .NETNa minha experiência, abordagens como RAII ou contagem de referências tornam muito mais fácil tratar memória e recursos externos de forma unificada, o que também facilita escrever código correto e raciocinar sobre ele
Isso não significa que eu seja explicitamente contra a coleta de lixo. Como qualquer outra coisa, é uma ferramenta com prós e contras. A abordagem de RCU com “GC manual” mencionada no texto é interessante para certas tarefas
Não é por acaso que a maioria dos modelos teóricos de computação assume memória infinita. Em alguns tipos de software, como kernels de sistemas operacionais ou aplicações hard real-time, a capacidade de processamento também é alocada manualmente, mas quase não existem linguagens que exijam alocação manual de capacidade de processamento
Por motivos semelhantes, o gerenciamento automático de memória é muito útil para abstrair computação. Ele evita que detalhes de memória de uma sub-rotina vazem para o chamador, e no uso de CPU esses detalhes também raramente aparecem
Todo cálculo não trivial envolve alguma quantidade não constante de processamento e memória, mas I/O normalmente acontece nas bordas do sistema. Gerenciar I/O também é muito importante, claro, mas não é tão central quanto processamento e memória para o conceito de computação e para a centralidade das abstrações computacionais
Por exemplo, Rust acabou adquirindo segurança de I/O, e por isso descritores de arquivo como
OwnedFdno Unix ou handles comoOwnedHandleno Windows tornam-se objetos com posse, e não inteiros como o número 4À primeira vista, isso parece apenas sobre evitar erros bobos, como fazer aritmética com handles ou usar incorretamente valores reservados como sentinelas, mas, graças ao modelo de ownership, mesmo quando se faz coisas complicadas com handles, a posse fica explícita e isso também se torna transparente para quem vai manter o código depois
Passei a valorizar muito RAII
Algumas linguagens têm RAII, algumas oferecem palavras-chave, outras oferecem gerenciamento no estilo arena ou lambdas com gerenciamento implícito. Algumas contam com um pouco de ajuda do sistema de tipos, outras misturam um pouco de cada uma dessas abordagens
Além disso, assim como desenvolvedores de sistemas precisam depender de analisadores estáticos, os analisadores estáticos dessas linguagens também podem verificar o que passou batido quando o sistema de tipos sozinho não basta
Por exemplo, a instrução try-with-resources do Java garante que os recursos sejam liberados com segurança mesmo quando ocorre uma exceção: https://docs.oracle.com/javase/tutorial/essential/exceptions...
Mesmo com esses blocos fundamentais, dá para construir um sistema bastante robusto e seguro em relação a recursos