Guía definitiva del Recolector de Basura en Javascript

16 Nov 2016

Introducción

El recolector de basura (también llamado GC por sus siglas en inglés) es un concepto que todos los desarrolladores conocen en mayor o menor medida, pero en torno al cual siempre existen lagunas relacionadas con su funcionamiento e implementación. En este artículo vamos a tratar de explicar todo lo relativo a este sistema de gestión de memoria, partiendo de la teoría más general hasta llegar a sus particularidades dentro del lenguaje Javascript.

La intención de esta guía es la de resultar una herramienta teórica para desarrolladores. Para ello, estudiaremos las especificaciones de los motores más importantes a día de hoy sin entrar a discutir cuál ofrece mejor o peor rendimiento. En su lugar, trataremos de aportar las pistas para aprovechar en la medida de lo posible sus características y detectar posibles problemas relacionados en nuestros programas.

Concepto

Dentro de las Ciencias de Computación, el recolector de basura, o garbage collector en inglés (GC), es un mecanismo implícito de gestión de memoria. Esta herramienta fue inventada por John McCarthy a finales de los años 50 del pasado siglo como una solución automática a la gestión manual de memoria para el lenguaje Lisp.

John McCarthy (1927 – 2011), también conocido como Tío John McCarthy, fue un prominente informático que recibió el Premio Turing en 1971 por sus importantes contribuciones en el campo de la Inteligencia Artificial. Padre de dicho término, desarrolló la familia de lenguajes de programación Lisp, influenció de forma significativa el desarrollo del lenguaje ALGOL y es también considerado como el primero en utilizar el concepto de cloud computing.

Fundamentos

Todo lenguaje de programación de bajo nivel requiere de una cantidad de memoria para trabajar. En esta memoria, cedida por el Sistema Operativo, cada programa debe ser capaz ubicar los objetos que está manejando en tiempo de ejecución, monitorizar su estado, reciclarlos cuando ya no son necesarios e, idealmente, compactar el espacio resultante para optimizar el rendimiento.

La gestión de dicha memoria, dependiendo del lenguaje, puede ser de dos tipos: manual o automática.

Gestión manual de memoria

La gestión manual de memoria, es aquella donde se asignan y liberan los recursos de memoria de forma explícita. Esto significa que es el desarrollador quien debe administrar los registros asignando memoria a sus objetos mediante punteros y liberarlos cuando ya no sean necesarios.

En Ciencias de la Computación, un puntero es un objeto del lenguaje de programación cuyo valor se refiere a (o “apunta a”) otro valor almacenado en una dirección de memoria diferente.

Wikipedia, Puntero (informática)

Hasta mediados de los años 90, pese a que ya se habían introducidos modelos automáticos (como el caso de Lisp), la mayoría de lenguajes utilizados en la industria requerían de este tipo de gestión de memoria.

Algunos de estos, aún populares a día de hoy (en según qué ámbitos), son: C, C++, Pascal, Ensamblador, Fortran o Prolog.

Gestión automática: GC

La gestión automática de memoria, también denominada gestión implícita, es aquella donde las tareas de reserva, monitorización y reciclaje son llevadas a cabo por el propio sistema sin la intervención del programador. Es en este escenario donde el Recolector de Basura se encarga de identificar y eliminar la memoria ocupada por objetos que ya no están en uso por el programa (conociéndose a esta memoria residual como ‘basura’).

Desde mediados de los noventa, este sistema ha ido creciendo en popularidad a raíz del lenguaje Java, extendiendo su paradigma a los más recientes como Ruby, Javascript, Swift o GO.

Funcionamiento del Recolector de Basura

Como ya se ha indicado, el propósito del recolector es monitorizar la memoria reservada del sistema para detectar cuándo ésta ya no es necesaria y, eventualmente, liberarla para devolverla al SO (sistema operativo) o al pool del propio programa.

Un pool o fondo en informática es un conjunto de recursos inicializados que se mantienen listos para su uso, en lugar de ser asignados y destruidos bajo demanda.

Wikipedia, Pool (informática)

En los lenguajes de alto nivel, cuando un programa es compilado, se incluyen de forma predeterminada las subrutinas que constituyen el propio recolector. De este modo, el sistema ya cuenta con las herramientas necesarias para ejecutar periódicamente el procedimiento de optimización de forma desatendida y automática.

Será durante esa ejecución cuando el recolector se encargue de recorrer los espacios de memoria definidos por el lenguaje evaluando las referencias de los objetos que la ocupan.

Referencias

El aspecto clave para entender el funcionamiento del recolector, es el concepto de referencia.

Dentro del contexto de gestión de memoria, se dice que un objeto referencia a otro si el primero tiene acceso al segundo (ya sea de forma implícita o explícita).

Objetos atómicos

Derivado de lo anterior, surge otro concepto básico en la terminología de gestión de memoria como es el de objeto atómico (‘leaf object‘ en inglés).

Un objeto atómico es aquel que no hace referencia a ningún otro objeto. En un lenguaje tipado, el compilador a menudo puede determinar en tiempo de compilación que ciertos tipos pueden ser representados unívocamente como objetos atómicos. Normalmente éstos son de un tipo escalar o un tipo vectorial de escalares con magnitud limitada.

