de recolección de basura en dicho lenguaje (se explica por qué las
particularidades descriptas en la sección anterior complican la
recolección de basura y cuales son las que más molestan).
- ESTADO: TERMINADO, CORREGIDO
+ ESTADO: TERMINADO
.. _dgc:
vez más el algoritmo distingue objetos grandes de pequeños. Los pequeños se
asignan de las siguiente manera::
- function new_small(block_size) is
+ function new_small(block_size) is
+ block = find_block_with_size(block_size)
+ if block is null
+ collect()
block = find_block_with_size(block_size)
if block is null
- collect()
+ new_pool()
block = find_block_with_size(block_size)
- if block is null
- new_pool()
- block = find_block_with_size(block_size)
- return block
+ return block
Se intenta reiteradas veces conseguir un bloque del tamaño correcto libre,
realizando diferentes acciones si no se tiene éxito. Primero se intenta hacer
Para intentar buscar un bloque de memoria libre se realiza lo siguiente::
- function find_block_with_size(block_size) is
+ function find_block_with_size(block_size) is
+ block = free_lists[block_size].pop_first()
+ if block is null
+ assign_page(block_size)
block = free_lists[block_size].pop_first()
- if block is null
- assign_page(block_size)
- block = free_lists[block_size].pop_first()
- return block
+ return block
Si no se puede obtener un bloque de la lista de libres correspondiente, se
busca asignar una página libre al tamaño de bloque deseado de forma de
*alimentar* la lista de libres con dicho tamaño::
- function assign_page(block_size) is
- foreach pool in heap
- foreach page in pool
- if page.block_size is FREE
- page.block_size = block_size
- foreach block in page
- free_lists[page.block_size].link(block)
+ function assign_page(block_size) is
+ foreach pool in heap
+ foreach page in pool
+ if page.block_size is FREE
+ page.block_size = block_size
+ foreach block in page
+ free_lists[page.block_size].link(block)
Cuando todo ello falla, el último recurso consiste en pedir memoria al sistema
operativo, creando un nuevo *pool*::
- funciones new_pool(number_of_pages = 1) is
- pool = alloc(pool.sizeof)
- if pool is null
- return null
- pool.number_of_pages = number_of_pages
- pool.pages = alloc(number_of_pages * PAGE_SIZE)
- if pool.pages is null
- free(pool)
- return null
- heap.add(pool)
- foreach page in pool
- page.block_size = FREE
- return pool
+ function new_pool(number_of_pages = 1) is
+ pool = alloc(pool.sizeof)
+ if pool is null
+ return null
+ pool.number_of_pages = number_of_pages
+ pool.pages = alloc(number_of_pages * PAGE_SIZE)
+ if pool.pages is null
+ free(pool)
+ return null
+ heap.add(pool)
+ foreach page in pool
+ page.block_size = FREE
+ return pool
Se recuerda que la función ``alloc()`` es un :ref:`servicio
<gc_intro_services>` provisto por el *low level allocator* y en la
de una página, entonces se utiliza otro algoritmo para alocar un objeto
grande::
- function new_big(size) is
- number_of_pages = ceil(size / PAGE_SIZE)
+ function new_big(size) is
+ number_of_pages = ceil(size / PAGE_SIZE)
+ pages = find_pages(number_of_pages)
+ if pages is null
+ collect()
pages = find_pages(number_of_pages)
if pages is null
- collect()
- pages = find_pages(number_of_pages)
- if pages is null
- minimize()
- pool = new_pool(number_of_pages)
- if pool is null
- return null
- pages = assign_pages(pool, number_of_pages)
- pages[0].block_size = PAGE
- foreach page in pages[1..end]
- page.block_size = CONTINUATION
- return pages[0]
+ minimize()
+ pool = new_pool(number_of_pages)
+ if pool is null
+ return null
+ pages = assign_pages(pool, number_of_pages)
+ pages[0].block_size = PAGE
+ foreach page in pages[1..end]
+ page.block_size = CONTINUATION
+ return pages[0]
De forma similar a la asignación de objetos pequeños, se intenta encontrar una
serie de páginas contiguas, dentro de un mismo *pool*, suficientes para
completamente libres::
function minimize() is
- for pool in heap
+ foreach pool in heap
all_free = true
- for page in pool
+ foreach page in pool
if page.block_size is not FREE
all_free = false
break
Volviendo a la función ``new_big()``, para hallar una serie de páginas
contiguas se utiliza el siguiente algoritmo::
- function find_pages(number_of_pages) is
- foreach pool in heap
- pages = assign_pages(pool, number_of_pages)
- if pages
- return pages
- return null
+ function find_pages(number_of_pages) is
+ foreach pool in heap
+ pages = assign_pages(pool, number_of_pages)
+ if pages
+ return pages
+ return null
Como se dijo, las páginas deben estar contenidas en un mismo *pool* (para
tener la garantía de que sean contiguas), por lo tanto se busca *pool* por
*pool* dicha cantidad de páginas libres consecutivas a través del siguiente
algoritmo::
- function assign_pages(pool, number_of_pages) is
- pages_found = 0
- first_page = null
- foreach page in pool
- if page.block_size is FREE
- if pages_found is 0
- pages_found = 1
- first_page = page
- else
- pages_found = pages_found + 1
- if pages_found is number_of_pages
- return [first_page .. page]
+ function assign_pages(pool, number_of_pages) is
+ pages_found = 0
+ first_page = null
+ foreach page in pool
+ if page.block_size is FREE
+ if pages_found is 0
+ pages_found = 1
+ first_page = page
else
- pages_found = 0
- first_page = null
- return null
+ pages_found = pages_found + 1
+ if pages_found is number_of_pages
+ return [first_page .. page]
+ else
+ pages_found = 0
+ first_page = null
+ return null
Una vez más, cuando todo ello falla (incluso luego de una recolección), se
intenta alocar un nuevo *pool*, esta vez con una cantidad de páginas
y proveer finalización asegurada puede ser muy deseable.
+.. _dgc_committed:
+
Memoria *encomendada*
^^^^^^^^^^^^^^^^^^^^^
El algoritmo actual divide un *pool* en dos áreas: memoria *encomendada*
Esquema de un bloque cuando está activada la opción ``SENTINEL``.
.. aafig::
+ :textual:
| | | | |
+-- Palabra ---+-- Palabra ---+-- Tamaño bloque de usuario --+- Byte -+
| | | | |
+--------------+--------------+------------------------------+--------+
- | Tamaño del | Pre | | Post |
- | bloque de | | Bloque de usuario | |
- | usuario | 0xF4F4F4F4 | | 0xF5 |
+ | "Tamaño del" | Pre | | Post |
+ | "bloque de" | | Bloque de usuario | |
+ | "usuario" | 0xF4F4F4F4 | | 0xF5 |
+--------------+--------------+------------------------------+--------+
A
|
principales problemas percibidos por la comunidad que utiliza el lenguaje.
+.. _dgc_bad_code:
+
Complejidad del código y documentación
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
El análisis del código fue muy complicado debido a la falta de documentación
o mejorarlo. Esto a su vez provoca que, al no disponer de una implementación
de referencia sencilla, sea muy difícil implementar un recolector nuevo.
+.. highlight:: d
+
Este es, probablemente, la raíz de todos los demás problemas del recolector
actual. Para ilustrar la dimensión del problema se presenta la implementación
real de la función ``bigAlloc()``::
*heap*.
+
+.. Esto sería muy similar a la sección de "Recolección de basura) pero en
+ vez de ir describiendo los algoritmos iría comentando por qué los tomo
+ o descarto
+ ESTADO: INCOMPLETO
+
+
+.. _dgc_via:
+
+Análisis de viabilidad
+----------------------------------------------------------------------------
+
+Ya conociendo el lenguaje de programación D_ (con sus necesidades
+particulares), el estado del arte en recolección de basura y el recolector
+actual de D_ es posible evaluar la viabilidad de los distintos algoritmos
+vistos en el capítulo :ref:`gc`. Se recuerda que dentro del análisis de
+viabilidad de considera de gran importancia la viabilidad social y política de
+la mejora, es decir, se presta particular atención en encontrar una mejora que
+tenga una buena probabilidad de ser aceptada por la comunidad de D_.
+
+
+.. _dgc_via_classic:
+
+Algoritmos clásicos
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+En esta sección se presenta un análisis de los :ref:`algoritmos clásicos
+<gc_classic>`, de forma de poder analizar a grandes rasgos las principales
+familias para ir determinando la dirección principal de la solución.
+
+
+.. _dgc_via_rc:
+
+Conteo de referencias
+^^^^^^^^^^^^^^^^^^^^^
+Ya se ha propuesto en el pasado la utilización de conteo de referencias en D_
+pero no se ha demostrado un interés real, más allá de soluciones en
+bibliotecas [NGD38689]_. Las razones para no utilizar conteo de referencia son
+más o menos las mismas que las desventajas mencionadas en la sección
+:ref:`gc_rc` (en el capítulo :ref:`gc`), siendo la principal la incapacidad de
+recolectar ciclos. Sin embargo hay otras razones importantes.
+
+Una de ellas es la inter-operatividad con C. El utilizar un contador de
+referencias requiere la manipulación del contador por parte del código C con
+el que se interactúe. Si bien este problema ya está presente si código
+C guarda un puntero a un objeto almacenado en el *heap* del recolector de D_
+en el *heap* de C (es decir, en una celda de memoria asignada por
+``malloc()``), esto es poco común. Sin embargo, mientras que una función de
+C se está ejecutando, es extremadamente común que pueda almacenar en el
+*stack* una referencia a un objeto de D_ y en ese caso el recolector actual
+puede manejarlo (mientras la función de C esté corriendo en un hilo creado por
+D_). Sin embargo al usar un conteo de referencias esto es más problemático, ya
+que no se mantiene la invariante del algoritmo si no son actualizados siempre
+los contadores.
+
+Otro problema es que al liberarse una celda, existe la posibilidad de tener
+que liberar todo el sub-grafo conectado a ésta. Cuando este sub-grafo es
+grande, se puede observar una gran pausa.
+
+Si bien estas razones son suficientes como para considerar que el conteo de
+referencias no es un algoritmo que sea viable en D_, hay muchas técnicas
+y optimizaciones para minimizarlas (como liberación perezosa, conteo de
+referencias pospuesto, etc. [JOLI96]_). Sin embargo hay otra razón importante
+que descarta esta familia de algoritmos ya que todas las variaciones de conteo
+de referencias implican, en mayor o menor medida, el entrelazado del trabajo
+del recolector con el del *mutator*. Si bien esta es una característica en
+general muy deseable (porque hace que el recolector sea :ref:`incremental
+<gc_inc>`), en D_ no lo es porque tiene como requerimiento no hacer pagar el
+precio de cosas que no se usan. En D_ debe ser posible no utilizar el
+recolector de basura y, al no hacerlo, no tener ningún tipo de trabajo extra
+asociado a éste. De usarse conteo de referencias esto no sería posible.
+
+Si bien este requerimiento puede ser discutible técnicamente, hay una gran
+resistencia social y política ante cualquier tipo de recolector que imponga
+una penalización de rendimiento a alguien que no quiera usarlo [NGD38689]_.
+Además requiere un cambio complejo y profundo en el compilador, siendo éste
+uno de los eslabones con mayor resistencia a introducir cambios.
+
+Por lo tanto se concluye que el conteo de referencias no es un algoritmo
+viable para este trabajo.
+
+
+.. _dgc_via_mark_sweep:
+
+Marcado y barrido
+^^^^^^^^^^^^^^^^^
+El marcado y barrido es un algoritmo evidentemente viable debido a que es la
+base del algoritmo del recolector de basura actual.
+
+En general en la comunidad de D_ no hay mayores críticas al marcado y barrido
+en sí, si no más bien a problemas asociados a la implementación actual,
+principalmente a las grandes pausas o la falta de :ref:`precisión
+<gc_conserv>` [NGD54084]_ [NGL13744]_ [NGD44607]_ [NGD29291]_ [NGDN87831]_
+[NGDN87831]_ [NGL3937]_ [NGD22968]_ [NGA15246]_ [NGD5622]_ [NGD2547]_
+[NGD18354]_.
+
+Esta familia de algoritmos se adapta bien a los requerimientos principales de
+D_ en cuanto a recolección de basura (ver :ref:`dgc_needs`), por ejemplo
+permite recolectar de forma conservativa, no impone un *overhead* a menos que
+se utilice el recolector, permite liberar memoria manualmente, se adapta de
+forma simple para soportar punteros *interiores* y permite finalizar objetos
+(con las limitaciones mencionadas en :ref:`dgc_prob_final`).
+
+Sin embargo muchas de las limitaciones del recolector actual (ver
+:ref:`dgc_bad`), no son inherentes al marcado y barrido, por lo que aún
+conservando la base del algoritmo, es posible realizar una cantidad de mejoras
+considerable.
+
+Una de las principales mejoras que pueden realizarse es hacer al recolector
+:ref:`concurrente <gc_concurrent>` y parcialmente más :ref:`preciso
+<gc_conserv>`. Estas dos mejoras solamente alcanzarían para mejorar de forma
+notable el tiempo de pausa en las recolecciones y la cantidad de memoria
+retenida debido a falsos positivos.
+
+Más adelante veremos detalles sobre algunos de estos aspectos y sobre algunos
+algoritmos particulares que permiten hacer concurrente al recolector actual.
+
+
+Copia de semi-espacio
+^^^^^^^^^^^^^^^^^^^^^
+La copia de semi-espacio, al igual que cualquier otro tipo de recolector con
+movimiento, requiere (en la mayoría de los casos) disponer de una
+:ref:`precisión <gc_conserv>` casi completa. Las celdas para las cuales hay
+alguna referencia que no es precisa no pueden ser movidas, ya que al no estar
+seguros que la referencia sea tal, ésta no puede ser actualizada con la
+dirección de la nueva ubicación de la celda movida porque de no ser una
+referencia se estarían alterando datos del usuario, corrompiéndolos.
+
+Es por esto que si el recolector no es mayormente preciso, las celdas que
+pueden ser movidas son muy pocas y, por lo tanto, se pierden las principales
+ventajas de esta familia de recolectores (como la capacidad de asignar nueva
+memoria mediante *pointer bump allocation*).
+
+Este aumento de precisión, sin embargo, es bastante realizable. Es posible, en
+teoría, hacer que al menos el *heap* sea preciso, aunque es discutible si en
+la práctica es aceptable el *overhead* en espacio necesario para almacenar la
+información del tipo de una celda. Esto se analiza en más detalle al evaluar
+la recolección precisa en la siguiente sección.
+
+Si bien las principales herramientas para que sea viable un recolector por
+copia de semi-espacio están disponibles en D_ (como la posibilidad de hacer
+*pinning* the celdas o el potencial incremento de precisión), este lenguaje
+nunca va a poder proveer precisión total, haciendo que no sea posible
+implementar un recolector por copia de semi-espacio puro. Siempre habrá que
+disponer un esquema híbrido para poder manejar las celdas que no puedan
+moverse, incrementado mucho la complejidad del recolector.
+
+Si bien un esquema híbrido es algo técnicamente posible, nuevamente la
+resistencia social a un cambio de esta envergadura es de importancia
+suficiente como para inclinarse por una solución menos drástica.
+
+
+.. _dgc_via_art:
+
+Principales categorías del estado del arte
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+En esta sección se realiza un análisis de la viabilidad de las principales
+categorías de recolectores según se presentaron en la sección :ref:`gc_art`.
+
+Recolección directa / indirecta
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Como se ha visto al analizar el conteo de referencias, lo más apropiado para
+D_ pareciera ser continuar con el esquema de recolección indirecta, de forma
+tal de que el precio de la recolección solo deba ser pagado cuando el
+*mutator* realmente necesita del recolector. Es por esto que no parece ser una
+opción viable introducir recolección directa en este trabajo.
+
+
+Recolección incremental
+^^^^^^^^^^^^^^^^^^^^^^^
+La recolección incremental puede ser beneficiosa para D_, dado que puede
+servir para disminuir el tiempo de pausa del recolector. Sin embargo, en
+general es necesario instrumentar el *mutator* para reportar cambios en el
+grafo del conectividad al recolector. Además puede contar con los mismos
+problemas que la recolección directa, puede hacer que el usuario tenga que
+pagar el precio de la recolección, incluso cuando no la necesita, si por cada
+asignación el recolector realiza parte de una recolección que no fue
+solicitada.
+
+Recolección concurrente / paralela / *stop-the-world*
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+El recolector actual es *stop-the-world*, sin embargo esta es una de las
+principales críticas que tiene. El recolector se podría ver beneficiado de
+recolección paralela, tanto para realizar la recolección más velozmente en
+ambientes multi-procesador, como para disminuir el tiempo de pausa. Sin
+embargo, el hecho de que todos los hilos se pausen para realizar parte del
+trabajo del recolector puede ser contraproducente para programas *real-time*
+que pretendan usar un hilo que no sufra de la latencia del recolector,
+asegurando que nunca lo use (aunque se podrían ver esquemas para ajustarse
+a estas necesidades).
+
+En general los recolectores concurrentes necesitan también instrumentar el
+*mutator* para reportar cambios en el grafo de conectividad al recolector,
+como sucede con la recolección directa o incremental, sin embargo hay
+algoritmos que no tienen este requerimiento, utilizando servicios del sistema
+operativo para tener una *fotografía* de la memoria para que la fase de
+marcado pueda realizarse sin perturbar al *mutator* ni requerir de su
+cooperación [RODR97]_. Este tipo de algoritmos serían un buen candidato para
+D_, dado que requiere pocos cambios y es transparente al *mutator*.
+
+
+Recolección conservativa / precisa
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Si bien D_ puede proveer al recolector de basura información de tipos para los
+objetos almacenados en el *heap*, todo recolector para D_ deberá soportar
+cierto grado de recolección conservativa (ver :ref:`gc_conserv`), debido a las
+siguientes razones:
+
+* Si bien D_ podría incorporar información de tipos para el *stack*
+ (utilizando, por ejemplo, la técnica de *shadow stack* [HEND02]_), para
+ poder interactuar con C/C++, el recolector debe poder interpretar los *stack
+ frames* [#dgcstackframe]_ de estos lenguajes, que no disponen de información
+ de tipos.
+
+* Los registros del procesador tienen un problema similar, con la diferencia
+ de que el costo de implementar algo similar a *shadow stack* para los
+ registros sería impracticable, más allá de que exista la misma limitación
+ que con el *stack* para poder interactuar con C/C++.
+
+* D_ soporta uniones (ver :ref:`d_low_level`). Para una unión es imposible
+ determinar si un campo es un puntero o no. Por ejemplo::
+
+ union U {
+ size_t x;
+ void* p;
+ }
+
+ Aquí el recolector no puede saber nunca si el valor almacenado será un
+ ``size_t`` o un ``void*``, por lo tanto deberá tratar **siempre** esa
+ palabra de forma conservativa (es decir, interpretarla como un *posible*
+ puntero). Este requerimiento puede ser relajado si el usuario proveyera
+ alguna forma de determinar que tipo está almacenando la unión en un
+ determinado momento. Sin embargo el costo de pedir al usuario este tipo de
+ restricción puede ser muy alto.
+
+Sin embargo, ya hay un trabajo relacionado avanzando en este sentido, que
+agrega precisión al marcado del *heap*. David Simcha comienza con este trabajo
+explorando la posibilidad de agregar precisión parcial al recolector,
+generando información sobre la ubicación de los punteros para cada tipo
+[DBZ3463]_. Su trabajo se limita a una implementación a nivel biblioteca de
+usuario y sobre `D 2.0`_. Desafortunadamente su trabajo pasa desapercibido
+por un buen tiempo.
+
+Sin embargo un tiempo después Vincent Lang (mejor conocido como *wm4* en la
+comunidad de D_), retoma este trabajo, pero modificando el compilador DMD_
+y trabajando con `D 1.0`_ y Tango_. Es por esto que el aumento de precisión
+parece ser un área fértil para este trabajo, en particular si se colabora con
+el trabajo realizado por David y Vincent.
+
+.. [#dgcstackframe] Un *stack frame* (*marco de la pila* en castellano),
+ también conocido como *activation record* (o *registro de activación* en
+ castellano) es una estructura de datos dependiente de la arquitectura que
+ contiene información del estado de una función, incluyendo, por ejemplo,
+ sus variables locales, parámetros y dirección de retorno.
+
+
+Recolección con movimiento de celdas
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Esta posibilidad ya se ha discutido al analizar la posibilidad de utilizar
+recolección con copia de semi-espacios. El trabajo mencionado en la sub-sección
+anterior agrega información suficiente como poder diferenciar que celdas se
+pueden mover y cuales no, sin embargo queda como incógnita qué proporción de
+celdas deben permanecer inmovilizadas como para evaluar si un cambio tan
+grande puede rendir frutos o no.
+
+A priori, pareciera que la relación cantidad y complejidad de cambios sobre
+beneficios potenciales no fuera muy favorable a esta mejora.
+
+
+Lista de libres / *pointer bump allocation*
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Como consecuencia de los puntos anteriores, no es técnicamente posible
+realizar *pointer bump allocation* pura en D_. Al haber objetos *pinned*,
+siempre es necesario o bien contar con una lista de libres, o detectar
+*huecos* en un esquema de *pointer bump allocation*. Es por esto que parece
+ser más viable conservar el esquema de listas de libres.
+
+Esta mejora también entra en la categoría de opciones viables pero cuya
+complejidad no parece valer la pena dada la limitada utilidad que se espera
+dadas las particulares características de D_ en cuanto a precisión de
+información de tipos de *stack*, uniones, etc.
+
+
+Recolección por particiones / generacional
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Una vez más la recolección por particiones, en particular la generacional,
+requiere de la instrumentación del *mutator* para comunicar cambios en el
+grafo de conectividad al recolector, por lo que es poco viable. Aunque existen
+algoritmos que no necesitan este tipo de comunicación dado que está
+garantizado que no existan conexiones entre celdas de las distintas
+particiones, requiere grandes cambios en el compilador y realizar análisis
+estático bastante complejo [HIRZ03]_. Además al ser D_ un lenguaje de bajo
+nivel, es muy difícil garantizar que estas conexiones inter-particiones no
+puedan existir realmente; y de poder lograrlo, podría ser demasiado
+restrictivo.
+
+
.. include:: links.rst
.. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :
projects / z.facultad / 75.00 / informe.git / blobdiff