El recolector de basura

El recolector de basura (en inglés, garbage collector) es la parte de un lenguaje de programación que devuelve al sistema la memoria que el programa ya no puede usar. Un programa en marcha crea objetos sin parar, cadenas de texto, listas, registros leídos de una base de datos, y cada uno ocupa un trozo de memoria que alguien tiene que liberar cuando deja de hacer falta. En lenguajes como C lo hace el programador, pidiendo memoria y devolviéndola a mano, y los dos errores posibles son famosos: olvidarse de devolverla, con lo que el programa engorda hasta que el sistema lo mata, o devolverla mientras otra parte del programa aún la usa, con lo que esa parte lee basura o escribe sobre datos ajenos. El recolector quita esa tarea de las manos del programador y la convierte en un trabajo de la máquina.

La figura de esta página es un trozo de memoria con sus objetos y las referencias entre ellos. A la izquierda están las raíces, las variables que el programa tiene a mano en ese momento; cada flecha es una referencia de un objeto a otro. Se pueden crear objetos, soltar referencias y, cuando se quiera, recolectar. Con el método de marcar y barrer, el recolector sale de las raíces, sigue las flechas y marca todo lo que alcanza; lo que se queda sin marcar es basura, aunque tenga flechas entrantes desde otra basura. Con el método de contar referencias, cada objeto lleva la cuenta de cuántas flechas le llegan y se libera en cuanto baja a cero, y la figura enseña su punto ciego: dos objetos que se apuntan entre sí y a los que ya no apunta nadie nunca llegan a cero.

La definición que hace posible todo esto es más sutil de lo que parece. Un recolector no sabe qué memoria va a usar el programa en el futuro, que es lo que de verdad importa; lo que sabe calcular es qué memoria puede alcanzar, siguiendo referencias desde las variables vivas. Basura es todo lo que no se alcanza, porque un programa no tiene manera de llegar hasta ello. Esa sustitución de «lo que no se usará» por «lo que no se puede usar» es el truco entero, y significa que un recolector no evita las fugas de memoria: un objeto que alguien sigue referenciando sin querer, un registro de eventos que nadie vacía, una caché que solo crece, es alcanzable, y por tanto se queda.

John McCarthy inventó el mecanismo en 1959 para Lisp, cuyo único material eran celdas de lista enlazada que se creaban y abandonaban a cada paso, y lo describió en el artículo de 1960 que presentaba el lenguaje. Su recolector arrancaba solo cuando la memoria se agotaba, marcaba desde las raíces y barría el resto, y detenía el programa mientras tanto; el nombre, según contó él mismo, era ya un chiste de la época. El mismo año George Collins propuso la alternativa de contar referencias, que no para el programa y libera cada objeto en el instante en que deja de usarse, a costa de actualizar una cuenta en cada asignación y de no ver los ciclos. Las dos ideas siguen vivas sesenta años después. Python, Swift y PHP cuentan referencias, Python con un recolector de ciclos de refuerzo; Java, C#, JavaScript y Go marcan y barren, cada uno a su manera.

La gran mejora llegó con una observación empírica. Henry Lieberman y Carl Hewitt en 1983, y David Ungar poco después, midieron que la mayoría de los objetos muere muy joven: se crean, se usan en un cálculo y sobran a los pocos milisegundos, mientras que los que sobreviven un rato suelen sobrevivir mucho. Un recolector generacional separa la memoria en una zona de recién nacidos, que se limpia muy a menudo y muy deprisa porque casi todo lo que hay en ella es basura, y una de veteranos, que se revisa poco. Los recolectores modernos añaden a eso el trabajo concurrente, marcar mientras el programa sigue corriendo en otros procesadores, para que las pausas en las que todo se detiene bajen de los segundos de los primeros Lisp a menos de un milisegundo. Esas pausas son el precio visible de la técnica, y el motivo de que los videojuegos, los sistemas de negociación bursátil y los motores de aviones hayan desconfiado de ella.

Marcar es una búsqueda en anchura o en profundidad sobre el grafo de objetos, y las raíces son, sobre todo, las variables de las funciones que están en la pila de llamadas en ese momento, más las globales. El recolector trabaja por debajo del lenguaje y por encima del sistema operativo, que solo conoce páginas de memoria y no objetos, y que liberará de golpe todo lo que quede cuando el programa termine. Rust, el lenguaje que más ha discutido esta herencia, no lleva recolector: su compilador calcula en qué punto del programa cada valor deja de tener dueño y pone ahí la liberación, de forma que la memoria se devuelve en un momento conocido y sin pausas, y deja el conteo de referencias para los casos en que el dueño no puede decidirse de antemano.

Lo que se gana con un recolector es atención. El programador deja de pensar en quién libera qué y en qué orden, que es la fuente de una parte enorme de los fallos de seguridad del software escrito en C, y la máquina pone a cambio algo de tiempo y algo de memoria de más. Lo que no se gana es inmunidad: la fuga en un lenguaje con recolector es una referencia que uno se ha olvidado de soltar, y encontrarla exige volver a mirar el grafo de la figura, raíz por raíz, para ver por qué sigue llegando una flecha.

La lista enlazada – La búsqueda en anchura y en profundidad – La variable – El sistema operativo – Del código al proceso