Dicho de otro modo, aquel objeto que por su naturaleza solo puede contener un valor y no referenciar a otro, se denomina atómico. Volveremos a este concepto cuando tratemos los pormenores del sistema en Javascript.

Algoritmos de recolección de referencias

La implementación del recolector de basura puede variar de un lenguaje de programación a otro, al igual que de una biblioteca a otra. Esto posibilita diferentes aproximaciones o algoritmos, cada una con sus ventajas e inconvenientes.

La literatura sobre el recolector de basura es extensa y muy técnica; el procedimiento actual para la recolección es un aspecto específico de cada implementación, por lo que puede variar entre los diferentes lenguajes.

David Flanagan, JavaScript, The Definitive Guide (Fourth Edition). Traducción propia.

Pese a estas diferencias prácticas, podemos agrupar los principales algoritmos de recolección en dos familias teóricas principales: el conteo de referencias y el marcado.

Recolección de basura por conteo de referencias

NOTA: Incluimos este sistema por razones didácticas pero, a día de hoy, se considera obsoleto y en desuso. Ni Javascript, ni la mayoría de lenguajes modernos utilizan este algoritmo, por lo que si el lector busca el aspecto práctico de este artículo, le invitamos a saltar al siguiente punto.

El conteo de referencias (o Reference Counting) es la técnica más sencilla para identificar direcciones de memoria que no están actualmente en uso. El proceso realiza una administración automática de la memoria al mantener una contabilidad en cada objeto, normalmente en su cabecera, de cuántas referencias apuntan al mismo.

Si un objeto, o dirección de memoria, no está siendo referenciado por ningún otro, se considera que no está en uso y, por tanto, puede ser liberado.

En la nomenclatura propia de la gestión de memoria, decimos que un objeto referenciado por al menos otro es un objeto vivo, en oposición a aquel no referenciado y que denominamos objeto muerto.

Este planteamiento presenta una serie de desventajas:

  • El campo del objeto que se utiliza para llevar el conteo posee un tamaño limitado y, por lo tanto, el sistema puede colapsar si el número de referencias posibles a dicho objeto es ilimitado;
  • El recuento de referencia implica una operación en cada modificación de un puntero, lo que aumenta el tamaño del código, la demanda de ancho de banda de memoria, y puede derivar en una grave penalización de rendimiento (especialmente en entornos multihilo donde las actualizaciones de conteo de referencia requieren sincronización).
  • Cada objeto necesita un tamaño ligeramente mayor para almacenar el recuento de referencia;
  • Si alguno de los objetos forma parte de una estructura de datos cíclicos, siempre tendrá un recuento de referencia distinto de cero y, por lo tanto, no podrán ser reciclados cuando ya no sean necesarios.

Ciclos

En programación, nos referimos a ciclos cuando una serie de objetos se referencian entre sí creando un bucle cerrado. Al conjunto de referencias mutuas se le conoce como Referencia Circular (Circular reference).

Las referencias circulares aparecen en programación cuando una pieza de código requiere el resultado de otra, pero ese código necesita, a su vez, el resultado de la primera.

Wikipedia, Circular reference

circular-reference

Ejemplo de referencia circular (en rojo)

Como revela la anterior ilustración, si un objeto X contiene una referencia a un objeto Y, y ese objeto Y contiene una referencia al objeto X, ambos objetos forman un conjunto mutuamente dependiente. Aunque todo el conjunto quede en desuso y no sea necesario en el programa, su conteo de referencias siempre mostrará al menos una dependencia, por lo que el recolector no puede actuar sobre él.

Para lidiar con los problemas enumerados anteriormente, los sistemas de gestión evolucionaron con algoritmos más complejos y precisos. Y es así como llegamos a las soluciones modernas, derivadas todas ellas en mayor o menor medida de la familiar de algoritmos que trataremos a continuación: el de marcado y barrido.

Recolección de basura por marcado y barrido: Mark-Sweep

A día de hoy, todos los recolectores de basura modernos basan su funcionamiento en alguna variante de los algoritmos Mark-Sweep.

En esencia, este algoritmo realiza dos operaciones básicas. La primera, debe ser capaz de ‘marcar’ qué objetos son inalcanzables y la segunda, debe poder ‘barrer’ la memoria que ya no es necesaria para devolverla nuevamente al programa.

Fase de marcado

La fase de marcado (‘Mark‘) se basa en los conceptos de ‘alcance‘ y ‘raíz‘ tomando todos los valores de un entorno y determinando si son o no accesibles por el programa.

Los objetos se agrupan así en accesibles (directa o indirectamente) e innaccesibles. Ambos términos se corresponden con los ya mecionados objetos ‘vivos’ y ‘muertos’ respectivamente.

Los objetos que un programa puede acceder directamente son aquellos que han sido referenciados por las variables globales (conocidas éstas últimas como raíces), mientras que los objetos indirectamente accesibles son aquellos referenciados por algún otro objeto accesible (directa o indirectamente).

marking-objects

Representación del marcado de objetos a partir de una raíz. Imagen original aquí

El marcado sobre un objeto indicando si está o no vivo, puede realizarse de dos formas: con un bit asociado en la propia memoria reservada del objeto que sirve de marca (Bit Mark), o utilizando un mapeado a modo de diccionario (Bitmap Marking).

Bit de Marca (Bit Mark)

