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:
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
La estructura ``Pool`` está compuesta por los siguientes atributos (ver figura
:vref:`fig:dgc-pool`):
+.. fig:: fig:dgc-pool
+
+ Vista gráfica de la estructura de un *pool* de memoria.
+
+ .. aafig::
+ :scale: 120
+
+ /--- "baseAddr" "ncommitted = i" "topAddr" ---\
+ | V |
+ |/ |/ |/
+ +---- "committed" -----+------- "no committed" ----------+
+ /| /| /|
+ V V V
+ +--------+--------+-----+--------+-----+-------------------+
+ páginas | 0 | 0 | ... | i | ... | "npages - 1" |
+ +--------+--------+-----+--------+-----+-------------------+
+ A A A A A A
+ | | | | | |
+ +--------+--------+-----+--------+-----+-------------------+
+ pagetable | Bins 0 | Bins 1 | ... | Bins i | ... | "Bins (npages-1)" |
+ +--------+--------+-----+--------+-----+-------------------+
+
*baseAddr* y *topAddr*
punteros al comienzo y fin de la memoria que almacena todas las páginas del
*pool* (*baseAddr* es análogo al atributo *pages* utilizado en las
``B_UNCOMMITTED`` (valor que tienen las páginas que no fueron encomendadas
aún) y ``B_FREE``.
-.. fig:: fig:dgc-pool
-
- Vista gráfica de la estructura de un *pool* de memoria.
-
- .. aafig::
- :scale: 120
-
- /--- "baseAddr" "ncommitted = i" "topAddr" ---\
- | V |
- |/ |/ |/
- +---- "committed" -----+------- "no committed" ----------+
- /| /| /|
- V V V
- +--------+--------+-----+--------+-----+-------------------+
- páginas | 0 | 0 | ... | i | ... | "npages - 1" |
- +--------+--------+-----+--------+-----+-------------------+
- A A A A A A
- | | | | | |
- +--------+--------+-----+--------+-----+-------------------+
- pagetable | Bins 0 | Bins 1 | ... | Bins i | ... | "Bins (npages-1)" |
- +--------+--------+-----+--------+-----+-------------------+
-
Como se observa, además de la información particular del *pool* se almacena
toda la información de páginas y bloques enteramente en el *pool* también.
Esto simplifica el manejo de que lo es memoria *pura* del *heap*, ya que queda
y proveer finalización asegurada puede ser muy deseable.
+.. _dgc_committed:
+
Memoria *encomendada*
^^^^^^^^^^^^^^^^^^^^^
El algoritmo actual divide un *pool* en dos áreas: memoria *encomendada*
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