Marcado y barrido: las raíces, los tres colores y el fin de los ciclos

Hay una pregunta que el recolector de Lua no se hace nunca: ¿alguien sigue usando este objeto? Esa pregunta es indecidible y ningún sistema serio la intenta. La que sí se hace es mucho más humilde y perfectamente mecánica: ¿existe todavía un camino de punteros que llegue hasta aquí desde algún sitio conocido? Toda la maquinaria del recolector —los colores, las listas grises, las barreras que verás en las lecciones siguientes— existe para contestar esa segunda pregunta con exactitud y sin detener el programa más de la cuenta. Entender el algoritmo base no es un lujo académico: es lo que separa a quien acepta que su motor de juego tenga tirones inexplicables de quien sabe exactamente qué está pasando y en qué fase.

Alcanzable, que no es lo mismo que usado

Un recolector con seguimiento parte de un conjunto de objetos que se declaran vivos por definición y desde ahí camina el grafo de punteros. Todo lo que alcanza, vive. Todo lo que no alcanza, muere. Ese conjunto de partida son las raíces, y en Lua es asombrosamente pequeño: el hilo principal, el registro —la tabla interna donde la biblioteca de C guarda lo que quiere mantener vivo, y que contiene a su vez la tabla de globales— y las metatablas de los tipos básicos que el estado cachea.

Eso es todo. Tu tabla de configuración global no es una raíz: vive porque el registro apunta a la tabla de globales, y esa tabla apunta a ella. Una variable local viva no es una raíz: vive porque está en la pila de un hilo, y el hilo cuelga del registro o de otro objeto alcanzable. La consecuencia práctica es que una fuga de memoria en Lua tiene siempre la misma forma, sin excepción: alguna estructura alcanzable guarda una referencia que ya no te sirve. No hay fugas espontáneas; hay caches sin política de expulsión, listas de observadores que nunca se dan de baja y closures que capturan más de lo que necesitan.

local registro_de_eventos = {}          -- alcanzable desde _G