La marca de bit (también llamada One-bit o Bit Mark) es una variante del conteo de referencias tradicional donde se utiliza un indicador (flag) de un bit asociado al puntero del objeto para indicar si éste tiene al menos una referencia apuntándole. Si eliminamos una referencia a un objeto marcado, el sistema debe volver a escanear su raíz para actualizar dicha marca.

Mapeado de bits (Bitmap Marking)

En los recolectores de tipo Mark-Sweep, un marcado de tipo bitmap es una técnica en la que se almacena la correspondiente marca de bit de un objeto en un rango de memoria separado que constituye un diccionario. Esto favorece la identificación de cada referencia así como diversos sistemas de caché al evitar al sistema recorrer cada página de memoria para alterar un bit directamente en el objeto marcado.

Fase de barrido

Una vez el sistema ha trazado el alcance de todos los objetos desde la raíz, el siguiente paso es eliminar aquellos que han quedado aislados y que, por tanto, son considerados como desechables. Esa labor le corresponde a esta segunda fase de barrido (o ‘Sweep‘).

El barrido es la segunda fase dentro de un sistema de gestión Mark-Sweep. En ella, se realiza una transferencia secuencial (dirección-orden) sobre la memoria para reciclar aquellos bloques que permanecen sin marcar. Como paso previo, el barrido normalmente reúne todos estos bloques en una o más listas libres.

recollection

Esquema representando el resultado de un barrido tras la recolección

Compactación

Un aspecto a tener en cuenta es que tras el reciclaje de objetos la memoria del sistema puede terminar muy fragmentanda ralentizado con ello futuras asignaciones. Es por ello que muchos gestores realizan en esta fase de barrido un compactado de la memoria reduciendo con ello los espacios vacíos entre registros y mejorando el rendimiento posterior del recolector.

Dicho de otro modo, la compactación es el proceso de mover y reubicar los objetos vivos para eliminar el espacio muerto que ha podido quedar entre ellos..

gc-mark-sweep-compact

Representación del proceso de compactado tras el barrido.

Gestión de memoria en Javascript

Los procedimientos y fases que hemos visto hasta ahora son planteamientos teóricos cuya implementación depende del lenguaje o sistema sobre el que se está trabajando.

Javascript, que es el caso que nos ocupa, posee además la característica de que dispone de varias implementaciones sobre un mismo estándar, en este caso, ECMAScript. La lista de motores es muy amplia, lo que implica que también un número igual de implementaciones del recolector de basura.

A continuación, explicaremos las nociones básicas de gestión que pueden resultar comunes a todos ellos, deteniéndonos más en detalle sobre las particularidades de los motores más utilizados a día de hoy: V8 (Chrome, Node.js, Opera), SpiderMonkey (Firefox) y Chakra (Internet Explorer, Edge).

Comencemos pues con las bases comunes.

Tipos de datos primitivos

Antes de entender cómo trabaja la gestión de memoria Javascript, debemos conocer qué tipo de valores se almacenan y cómo estos funcionan dentro de la estructura general de grafos. Para ello, nos detenemos en primer lugar con los tipos de datos primitivos.

En Javascript, una primitiva es un dato inmutable que no constituye un objeto y que no posee métodos.

Dentro del lenguaje tenemos 6 tipos de datos primitivos: string, number, boolean, null, undefined, y el recientemente incorporado symbol (ECMAScript 2015).

De entre los anteriores, detallemos aquellos que están directamente relacionados con la gestión de memoria:

String

Cadena de datos textuales constituida por un conjunto de elementos de valores de 16 bits. A diferencia de lenguajes como C, las cadenas en Javascript (como valores primitivos que son) son immutables. Esto quiere decir que una cadena, una vez creada, no puede modificarse. Sin embargo, sí es posible crear una nueva cadena a partir de la manipulación mediante operaciones de la cadena original.

Number

De acuerdo con la especificación, solo existe un tipo de número en Javascript: el formato de coma flotante de doble precisión de 64 bits. Este se corresponde con un valor que abarca entre -(2^53 -1) y (2^53 -1). No existe el tipo específico para enteros (32 bits) en oposición a los valores en coma flotante.

Además de los valores anteriores, este tipo posee tres valores simbólicos: +Infinity, -Infinity, y NaN (not-a-number).

Boolean

Boolean representa una entidad lógica que puede albergar uno de dos valores posibles: true (verdadero), y false (falso).

Estas primitivas, no pueden referenciar a ningún otro valor. En un grafo de objetos, estos valores son siempre atómicos, y ello significa que no tienen descendientes ocupando así el último elemento de cada rama.

En este esquema, solo puede existir un tipo de contenedor: el objeto principal (Object). En Javascript, este objeto actúa como raíz, siendo de él del que parten todas las relaciones con el resto de valores.

graph-model

Grafo representativo del modelo de objetos Javascript. Original aquí

La imagen anterior se describe como sigue:

  • Raíz: marcada con el punto azul, se corresponde con el Objeto principal. Este objeto puede referirse al objeto léxico global o a una clausura. Por ejemplo, el objeto window.
  • Valores de objeto: indicados mediante puntos rojos, estos valores se corresponden con objetos definidos explícitamente (por ejemplo, funciones).
  • Valores escalares: indicados con puntos verdes, estos son las primitivas inmutables del lenguaje y, por tanto, último extremo de cada nodo. Estos valores serían por ejemplo las cadenas, números o booleanos anteriormente citados.

