X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/7782ad9353bb81b20987841f8cfbf21d37ec20bd..93304243d72347314f0d9c402a0632ab50550016:/source/dgc.rst

diff --git a/source/dgc.rst b/source/dgc.rst
index f0e68d6..09c0c21 100644
--- a/source/dgc.rst
+++ b/source/dgc.rst
@@ -4,7 +4,7 @@
    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:
@@ -1331,6 +1331,8 @@ a ningún destructor), para el usuario puede ser una garantía muy débil
 y proveer finalización asegurada puede ser muy deseable.
 
 
+.. _dgc_committed:
+
 Memoria *encomendada*
 ^^^^^^^^^^^^^^^^^^^^^
 El algoritmo actual divide un *pool* en dos áreas: memoria *encomendada*
@@ -1821,6 +1823,304 @@ Marcado iterativo
    *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 :