X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/af3cc91ddf531e9eb73f3dac73b15ab317a3cbb2..6c0df59:/source/dgc.rst diff --git a/source/dgc.rst b/source/dgc.rst index 804d554..f087aef 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: @@ -854,9 +854,9 @@ siguiente función, que devuelve al *low level allocator* los *pools* 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 @@ -1058,6 +1058,28 @@ C ``malloc()``, ``realloc()`` y ``free()`` directamente. 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 @@ -1088,28 +1110,6 @@ La estructura ``Pool`` está compuesta por los siguientes atributos (ver figura ``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 @@ -1533,6 +1533,8 @@ recolector actual y en consecuencia sea muy complicado escribir 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()``:: @@ -1823,6 +1825,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 +`, 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 +`), 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 +` [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 ` y parcialmente más :ref:`preciso +`. 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 ` 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 :