Lógica de asignación de memoria en Javascript

Una vez establecidos los tipos de valores almacenables, veamos la lógica de asignación en Javascript a través de sencillos ejemplos:

// Reserva de memoria para un número (Number)
let num = 12345;
 
// Reserva de memoria para dos números (Number)
let [ num1, num2 ] = [ 1, 2 ];
 
// Reserva de memoria para dos números (Number) y un array (Object)
let [ a, b, ...rest ] = [ 1, 2, 3, 4, 5 ];
 
// Reserva de memoria para una cadena (String)
let str = 'Hello World'; // Reserva para cadena (String)
 
// Reserva de memoria para un objeto (Object) y sus valores
let obj = {
    x: 12345,           // Reserva para número (Number)
    y: 'Hello World',   // Reserva para cadena (String)
    z: x => x * 2       // Reserva para una función (Object)
};
 
// Reserva de memoria para un array (Object)
let arr = [ 35, 25, 10, 45, 3 ];
 
// Reserva de memoria para una función (Object)
let fn = ( x ) => x * 2;    // Los argumentos de una función, también
                            // reservan memoria según su tipo de datos.
 
// Reserva de memoria para una función utilizada como expresión (Object)
arr.sort( ( a, b ) => a - b );  // a y b reservan memoria para sendos números (Number)
 
// Reserva de memoria para un objeto Date (Object)
let d = new Date();

Asignaciones por referencia

En Javascript, cuando asignamos a una variable el valor de un array o un objeto ya definido previamente, estamos creando una referencia a dicho valor. Dicho de otro modo, no estamos copiando/clonando un objeto, sino apuntando a la dirección de memoria donde está almacenado su valor.

Es debido a esta referencia que el sistema no reserva memoria para dicho tipo, sino que únicamente se limita a crear un puntero:

let arr = [ 1, 2, 3, 4, 5 ],    // Reserva de memoria para un array (Object)
    copyArr = arr;              // NO se reserva memoria para un array.
                                // Se guarda solo el puntero a su referencia
 
let obj = {                     // Reserva de memoria para un objeto (Object)
    foo: 'Hello World'          // Reserva de memoria para una cadena (String)
},
    copyObj = obj               // NO se reserva memoria para un objeto
                                // Se guarda solo el puntero a su referencia

Con el ejemplo de una cadena (String), la cosa puede variar. Como ya mencionamos más arriba, las primitivas son inmutables (una vez creadas no pueden ser modificadas), pero sí pueden construirse nuevos valores partiendo de otros previamente definidos. En este caso, será el sistema (y la lógica de su implementación) el que decida si un valor derivado debe copiarse como un objeto nuevo o únicamente como un puntero relacionado:

let str = 'La donna e mobile',      // Reserva de memoria para una cadena (String)
 
    newStr = str.substr( str, 8 );  // El sistema puede NO reservar memoria para
                                    // una cadena (String), sino solo un puntero
                                    // para el rango [ 0, 8 ] del original

Cuando en lugar de copiar por referencia forzamos una clonación, el sistema sí reserva la memoria necesaria para un nuevo objeto:

let arr = [ 1, 2, 3, 4, 5 ],        // Reserva de memoria para un array (Object)
    cloneArr = arr.slice();         // Reserva de memoria para un array (Object)
 
let obj = {                         // Reserva de memoria para un objeto (Object)
    foo: 'Hello World'              // Reserva de memoria para una cadena (String)
},
    objCopy = Object.assign( {}, obj ); // Reserva de memoria para un objeto y sus propiedades

Lógica de reciclaje de memoria en Javascript

Antes de pormenorizar en los métodos utilizados por cada implementación, conviene aclarar que, como en cualquier lenguaje, el objetivo del recolector de basura es la de liberar memoria que actualmente no está en uso por parte del programa. Para ello, la lógica con la que el sistema marca si un valor es o no reciclable, radica en determinar si existe una ruta desde la raíz hasta dicho valor.

graph-model-broken

En este grafo, el recuadro negro marca aquellos valores huérfanos que pueden pasar a ser reciclados. Original aquí.

Estrategia del algoritmo Mark-Sweep

Como veremos a continuación tratando cada uno de los motores, todos los recolectores Javascript utilizan en la actualidad la metodología Mark-Sweep para gestionar su memoria.

Como ya analizamos más arriba, este conjunto de procedimientos se dividen en dos sub procesos o etapas que son los que dan nombre al sistema: la fase de marcado (mark) y la de barrido (sweep).

Fase de marcado

Vista ya la lógica de asignación en Javascript, recordamos cómo cada vez que creamos un objeto se reserva un espacio de memoria según el tipo de datos necesario. De forma paralela, se asigna también una marca para monitorizar su alcanzable desde el objeto raíz (bien se trate del objeto léxico global, o del scope de función).

El recolector puede así recorrer de forma periódica todo el listado de variables en un entorno dado, marcando cada valor que es referido por estas variables. Si una de estas referencias es un objeto (Object) o un array (internamente tratado también como un Object), se marca de forma recursiva cada una de sus propiedades (para los primeros) o elementos (para el segundo).