local function suscribir(objeto_pesado)
  registro_de_eventos[#registro_de_eventos + 1] = objeto_pesado
end

do
  local temporal = { datos = string.rep("x", 1e6) }
  suscribir(temporal)
end
-- temporal salio de alcance, pero el objeto sigue vivo:
-- hay un camino desde el registro hasta el, y con eso basta.
collectgarbage("collect")
print(collectgarbage("count"))           -- el megabyte sigue ahi

La distancia entre dejé de usarlo y dejó de ser alcanzable es donde vive el noventa por ciento de los problemas de memoria en programas Lua reales. El recolector es correcto; el grafo es lo que está mal.

De esa misma observación sale el método de diagnóstico, que es más mecánico de lo que parece. Ante una memoria que crece sin parar, la pregunta no es qué está fallando sino qué camino queda, y ese camino empieza obligatoriamente en una de las cuatro raíces. Recorrer el grafo desde la tabla de globales anotando qué se alcanza y comparar dos instantáneas separadas en el tiempo localiza al culpable en minutos, porque la estructura que crece entre ambas fotos es exactamente la que retiene lo que no debería.

El invariante de los tres colores

El marcado clásico de Dijkstra reparte los objetos en tres clases durante el recorrido, y esas clases se llaman colores por tradición.

• Blanco: no visitado todavía. Al final del marcado, blanco significa basura.
• Gris: visitado, pero sus referencias aún no se han explorado. Es la frontera del recorrido, la lista de pendientes.
• Negro: visitado y con todos sus hijos ya visitados o encolados. Terminado.

El algoritmo es un recorrido en anchura con una sola regla: se toma un objeto gris, se pintan de gris todos los blancos a los que apunta y el objeto pasa a negro. Se repite hasta que no queda nada gris. Entonces todo lo alcanzable es negro y todo lo blanco es, demostrablemente, inalcanzable.

flowchart LR
B[Blanco: no visitado, candidato a basura] --> G[Gris: visitado, hijos pendientes]
G --> N[Negro: visitado, hijos ya encolados]
N -.-> G
R[Raices: hilo principal, registro, metatablas de tipos basicos] --> G

De aquí sale el invariante tricolor, que es la afirmación central de todo el sistema: ningún objeto negro apunta directamente a un objeto blanco. Mientras eso se cumpla, el conjunto gris contiene toda la frontera pendiente y el algoritmo no puede perder nada por el camino. Cuando el gris se vacía, la clasificación es completa y correcta.

Ese invariante es trivial de mantener si el programa está parado durante todo el marcado, porque nadie mueve punteros mientras el recolector camina. En cuanto se permite que el programa siga ejecutándose entre paso y paso —que es de lo que trata la lección siguiente— el invariante deja de ser gratis y hay que defenderlo activamente. La flecha punteada del diagrama, la que devuelve un objeto de negro a gris, es exactamente el precio de esa defensa.

Barrido, y por qué el blanco cambia de bando

Terminado el marcado, la fase de barrido recorre linealmente la lista de todos los objetos creados. Los negros vuelven a blanco, preparados para el siguiente ciclo. Los que siguen blancos se liberan. Es una pasada simple, sin recursión y sin decisiones: la inteligencia estaba toda en el marcado.

Pero aquí aparece un problema de sincronización que conviene ver, porque explica un detalle del que se habla poco. Si el programa puede crear objetos mientras el recolector barre, ¿de qué color nace un objeto nuevo? Si nace blanco, el barrido que aún no ha llegado a su posición lo liberará, y habremos matado un objeto recién nacido y perfectamente vivo. Si nace negro, sobrevive, pero rompe el invariante en cuanto apunte a algo blanco.

La solución de Lua son dos blancos alternos. El estado mantiene una noción de blanco actual que se invierte al final de cada ciclo. Un objeto blanco del ciclo anterior es basura confirmada; un objeto blanco del ciclo en curso está recién nacido y es intocable. El barrido solo libera lo que lleva el blanco viejo, y así puede convivir con un programa que sigue asignando memoria a su espalda.

-- Lo que un ciclo completo hace, visto desde fuera:
--   1. pausa      esperar a que la memoria crezca lo suficiente
--   2. marcado    tenir de gris las raices y propagar hasta vaciar
--   3. atomico    cerrar el marcado sin interrupciones y cambiar el blanco
--   4. barrido    liberar lo que quedo con el blanco viejo
--   5. finales    ejecutar los finalizadores pendientes

print(collectgarbage("count"))   -- kilobytes en uso, con decimales
collectgarbage("collect")        -- fuerza un ciclo completo
print(collectgarbage("count"))   -- lo que de verdad estaba vivo

Conviene fijarse en la asimetría de costes entre las dos fases, porque explica bastantes cosas. Marcar cuesta en proporción a lo vivo: cuanto más grande sea tu grafo alcanzable, más caro. Barrer cuesta en proporción a lo creado, vivo o muerto, porque hay que recorrer la lista entera de objetos para decidir. Un programa con poca memoria viva y mucha rotación tiene marcados baratos y barridos caros; uno con estructuras enormes y estables tiene lo contrario. Saber en cuál de los dos casos estás es el primer paso de cualquier diagnóstico serio.

La fase atómica merece un nombre propio porque es la única parte del ciclo que no se puede trocear jamás. Ahí se vuelve a visitar lo que quedó pendiente, se resuelven las tablas débiles, se separan los objetos con finalizador y se invierte el blanco. Es corta por diseño, y su duración es el suelo absoluto de la pausa que el recolector puede llegar a imponer: por muy incremental que sea el resto, este trozo se paga entero de una vez.

El regalo: los ciclos dejan de existir como problema

Contar referencias es la alternativa obvia y la que muchos lenguajes eligieron. Cada objeto lleva un contador, cada asignación lo sube, cada abandono lo baja, y al llegar a cero el objeto se libera de inmediato. Es determinista, tiene pausas mínimas y una propiedad fatal: no puede liberar ciclos. Dos objetos que se apuntan mutuamente mantienen sus contadores en uno para siempre, aunque nadie más los conozca.

local padre = { nombre = "raiz" }
local hijo  = { nombre = "hoja" }
padre.hijo  = hijo
hijo.padre  = padre        -- ciclo perfecto, natural, correcto

padre, hijo = nil, nil     -- nadie los alcanza ya
collectgarbage("collect")  -- Lua los libera sin despeinarse

Este código es el idioma más natural del mundo: un nodo que conoce a su padre, una vista que conoce a su modelo, un buffer que conoce a la ventana que lo muestra. En un lenguaje con conteo de referencias puro, ese hijo.padre es una fuga, y el programador tiene que aprender un vocabulario entero de referencias débiles y punteros no propietarios para evitarla. En Lua no tiene que aprender nada, porque el recolector no pregunta cuántos te apuntan, sino se llega hasta ti, y a un ciclo aislado no se llega.

La contrapartida es igual de real y hay que enunciarla con la misma claridad. El conteo de referencias libera en el instante exacto en que la última referencia desaparece, y esa inmediatez es una propiedad valiosísima cuando el objeto retiene algo escaso: un descriptor de fichero, una conexión, un bloqueo. El recolector con seguimiento no ofrece nada parecido: un objeto muere cuando deja de ser alcanzable, pero se libera cuando el recolector pase por ahí, y esa distancia puede ser de milisegundos o de minutos. Lua asume ese intercambio conscientemente —recorre el grafo en vez de contar, y a cambio pierde el momento— y compensa la pérdida con un mecanismo aparte, las variables de cierre, que no tienen nada que ver con el recolector porque el problema que resuelven tampoco lo tiene.