Una pieza de software que me fascina son los garbage collectors (recolectores de basura). Para los no técnicos, dentro de los entornos de ejecución del software moderno existe algo similar a una flota de camiones de recogida de basura, sobre cuyo funcionamiento hay algunas técnicas que se pueden extrapolar al mundo offline.
En todo sistema las actividades pueden dividirse en dos grandes grupos: tareas esenciales y tareas contextuales. Las tareas esenciales son aquellas que diferencian el externamente al sistema de otros. Las tareas contextuales con frecuencia no son perceptibles pero influyen enormemente en la eficiencia del sistema.
Los GCs son una pieza de tarea contextual. El gobierno de un país debería parecerse a un recolector de basura, ejecutando en segundo plano tareas que mantienen una adecuada convivencia para los ciudadanos pero de forma que ellos se percaten lo mínimo posible. Precisamente uno de los problemas sociales que tenemos en España es que los ciudadanos hemos tenido que empezar a ocuparnos de arreglar los entuertos del gobierno en vez de ser al contrario. Existe incluso una película titulada A day without a mexican que ilustra lo que pasaría en California si no existiesen mejicanos ejecutando tareas contextuales.
Un GC trabaja eliminando de la memoria RAM objetos que ya no se están usando ni se usarán nunca más en el futuro. El criterio para saber si se van a usar en el futuro o no es si alguien se acuerda de que existen. Programáticamente, un objeto puede ser destruido cuando ya no existe ninguna referencia al mismo. Es decir, cuando es imposible alcanzarlo desde ninguna estructura de datos en uso por el programa.
Un objeto que ya no se usa no es destruido inmediatamente. La razón para ello es que hace tiempo que se comprobó que obligar al programador a destruir explícitamente todos los objetos que el programa ya no va a utilizar induce a frecuentes errores de codificación debidos al olvido por parte del programador de la tarea de destrucción. Es algo análogo a cómo en el mundo real cuando se contrata a un trabajador se le suministra un ordenador, pero cuando el trabajador deja su puesto su equipo no se envía inmediatamente a una planta de reciclado sino que permanece en un almacén temporalmente hasta que es retirado por un servicio externo de recogida de residuos.
En términos más generales se habla de separation of concerns, un patrón de diseño según el cual cada parte del programa debe ser responsable de una única función que sea lo más simple posible.
Algunos GCs pueden reciclar objetos además de destruirlos. Debido a que asignar memoria para alojar un objeto puede de ser una tarea relativamente costosa, el GC puede contar con pools de fragmentos de memoria reservados.
El GC funciona, por tanto, en dos grandes etapas: la de determinar qué objetos son susceptibles de ser destruidos y la de reorganizar el espacio liberado para que se pueda reasignar a nuevos objetos.
Para la determinación eficiente de objetos no en uso existen varias técnicas de optimización. El GC de Java usa lo que llama generaciones. Se basa en el principio de que existen objetos de vida corta y objetos de vida larga. Los objetos de vida más corta son, casi siempre, los últimos que se han creado. Si un objeto sobrevive a una criba del recolector de basura entonces deja de ser de vida corta y se convierte en otro de vida larga. Los objetos con diferentes intervalos de vida se almacenan en espacios separados y se chequean con diferente frecuencia. Es algo así como la caducidad de los alimentos en un frigorífico. Están los que caducan de un día para otro, los que duran una semana y los que duran varios meses. Si un alimento ha sobrevivido de un día para otro entonces es probable que dure una semana, y si ha sobrevivido de una semana para otra entonces es probable que dure un mes.
Tras eliminar algunos objetos si y otros no la memoria se queda hecha un queso de Gruyère y es preciso compactar los objetos supervivientes. Es como si hubiésemos sacados objetos al azar de unas estanterías dejando huecos de diferentes tamaños que probablemente no sean apropiados para colocar nuevos objetos. Para la compactación existen dos estrategias: compactar la colección o usar el doble de espacio de almacenamiento. Compactar la colección de objetos es simplemente como si recolocásemos todo en las estanterías de abajo hacia arriba. Para evitar el tiempo necesario en compactar los que se puede hacer es usar la memoria disponible sólo hasta la mitad y cuando se alcance el límite mover todos los objetos vivos a la otra mitad y descartar el resto. Trabajando con ítems físicos sería como tener dos almacenes y en vez de reordenarlos moviésemos todos los ítems de uno al otro cada cierto tiempo.
Para los lectores técnicos interesados en los detalles de implementación, el libro más usado como referencia es The Garbage Collection Handbook.
Pingback: Por qué hay que enseñar a los niños a programar (entre otras cosas) | La Pastilla Roja