Al escanear cada nodo de forma recursiva, el recolector puede localizar (y marcar) cada valor unitario que es alcanzable, desechando aquellos que quedan sin marca y que se identifican por tanto como basura.

Para realizar este proceso y monitorización de las marcas, los motores de Javascript modernos implementan una tabla sobre la que se realiza el mapeado (el Bitmap Marking que ya analizamos más arriba).

bitmap-marking

Representación de un mapa de marcas

NOTA: Obsérvese en la imagen anterior cómo el árbol de objetos responde a un modelo similar al estudiado por la Teoría de Grafos. Efectivamente, la memoria en Javascript puede ser conceptualizada como un grafo y de hecho, ésta juega un importante papel en los cálculos internos de los sistemas de gestión.

Dependiendo de la implementación, cada motor Javascript actuará de una forma diferente aunque todos responden, como veremos a continuación, a un modelo generacional. Esto quiere decir que si un objeto es referenciado por otro, su valor promociona entre distintos espacios pre establecidos. Sucesivos recorridos del recolector determinarán el ciclo de vida de estos valores según el espacio que ocupan: aquellos objetos que continúan siendo referenciados en el tiempo constituirán los espacios permanentes mientras que los huérfanos, se preparan en otros perecederos para posterior reciclaje.

Con las marcas establecidas y los objetos debidamente ubicados en su espacio correspondiente, se procede con la siguiente etapa del algoritmo: el barrido.

Fase de barrido

En este sub proceso, el recolector tiene información sobre todos los objetos dentro de un determinado ámbito, ya sea este el objeto léxico global, o el scope de una función.

Revisando así los espacios reservados, el sistema conoce por un lado qué objetos han sido marcados como ‘inalcanzables’ (reciclables), mientras que por otro, sabe qué objetos permanecen vivos (compactables).

La división de la memoria en estos espacios independientes, permite al recolector trabajar de forma eficiente sin necesidad de recorrer todo el árbol de nodos a cada iteración.

Aquellos valores (células o celdas según la terminología de cada motor) que habiten las tablas establecidas por el sistema como inalcanzables pueden ser liberadas devolviéndose así la memoria al sistema operativo (SO) o a la piscina de memoria libre (reservada) del navegador (si procede). Al mismo tiempo, las tablas vivas pueden ser compactadas eliminándose el espacio muerto entre objetos y optimizando con ello el rendimiento posterior de la aplicación.

Llegados a este punto, podemos pasar a estudiar las diferentes aproximaciones que los motores actuales utilizan para gestionar la memoria del sistema.

Diferencias entre los principales motores Javascript

v8-spidermonkey-chakra

Excelente ilustración realizada por el artista shoze. Original, aquí.

V8

V8 implementa actualmente un sistema de gestión de memoria basado en el paradigma generacional el cual representa una importante evolución con respecto a su anterior modelo secuencial.

Con este sistema, el motor mantiene dos regiones de memorias diferenciadas e independientes llamadas generaciones (una joven y otra antigua) delimitadas por la edad de los objetos que la componen. De este modo, el recolector se encarga de mover los elementos a lo largo de cada capa, o entre ellas, dependiendo de su longevidad.

Generación Joven

Los nuevos objetos se asignan inicialmente a la generación ‘joven’, la cual se subdivide en otras dos regiones que van intercambiando registros a modo de pilas. Tanto la asignación como el de movimiento entre capas dentro de esta generación es extremadamente rápido (del orden de 10ms).

Cuando ambos espacios se llenan, el sistema escanea todos sus registros para determinar qué objetos son alcanzables desde el raíz. Una vez completado, aquellos que continúan vivos, promocionan desde la generación joven, a la antigua.

Esta promoción, contra lo que puede intuirse, es un movimiento muy poco frecuente. En la práctica, los nuevos valores almacenados rara vez sobreviven el tiempo necesario como para promocionar. Los estudios realizados arrojan cifras de entre un 10 y un 30% de supervivencia con respecto a las colecciones en las generaciones jóvenes.

No importa cómo se realicen las mediciones; todos los estudios concluyen del mismo modo: la mayoría de objetos mueren jóvenes.

Generación Antigua

La segunda región principal de la memoria es la denominada Generación Antigua y a este espacio, como acabamos de ver, las asignaciones se suceden cuando un objeto es promocionado desde la Generación Joven.

V8 utiliza en este espacio el algoritmo ‘mark-compact‘ para sus colecciones. En esencia, este procedimiento es una combinación del ya tratado Mark-Sweep y del Algoritmo Cheney donde primero se marcan los objetos accesibles para luego moverlos hasta el principio de la pila eliminando los espacios intermedios.

Este proceso de reubicación y actualización de punteros implica un tiempo de cálculo largo, del orden de 1 o más segundos. En la práctica, este lapso es asumible dado que este tipo de movimientos son infrecuentes.

Pese a lo anterior, y como ventaja, podemos concluir que dado que no existen dependencias entre ambas generaciones, la evacuación desde el espacio joven y el procesado (compactado) en el antiguo pueden realizarse en paralelo. Esto supone, según las métricas, una mejora sustancial de rendimiento -en torno al 75%- con respecto al anterior modelo secuencial.

parallel-moving

Re acondicionamiento de objetos en paralelo y actualización de punteros

