X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/f0fa88b43b9fae7a2011ffeb77e1311060d1bc12..93304243d72347314f0d9c402a0632ab50550016:/source/dgc.rst diff --git a/source/dgc.rst b/source/dgc.rst index 9019246..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: @@ -461,25 +461,36 @@ algoritmo:: mark_free_lists() mark_static_data() push_registers_into_stack() + thread_self.stack.end = get_stack_top() mark_stacks() + pop_registers_from_stack() mark_user_roots() mark_heap() start_the_world() La variable **global** ``more_to_scan`` indica al algoritmo iterativo cuando -debe finalizar: la función ``mark()`` (que veremos más adelante) lo pone en -``true`` cuando una nueva celda debe ser visitada, por lo tanto la iteración -se interrumpe cuando no hay más celdas por visitar. +debe finalizar: la función ``mark_range()`` (que veremos más adelante) lo pone +en ``true`` cuando una nueva celda debe ser visitada, por lo tanto la +iteración se interrumpe cuando no hay más celdas por visitar. -Las funciones ``stop_the_world()`` y ``start_the_world()`` sencillamente -pausan y reanudan todos los hilos respectivamente:: +Las funciones ``stop_the_world()`` y ``start_the_world()`` pausan y reanudan +todos los hilos respectivamente (salvo el actual). Al pausar los hilos además +se guardan los registros del procesador en el *stack* y se guarda la posición +actual del *stack* para que la fase de marcado pueda recorrerlos:: function stop_the_world() is foreach thread in threads + if thread is thread_self + continue thread.pause() + push_registers_into_stack() + thread.stack.end = get_stack_top() function start_the_world() is foreach thread in threads + if thread is thread_self + continue + pop_registers_from_stack() thread.resume() La función ``clear_mark_scan_bits()`` se encarga de restablecer todos los @@ -517,9 +528,7 @@ Primero se marca el área de memoria estática de manera :ref:`conservativa ` (es decir, tomando cada *word* como si fuera un puntero):: function mark_static_data() is - foreach word in static_data - pointer = cast(void*) word - mark(pointer) + mark_range(static_data.begin, static_data.end) Para poder tomar los registros como parte del *root set* primero se apilan en el *stack* a través de la función:: @@ -528,14 +537,19 @@ en el *stack* a través de la función:: foreach register in registers push(register) +Y luego se descartan (no es necesario ni correcto restablecer los valores ya +que podrían tener nuevos valores) al sacarlos de la pila:: + + function pop_registers_from_stack() is + foreach register in reverse(registers) + pop() + Una vez hecho esto, basta marcar (de forma conservativa) los *stacks* de todos los threads para terminar de marcar el *root set*:: function mark_stacks() is foreach thread in threads - foreach word in thread.stack - pointer = cast(void*) word - mark(pointer) + mark_range(thread.stack.begin, thread.stack.end) Dado que D_ soporta manejo de memoria manual al mismo tiempo que memoria automática, es posible que existan celdas de memoria que no estén en el *root @@ -546,20 +560,23 @@ estas nuevas raíces. Es por esto que para concluir el marcado del *root set* completo se procede a marcar las raíces definidas por el usuario:: function mark_user_roots() is - foreach pointer in user_roots - mark(pointer) + foreach root_range in user_roots + mark_range(root_range.begin, root_range.end) El algoritmo de marcado no es recursivo sino iterativo por lo tanto al marcar una celda (o bloque) no se siguen sus *hijas*, solo se activa el bit de *scan* (a menos que la celda no contenga punteros, es decir, tenga el bit *noscan*):: - function mark(pointer) is - [pool, page, block] = find_block(pointer) - if block is not null and block.mark is false - block.mark = true - if block.noscan is false - block.scan = true - global more_to_scan = true + function mark_range(begin, end) is + pointer = begin + while pointer < end + [pool, page, block] = find_block(pointer) + if block is not null and block.mark is false + block.mark = true + if block.noscan is false + block.scan = true + global more_to_scan = true + pointer++ Por lo tanto en este punto, tenemos todas las celdas inmediatamente alcanzables desde el *root set* marcadas y con el bit *scan* activado si la @@ -577,15 +594,11 @@ celdas para visitar (con el bit *scan* activo):: if block.scan is true block.scan = false if page.block_size is PAGE // objeto grande - start = cast(byte*) page + begin = cast(byte*) page end = find_big_object_end(pool, page) - foreach word in start..end - pointer = cast(void*) word - mark(pointer) + mark_range(begin, end) else // objeto pequeño - foreach word in block - pointer = cast(void*) word - mark(pointer) + mark_range(block.begin, block.end) Aquí puede verse, con un poco de esfuerzo, la utilización de la :ref:`abstracción tricolor `: todas las celdas alcanzables @@ -665,9 +678,9 @@ objetos grandes se marcan todas las páginas que utilizaban como ``FREE``:: function free_big_object(pool, page) is pool_end = cast(byte*) pool.pages + (PAGE_SIZE * pool.number_of_pages) do - page = cast(byte*) page + PAGE_SIZE page.block_size = FREE - while page.block_size is CONTINUATION and page < pool_end + page = cast(byte*) page + PAGE_SIZE + while page < pool_end and page.block_size is CONTINUATION Además, los bloques que tienen en atributo ``final`` son finalizados llamando a la función ``finalize()``. Esta función es un servicio que provee la @@ -746,16 +759,15 @@ suficientemente grande como para poder almacenar el tamaño solicitado). Una 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 null - 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 @@ -765,39 +777,41 @@ pidiendo memoria al *low level allocator* (el sistema operativo generalmente). 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) - 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 ` provisto por el *low level allocator* y en la @@ -813,22 +827,22 @@ Si el tamaño de bloque necesario para cumplir con la asignación de memoria es 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 @@ -854,34 +868,34 @@ completamente libres:: 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 @@ -1284,10 +1298,8 @@ Asignación de memoria Recolección *mark(pbot, ptop)* - marca un rango de memoria. Este método es análogo al ``mark()`` - presentado en la sección :ref:`dgc_algo_mark` pero marca un rango - completo de memoria, lo que permite que sea considerablemente más - eficiente. + marca un rango de memoria. Este método es análogo al ``mark_range()`` + presentado en la sección :ref:`dgc_algo_mark`. *fullcollectshell()* guarda los registros en el *stack* y llama a ``fullcollect()``. El @@ -1319,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* @@ -1423,6 +1437,73 @@ utiliza conjuntos de bits. Esto trae dos ventajas principales: considerablemente la fase de marcado. +.. _dgc_debug: + +Herramientas para depuración +^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +El recolector provee algunas opciones para simplificar el diagnóstico +y depuración de problemas, tanto del mismo recolector como del programa del +usuario. + +Las opciones más importantes son: + + +``MEMSTOMP`` + Su función es escribir un patrón determinado de bits en todos los bytes de + un bloque de memoria según se haya: + + * Pedido un bloque menor a una página (``0xF0``). + * Pedido un bloque mayor a una página (``0xF1``). + * Dejado de usar debido a un pedido de achicamiento de un bloque + (``0xF2``). + * Pedido más páginas debido a un pedido de agrandamiento de un bloque + (``0xF0``). + * Liberado intencionalmente por el usuario (``0xF2``). + * Barrido (``0xF3``). + + Esto permite al diagnosticar un problema saber, por ejemplo, si un + determinado área de memoria fue recolectada recientemente, o liberada por + el usuario, o recién adquirida, etc. con tan solo ver si un patrón de bits + determinado está presente. Por supuesto puede existir *falsos positivos* + pero su probabilidad es lo suficientemente baja como para que sea útil en + la práctica. + +``SENTINEL`` + Su función detectar errores producidos por escribir más allá (o antes) del + área de memoria solicitada y está implementado reservando un poco más de + memoria de la que pide el usuario, devolviendo un puntero a un bloque + ubicado dentro del bloque real reservado (en vez de al inicio) y finalmente + escribiendo un patrón de bits en los extremos del borde real (ver figura + :vref:`fig:sentinel`), de forma de poder verificar en distintas situación + (por ejemplo al barrer el bloque) que esas áreas de más con los patrones de + bits estén intactas. Esto permite detectar de forma temprana errores tanto + en el recolector como en el programa del usuario. + + .. fig:: fig:sentinel + + 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 | + +--------------+--------------+------------------------------+--------+ + A + | + Puntero devuleto ---/ + +Ambas opciones son seleccionables sólo en tiempo de compilación del +recolector, por lo que su utilidad real, al menos para el usuario, se ve +severamente reducida. + .. _dgc_bad: @@ -1436,6 +1517,8 @@ participación y observación del grupo de noticias, de donde se obtuvieron los 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 @@ -1584,8 +1667,8 @@ y en particular para mejorar la implementación de de arreglos asociativos. Referencias débiles ^^^^^^^^^^^^^^^^^^^ El recolector actual no dispone de soporte de *referencias débiles* -[#dgcweakref]_, sin embargo hay una demanda [NGD86840]_ [NGD13301]_ [NGL8264]_ -[NGD69761]_ [NGD74624]_ [NGD88065]_ +[#dgcweakref]_, sin embargo hay una demanda apreciable [NGD86840]_ [NGD13301]_ +[NGL8264]_ [NGD69761]_ [NGD74624]_ [NGD88065]_. .. [#dgcweakref] Una referencia débil (o *weak reference* en inglés) es aquella que que no protege al objeto referenciado de ser reciclado por el @@ -1594,7 +1677,7 @@ El recolector actual no dispone de soporte de *referencias débiles* Para cubrir esta demanda, se han implementado soluciones como biblioteca para suplir la inexistencia de una implementación oficial [NGA9103]_. -Sin embargo éstas son en general poco robustas y extremadamente dependientes +Sin embargo éstas son en general poco robustas, extremadamente dependientes de la implementación del recolector y, en general, presentan problemas muy sutiles [NGD88065]_. Por esta razón se ha discutido la posibilidad de incluir la implementación de *referencias débiles* como parte del lenguaje @@ -1662,6 +1745,37 @@ bits para la fase de marcado, el resto del algoritmo es casi la versión más básica de marcado y barrido. Hay mucho lugar para mejoras en este sentido. +Configurabilidad +^^^^^^^^^^^^^^^^ +Si bien el recolector actual tiene algunas características configurables, +todas son seleccionables sólo en tiempo de compilación del recolector (no del +programa del usuario), como por ejemplo las opciones descriptas en +:ref:`dgc_debug`. Por lo tanto, a nivel práctico, es como si no tuviera +posibilidad alguna de ser configurado por el usuario, ya que no es parte del +ciclo de desarrollo normal el recompilar el recolector o *runtime* de un +lenguaje. + +Dado que es imposible que un recolector sea óptimo para todo tipo de +programas, es muy deseable permitir una configuración de parámetros del +recolector que permitan al usuario ajustarlo a las necesidades particulares de +sus programas. + + +.. _dgc_bad_ocup: + +Factor de ocupación del *heap* +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Otro problema potencialmente importante del recolector actual es que no se +tiene ningún cuidado con respecto a que, luego de una recolección, se haya +recuperado una buena parte del *heap*. Por lo tanto, en casos extremos, el +recolector tiene que hacer una recolección por cada petición de memoria, lo +que es extremadamente ineficiente. + +Para evitar esto, habría que usar algún esquema para evaluar cuando una +recolección no fue lo suficientemente *exitosa* y en ese caso pedir más +memoria al sistema operativo. + + Detalles ^^^^^^^^ Finalmente hay varios detalles en la implementación actual que podrían @@ -1709,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 +`, 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 :