O inacreditável coletor de lixo do Fil
(fil-c.org)- O FUGC da linguagem Fil-C é um coletor de lixo avançado com suporte a paralelismo e concorrência
- Funciona on-the-fly e usa o método grey-stack de Dijkstra sem interromper o programa inteiro
- Implementa um design com rastreamento exato de memória e processamento sem mover objetos
- Com uso de safepoints, permite gerenciamento de memória seguro e eficiente mesmo em ambientes multithread
- Oferece vários recursos de gerenciamento de memória no estilo C/Java/JavaScript, como tratamento de exceções ao acessar objetos liberados/liberação dupla
Visão geral do FUGC (o inacreditável coletor de lixo do Fil)
O Fil-C usa o FUGC (Fil's Unbelievable Garbage Collector), um coletor de lixo paralelo, concorrente, on-the-fly, grey-stack de Dijkstra, exato e não movente
O código-fonte do FUGC pode ser visto em fugc.c, mas ele não funciona sem várias lógicas de suporte do runtime e do compilador
Principais características do FUGC
- Processamento paralelo: executa marcação e sweep simultaneamente em várias threads; quanto mais núcleos de CPU, maior a velocidade de coleta
- Suporte a concorrência: as threads do coletor de lixo trabalham separadamente dos mutators (ou seja, threads do programa do usuário), e as threads da aplicação podem continuar rodando sem parar
- on-the-fly: sem stop-the-world global, cada thread trata de forma assíncrona tarefas específicas como varredura de pilha por meio de um "soft handshake" (= ragged safepoint)
- Método grey-stack: reinspeciona as pilhas das threads várias vezes até chegar a um ponto fixo, repetindo a marcação; se surgirem objetos adicionais nesse processo, a marcação continua
- Usa um store barrier simples, sem necessidade de load barrier
- Barreira de Dijkstra: ao armazenar um ponteiro no heap ou em variáveis globais durante a marcação, o objeto de destino também é marcado ao mesmo tempo
- Coleta exata: o runtime rastreia com precisão todas as posições de ponteiros, então o GC percorre apenas objetos reais
- Objetos não moventes: como a posição de memória dos objetos não muda, a coleta concorrente multithread e a sincronização ficam mais fáceis
- Design de advancing wavefront: o mutator não consegue aumentar a carga de trabalho do coletor, e os objetos marcados permanecem vivos durante aquele ciclo de coleta
- Coleta incremental: alguns objetos podem ser liberados durante o ciclo mesmo que estivessem vivos no início da coleta
Safepoint e gerenciamento de threads
- Pollcheck: o compilador insere periodicamente pollchecks; no caminho rápido, é apenas um desvio simples, e no caminho lento executa callbacks relacionados ao GC
- Soft handshake: solicita a todas as threads que executem callbacks de pollcheck e espera até a conclusão
- Gerenciamento de estado enter/exit: em funções de longa espera, bloqueios ou system calls onde o pollcheck é omitido, o coletor executa diretamente o callback correspondente
- Garante prevenção de condições de corrida e acesso seguro a ponteiros em ambientes com suporte a multithread
- Também oferece suporte a trabalhos especiais como depuração ou
forkusando modo stop-the-world, além de implementar tratamento de sinais de forma estável
Loop do coletor FUGC
- Espera por um gatilho de GC
- Ativa o store barrier e depois faz um soft handshake (callback no-op)
- Ativa alocação black (pré-marcação de novos objetos) e executa callback de reset de cache
- Marca as raízes globais
- Faz um soft handshake (varredura de pilha e callback de reset de cache); se a mark stack estiver vazia, vai para 7
- Tracing (marca as referências de cada objeto da mark stack; repete até a mark stack esvaziar e então volta para 5)
- Desativa o store barrier, prepara o sweep e faz um soft handshake de novo reset de cache
- Sweep (páginas ainda não varridas alocam como black, e as já varridas como white)
- Reentra no loop
Diferenças em relação a pesquisas anteriores e otimizações
- O FUGC é parecido com o coletor DLG (Doligez-Leroy-Gonthier), mas com barreira de Dijkstra simples e uso de grey stack, o que torna a implementação do store barrier mais intuitiva e com melhor desempenho
- A abordagem de ponto fixo converge rapidamente e com baixo custo
- Com sweep baseado em bitvector SIMD, a liberação é muito rápida e consome menos de 5% do tempo total de GC
- Otimizações de desempenho usando recursos como Verse heap config
Recursos bônus (extensibilidade do gerenciamento de memória)
Liberação de objetos
- Ao chamar
freeem C, o objeto é imediatamente sinalizado como liberado, e qualquer acesso posterior gera trap - Evita mau funcionamento do GC causado por dangling pointers
- Referências a objetos liberados são redirecionadas para um objeto free singleton, permitindo detecção confiável mesmo após realocação de memória
- Evita vazamentos de memória causados por ponteiros não utilizados que disparariam o GC
Finalizers
- É possível implementar de forma flexível filas de finalizers no estilo Java com filas personalizadas e processamento em threads
Referências fracas
- Funcionam da mesma forma que
weak referenceem Java, sem reference queue separada (phantom e soft reference não são suportadas)
Mapas fracos
- Parecidos com o WeakMap do JavaScript, mas com possibilidade de iterar todos os elementos e verificar a quantidade de elementos
Conclusão e significado
Com o FUGC, o Fil-C oferece forte segurança e tratamento de exceções intuitivo contra uso incorreto de free
- Foi projetado para sempre gerar trap ao acessar um objeto liberado ou em caso de liberação dupla
- Se o objeto não for liberado, o GC se encarrega de recuperá-lo corretamente
- Suporta vários padrões de gerenciamento de memória e oferece um ambiente familiar até para desenvolvedores de C/Java/JavaScript
1 comentários
Comentários no Hacker News
Hum, parece que o Fil-C pode ser algo realmente importante. Existe muito software que só existe em código C, então acho que precisamos de uma abordagem para mantê-lo. Os compiladores C tradicionais assumem grandes riscos de segurança para maximizar o desempenho em núcleo único, e esse tipo de trade-off já parece datado. A lista de suporte é realmente impressionante: CPython, SQLite, OpenSSH, ICU, CMake, Perl5, Bash etc. Não acho provável que qualquer um desses softwares seja reescrito em Rust. Fico curioso se o Fil-C poderia ser usado também para multitarefa entre processos mutuamente não confiáveis em ambientes sem MMU. Parece estar seguindo a direção certa com segurança baseada em capabilities, sincronização non-blocking e afins. Gostaria de saber se alguém já usou isso de verdade. Na prática, há relatos de que mesmo no pior caso a perda de desempenho é de cerca de 4x, e o nome é realmente engraçado. Filthy way! Filthy way!
Sobre a pergunta de se o Fil-C permite multitarefa entre processos não confiáveis em computadores sem MMU: em essência, o FUGC se apoia em funcionalidades do SO dependentes de MMU, mas imagino que também seria possível criar uma versão sem essa dependência. Quanto ao desempenho, esse 4x mais lento é o pior cenário, e fui eu mesmo quem reportou esse número. Tenho a tendência de sempre medir desempenho de forma realista e perseguir obsessivamente os problemas de performance para melhorá-los. De fato, consigo usar sem dificuldade no dia a dia programas de que gosto em suas versões Fil-C
Você disse que a lista de softwares suportados é impressionante; concordo em termos gerais, mas vejo os exemplos citados de forma um pouco diferente. CPython, Perl5 e outros já são runtimes de linguagens famosas por terem GC lento, então colocar mais um GC em cima disso não parece um design elegante e pode até causar uma queda maior de desempenho. E já existem tentativas de reimplementação ou substituição em Rust ou Go em alguns casos; por exemplo, para o SQLite existe o Turso. Além disso, esses softwares são projetos fundamentais muito ativamente mantidos, então talvez um dia eles mesmos façam refatorações internas ou até uma migração para Rust. Acho que o Fil-C se encaixa melhor em outro tipo de caso: código menos mantido, menos sensível a desempenho, mas ainda usado continuamente, como um programa em C de 50 anos atrás que alguém ainda tira da gaveta de vez em quando
Uma grande vantagem de o SQLite ser escrito em C é a portabilidade para sistemas operacionais não padronizados. Por exemplo, já usei diretamente com o μC/OS-II, um RTOS para embarcados. O projeto de sistemas embarcados é bem diferente de PC/servidor, então, por razões de desempenho e para evitar fragmentação de memória, às vezes nem se libera memória, marcando objetos/estruturas para reutilização. É uma ideia parecida com alocação de heap customizada ou pooling. Documentação de VFS do SQLite, introdução ao Micro-Controller OS
Você disse que os softwares em C da lista de exemplos não serão reescritos em Rust, mas fico pensando quanto tempo falta para que ferramentas de análise estática baseadas em IA evoluam a ponto de encontrar com precisão os problemas em código C e dar um feedback do tipo: “esta parte vai falhar, corrija assim”. Se uma ferramenta dessas realmente surgir, talvez continue sendo aceitável simplesmente seguir usando C
Vale observar que o Fil-C ainda não oferece suporte a sistemas de 32 bits (ou menores). Documentação sobre Invisicaps no Fil-C
Este projeto parece um caso raro de algo que avança ao mesmo tempo na pesquisa e na prática. Normalmente, esse tipo de coisa é tocado por equipes em grandes empresas de TI e mantido com receita de publicidade, então fico curioso sobre o contexto em que o Fil-C surgiu. Se não for apenas um projeto de paixão pessoal, quem financiou isso, quantos anos de trabalho foram investidos e qual é o objetivo final?
Pessoalmente, isso me parece um projeto de paixão
Em resposta à pergunta sobre o objetivo final, o copyright do projeto está indicado como 2024-2025 Epic Games, Inc.
Fico feliz só de o Fil-C existir. Mesmo quando esse tipo de tecnologia é eficaz em programas reais, muitos desenvolvedores acreditam que “isso não funciona”. O simples fato de mostrar que é implementável já encerra de vez inúmeras discussões
Fico curioso com os resultados de benchmark. A maior preocupação com esse tipo de abordagem é se o desempenho não despenca justamente nos casos de uso específicos em que C/C++ ainda são populares. Se throughput, latência e uso de memória ficarem parecidos demais com os de linguagens como Go, no fim talvez não sobre muito motivo para escolhê-lo
Em linguagens de programação, existe desde a era do assembly um discurso constante sobre desempenho. Só que a maioria dos desenvolvedores não é alguém com uma visão extraordinária como Ivan Suntherland, Alan Kay, Steve Jobs ou Bret Victor; são pessoas comuns que confiam naquilo que veem funcionando diante dos próprios olhos. Por isso, ainda hoje há incontáveis cópias de UNIX e C, e muita gente parece viver repetindo visões do passado em vez de criar algo novo. Claro, os dois que criaram UNIX e C nos anos 1970 também eram grandes visionários
Fico curioso por que foi usada uma estratégia de retreating wavefront em vez de advancing wavefront
Se os programas C existentes já têm chamadas
free(...)colocadas corretamente e ainda mantêm informações separadas de limites para todos os ponteiros, por que optar por um GC completo? Em vez disso, imagino que uma técnica de verificação temporal no estilo lock-and-key (referência: link para o artigo) talvez fosse melhor em termos de previsibilidade de uso de memória, desempenho e escalonamento. Suponho que o espaço necessário para armazenar as keys possa ser grande demais, ou que as verificações sejam lentas, ou ainda que surjam condições de corrida em ambientes multithreadA abordagem lock and key não tem os aspectos inteligentes próprios do Fil-C. O ponto forte do modelo de capabilities do Fil-C é ser completamente thread-safe e, na maioria dos casos, não exigir atomics especiais nem locking
Também acho interessante que ele permita aritmética de ponteiros fora dos limites sem dereferência. Compiladores às vezes exploram UB nesses casos para otimizar (pergunta relacionada no Stack Overflow); fico curioso se no LLVM interno do Fil-C essas otimizações são desativadas, ou se os ponteiros são gerenciados como uma combinação de “base + offset”, eliminando essa possibilidade desde a origem. Também me pergunto se isso não acaba fazendo perder certas otimizações aplicáveis a ponteiros normais
Parece um projeto realmente incrível. Chama atenção o fato de o fast path de
pollcheckser simplesmente load-and-branch. Existe uma técnica interessante usada no lugar desse tipo de branch, e ela está bem resumida no blog oficial do Android em "verificações implícitas de suspend"C com suporte a concorrência e GC, e ainda por cima um GC non-moving: isso é realmente surpreendente. Se eu pudesse pegar um projeto C de porte médio e, em troca de uma perda de desempenho em runtime de 2x a 3x, reduzir bugs de memória, eu aceitaria sem hesitar. Fico curioso sobre o quão fácil é adotar isso de forma incremental. Funciona alvo por alvo, ou é preciso trocar toda a toolchain?
Eu me importo com C, com desempenho e com segurança. Esse GC e essa estrutura de capabilities são atraentes. Já pensei várias vezes em como seria um “C mais seguro”; cheguei a examinar a ideia de capabilities algumas vezes, mas não sou bom em código de compilador. Fico curioso se o suporte a Windows é difícil
Fico curioso sobre como o GC rastreia os root objects. Existe alguma etapa de compilação que marca previamente as roots que o GC deve escanear? Se alguém souber explicar, seria ótimo
Este projeto é realmente impressionante. É até estranho eu nunca ter ouvido falar dele antes. Estou animado para testar pessoalmente. Talvez os limites de desempenho dificultem o uso em produção, mas como forma de verificar diretamente a segurança de certos programas, parece extremamente útil. Passa uma sensação de ser mais abrangente do que os sanitizers que costumo usar