Para más información al respecto:
Back To Basics: Generational Garbage Collection
Jank Busters Part One
Jank Busters Part Two: Orinoco
Effectively Managing Memory at Gmail scale

SpiderMonkey

La implementación del intérprete de JavaScript de Mozilla es similar a V8 en términos generales: ambos son de la familia Mark-Sweep y de marca generacional. Ambos tienen soporte para una recolección incremental y poseen mecanismos para compactar los registros.

Si acabamos de ver cómo V8 divide su memoria en espacios llamados generaciones, SpiderMonkey lo hace en bloques de 4K llamados arenas.

Las Arenas

Las arenas son los espacios generacionales dentro del motor SpiderMonkey. Éstas se componen a su vez de células (también llamadas celdas), las cuales se constituyen con un tamaño y un tipo determinado. Cada tipo de célula se organiza en una arena concreta, siendo así que cada una contiene únicamente células del mismo tipo y tamaño.

arenas-spidermonkey

Diagrama simplificado de arenas con dos tipos diferentes de células

El algoritmo del recolector trabaja así en 3 fases:

  • Selecciona qué céldas hay que mover entre arenas.
  • Mueve las celdas seleccionadas.
  • Actualiza los punteros a las nuevas posiciones

Una arena no puede ser liberada mientras contenga células ‘vivas’. Las células asignadas al mismo tiempo pueden tener diferentes vidas por lo que el sistema puede alcanzar un estado en el que haya muchas arenas almacenando tan sólo unas pocas células. Estos espacios o huecos en las arenas, pueden rellenarse únicamente con nuevas celdas del mismo tipo, pero no pueden devolver la memoria al sistema operativo aunque ésta sea baja.

Es por ello que la gestión de memoria bajo SpiderMonkey depende de forma indisoluble del número de arenas activas, recordando que éstas ocupan un tamaño invariable de 4K.

Layout of an arena:
An arena is 4K in size and 4K-aligned. It starts with the ArenaHeader
descriptor followed by some pad bytes. The remainder of the arena is
filled with the array of T things. The pad bytes ensure that the thing
array ends exactly at the end of the arena.

Comentario extraído del código fuente SpiderMonkey GC

Para más información al respecto:
Compacting Garbage Collection in SpiderMonkey

Chakra

El motor Chakra de Microsoft presente en Internet Explorer y Edge ha sabido también evolucionar desde un modelo conservador de marcas al generacional utilizado por sus competidores, soportando tanto colecciones parciales como concurrentes. Es por esto que al hablar también de los navegadores más recientes de la familia Microsoft, nos encontramos de nuevo frente a un subconjunto de la familia de algoritmos Mark-Sweep.

Siguiendo una estructura similar a la de SpiderMonkey, Chakra asigna objetos ‘simples’ (nombre dado a las primitivas Number -números- y String -cadenas-) en un espacio de memoria diferente al de los objetos regulares (Object). Estas primitivas, como objetos atómicos, no mantienen punteros a otros objetos, lo que implica que no requieran tanta atención durante la recolección como sí ocurre con los objetos regulares.

Esta asignación en espacios separados conlleva además dos ventajas. Primero, todo este espacio puede ser omitido durante la fase de marcado (Mark), lo cual reduce su saturación. Segundo, mientras se continúa con la recopilación simultánea, las nuevas asignaciones no requieren de un re escaneado de todas las referencias.

chakra-gc

Diagrama simplificado con la distribución de células en Chakra

Una característica interesante sobre Chakra es que, utilizado en aplicaciones bajo entornos Windows 10, el host puede administrar cualquier cantidad de memoria demandada por el entorno de ejecución (por ejemplo, un entorno de aplicación completo Javascript con su propio recolector de basura independiente).

Para más información al respecto:
Advances in JavaScript Performance in IE10 and Windows 8
Hosting the JavaScript Runtime

Limitaciones actuales del Recolector de Basura

Aunque ya hemos mencionado que la implementación del GC puede variar de un lenguaje a otro, encontramos algunas limitaciones que son independientes al conjunto de algoritmos con el que trabaje.

El principal problema radica en que el proceso para determinar si un determinado registro de memoria es necesario o no para el sistema, es indecible. Dicho de otro modo, no puede resolverse de forma unívoca mediante un algoritmo.

En teoría de la computabilidad y en teoría de la complejidad computacional, un problema indecidible es un problema de decisión para el cual es imposible construir un algoritmo que siempre conduzca a una respuesta de sí o no correcta.

Wikipedia, Problema indecidible

wang-tiles

Ejemplo de problema indecible: el clásico Problema del Dominó de Hao Wang.

Como consecuencia de esta restricción, las recolecciones de basura implementan sólo soluciones parciales. Es por ello que lenguajes de bajo nivel (como C o C++) apuestan por una gestión manual de memoria, más eficiente y precisa a priori, frente a los lenguajes modernos de alto nivel que liberan al desarrollador de esta carga mediante su gestión automática (y por tanto, sujeta a errores).

Fugas de memoria, o Memory Leaks, en Javascript

Conociendo los aspectos ya estudiados del recolector de basura, podemos evitar el cometer errores que entorpezcan la gestión de memoria por parte del sistema. Si bien escribir un código amigable no es estrictamente necesario siempre que sigamos las buenas prácticas y contemos con una estrategia, sí lo es el evitar esos descuidos que terminan en fugas de memoria.

