El increíble recolector de basura de Fil

 (fil-c.org)
1 puntos por GN⁺ 2025-09-06 | 1 comentarios | Compartir por WhatsApp
  • El FUGC del lenguaje Fil-C es un recolector de basura avanzado que soporta procesamiento paralelo y concurrencia
  • Usa on-the-fly (ejecución inmediata) y el método grey-stack de Dijkstra sin detener todo el programa
  • Implementa un diseño con seguimiento preciso de memoria y procesamiento sin mover objetos
  • Con safepoints, permite una gestión de memoria segura y eficiente incluso en entornos multihilo
  • Ofrece diversas funciones de gestión de memoria al estilo C/Java/JavaScript, como lanzar excepciones al acceder a objetos liberados o liberarlos dos veces

Resumen de FUGC (el increíble recolector de basura de Fil)

Fil-C usa FUGC (Fil's Unbelievable Garbage Collector), un recolector de basura paralelo, concurrente, on-the-fly, grey-stack de Dijkstra, preciso y no moviente.
El código fuente de FUGC puede verse en fugc.c, pero no puede funcionar sin la diversa lógica de soporte del runtime y del compilador.

Características principales de FUGC

  • Procesamiento paralelo: realiza el marcado y el barrido simultáneamente en varios hilos; cuantos más núcleos de CPU haya, más rápido recolecta
  • Soporte de concurrencia: el hilo del recolector de basura trabaja por separado de los mutators (es decir, los hilos del programa de usuario), por lo que los hilos de la aplicación pueden seguir ejecutándose sin detenerse
  • On-the-fly (ejecución inmediata): sin un stop-the-world global, usa un "soft handshake" (= ragged safepoint) para que cada hilo procese de forma asíncrona tareas específicas como el escaneo de pila
  • Método grey-stack: vuelve a examinar varias veces las pilas de los hilos hasta alcanzar un punto fijo y repetir el marcado; si en el proceso aparecen objetos adicionales, se vuelve a ejecutar el marcado
  • Aprovecha una store barrier simple y no requiere load barrier
  • Barrera de Dijkstra: si durante el marcado se guarda un puntero en el heap o en una variable global, el objeto de destino también se marca al mismo tiempo
  • Recolección precisa: el runtime rastrea con exactitud todas las ubicaciones de punteros, así que el GC solo recorre objetos reales
  • Procesamiento sin mover objetos: la ubicación en memoria de los objetos no cambia, lo que facilita la recolección concurrente multihilo y la sincronización
  • Diseño de advancing wavefront: el mutator no puede aumentar la carga de trabajo del recolector; los objetos marcados se conservan durante ese ciclo de recolección
  • Recolección incremental: algunos objetos pueden liberarse durante el ciclo aunque estuvieran vivos al inicio de la recolección

Safepoint y gestión de hilos

  • Pollcheck: el compilador inserta periódicamente pollchecks; en la ruta rápida es una simple bifurcación, y en la ruta lenta ejecuta callbacks relacionados con el GC
  • Soft handshake: solicita a todos los hilos que ejecuten el callback de pollcheck y espera a que terminen
  • Gestión de estado enter/exit: en funciones bloqueantes de larga duración, llamadas al sistema, etc., donde se omite pollcheck, el collector ejecuta directamente ese callback
  • Garantiza la prevención de condiciones de carrera y el acceso seguro a punteros en entornos con soporte multihilo
  • Usa el modo stop-the-world para tareas especiales como depuración o fork, y también implementa el manejo de señales de forma estable

Bucle del recolector FUGC

  1. Espera a que se dispare el GC
  2. Activa la store barrier y luego hace un soft handshake (callback no-op)
  3. Activa la asignación black (premarcado de objetos nuevos) y ejecuta el callback de reinicio de caché
  4. Marca las raíces globales
  5. Soft handshake (callbacks de escaneo de pila y reinicio de caché); si la pila de marcado está vacía, pasa al 7
  6. Trazado (marca referencias para cada objeto de la pila de marcado; repite hasta que la pila quede vacía y luego vuelve al 5)
  7. Desactiva la store barrier, prepara el barrido y hace un soft handshake para reiniciar de nuevo la caché
  8. Barrido (las páginas aún no barridas asignan en black y las ya barridas en white)
  9. Reingresa al bucle

Diferencias frente a investigaciones previas y optimización

  • FUGC es similar al collector DLG (Doligez-Leroy-Gonthier), pero gracias a una barrera de Dijkstra simple y al uso de grey stack, la implementación de la store barrier es más intuitiva y ofrece mejor rendimiento
  • Converge rápidamente con el enfoque de punto fijo y tiene bajo costo
  • El barrido basado en bitvector SIMD permite una liberación extremadamente rápida y consume menos del 5% del tiempo total de GC
  • Rendimiento optimizado con elementos como Verse heap config

Funciones extra (extensibilidad de la gestión de memoria)

Liberación de objetos

  • Cuando se llama a free en C, el objeto se marca de inmediato como liberado, y cualquier acceso posterior provoca un trap
  • Evita fallos del GC causados por dangling pointers (punteros colgantes)
  • Las referencias a objetos liberados se redirigen a un singleton de objeto libre, lo que permite detectarlos de forma confiable incluso después de reasignar memoria
  • Evita fugas de memoria que disparan el GC por punteros no utilizados

Finalizadores

  • Es posible implementar de forma flexible una cola de finalizadores al estilo Java mediante colas personalizadas y manejo de hilos

Referencias débiles

  • Funcionan igual que una weak reference de Java; no hay una reference queue separada (no soporta phantom ni soft references)

Weak maps

  • Similar a WeakMap de JavaScript, aunque permite iterar todos los elementos y consultar cuántos hay

Conclusión e importancia

Con FUGC, Fil-C ofrece seguridad robusta y manejo intuitivo de excepciones frente al mal uso de free.

  • Está diseñado para que siempre se produzca un trap al acceder a un objeto liberado o al hacer doble liberación
  • Si no se libera un objeto, el GC se encarga de recuperarlo correctamente
  • Soporta diversos patrones de gestión de memoria y ofrece un entorno familiar incluso para desarrolladores de C/Java/JavaScript

Lecturas relacionadas

1 comentarios

 
GN⁺ 2025-09-06
Comentarios en Hacker News

  • Mmm, parece que Fil-C podría llegar a ser realmente importante. Hay mucho software que existe únicamente como código C, así que creo que hace falta una forma de mantenerlo. Los compiladores de C tradicionales asumen grandes riesgos de seguridad para exprimir al máximo el rendimiento de un solo núcleo, y ese tipo de trade-off ya se siente anticuado. La lista de compatibilidad es realmente impresionante: CPython, SQLite, OpenSSH, ICU, CMake, Perl5, Bash, etc. No creo que ninguno de esos programas vaya a reescribirse en Rust. Me pregunto si Fil-C también podría usarse para multitarea entre procesos no confiables en entornos sin MMU. Parece que va en una dirección correcta con seguridad basada en capacidades, sincronización no bloqueante y demás. Me gustaría saber si alguien ya lo ha usado de verdad. Según se reporta, incluso en el peor de los casos solo se vuelve unas 4 veces más lento, y el nombre está buenísimo. ¡Filthy way! ¡Filthy way!

    • Sobre la pregunta de si Fil-C permitiría multitarea entre procesos no confiables en computadoras sin MMU: en principio, FUGC sí se basa en funciones del sistema operativo que dependen de la MMU, pero creo que podría hacerse una versión sin esa dependencia. En cuanto al rendimiento, eso de 4 veces más lento es el peor escenario, y yo mismo reporté esa cifra. Tiendo a medir el rendimiento siempre de forma realista y a mejorar obsesivamente los problemas de performance. De hecho, incluso con versiones Fil-C del software puedo usar sin problema programas que utilizo normalmente en mi día a día

    • Dijeron que la lista de software compatible era impresionante; estoy de acuerdo en términos generales, pero veo esos ejemplos un poco distinto. CPython, Perl5 y similares son runtimes de lenguajes que ya de por sí son famosos por tener GC lento, así que ponerles encima otro GC no parece precisamente un diseño elegante, y de hecho podría penalizar bastante el rendimiento. Además, ya existen algunos intentos de reimplementarlos o sustituirlos con Rust o Go; por ejemplo, para SQLite está Turso. Y como este tipo de software son proyectos fundamentales muy activos, podría pasar que algún día hagan por su cuenta un refactor importante o un port a Rust. Más bien creo que Fil-C encaja mejor en software menos mantenido, menos sensible al rendimiento, pero que igual se sigue usando, como un programa en C de hace 50 años que alguien todavía saca de vez en cuando

    • Una ventaja de que SQLite esté escrito en C es su portabilidad a sistemas operativos no estándar. Por ejemplo, tengo experiencia usándolo directamente sobre μC/OS-II, un RTOS para embebidos. El diseño de entornos embebidos es bastante distinto al de PC/servidor: para rendimiento y para evitar fragmentación de memoria, a veces ni siquiera se libera memoria y en su lugar se marcan objetos/estructuras para reutilizarlos. Es una idea como asignación de heap personalizada o pooling. Documentación de VFS de SQLite, introducción a Micro-Controller OS

    • Dijeron que ese software en C de la lista no se va a reescribir en Rust, y me da curiosidad cuánto falta para que las herramientas de análisis estático basadas en IA mejoren al punto de detectar con precisión los problemas en código C y darte retroalimentación del tipo “esta parte va a fallar, arréglala así”. Si de verdad aparecen herramientas así, quizá seguir usando C sin más llegue a ser aceptable

    • Solo como referencia: Fil-C todavía no soporta sistemas de 32 bits (o menores). Documentación sobre Invisicaps en Fil-C

  • Da la impresión de que este proyecto es uno de esos casos raros que persiguen a la vez investigación y utilidad práctica. Normalmente cosas así las hace un gran gigante tecnológico con un equipo financiado por ingresos publicitarios; me da curiosidad saber de qué contexto salió Fil-C. Si no es simplemente un proyecto personal hecho por pasión, quisiera saber quién puso el dinero, cuántos años-persona se invirtieron y cuál es el objetivo final

    • En lo personal, esto me parece un proyecto por pura pasión

    • Sobre la pregunta del objetivo final: en el proyecto se indica que el copyright es 2024-2025 Epic Games, Inc.

  • Qué bueno que Fil-C exista. Incluso si este tipo de tecnología resulta efectiva en programas reales, mucha gente desarrolladora suele creer que “eso no se puede hacer”; el simple hecho de demostrar que sí puede implementarse ya corta de raíz un montón de discusiones

    • Me gustaría ver benchmarks. La mayor preocupación con un enfoque así es si el rendimiento se desploma demasiado en ciertos casos de uso donde C/C++ sigue siendo popular. Si el throughput, la latencia o el uso de memoria terminan pareciéndose demasiado a los de Go, entonces al final quedaría poco motivo para elegirlo

    • En los lenguajes de programación, la discusión sobre rendimiento existe desde los tiempos del ensamblador. Pero la mayoría de los desarrolladores no son visionarios extraordinarios como Ivan Suntherland, Alan Kay, Steve Jobs o Bret Victor; son personas comunes que necesitan ver algo funcionando directamente frente a ellos para confiar. Por eso todavía está lleno de clones de UNIX y C, y mucha gente vive repitiendo sin más las visiones del pasado en vez de crear algo nuevo. Claro, esos dos que hicieron UNIX y C en los años 70 también eran grandes visionarios

  • Me pregunto por qué usaron una estrategia de retreating wavefront en lugar de advancing wavefront

  • Si los programas C existentes ya tienen llamadas a free(...) bien colocadas, y además se está administrando información de rango separada para todos los punteros, me pregunto por qué eligieron un GC completo. En su lugar, una técnica de temporal checking tipo lock-and-key (material de referencia: enlace al paper) podría ser mejor para la previsibilidad del uso de memoria, el rendimiento o la planificación. Supongo que quizá el espacio para guardar las keys es demasiado grande, o que las verificaciones tardan mucho, o que en un entorno multihilo aparecen problemas de race condition

    • El enfoque lock-and-key no tiene las características inteligentes propias de Fil-C. La fortaleza del modelo de capacidades de Fil-C es que es completamente thread-safe y, en la mayoría de los casos, no necesita atomics especiales ni locking

    • También me parece interesante que permita aritmética de punteros fuera de rango siempre que no haya dereference del puntero. A veces los compiladores aprovechan ese UB para optimizar (pregunta relacionada en Stack Overflow); me pregunto si en el LLVM interno de Fil-C esas optimizaciones están desactivadas, o si gestionan los punteros como combinación de “base + offset” y así bloquean por completo esa posibilidad. Y, de ser así, también me pregunto si eso no haría perder ciertas optimizaciones que sí se aplican a punteros normales

  • De verdad parece un proyecto muy bueno. Me llamó la atención que el fast path de pollcheck sea simplemente load-and-branch. Hay una técnica interesante que se usa en lugar de este tipo de branch, y está bien explicada en el blog oficial de Android, en "implicit suspend checks"

    • Ese tipo de optimización se usa mucho en poll check. De hecho, la mayoría de las JVM de producción ya la aplican. Pero todavía no estoy en una etapa en la que deba preocuparme por optimizaciones de tan bajo nivel. Ahora mismo todavía me faltan optimizaciones básicas de alto nivel

  • Un C con soporte de concurrencia y con GC, y además con un GC non-moving: eso sí que sorprende. Si en un proyecto mediano en C pudiera reducir bugs de memoria a cambio de perder 2 a 3 veces de rendimiento en tiempo de ejecución, yo estaría dispuesto a aceptarlo. Me pregunto qué tan fácil es adoptarlo de forma gradual. ¿Se puede por objetivo individual, o hay que reemplazar todo el toolchain?

  • Para mí importan C, el rendimiento y la seguridad. Este GC y la estructura de capacidades me resultan atractivos. Varias veces he pensado cómo se vería un “C más seguro”, y aunque he revisado el concepto de capacidades varias veces, no se me da bien meter mano al código de compiladores. Me pregunto si dar soporte para Windows sería difícil

    • Como comentario aparte: la primera oración, al no llevar Oxford comma, me tomó bastante tiempo entenderla. No es común ver un ejemplo tan claro de eso

  • Me pregunto cómo rastrea el GC los root objects. ¿Hay alguna fase de compilación que marque de antemano las raíces que debe escanear el GC? Si alguien sabe, agradecería una explicación

    • LLVM lo resuelve insertando instrucciones para poblar el stack map

  • Este proyecto realmente sorprende. Es raro que nunca hubiera oído hablar de él hasta ahora. Tengo ganas de probarlo. Puede que por límites de rendimiento no sirva para producción en algunos casos, pero como forma de verificar directamente la seguridad de ciertos programas se ve realmente útil. Se siente más abarcador que los sanitizers que uso habitualmente