Recordemos rápidamente el ciclo de trabajo de los sistemas modernos Javascript para gestión de memoria:

  • Reservar la memoria necesaria cuando se crea un objeto
  • Utilizarla (sub procesos de lectura y escritura)
  • Liberar la memoria una vez ya no es necesaria

Las fugas de memoria se producen cuando falla el último paso de los anteriores y, por lo tanto, ésta no se libera.

En esencia, una fuga de memoria puede definirse como una memoria que ya no es necesaria para la aplicación, pero que por algún motivo, no es devuelta al sistema operativo o a la piscina de memoria libre disponible.

Sebastián Peyrott, 4 Types of Memory Leaks in JavaScript and How to Get Rid Of Them

Habiendo ya visto cómo trabaja el algoritmo Mark-Sweep, los principales errores en los que podemos caer durante un desarrollo son los relacionados, no ya con el conteo de referencias sobre cada objeto, sino con esa ruta que une la raíz del sistema con cada uno de nuestros objetos declarados en un grafo.

memoryusage

Gráfica que representa una fuga de memoria detectada desde las Chrome DevTools. Original aquí.

Todo lo anterior, traducido a términos habituales para los programadores, serían los problemas derivados de:

  • Variables globales accidentales
  • Acciones periódicas y callbacks olvidadas

Variables globales accidentales

En Javascript, la creación accidental de variables globales fue un problema histórico hasta la llegada de las herramientas de calidad de código (los llamados linters) o la inclusión del modo estricto.

Con anterioridad (y aún hoy fuera del modo estricto), toda variable que no era declarada de forma explícita, pasaba a ser una propiedad del objeto léxico global.

Este comportamiento interno de Javascript conlleva que toda variable iniciada sin declarar en un determinado scope, pasa a formar parte del global de la aplicación:

let foo = ( x ) => {    // Reserva de memoria para una función (Object)
    result = x * 2;     // Variable 'result' no declarada
 
    return result;
};

En el caso anterior, result no ha sido declarado dentro del scope de la función foo. Eso obliga al intérprete a declarar esa variable como global, sacándola de su scope. El ejemplo equivale a lo siguiente:

var result;
 
let foo = ( x ) => {
    result = x * 2;
 
    return result;
};

O también:

let foo = ( x ) => {
    window.result = x * 2;
 
    return result;
};

Pensemos ahora que la función foo no es referenciada desde ninguna parte de nuestro programa siendo así que el recolector la marque como ‘inalcanzable’. Sin embargo, aunque para nosotros la memoria reservada para foo ya no es útil, result mantiene una referencia a su cuerpo y, para el algoritmo, ésta continúa en uso y no debe ser purgada.

Este problema tiene dos soluciones: si la no declaración de la variable es accidental, basta con hacerlo en su correspondiente scope. Si por el contrario es intencionada, una vez que el valor ya no sea necesario, deberíamos eliminarlo/anularlo:

foo();  // Utilizamos nuestra función
 
// Una vez hemos utilizado el resultado y no lo volvemos a necesitar
window.result = null;

Si bien una variable global con un valor simple asociado como la del ejemplo no es una fuga de memoria importante, hay que pensar en escenarios donde ‘result’ puede almacenar gran cantidad de datos: una caché, una respuesta dada por un servidor en forma de JSON o estructura DOM, etc…

Acciones periódicas y callbacks olvidadas

Las acciones periódicas son otro foco habitual de fugas de memoria en arquitecturas modernas de tipo SPA (Single-page application).

Una muestra podría ser un temporizador que refresca datos en pantalla de forma periódica mediante llamadas a servidor:

let chartData = getChartData(),
    chartDataContainer = document.getElementById( 'chartDataContainer' );
 
setInterval( () => {
    let liveChart = chartDataContainer.querySelector( '.liveCharts' );
 
    printData( charData, liveChart );
}, 1000 );

Aquí el problema potencial reside en que las variables fuera del intervalo (chartData y chartDataContainer), deberían anularse una vez que ya no sean necesarias. De lo contrario, aunque estas se eliminen, permanecerán en memoria mientras sean requeridas por el cuerpo del intervalo.

Además de lo anterior, tenemos una referencia a un elemento DOM (chartDataContainer) que puede quedar en algún punto del programa obsoleto. Si este nodo fuera eliminado, o sobreescrito por otro (escenarios habituales en aplicaciones modernas), el sistema no puede liberar la memoria que está ocupando porque la variable chartDataContainer continúa manteniendo su referencia al tiempo que es requerida por setInterval. Es necesario que el intervalo se detenga de forma programática para que el recolector evalúe sus términos y actúe.

Observables

Un tema relacionado con el anterior son los observables que establecemos sobre elementos DOM.

Resulta habitual asociar funciones (callbacks) a determinadas acciones sobre elementos que, al igual que en el punto anterior, pueden quedar obsoletas.

Un ejemplo al respecto:

let myBtn = document.getElementById( 'save' ),
 
    saveForm = () => {
        /*
         * Acciones necesarias para guardar un formulario
         * ...
         */
        console.info( 'Form saved!' );
    };
 
myBtn.addEventListener( 'click', saveForm );
 
// Eliminamos el elemento en algún momento del programa
myBtn.parentNode.removeChild( myBtn );

Fácilmente puede verse aquí cómo cuando eliminamos el botón de nuestra supuesta aplicación, el observador continúa manteniendo su referencia.

A pesar de lo que nos pueda sugerir la intuición, los navegadores modernos pueden lidiar con este problema. Actualmente, el árbol DOM está integrado dentro de las tablas de observación que el recolector evalúa, por lo que en teoría, es capaz de detectar que un observable ha quedado huérfano u obsoleto cuando su objeto de referencia deja de ser alcanzable desde la raíz.

Para reforzar este comportamiento, bibliotecas de terceros como jQuery anulan automáticamente los observables cuando el elemento sobre el que hacen referencia es eliminado (siempre a través de los métodos propios de jQuery).

Obsérvese este fragmento del código original de jQuery:

function remove( elem, selector, keepData ) {
    var node,
        nodes = selector ? jQuery.filter( selector, elem ) : elem,
        i = 0;
 
    for ( ; ( node = nodes[ i ] ) != null; i++ ) {
        if ( !keepData && node.nodeType === 1 ) {
            jQuery.cleanData( getAll( node ) );
        }
 
        if ( node.parentNode ) {
            if ( keepData && jQuery.contains( node.ownerDocument, node ) ) {
                setGlobalEval( getAll( node, "script" ) );
            }
            node.parentNode.removeChild( node );
        }
    }
 
    return elem;
}

La línea clave es:

jQuery.cleanData( getAll( node ) );

Donde se llama al método que anula los eventos asociados al elemento eliminado:

var cleanData = function( elems ) {
    /* ... */
    jQuery.removeEvent( elem, type, data.handle );
};

NOTA: Los fragmentos anteriores pueden consultarse en línea desde GitHub aquí (enlace revisado a fecha del artículo; noviembre, 2016)

Conclusión

En este artículo hemos presentado el funcionamiento del recolector de basura en Javascript. Para ello, hemos partido de la teoría más general hasta la revisión de las particularidades de los motores más utilizados a día de hoy.

A modo de resumen, podemos hablar de que en la actualidad, los recolectores son de tipo generacional; esto es, que basan la recolección de referencias en diferentes espacios según su tipo y longevidad. En el momento en que estos objetos son referenciados, promocionan desde tablas temporales a otras permanentes, mientras que aquellos huérfanos se trasladan a posiciones reciclables. El seguimiento de estas referencias, se realiza mediante el escaneo de sus rutas desde un objeto raíz para así determinar si son o no alcanzables por el programa.

A partir de esta información y sus marcas, el recolector puede liberar aquellos valores que han quedado inalcanzables, devolviendo la memoria o bien al sistema operativo, o bien al pool de la propia aplicación. Una vez purgadas las tablas, éstas se compactan eliminando los espacios muertos intermedios.

Por último, relacionado con este ciclo de gestión, hemos destacado cómo el recolector es indecible, lo que quiere decir que no siempre será capaz de resolver con éxito cualquier situación que pueda acontecer. Además de esto, dado que su ejecución no puede ser lanzada de forma explícita por parte del desarrollador, queda ésta limitada a la propia lógica del intérprete. Dicho de otro modo, no podemos forzar al recolector a que escanee nuestro programa liberando memoria de una forma puntual, sino que tenemos que esperar a que éste itere según sus propios ciclos internos.

Pese a lo anterior, como desarrolladores, podemos optimizar el sucio trabajo del recolector evitando errores comunes que acaban convirtiéndose en fugas de memoria. Para ello, una buena planificación previa así como un correcto uso de las herramientas de monitorización (linters y herramientas del navegador) nos serán de gran ayuda a la hora de analizar nuestro trabajo y estar al tanto de los recursos utilizados por el sistema durante el tiempo de ejecución.

No es el objetivo de este artículo el mostrar cómo detectar y solucionar dichos errores (eso quedará para otra futura guía) sino el comprender porqué estos se producen gracias a un mejor conocimiento del funcionamiento interno del gestor de memoria.

Más:

{3} Comentarios.

  1. Gabriel Crespo

    Tremendo articulo hermano.

  2. jmzc

    No comprendo esta parte

    “…tenemos una referencia a un elemento DOM que puede quedar en algún punto del programa obsoleto. Si dicho elemento es eliminado, o sobreescrito por otro nodo (escenarios habituales en aplicaciones modernas), su referencia se mantiene mientras el intérvalo no sea detenido”

    Entiendo que el código

    let mainChart = document.getElementById( ‘MainChart’ );

    se evalúa en cada ejecución del intervalo.
    Por tanto, entiendo que si se elimina el elemento ‘MainChart’ entre ejecuciones , document.getElementById( ‘MainChart’ ) retornaría ‘undefined’ o ‘null’
    Y como mainChart es local a la función, su ámbito concluye tras su ejecución y no mantiene referencias

    No veo el leak de memoria

    Un saludo

    • Carlos Benítez

      Hola;
      he modificado el artículo en esa sección porque, efectivamente, no estaba claro lo que quería expresar. He cambiado también el ejemplo esperando que ahora no dé lugar a dudas.

      Gracias por tu apunte!
      Un saludo.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *