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: SIN EMPEZAR, REVISAR LO HECHO
+ ESTADO: TERMINADO
-.. _ref_dgc:
+.. _dgc:
Recolección de basura en D
============================================================================
-TODO
+D_ propone un nuevo desafío en cuanto al diseño de un recolector de basura,
+debido a la gran cantidad características que tiene y paradigmas que soporta.
+D_ ya cuenta con un recolector que hace lo necesario para funcionar de forma
+aceptable, pero su diseño e implementación son relativamente sencillas
+comparadas con el :ref:`estado del arte <gc_art>` de la recolección de basura
+en general. Además la implementación actual presenta una serie de problemas
+que se evidencia en las quejas que regularmente la comunidad de usuarios de D_
+menciona en el grupo de noticias.
+En esta sección se analizarán las necesidades particulares de D_ con respecto
+a la recolección de basura. También se analiza el diseño e implementación del
+recolector actual y finalmente se presenta una recompilación de los
+principales problemas que presenta.
-Dificultades para recolectar basura en D
+
+
+.. _dgc_needs:
+
+Características y necesidades particulares de D_
----------------------------------------------------------------------------
-TODO
+En esta sección se hará un recorrido por las características y necesidades
+particulares que tiene D_ como lenguaje con respecto a la recolección de
+basura.
+
+
+
+.. _dgc_prob_low_level:
+
+Programación de bajo nivel (*system programming*)
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Sin dudas las características de D_ que lo hacen más complejo a la hora de
+implementar un recolector de basura son sus capacidades de programación de
+bajo nivel (ver :ref:`d_low_level`).
+
+Al proveer acceso a *assembly*, permitir estructuras de tipo *union* y ser
+compatible con C/C++, el recolector de basura tiene muchas restricciones. Por
+ejemplo debe tratar de forma conservativa los registros y el *stack*, ya que
+es la única forma de interactuar de forma segura con C/C++ y *assembly*.
+
+Además debe poder interactuar con manejo de memoria explícito, ya sea
+omitiendo por completo el *heap* del recolector o liberando explícitamente
+memoria de éste. Esta característica es muy inusual en un recolector,
+a excepción de recolectores conservativos diseñados para C/C++ que tienen las
+mismas (o más) limitaciones.
+
+El control sobre la alineación de memoria es otra complicación sobre el
+recolector de basura, incluso aunque éste sea conservativo. Dado que tratar la
+memoria de forma conservativa byte a byte sería impracticable (tanto por la
+cantidad de falsos positivos que esto provocaría como por el impacto en el
+rendimiento por el exceso de posibles punteros a revisar, además de lo
+ineficiente que es operar sobre memoria no alineada), en general el recolector
+asume que el usuario nunca va a tener la única referencia a un objeto en una
+estructura no alineada al tamaño de palabra.
+
+
+
+.. _d_prob_high_level:
+
+Programación de alto nivel
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Las características de programación de alto nivel también impone dificultades
+o restricciones al recolector de basura (ver :ref:`d_high_level`). Por ejemplo
+el soporte de rebanado (*slicing*) de arreglos hace que el recolector deba
+soportar punteros *interiores* [#dgcinterior]_ (esto también es necesario
+porque en general en D_ o en cualquier lenguaje de bajo nivel se puede tener
+un puntero a cualquier parte de una celda).
+
+.. [#dgcinterior] Los punteros *interiores* son aquellos que en vez de apuntar
+ al inicio de una celda, apuntan a una dirección arbitraria dentro de ella.
+ Esto no es posible en muchos lenguajes de programación, como por ejemplo
+ Java_, lo que simplifica la recolección de basura.
+
+Los arreglos dinámicos y asociativos en particular dependen fuertemente del
+recolector de basura, en particular cuando se agregan elementos (o se
+concatenan dos arreglos).
+
+Dado que los *strings* son arreglos dinámicos y que el lenguaje provee un buen
+soporte de arreglos dinámicos y asociativos y *slicing*, es de esperarse que
+el recolector deba comportarse de forma correcta y eficiente ante las
+operaciones más típicas de estas estructuras que dependan de él.
+
+
+
+.. _dgc_prob_types:
+Información de tipos
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Hasta aquí D_ comparte todas las restricciones con respecto a la recolección
+de basura con los lenguajes de bajo nivel que no tienen ningún soporte para
+recolectar basura. Sin embargo, a diferencia de éstos, D_ tiene una
+información de tipos más rica. Al momento de asignar memoria D_ puede proveer
+cierta información sobre el objeto a asignar (como si puede contener punteros
+o no) que puede ser utilizada por el recolector para realizar una recolección
+más precisa (ver :ref:`gc_conserv`).
+
+En general esta información no es suficiente como para implementar un
+recolector completamente preciso (no al menos sin agregar un mejor soporte de
+reflexión al lenguaje) pero puede ser de ayuda considerable para el
+recolector.
+
+
+
+.. _dgc_prob_final:
+
+Orientación a objetos y finalización
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+D_ soporta el paradigma de orientación a objetos, donde es común permitir que
+un objeto, al ser destruido, realice alguna tarea de finalización (a través de
+una función miembro llamada *destructor*, o ``~this()`` en D_). Esto significa
+que el recolector, al encontrar que no hay más referencias a un objeto, debe
+ejecutar el destructor.
+
+La especificación dice:
+
+ The garbage collector is not guaranteed to run the destructor for all
+ unreferenced objects. Furthermore, the order in which the garbage collector
+ calls destructors for unreference objects is not specified. This means that
+ when the garbage collector calls a destructor for an object of a class that
+ has members that are references to garbage collected objects, those
+ references may no longer be valid. This means that destructors cannot
+ reference sub objects.
+
+Afortunadamente el orden de finalización no está definido, ya que esto sería
+extremadamente difícil de proveer por un recolector (si no imposible). Esto
+significa que si bien se ejecutan el destructores de los objetos que dejan de
+ser alcanzables desde el *root set*, no se define en que orden se hace, y por
+lo tanto un objeto no puede acceder a sus atributos que sean referencias
+a otros objetos en un destructor.
+Esta restricción en realidad se ve relaja con el soporte de *RAII*. Si se
+utiliza la palabra clave ``scope`` al crear una serie de objetos, estos serán
+destruidos determinísticamente al finalizar el *scope* actual en el orden
+inverso al que fueron creados y, por lo tanto, un usuario podría hacer uso de
+los atributos que sean referencias a otros objetos creados con ``scope`` si el
+orden en que fueron creados (y por lo tanto en que serán destruidos) se lo
+permite.
+
+Sin embargo no hay forma actualmente de saber dentro de un destructor si este
+fue llamado determinísticamente o no, por lo tanto es virtualmente imposible
+hacer uso de esta distinción, a menos que una clase sea declarada para ser
+creada solamente utilizando la palabra reservada ``scope``.
+
+Cabe aclarar que estrictamente hablando, según la especificación de D_, el
+recolector no debe garantizar la finalización de objetos bajo ninguna
+circunstancia, es decir, el recolector podría no llamar a ningún destructor.
+Sin embargo esto es probablemente un problema de redacción vaga y dadas las
+garantías que provee la implementación actual la comunidad de D_ cuenta con
+ellas porque además son deseables (y sencillas de implementar).
+
+
+
+.. _dgc_actual:
Recolector de basura actual de D
----------------------------------------------------------------------------
-TODO
+Como paso básico fundamental para poder mejorar el recolector de basura de D_,
+primero hay que entender la implementación actual, de forma de conocer sus
+puntos fuertes, problemas y limitaciones, de manera tal de poder analizar
+formas de mejorarlo.
+
+Como se mencionó en la sección :ref:`d_lang`, en D_ hay dos bibliotecas base
+para soportar el lenguaje (*runtimes*): Phobos_ y Tango_. La primera es la
+biblioteca estándar de D_, la segunda un proyecto más abierto y dinámico que
+surgió como alternativa a Phobos_ debido a que Phobos_ es muy descuidada y que
+era muy difícil impulsar cambios en ella. Ahora Phobos_ tiene el agravante de
+estar *congelada* en su versión 1 (solo se realizan correcciones de errores).
+Dado que Tango_ está mejor organizada, su desarrollo es más abierto (aceptan
+cambios y mejoras) y que hay una mayor disponibilidad de programas
+y bibliotecas escritos para Tango_, en este trabajo se decide tomar esta
+biblioteca *runtime* como base para el análisis y mejoras propuestas, a pesar
+de ser Phobos_ la estándar. De todas formas el recolector de basura de Tango_
+es prácticamente el mismo que el de Phobos_, por lo tanto éste análisis en
+particular es válido para cualquiera de las dos.
+El recolector actual es un recolector :ref:`indirecto <gc_direct>`, :ref:`no
+incremental <gc_inc>` que realiza un :ref:`marcado y barrido <gc_mark_sweep>`
+relativamente básico. A diferencia del algoritmo clásico presentado éste
+realiza un marcado no recursivo. La fase de marcado es :ref:`stop-the-world
+<gc_concurrent` mientras que la fase de barrido corre en paralelo con el
+*mutator*, excepto el hilo que disparó la recolección que es quien efectúa el
+barrido (además los hilos que intenten asignar nueva memoria o interactuar con
+el recolector de cualquier otra forma se bloquean hasta que la fase de barrido
+concluya). El marcado es casi totalmente :ref:`conservativo <gc_conserv>`; si
+bien posee alguna información de tipos (distingue entre celdas que pueden
+tener punteros y celdas que definitivamente no los tienen, pero no dispone de
+información sobre qué campos de las celdas son punteros y cuales no). Además
+no tiene soporte alguno de :ref:`recolección particionada <gc_part>`.
-Diseño
+Si bien el recolector es bastante básico, posee una :ref:`organización de
+memoria <dgc_org>` relativamente moderna (utiliza una :ref:`lista de libres
+<gc_free_list>` con un *two level allocator*) y algunas optimizaciones
+particulares para amortiguar casos patológicos.
+
+
+.. _dgc_org:
+
+Organización del *heap*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-.. Acá iría básicamente lo que escribí en el blog sobre la implmentación
- actual
+La memoria del *heap* está organizada en *pools*. Un *pool* es una región de
+*páginas* contiguas. Una página es, en general, la unidad mínima de memoria que
+maneja un sistema operativo con soporte de memoria virtual. Cada página dentro
+de un *pool* sirve a su vez como contenedora de bloques (llamados *bin* en la
+:ref:`implementación <dgc_impl>`) de tamaño fijo. Todos los bloques
+pertenecientes a la misma página tienen el mismo tamaño de bloque (ver figura
+:vref:`fig:dgc-org`). Los tamaños de bloque posibles son potencias de 2 desde
+16 bytes hasta 4096 (el tamaño típico de una página), es decir: 16, 32, 64,
+128, 256, 512, 1024, 2048 y 4096 [#dgcpageplus]_. Todos los objetos, arreglos
+o celdas en general se ubican en estos bloques (en uno del tamaño más pequeño
+que haya que sea suficientemente grande como para almacenar dicho objeto). En
+caso de que un objeto sea mayor a una página, se utilizan la menor cantidad de
+páginas contiguas de un pool que tengan espacio suficiente para almacenar
+dicho objeto.
+
+.. [#dgcpageplus] Además existe otro tamaño de bloque especial que se utiliza
+ para indicar la continuación de un objeto grande (que ocupan más de una
+ página).
+
+.. fig:: fig:dgc-org
+
+ Organización del *heap* del recolector de basura actual de D.
-TODO
+ Organización del *heap*. En este ejemplo todos los *pools* tienen 2 páginas
+ excepto el *pool* 2 que tiene una sola. El tamaño de bloque que almacena
+ cada página varía entre 64 bytes (página 0 del *pool* 2) hasta 4096 (ambas
+ páginas del *pool* N) que es una página completa.
+ .. aafig::
+ :scale: 120
+ +----------------------------------------------------------------------+
+ | Heap |
+ +======================================================================+
+ | "Pool 0" "Pool 1" "Pool 2" "Pool 3" ... "Pool N" |
+ | +----------+ +----------+ +----------+ +----------+ +----------+ |
+ | | Página 0 | | Página 0 | | Página 0 | | Página 0 | ... | Página 0 | |
+ | | (8x512) | | (4x1024) | | (64x64) | | (2x2048) | ... | (1x4096) | |
+ | |+--------+| |+--------+| |+--------+| |+--------+| |+--------+| |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| || Bloque || ||qqqqqqqq|| || || || || |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| |+--------+| ||qqqqqqqq|| || Bloque || || || |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| || Bloque || ||qqqqqqqq|| || || || || |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| |+--------+| ||qqqqqqqq|| |+--------+| || Bloque || |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| || Bloque || ||qqqqqqqq|| || || || || |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| |+--------+| ||qqqqqqqq|| || Bloque || || || |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| || Bloque || ||qqqqqqqq|| || || || || |
+ | || Bloque || || || ||qqqqqqqq|| || || || || |
+ | |+--------+| |+--------+| |+--------+| |+--------+| |+--------+| |
+ | | Página 1 | | Página 1 | +----------+ | Página 1 | ... | Página 1 | |
+ | | (16x256) | | (8x512) | | (32x128) | ... | (1x4096) | |
+ | |+--------+| |+--------+| |+--------+| |+--------+| |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| ||nnnnnnnn|| || || |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| ||nnnnnnnn|| || || |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| ||nnnnnnnn|| || || |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| ||nnnnnnnn|| || Bloque || |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| ||nnnnnnnn|| || || |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| ||nnnnnnnn|| || || |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| ||nnnnnnnn|| || || |
+ | |+--------+| || Bloque || ||nnnnnnnn|| || || |
+ | |+--------+| |+--------+| |+--------+| ... |+--------+| |
+ | +----------+ +----------+ +----------+ +----------+ |
+ +----------------------------------------------------------------------+
-Implementación
+Cada página de un *pool* puede estar asignada a contener bloques de un tamaño
+específico o puede estar libre. A su vez, cada bloque puede estar ocupado por
+una celda o estar libre. Los bloques libres de un tamaño específico (a
+excepción de aquellos bloques que ocupen una página entera) además forman
+parte de una :ref:`lista de libres <gc_free_list>` (ver figura
+:vref:`fig:dgc-free-list`). Esto permite asignar objetos relativamente
+pequeños de forma bastante eficiente.
+
+.. fig:: fig:dgc-free-list
+
+ Ejemplo de listas de libres.
+
+ .. digraph:: dgc_free_list
+
+ margin = 0;
+ rankdir = LR;
+ ratio = fill;
+ size = "4.6,3.6";
+ node [ shape = record, width = 0, height = 0 ];
+
+ subgraph cluster_heap {
+ style = solid;
+ color = black;
+
+ free [ label = "Libres|<p16> 16|<p32> 32|<p64> 64|<p128> 128|<p256> 256|<p512> 512|<p1024> 1024|<p2048> 2048" ];
+
+ free:p16 -> b1 -> b2 -> b3;
+ free:p32 -> b4 -> b5 -> b6 -> b7 -> b8;
+ // free:p64 is empty
+ free:p128 -> b9;
+ free:p256 -> b10 -> b11;
+ free:p512 -> b12;
+ free:p1024 -> b13 -> b14;
+ free:p2048 -> b15 -> b16 -> b17;
+ }
+
+
+Atributos de *pool*
+^^^^^^^^^^^^^^^^^^^
+Cada *pool* tiene la siguiente información asociada:
+
+*number_of_pages*
+ cantidad de páginas que tiene. Esta cantidad es fija en toda la vida de un
+ *pool*.
+
+*pages*
+ bloque de memoria contiguo de tamaño ``PAGE_SIZE * number_of_pages``
+ (siendo ``PAGE_SIZE`` el tamaño de página, que normalmente son 4096 bytes).
+
+
+Atributos de página
+^^^^^^^^^^^^^^^^^^^
+Cada página dentro de un *pool* tiene un único atributo asociado: *block_size*.
+Se trata del tamaño de los bloques que almacena esta página.
+
+Una página siempre almacena bloques del mismo tamaño, que pueden ser 16, 32,
+64, 128, 256, 512, 1024, 2048 o 4096 (llamado con el nombre especial
+``PAGE``). Además hay dos tamaños de bloque simbólicos que tienen un
+significado especial:
+
+``FREE``
+ indica que la página está completamente libre y que la página está
+ disponible para albergar cualquier tamaño de bloque que sea necesario (pero
+ una vez que se le asignó un nuevo tamaño de bloque ya no puede ser cambiado
+ hasta que la página vuelva a liberarse por completo).
+
+``CONTINUATION``
+ indica que esta página es la continuación de un objeto grande (es decir,
+ que ocupa una o más páginas). Luego se presentan más detalles sobre objetos
+ grandes.
+
+Las páginas con esto tamaños de bloque especiales (conceptualmente) no
+contienen bloques.
+
+
+Atributos de bloque
+^^^^^^^^^^^^^^^^^^^
+Cada bloque tiene asociados varios atributos:
+
+*mark*
+ utilizado en la fase de :ref:`marcado <dgc_algo_mark>`, indica que un nodo
+ ya fue visitado (serían las celdas *negras* en la :ref:`abstracción
+ tricolor <gc_intro_tricolor>`).
+
+*scan*
+ utilizado también en la fase de :ref:`marcado <dgc_algo_mark>`, indica que
+ una celda visitada todavía tiene *hijas* sin marcar (serían las celdas
+ *grises* en la :ref:`abstracción tricolor <gc_intro_tricolor>`).
+
+*free*
+ indica que el bloque está libre (no está siendo utilizado por ningún objeto
+ *vivo*). Esto es necesario solo por la forma en la que realiza el
+ :ref:`marcado <dgc_algo_mark>` y :ref:`barrido <dgc_algo_sweep>` en el
+ :ref:`algoritmo actual <dgc_algo>` (las celdas con el atributo este
+ atributo son tomadas como *basura* aunque estén marcadas con *mark*).
+
+*final*
+ indica que el bloque contiene un objeto que tiene un destructor (que debe
+ ser llamado cuando la celda pasa de *viva* a *basura*).
+
+*noscan*
+ indica que el bloque contiene un objeto que no tiene punteros y por lo
+ tanto no debe ser marcado de forma conservativa (no tiene *hijas*).
+
+
+Objetos grandes
+^^^^^^^^^^^^^^^
+El recolector de basura actual de D_ trata de forma diferente a los objetos
+grandes. Todo objeto grande empieza en un bloque con tamaño ``PAGE``
+y (opcionalmente) continúa en los bloques contiguos subsiguientes que tengan
+el tamaño de bloque ``CONTINUATION`` (si el objeto ocupa más que una página).
+El fin de un objeto grande queda marcado por el fin del *pool* o una página
+con tamaño de bloque distinto a ``CONTINUATION`` (lo que suceda primero).
+
+Cuando un objeto grande se convierte en *basura*, todas sus páginas se liberan
+por completo, siendo marcadas con tamaño ``FREE`` para que puedan ser
+almacenado en ellas otros objetos grandes o incluso nuevos bloques de un
+tamaño determinado.
+
+
+
+.. _dgc_algo:
+
+Algoritmos del recolector
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-.. Acá diría por qué hay que reescribirlo para usar lo que está
+A continuación se explica como provee el recolector actual de D_ los servicios
+básicos que debe proveer cualquier recolector, como se presentó en la sección
+:ref:`gc_intro_services`.
+
+Cabe aclarar que se presenta una versión simplificada del algoritmo, o más
+precisamente, de la implementación del algoritmo, ya que no se exponen en esta
+sección muchas optimizaciones que harían muy compleja la tarea de explicar
+como funciona conceptualmente. En la siguiente sección, :ref:`dgc_impl`, se
+darán más detalles sobre las optimizaciones importantes y diferencias con el
+algoritmo aquí presentado, junto con detalles sobre como se implementa la
+organización del *heap* que se explicó en la sección anterior.
+
+
+.. _dgc_algo_collect:
+
+Recolección
+^^^^^^^^^^^
+A grandes rasgos el algoritmo de recolección puede resumirse de las dos fases
+básicas de cualquier algoritmo de :ref:`marcado y barrido <gc_mark_sweep>`::
+
+ function collect() is
+ mark_phase()
+ sweep_phase()
+
+
+.. _dgc_algo_mark:
+
+Fase de marcado
+^^^^^^^^^^^^^^^
+Esta fase consiste de varios pasos, que pueden resumirse en el siguiente
+algoritmo::
+
+ function mark_phase() is
+ global more_to_scan = false
+ stop_the_world()
+ clear_mark_scan_bits()
+ 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_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()`` 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
+atributos *mark* y *scan* de cada bloque del *heap*::
+
+ function clear_mark_scan_bits() is
+ foreach pool in heap
+ foreach page in pool
+ foreach block in page
+ block.mark = false
+ block.scan = false
+
+La función ``mark_free_lists()`` por su parte se encarga de activar el bit
+*mark* de todos los bloques de las listas de libres de manera de que la fase
+de marcado (que es iterativa y realiza varias pasadas sobre **todo** el
+*heap*, incluyendo las celdas libres) no visite las celdas libres perdiendo
+tiempo sin sentido y potencialmente manteniendo *vivas* celdas que en
+realidad son *basura* (falsos positivos)::
+
+ function mark_free_lists() is
+ foreach free_list in heap
+ foreach block in free_list
+ block.mark = true
+ block.free = true
+
+Notar que los bloques libres quedan entonces marcados aunque sean *basura* por
+definición. Para evitar que en la etapa de barrido se tomen estos bloques como
+celdas vivas, a todos los bloques en la lista de libres también se los marca
+con el bit *free*, así el barrido puede tomar como *basura* estos bloques
+aunque estén marcados.
+
+El *root set* está compuesto por el área de memoria estática (variables
+globales), los *stacks* de todos los hilos y los registros del procesador.
+Primero se marca el área de memoria estática de manera :ref:`conservativa
+<gc_conserv>` (es decir, tomando cada *word* como si fuera un puntero)::
+
+ function mark_static_data() is
+ 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::
+
+ function push_registers_into_stack() is
+ 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
+ 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
+set* convencional ni en el *heap* del recolector. Para evitar que se libere
+alguna celda a la cual todavía existen referencias desde memoria administrada
+por el usuario, éste debe informarle al recolector sobre la existencia de
+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 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_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
+celda puede contener punteros. Por lo tanto solo resta marcar (nuevamente de
+forma conservativa) iterativamente todo el *heap* hasta que no hayan más
+celdas para visitar (con el bit *scan* activo)::
+
+ function mark_heap() is
+ while global more_to_scan
+ global more_to_scan = false
+ foreach pool in heap
+ foreach page in pool
+ if page.block_size <= PAGE // saltea FREE y CONTINUATION
+ foreach block in page
+ if block.scan is true
+ block.scan = false
+ if page.block_size is PAGE // objeto grande
+ begin = cast(byte*) page
+ end = find_big_object_end(pool, page)
+ mark_range(begin, end)
+ else // objeto pequeño
+ mark_range(block.begin, block.end)
+
+Aquí puede verse, con un poco de esfuerzo, la utilización de la
+:ref:`abstracción tricolor <gc_intro_tricolor>`: todas las celdas alcanzables
+desde el *root set* son pintadas de *gris* (tienen los bits *mark* y *scan*
+activados), excepto aquellas celdas atómicas (es decir, que se sabe que no
+tienen punteros) que son marcadas directamente de *negro*. Luego se van
+obteniendo celdas del conjunto de las *grises*, se las pinta de *negro* (es
+decir, se desactiva el bit *scan*) y se pintan todas sus *hijas* de *gris* (o
+*negro* directamente si no tienen punteros). Este procedimiento se repite
+mientras el conjunto de celdas *grises* no sea vacío (es decir, que
+``more_to_scan`` sea ``true``).
+
+A continuación se presenta la implementación de las funciones suplementarias
+utilizadas en la fase de marcado::
+
+ function find_big_object_end(pool, page) is
+ pool_end = cast(byte*) pool.pages + (PAGE_SIZE * pool.number_of_pages)
+ do
+ page = cast(byte*) page + PAGE_SIZE
+ while page.block_size is CONTINUATION and page < pool_end
+ return page
+
+ function find_block(pointer) is
+ foreach pool in heap
+ foreach page in pool
+ if page.block_size is PAGE
+ big_object_start = cast(byte*) page
+ big_object_end = find_big_object_end(pool, page)
+ if big_object_start <= pointer < big_object_end
+ return [pool, page, big_object_start]
+ else if page.bloc_size < PAGE
+ foreach block in page
+ block_start = cast(byte*) block
+ block_end = block_start + page.block_size
+ if block_start <= pointer < block_end
+ return [pool, page, block_start]
+ return [null, null, null]
+
+Cabe destacar que la función ``find_block()`` devuelve el *pool*, la página
+y el comienzo del bloque al que apunta el puntero, es decir, soporta punteros
+*interiores*.
+
+
+.. _dgc_algo_sweep:
+
+Fase de barrido
+^^^^^^^^^^^^^^^
+Esta fase es considerablemente más sencilla que el marcado; el algoritmo puede
+dividirse en dos pasos básicos::
+
+ function sweep_phase() is
+ sweep()
+ rebuild_free_lists()
+
+El barrido se realiza con una pasada por sobre todo el *heap* de la siguiente
+manera::
+
+ function sweep() is
+ foreach pool in heap
+ foreach page in pool
+ if page.block_size <= PAGE // saltea FREE y CONTINUATION
+ foreach block in page
+ if block.mark is false
+ if block.final is true
+ finalize(block)
+ block.free = true
+ block.final = false
+ block.noscan = false
+ if page.block_size is PAGE // objeto grande
+ free_big_object(pool, page)
+
+Como se observa, se recorre todo el *heap* en busca de bloques y páginas
+libres. Los bloques libres son marcados con el atributo ``free`` y las páginas
+libres son marcadas con el tamaño de bloque simbólico ``FREE``. Para los
+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.block_size = FREE
+ 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
+biblioteca *runtime* y en última instancia llama al destructor del objeto
+almacenado en el bloque a liberar.
+
+Una vez marcados todos los bloques y páginas como libre, se procede
+a reconstruir las listas de libres. En el proceso buscan las páginas que
+tengan todos los bloques libres para marcar la página completa como libre (de
+manera que pueda utilizarse para albergar otro tamaño de bloque u objetos
+grandes de ser necesario)::
+
+ function rebuild_free_lists() is
+ foreach free_list in heap
+ free_list.clear()
+ foreach pool in heap
+ foreach page in pool
+ if page.block_size < PAGE // objetos pequeños
+ if is_page_free(page)
+ page.block_size = FREE
+ else
+ foreach block in page
+ if block.free is true
+ free_lists[page.block_size].link(block)
+
+Esta reorganización de listas libres además mejoran la localidad de
+referencia y previenen la fragmentación. La localidad de referencia se ve
+mejorada debido a que asignaciones de memoria próximas en el tiempo serán
+también próximas en espacio porque pertenecerán a la misma página (al menos si
+las asignaciones son todas del mismo tamaño). La fragmentación se minimiza por
+el mismo efecto, primero se asignarán todos los bloques de la misma página.
+
+A continuación se presenta la implementación de una de las funciones
+suplementarias de la fase de barrido::
+
+ function is_page_free(page) is
+ foreach block in page
+ if block.free is false
+ return false
+ return true
+
+Las demás funciones suplementarias pertenecen a la manipulación de listas
+libres que no son más que operaciones sobre una lista simplemente enlazada. En
+la sección :ref:`dgc_impl` se verá con más detalles como las implementa el
+recolector actual.
+
+
+.. _dgc_algo_alloc:
+
+Asignación de memoria
+^^^^^^^^^^^^^^^^^^^^^
+La asignación de memoria del recolector es relativamente compleja, excepto
+cuando se asigna un objeto pequeño y ya existe algún bloque con el tamaño
+preciso en la lista de libres. Para el resto de los casos la cantidad de
+trabajo que debe hacer el recolector para asignar la memoria es considerable.
+
+El algoritmo de asignación de memoria se puede resumir así::
+
+ function new(size, attrs) is
+ block_size = find_block_size(size)
+ if block_size < PAGE
+ block = new_small(block_size)
+ else
+ block = new_big(size)
+ if block is null
+ throw out_of_memory
+ if final in attrs
+ block.final = true
+ if noscan in attrs
+ block.noscan = true
+ return cast(void*) block
+
+La función ``find_block_size()`` sencillamente busca el tamaño de bloque se
+mejor se ajuste al tamaño solicitado (es decir, el bloque más pequeño lo
+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
+ block = find_block_with_size(block_size)
+ if block is null
+ collect()
+ block = find_block_with_size(block_size)
+ if block is null
+ new_pool()
+ block = find_block_with_size(block_size)
+ 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
+una :ref:`recolección <dgc_algo_collect>` y si no se puede encontrar
+suficiente espacio luego de ella se intenta crear un nuevo *pool* de memoria
+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
+ block = free_lists[block_size].pop_first()
+ if block is null
+ assign_page(block_size)
+ block = free_lists[block_size].pop_first()
+ 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)
+
+Cuando todo ello falla, el último recurso consiste en pedir memoria al sistema
+operativo, creando un nuevo *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
+implementación actual de D_ en general es el sistema operativo (aunque
+opcionalmente puede utilizarse la biblioteca estándar de C, que a su vez
+utiliza el sistema operativo).
+
+Cualquier error en estas funciones es propagado y en última instancia, cuando
+todo falla, la función ``new()`` termina lanzando una excepción indicando que
+se agotó la memoria.
+
+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)
+ 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]
+
+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
+almacenar el tamaño requerido y si esto falla, se realizan diferentes pasos
+y se vuelve a intentar. Puede observarse que, a diferencia de la asignación de
+objetos pequeños, si luego de la recolección no se pudo encontrar lugar
+suficiente, se trata de minimizar el uso de memoria física utilizando la
+siguiente función, que devuelve al *low level allocator* los *pools*
+completamente libres::
+
+ function minimize() is
+ for pool in heap
+ all_free = true
+ for page in pool
+ if page.block_size is not FREE
+ all_free = false
+ break
+ if all_free is true
+ free(pool.pages)
+ free(pool)
+ heap.remove(pool)
+
+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
+
+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]
+ 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
+suficientes como para almacenar el objeto grande y si esto falla el error se
+propaga hasta la función ``new()`` que lanza una excepción.
+
+
+.. _dgc_algo_free:
+
+Liberación de memoria
+^^^^^^^^^^^^^^^^^^^^^
+La liberación de la memoria asignada puede hacerse explícitamente. Esto
+saltea el mecanismo de recolección, y es utilizado para dar soporte a manejo
+explícito de memoria asignada en el *heap* del recolector. En general el
+usuario no debe utilizar liberación explícita, pero puede ser útil en casos
+muy particulares::
+
+ function delete(pointer) is
+ [pool, page, block_start] = find_block(pointer)
+ if block is not null
+ block.free = true
+ block.final = false
+ block.noscan = false
+ if page.block_size is PAGE // objeto grande
+ free_big_object(pool, page)
+ else // objeto pequeño
+ free_lists[page.block_size].link(block)
+
+Como se puede observar, si el objeto es pequeño se enlaza a la lista de libres
+correspondiente y si es grande se liberan todas las páginas asociadas a éste,
+de forma similar a la :ref:`fase de barrido <dgc_algo_sweep>`. A diferencia de
+ésta, no se finaliza el objeto (es decir, no se llama a su destructor).
+
+
+.. _dgc_algo_final:
+
+Finalización
+^^^^^^^^^^^^
+Al finalizar el programa, el recolector es finalizado también y lo que realiza
+actualmente, además de liberar la memoria propia del recolector, es realizar
+una recolección. Es decir, si hay objetos que son todavía alcanzables desde el
+*root set*, esos objetos no son finalizados (y por lo tanto sus destructores
+no son ejecutados).
+
+Como se ha visto, esto es perfectamente válido ya que D_ no garantiza que los
+objetos sean finalizados.
+
+
+
+.. _dgc_impl:
+
+Detalles de implementación
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Hay varias diferencias a nivel de implementación entre lo que se presentó en
+las secciones anteriores y como está implementado realmente el recolector
+actual. Con los conceptos e ideas principales del ya explicadas, se procede
+a ahondar con más detalle en como está construido el recolector y algunas de
+sus optimizaciones principales.
+
+Vale aclarar que el recolector de basura actual está implementado en D_.
+
+
+Estructuras de datos del recolector
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+El recolector está principalmente contenido en la estructura llamada ``Gcx``.
+Dicha estructura tiene los siguientes atributos (divididos en categorías para
+facilitar la comprensión):
+
+Raíces definidas por el usuario
+ *roots* (*nroots*, *rootdim*)
+ arreglo variable de punteros simples que son tomados como raíces
+ provistas por el usuario.
+
+ *ranges* (*nranges*, *rangedim*)
+ arreglo variable de rangos de memoria que deben ser revisados (de forma
+ conservativa) como raíces provistas por el usuario. Un rango es una
+ estructura con dos punteros: ``pbot`` y ``ptop``. Toda la memoria entre
+ estos dos punteros se toma, palabra por palabra, como una raíz del
+ recolector.
+
+Estado interno del recolector
+ *anychanges*
+ variable que indica si en la fase de marcado se encontraron nuevas
+ celdas con punteros que deban ser visitados. Otra forma de verlo es como
+ un indicador de si el conjunto de celdas *grises* está vacío luego de
+ una iteración de marcado (utilizando la :ref:`abstracción tricolor
+ <gc_intro_tricolor>`). Es análoga a la variable ``more_to_scan``
+ presentada en :ref:`dgc_algo_mark`.
+
+ *inited*
+ indica si el recolector fue inicializado.
+
+ *stackBottom*
+ puntero a la base del *stack* (asumiendo que el stack crece hacia arriba).
+ Se utiliza para saber por donde comenzar a visitar el *stack* de forma
+ conservativa, tomándolo con una raíz del recolector.
+
+ *Pools* (*pooltable*, *npools*)
+ arreglo variable de punteros a estructuras ``Pool`` (ver más adelante).
+ Este arreglo se mantiene siempre ordenado de menor a mayor según la
+ dirección de memoria de la primera página que almacena.
+
+ *bucket*
+ listas de libres. Es un arreglo de estructuras ``List`` utilizadas para
+ guardar la listas de libres de todos los tamaños de bloques posibles (ver
+ más adelante).
+
+Atributos que cambian el comportamiento
+ *noStack*
+ indica que no debe tomarse al *stack* como raíz del recolector. Esto es
+ muy poco seguro y no debería ser utilizado nunca, salvo casos
+ extremadamente excepcionales.
+
+ *log*
+ indica si se debe guardar un registro de la actividad del recolector. Es
+ utilizado principalmente para depuración.
+
+ *disabled*
+ indica que no se deben realizar recolecciones implícitamente. Si al
+ tratar de asignar memoria no se puede hallar celdas libres en el *heap*
+ del recolector, se pide más memoria al sistema operativo sin correr una
+ recolección para intentar recuperar espacio. Esto es particularmente
+ útil para secciones de un programa donde el rendimiento es crítico y no
+ se pueden tolerar grandes pausas como las que puede provocar el
+ recolector.
+
+Optimizaciones
+ *p_cache*, *size_cache*
+ obtener el tamaño de un bloque dado un puntero es una tarea costosa
+ y común. Para evitarla en casos donde se calcula de forma sucesiva el
+ tamaño del mismo bloque (como puede ocurrir al concatenar arreglos
+ dinámicos) se guarda el último calculado en estas variables a modo de
+ *caché*.
+
+ *minAddr*, *maxAddr*
+ punteros al principio y fin del *heap*. Pueden haber *huecos* entre
+ estos dos punteros que no pertenezcan al *heap* pero siempre se cumple
+ que si un puntero apunta al *heap* debe estar en este rango. Esto es
+ útil para hacer un cálculo rápido para descartar punteros que fueron
+ tomados de forma conservativa y en realidad no apuntan al *heap* (ver la
+ función ``find_block()`` en :ref:`dgc_algo_mark`).
+
+
+*Pools*
+^^^^^^^
+La primera diferencia es como está organizado el *heap*. Si bien la
+explicación presentada en la sección :ref:`dgc_org` es correcta, la forma en
+la que está implementado no es tan *naïve* como los algoritmos presentados en
+:ref:`dgc_algo` sugieren.
+
+El recolector guarda un arreglo variable de estructuras ``Pool``. Cabe
+destacar que para implementar el recolector no se pueden utilizar los arreglos
+dinámicos de D_ (ver sección :ref:`d_high_level`) dado que éstos utilizan de
+forma implícita el recolector de basura, por lo tanto todos los arreglos
+variables del recolector se implementan utilizando las funciones de
+C ``malloc()``, ``realloc()`` y ``free()`` directamente.
-TODO
+La estructura ``Pool`` está compuesta por los siguientes atributos (ver figura
+:vref:`fig:dgc-pool`):
+*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
+ secciones anteriores para mayor claridad).
+
+*mark*, *scan*, *freebits*, *finals*, *noscan*
+ conjunto de bits (*bitsets*) para almacenar los indicadores descriptos en
+ :ref:`dgc_org` para todos los bloques de todas las páginas del *pool*.
+ *freebits* es análogo a *free* y *finals* a *final* en los atributos
+ descriptos en las secciones anteriores.
+
+*npages*
+ cantidad de páginas que contiene este *pool* (fue nombrado
+ *number_of_pages* en las secciones anteriores para mayor claridad).
+
+*ncommitted*
+ cantidad de páginas *encomendadas* al sistema operativo (*committed* en
+ inglés). Este atributo no se mencionó anteriormente porque el manejo de
+ páginas encomendadas le agrega una complejidad bastante notable al
+ recolector y es solo una optimización para un sistema operativo en
+ particular (Microsoft Windows).
+
+*pagetable*
+ arreglo de indicadores de tamaño de bloque de cada página de este *pool*.
+ Los indicadores válidos son ``B_16`` a ``B_2048`` (pasando por los valores
+ posibles de bloque mencionados anteriormente, todos con el prefijo
+ "``B_``"), ``B_PAGE``, ``B_PAGEPLUS`` (análogo a ``CONTINUATION``),
+ ``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
+una gran porción continua de memoria sin estar intercalada con
+meta-información del recolector.
+
+Para poder acceder a los bits de un bloque en particular, se utiliza la
+siguiente cuenta para calcular el índice en el *bitset*:
+
+.. math::
+
+ index(p) = \frac{p - baseAddr}{16}
+
+Donde ``p`` es la dirección de memoria del bloque. Esto significa que, sin
+importar cual es el tamaño de bloque de las páginas del *pool*, el *pool*
+siempre reserva suficientes bits como para que todas las páginas puedan tener
+tamaño de bloque de 16 bytes. Esto puede ser desperdiciar bastante espacio si
+no predomina un tamaño de bloque pequeño.
+
+
+Listas de libres
+^^^^^^^^^^^^^^^^
+Las listas de libres se almacenan en el recolector como un arreglo de
+estructuras ``Lista``, que se compone solamente de un atributo ``List* next``
+(es decir, un puntero al siguiente). Entonces cada elemento de ese arreglo es
+un puntero al primer elemento de la lista en particular.
+
+La implementación utiliza a los bloques de memoria como nodos directamente.
+Como los bloques siempre pueden almacenar una palabra (el bloque de menor
+tamaño es de 16 bytes y una palabra ocupa comúnmente entre 4 y 8 bytes según
+se trabaje sobre arquitecturas de 32 o 64 bits respectivamente), se almacena
+el puntero al siguiente en la primera palabra del bloque.
+
+
+Algoritmos
+^^^^^^^^^^
+Los algoritmos en la implementación real son considerablemente menos modulares
+que los presentados en la sección :ref:`dgc_algo`. Por ejemplo, la función
+``collect()`` es una gran función de 300 líneas de código.
+
+A continuación se resumen las funciones principales, separadas en categorías
+para facilitar la comprensión. Los siguientes son métodos de la estructura
+``Gcx``:
+
+Inicialización y terminación
+ *initialize()*
+ inicializa las estructuras internas del recolector para que pueda ser
+ utilizado. Esta función la llama la biblioteca *runtime* antes de que el
+ programa comience a correr.
+
+ *Dtor()*
+ libera todas las estructuras que utiliza el recolector.
+
+Manipulación de raíces definidas por el usuario
+ *addRoot(p)*, *removeRoot(p)*, *rootIter(dg)*
+ agrega, remueve e itera sobre las raíces simples definidas por el
+ usuario.
+
+ *addRange(pbot, ptop)*, *remove range(pbot)*, *rangeIter(dg)*
+ agrega, remueve e itera sobre los rangos de raíces definidas por el
+ usuario.
+
+Manipulación de indicadores
+ *getBits(pool, biti)*
+ obtiene los indicadores especificados para el bloque de índice ``biti``
+ en el *pool* ``pool``.
+
+ *setBits(pool, biti, mask)*
+ establece los indicadores especificados en ``mask`` para el bloque de
+ índice ``biti`` en el *pool* ``pool``.
+
+ *clrBits(pool, biti, mask)*
+ limpia los indicadores especificados en ``mask`` para el bloque de
+ índice ``biti`` en el *pool* ``pool``.
+
+ Cada bloque (*bin* en la terminología de la implementación del recolector)
+ tiene ciertos indicadores asociados. Algunos de ellos pueden ser
+ manipulados (indirectamente) por el usuario utilizando las funciones
+ mencionadas arriba.
+
+ El parámetro ``mask`` debe ser una máscara de bits que puede estar
+ compuesta por la conjunción de los siguientes valores:
+
+ *FINALIZE*
+ el objeto almacenado en el bloque tiene un destructor (indicador
+ *finals*).
+
+ *NO_SCAN*
+ el objeto almacenado en el bloque no contiene punteros (indicador
+ *noscan*).
+
+ *NO_MOVE*
+ el objeto almacenado en el bloque no debe ser movido [#dgcmove]_.
+
+.. [#dgcmove] Si bien el recolector actual no tiene la capacidad de mover
+ objetos, la interfaz del recolector hacer que sea posible una
+ implementación que lo haga, ya que a través de este indicador se pueden
+ fijar objetos apuntados desde algún segmento no conservativo (objeto
+ *pinned*).
+
+Búsquedas
+ *findPool(p)*
+ busca el *pool* al que pertenece el objeto apuntado por ``p``.
+
+ *findBase(p)*
+ busca la dirección base (el inicio) del bloque apuntado por ``p``
+ (``find_block()`` según la sección :ref:`dgc_algo_mark`).
+
+ *findSize(p)*
+ busca el tamaño del bloque apuntado por ``p``.
+
+ *getInfo(p)*
+ obtiene información sobre el bloque apuntado por ``p``. Dicha
+ información se retorna en una estructura ``BlkInfo`` que contiene los
+ siguientes atributos: ``base`` (dirección del inicio del bloque),
+ ``size`` (tamaño del bloque) y ``attr`` (atributos o indicadores del
+ bloque, los que se pueden obtener con ``getBits()``).
+
+ *findBin(size)*
+ calcula el tamaño de bloque más pequeño que pueda contener un objeto de
+ tamaño ``size`` (``find_block_size()`` según lo visto en
+ :ref:`dgc_algo_alloc`).
+
+Asignación de memoria
+ *reserve(size)*
+ reserva un nuevo *pool* de al menos ``size`` bytes. El algoritmo nunca
+ crea un *pool* con menos de 256 páginas (es decir, 1 MiB).
+
+ *minimize()*
+ minimiza el uso de la memoria retornando *pools* sin páginas usadas al
+ sistema operativo.
+
+ *newPool(n)*
+ reserva un nuevo *pool* con al menos ``n`` páginas. Junto con
+ ``Pool.initialize()`` es análoga a ``new_pool()``, solo que esta función
+ siempre incrementa el número de páginas a, al menos, 256 páginas (es
+ decir, los *pools* son siempre mayores a 1 MiB). Si la cantidad de
+ páginas pedidas supera 256, se incrementa el número de páginas en un 50%
+ como para que sirva para futuras asignaciones también. Además a medida
+ que la cantidad de *pools* crece, también trata de obtener cada vez más
+ memoria. Si ya había un *pool*, el 2do tendrá como mínimo 2 MiB, el 3ro
+ 3 MiB y así sucesivamente hasta 8 MiB. A partir de ahí siempre crea
+ *pools* de 8 MiB o la cantidad pedida, si ésta es mayor.
+
+ *Pool.initialize(n_pages)*
+ inicializa un nuevo *pool* de memoria. Junto con ``newPool()`` es
+ análoga a ``new_pool()``. Mientras ``newPool()`` es la encargada de
+ calcular la cantidad de páginas y crear el objeto *pool*, esta función
+ es la que pide la memoria al sistema operativo. Además inicializa los
+ conjuntos de bits: ``mark``, ``scan``, ``freebits``, ``noscan``.
+ ``finals`` se inicializa de forma perezosa, cuando se intenta asignar el
+ atributo ``FINALIZE`` a un bloque, se inicializa el conjunto de bits
+ ``finals`` de todo el *pool*.
+
+ *allocPage(bin)*
+ asigna a una página libre el tamaño de bloque ``bin`` y enlaza los
+ nuevos bloques libres a la lista de libres correspondiente (análogo
+ a ``assign_page()``).
+
+ *allocPages(n)*
+ Busca ``n`` cantidad de páginas consecutivas libres (análoga
+ a ``find_pages(n)``).
+
+ *malloc(size, bits)*
+ asigna memoria para un objeto de tamaño ``size`` bytes. Análoga al
+ algoritmo ``new(size, attr)`` presentado, excepto que introduce además
+ un caché para no recalcular el tamaño de bloque necesario si se realizan
+ múltiples asignaciones consecutivas de objetos del mismo tamaño y que la
+ asignación de objetos pequeños no está separada en una función aparte.
+
+ *bigAlloc(size)*
+ asigna un objeto grande (análogo a ``new_big()``). La implementación es
+ mucho más compleja que la presentada en ``new_big()``, pero la semántica
+ es la misma. La única diferencia es que esta función aprovecha que
+ ``fullcollectshell()`` / ``fullcollect()`` retornan la cantidad de
+ páginas liberadas en la recolección por lo que puede optimizar levemente
+ el caso en que no se liberaron suficientes páginas para asignar el
+ objeto grande y pasar directamente a crear un nuevo *pool*.
+
+ *free(p)*
+ libera la memoria apuntada por ``p`` (análoga a ``delete()`` de la
+ sección anterior).
+
+ Recordar que la ``pooltable`` siempre se mantiene ordenada según la
+ dirección de la primera página.
+
+Recolección
+ *mark(pbot, ptop)*
+ 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
+ algoritmo presentado en :ref:`dgc_algo_mark` es simbólico, ya que si los
+ registros se apilaran en el *stack* dentro de otra función, al salir de
+ esta se volverían a des-apilar, por lo tanto debe ser hecho en la misma
+ función ``collect()`` o en una función que luego la llame (como en este
+ caso).
+
+ *fullcollect(stackTop)*
+ realiza la recolección de basura. Es análoga a ``collect()`` pero es
+ considerablemente menos modular, todos los pasos se hacen directamente
+ en esta función: marcado del *root set*, marcado iterativo del *heap*,
+ barrido y reconstrucción de la lista de libres. Además devuelve la
+ cantidad de páginas que se liberaron en la recolección, lo que permite
+ optimizar levemente la función ``bigAlloc()``.
+
+
+Finalización
+^^^^^^^^^^^^
+El recolector actual, por omisión, solamente efectúa una recolección al
+finalizar. Por lo tanto, no se ejecutan los destructores de todos aquellos
+objetos que son alcanzables desde el *root set* en ese momento. Existe la
+opción de no realizar una recolección al finalizar el recolector, pero no de
+finalizar *todos* los objetos (alcanzables o no desde el *root set*). Si bien
+la especificación de D_ permite este comportamiento (de hecho la
+especificación de D_ es tan vaga que permite un recolector que no llame jamás
+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*
+(*committed* en inglés) y *no-encomendada*. Esto se debe a que originalmente
+el compilador de D_ DMD_ solo funcionaba en Microsoft Windows y este sistema
+operativo puede asignar memoria en dos niveles. Por un lado puede asignar al
+proceso un espacio de memoria (*address space*) pero sin asignarle la memoria
+correspondiente. En un paso posterior se puede *encomendar* la memoria (es
+decir, asignar realmente la memoria).
+
+Para aprovechar esta característica el recolector diferencia estos dos
+niveles. Sin embargo, esta diferenciación introduce una gran complejidad (que
+se omitió en las secciones anteriores para facilitar la comprensión),
+y convierte lo que es una ventaja en un sistema operativo en una desventaja
+para todos los demás (ya que los cálculos extra se realizan pero sin ningún
+sentido). De hecho hay sistemas operativos, como Linux_, que realizan este
+trabajo automáticamente (la memoria no es asignada realmente al programa hasta
+que el programa no haga uso de ella; esta capacidad se denomina *overcommit*).
+
+Como se vio en la figura :vref:`fig:dgc-pool`, lás páginas de un *pool* se
+dividen en *committed* y *uncommitted*. Siempre que el recolector recorre un
+*pool* en busca de una página o bloque, lo hace hasta la memoria *committed*,
+porque la *uncommitted* es como si jamás se hubiera pedido al sistema
+operativo a efectos prácticos. Además, al buscar páginas libres, si no se
+encuentran entre las *encomendadas* se intenta primero *encomendar* páginas
+nuevas antes de crear un nuevo *pool*.
+
+
+Sincronización
+^^^^^^^^^^^^^^
+Si bien el recolector no es paralelo ni concurrente (ver :ref:`gc_art`),
+soporta múltiples *mutator*\ s. La forma de implementarlo es la más simple.
+Todas las operaciones sobre el recolector que se llaman externamente están
+sincronizadas utilizando un *lock* global (excepto cuando hay un solo hilo
+*mutator*, en cuyo caso se omite la sincronización). Esto afecta también a la
+asignación de memoria.
+
+
+
+.. _dgc_good:
+
+Características destacadas
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Si bien el recolector en términos generales no se aleja mucho de un
+:ref:`marcado y barrido clásico <gc_mark_sweep>`, tiene algunas mejoras por
+sobre el algoritmo más básicos que vale la pena destacar:
+
+
+Organización del *heap*
+^^^^^^^^^^^^^^^^^^^^^^^
+El *heap* está organizado de una forma que, si bien no emplea las técnicas más
+modernas que pueden observarse en el estado del arte (como :ref:`regiones
+<gc_free_list>`), es relativamente sofisticada. El esquema de *pools*
+y bloques permite disminuir considerablemente los problemas de *fragmentación*
+de memoria y evita búsquedas de *huecos* que pueden ser costosas (como
+*best-fit* [#dgcbestfit]_) o desperdiciar mucho espacio (como *first-fit*
+[#dgcfirstfit]_), logrando un buen equilibrio entre velocidad y espacio
+desperdiciado.
+
+.. [#dgcbestfit] Las búsquedas de tipo *best-fit* son aquellas donde se busca
+ el *hueco* en el *heap* (es decir, una región contínua de memoria
+ libre) que mejor se ajuste al tamaño del objeto a asignar. Es decir, el
+ *hueco* más pequeño lo suficientemente grande como para almacenarlo.
+
+.. [#dgcfirstfit] Las búsquedas de tipo *first-fit* son aquellas donde se busca
+ el primer *hueco* en el *heap* (es decir, una región contínua de memoria
+ libre) que sea lo suficientemente grande como para almacenar el objeto
+ a asignar.
+
+
+Fase de marcado iterativa
+^^^^^^^^^^^^^^^^^^^^^^^^^
+A diferencia del algoritmo clásico recursivo, el algoritmo del recolector
+actual es iterativo. El algoritmo recursivo tiene un problema fundamental: se
+puede llegar a un desbordamiento de pila (o *stack overflow*). La cantidad de
+recursiones necesarias es, en el peor caso, :math:`O(|Live \thickspace set|)`
+(por ejemplo, si todas las celdas del *heap* formaran una lista simplemente
+enlazada). Hay muchas técnicas para lidiar con este problema, algunas que
+podrían aplicarse a D_ y otras que no (como *pointer reversal*) [JOLI96]_. El
+recolector actual, sin embargo, cambia complejidad en espacio por complejidad
+en tiempo, utilizando un algoritmo iterativo que es constante (:math:`O(1)`)
+en espacio, pero que requiere varias pasada sobre el *heap* en vez de una (la
+cantidad de pasadas es en el peor caso, al igual que la cantidad de
+recursiones del algoritmo recursivo, :math:`O(|Live \thickspace set|)`, pero
+cada pasada se realiza por sobre todo el *heap*).
+
+
+Conjuntos de bits para indicadores
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+El algoritmo clásico propone almacenar en la propia celda la marca (para la
+fase de marcado) y otros indicadores. El algoritmo del recolector actual
+utiliza conjuntos de bits. Esto trae dos ventajas principales:
+
+* Permite minimizar el espacio requerido, ya que de otra forma en general se
+ desperdicia una palabra entera como cabecera de celda para guardar este tipo
+ de información.
+
+* Mejora la localidad de referencia, ya que los indicadores se escriben de
+ forma muy compacta y en una región de memoria contigua que generalmente
+ puede entrar en el cache o en pocas páginas de memoria acelerando
+ 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:
Problemas y limitaciones
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-TODO
+A continuación se presentan los principales problemas encontrados en la
+implementación actual del recolector de basura de D_. Estos problemas surgen
+principalmente de la observación del código y de aproximadamente tres años de
+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
+y desorganización del código. Además se nota que el recolector ha sido escrito
+en una fase muy temprana y que a ido evolucionando a partir de ello de forma
+descuidada y sin ser rescrito nunca para aprovechar las nuevas características
+que el lenguaje fue incorporando (por ejemplo *templates*).
+
+Estos dos problemas (código complicado y falta de documentación) producen un
+efecto de círculo vicioso, porque provocan que sea complejo entender el
+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.
+
+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()``::
+
+ /**
+ * Allocate a chunk of memory that is larger than a page.
+ * Return null if out of memory.
+ */
+ void *bigAlloc(size_t size)
+ {
+ Pool* pool;
+ size_t npages;
+ size_t n;
+ size_t pn;
+ size_t freedpages;
+ void* p;
+ int state;
+
+ npages = (size + PAGESIZE - 1) / PAGESIZE;
+
+ for (state = 0; ; )
+ {
+ // This code could use some refinement when repeatedly
+ // allocating very large arrays.
+
+ for (n = 0; n < npools; n++)
+ {
+ pool = pooltable[n];
+ pn = pool.allocPages(npages);
+ if (pn != OPFAIL)
+ goto L1;
+ }
+
+ // Failed
+ switch (state)
+ {
+ case 0:
+ if (disabled)
+ { state = 1;
+ continue;
+ }
+ // Try collecting
+ freedpages = fullcollectshell();
+ if (freedpages >= npools * ((POOLSIZE / PAGESIZE) / 4))
+ { state = 1;
+ continue;
+ }
+ // Release empty pools to prevent bloat
+ minimize();
+ // Allocate new pool
+ pool = newPool(npages);
+ if (!pool)
+ { state = 2;
+ continue;
+ }
+ pn = pool.allocPages(npages);
+ assert(pn != OPFAIL);
+ goto L1;
+ case 1:
+ // Release empty pools to prevent bloat
+ minimize();
+ // Allocate new pool
+ pool = newPool(npages);
+ if (!pool)
+ goto Lnomemory;
+ pn = pool.allocPages(npages);
+ assert(pn != OPFAIL);
+ goto L1;
+ case 2:
+ goto Lnomemory;
+ default:
+ assert(false);
+ }
+ }
+
+ L1:
+ pool.pagetable[pn] = B_PAGE;
+ if (npages > 1)
+ cstring.memset(&pool.pagetable[pn + 1], B_PAGEPLUS, npages - 1);
+ p = pool.baseAddr + pn * PAGESIZE;
+ cstring.memset(cast(char *)p + size, 0, npages * PAGESIZE - size);
+ debug (MEMSTOMP) cstring.memset(p, 0xF1, size);
+ //debug(PRINTF) printf("\tp = %x\n", p);
+ return p;
+
+ Lnomemory:
+ return null; // let mallocNoSync handle the error
+ }
+
+Se recuerda que la semántica de dicha función es la misma que la de la función
+``new_big()`` presentada en :ref:`dgc_algo_alloc`.
+
+Además, como se comentó en la sección anterior, los algoritmos en la
+implementación real son considerablemente menos modulares que los presentados
+en la sección :ref:`dgc_algo`. Por ejemplo, la función ``fullcollect()`` son
+300 líneas de código.
+
+
+Memoria *encomendada*
+^^^^^^^^^^^^^^^^^^^^^
+Como se comentó en la sección anterior, diferenciar entre memoria
+*encomendada* de memoria *no-encomendada* es complejo y levemente costoso (en
+particular para sistemas operativos que no hacen esta distinción, al menos
+explícitamente, donde no hay ningún beneficio en realizar esta distinción).
+
+Incluso para Microsoft Windows, la ventaja de realizar esta distinción es
+discutible.
+
+
+Precisión
+^^^^^^^^^
+Este fue históricamente uno de los problemas principales del recolector de D_
+[NGD46407]_ [NGD35364]_. Sin embargo, desde que, en la versión 1.001, se ha
+incorporado la capacidad de marcar un bloque como de datos puros (no contiene
+punteros, el atributo ``NO_SCAN``) [NGA6842]_, la gravedad de esos problemas ha
+disminuido considerablemente, aunque siguieron reportándose problemas más
+esporádicamente [NGD54084]_ [NGL13744]_.
+
+De todas maneras queda mucho lugar para mejoras, y es un tema recurrente en el
+grupo de noticias de D_ y se han discutido formas de poder hacer que, al menos
+el *heap* sea preciso [NGD44607]_ [NGD29291]_. Además se mostró un interés
+general por tener un recolector más preciso [NGDN87831]_, pero no han habido
+avances al respecto.
+
+Otra forma de minimizar los efectos de la falta de precisión que se ha
+sugerido reiteradamente en el grupo es teniendo la
+posibilidad de indicar cuando no pueden haber punteros interiores a un bloque
+[NGD89394]_ [NGD71869]_. Esto puede ser de gran utilidad para objetos grandes
+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 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
+ recolector.
+
+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, 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
+[NGD88559]_.
+
+
+Concurrencia
+^^^^^^^^^^^^
+El soporte actual de concurrencia, en todos sus aspectos, es muy primitivo. El
+recolector apenas soporta múltiples *mutators* pero con un nivel de
+sincronización excesivo.
+
+Se ha sugerido en el pasado el uso de *pools* y listas de libres específicos
+de hilos, de manera de disminuir la contención, al menos para la asignación de
+memoria [NGD75952]_ [NGDN87831]_.
+
+Además se ha mostrado un interés por tener un nivel de concurrencia aún mayor
+en el recolector, para aumentar la concurrencia en ambientes *multi-core* en
+general pero en particular para evitar grandes pausas en programas con
+requerimientos de tiempo real, históricamente una de las principales críticas
+al lenguaje [NGDN87831]_ [NGL3937]_ [NGD22968]_ [NGA15246]_ [NGD5622]_
+[NGD2547]_ [NGD18354]_.
+
+
+Finalización
+^^^^^^^^^^^^
+El recolector actual no garantiza la finalización de objetos. En particular
+los objetos no son finalizados (es decir, no se llama a sus destructores)
+si aún alcanzables desde el *root set* cuando el programa termina. Cabe
+destacar que esto puede darse porque hay una referencia real desde el *root
+set* (en cuyo caso queda bajo el control del usuario) pero también, dado que
+el *root set* se visita de forma conservativa, se puede deber a un falso
+positivo, en cuyo caso la omisión de la finalización queda por completo fuera
+del control del usuario (y lo que es aún peor, el usuario no puede ser
+siquiera notificado de esta anomalía).
+
+Si bien la especificación de D_ no requiere esta capacidad (de hecho,
+rigurosamente hablando la especificación de D_ no garantiza la finalización de
+objetos bajo ninguna circunstancia), no hay mayores problemas para implementar
+un recolector que de este tipo de garantías [NGD88298]_.
+
+Además los objetos pueden ser finalizados tanto determinísticamente
+(utilizando ``delete`` o ``scope``; ver secciones :ref:`d_low_level`
+y :ref:`d_dbc`) como no determinísticamente (cuando son finalizados por el
+recolector). En el primer caso se puede, por ejemplo, acceder sus atributos
+u otra memoria que se conozca *viva*, mientras que en el segundo no. Sin
+embargo un destructor no puede hacer uso de esta distinción, haciendo que la
+finalización determinística tenga a fines prácticos las mismas restricciones
+que la finalización no determinística. Es por esto que se ha sugerido permitir
+al destructor distinguir estos dos tipos de finalización [NGD89302]_.
+
+
+Eficiencia
+^^^^^^^^^^
+El rendimiento en general del recolector es una de las críticas frecuentes. Si
+bien hay muchos problemas que han sido resueltos, en especial por la inclusión
+de un mínimo grado de precisión en la versión 1.001, en la actualidad se
+siguen encontrando en el grupo de noticias críticas respecto a esto
+[NGD43991]_ [NGD67673]_ [NGD63541]_ [NGD90977]_.
+
+La principal causa del bajo rendimiento del recolector actual es,
+probablemente, lo simple de su algoritmo principal de recolección. Más allá de
+una organización del *heap* moderadamente apropiada y de utilizar conjuntos de
+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
+mejorarse:
+
+Listas de libres
+ hay 12 listas de libres, como para guardar bloques de tamaño de ``B_16``
+ a ``B_2048``, ``B_PAGE``, ``B_PAGEPLUS``, ``B_UNCOMMITTED`` y ``B_FREE``;
+ sin embargo solo tienen sentido los bloques de tamaño ``B_16``
+ a ``B_2048``, por lo que 4 de esas listas no se utilizan.
+
+Conjuntos de bits para indicadores
+ los indicadores para la fase de marcado y otras propiedades de un bloque
+ son almacenados en conjuntos de bits que almacenan los indicadores de todos
+ los bloques de un *pool*. Si bien se ha mencionado esto como una ventaja,
+ hay lugar todavía como para algunas mejoras. Como un *pool* tiene páginas
+ con distintos tamaños de bloque, se reserva una cantidad de bits igual a la
+ mayor cantidad posible de bloques que puede haber en el *pool*; es decir,
+ se reserva 1 bit por cada 16 bytes del *pool*. Para un *pool* de 1 MiB
+ (tamaño mínimo), teniendo en cuenta que se utilizan 5 conjuntos de bits
+ (``mark``, ``scan``, ``finals``, ``freebits`` y ``noscan``), se utilizan 40
+ KiB de memoria para conjuntos de bits (un 4% de *desperdicio* si, por
+ ejemplo, ese *pool* estuviera destinado por completo a albergar un solo
+ objeto grande; lo que equivaldría al 2560 objetos de 16 bytes
+ desperdiciados en bits inutilizados).
+
+Repetición de código
+ Hay algunos fragmentos de código repetidos innecesariamente. Por ejemplo en
+ varios lugares se utilizan arreglos de tamaño variable que se implementan
+ repetidas veces (en general como un puntero al inicio del arreglo más el
+ tamaño actual del arreglo más el tamaño de la memoria total asignada
+ actualmente). Esto es propenso a errores y difícil de mantener.
+
+Uso de señales
+ el recolector actual utiliza las señales del sistema operativo ``SIGUSR1``
+ y ``SIGUSR2`` para pausar y reanudar los hilos respectivamente. Esto
+ puede traer inconvenientes a usuarios que desean utilizar estas
+ señales en sus programas (o peor aún, si interactúan con bibliotecas
+ de C que hacen uso de estas señales) [NGD5821]_.
+
+Marcado iterativo
+ si bien esto se mencionó como algo bueno del recolector actual, es un
+ compromiso entre tiempo y espacio, y puede ser interesante analizar otros
+ métodos para evitar la recursión que no requieran tantas pasadas sobre el
+ *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:
-Como se ha visto, D_ es un lenguaje de programación muy completo,
-pero aún tiene algunos aspectos inconclusos. Su recolector de basura
-está en un estado de evolución muy temprana. Se trata de un marcado y
-barrido (*mark and sweep*) conservativo que, en ciertas circunstancias,
-no se comporta como es debido, ya que revisa toda la memoria del programa
-en busca de referencias a objetos en el *heap* (en vez de revisar sólo
-las partes que almacenan punteros). Esto produce que, en ciertos casos,
-por ejemplo al almacenar arreglos de número o *strings* en la pila, el
-recolector de basura se encuentre con *falsos positivos*, pensando que
-un área del *heap* está siendo utilizada cuando en realidad el puntero
-que hacía referencia a ésta no era tal. Este efecto puede llevar a la
-pérdida de memoria masiva, llegando al límite de que eventualmente
-el sistema operativo tenga que matar al programa por falta de memoria
-[DNG46407]_. Aún cuando el programa no tenga estos problemas de por sí,
-por usar datos que no pueden ser confundidos con direcciones de memoria,
-este problema podría ser explotado por ataques de seguridad, inyectando
-valores que sí sean punteros válidos y provocando el efecto antes
-mencionado que deriva en la terminación abrupta del programa [DNG35364]_.
-Finalmente, a estos problemas se suman los problemas de *performance*
-[DNG43991]_.
+* 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.
-Es difícil que D_ pueda ser un lenguaje de programación exitoso si
-no provee un recolector de basura eficiente y que realmente evite la
-pérdida masiva de memoria. Por otro lado, D_ podría atraer a una base de
-usuarios mucho más amplia, si la gama de estrategias de recolección es
-más amplia, pudiendo lograr adaptarse a más casos de uso sin llegar al
-límite de tener que caer en el manejo explícito de memoria y perder por
-completo las ventajas de la recolección de basura (con la consecuencia
-ya mencionada de que el manejo de memoria tenga que pasar a ser parte
-de las interfaces y la complejidad que esto agrega al diseño -y uso-
-de una biblioteca).
+* 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;
+ }
-Soluciones Propuestas
+ 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.
-Para poder implementar un recolector de basura no conservativo es
-necesario disponer de un soporte de reflexión (en tiempo de compilación
-[DNG44607]_ y de ejecución [DNG29291]_) bastante completo . De otra forma
-es imposible distinguir si un área de memoria de la pila es utilizada
-como un puntero o como un simple conjunto de datos. D_ provee algún
-grado de reflexión, pero muy limitado como para poder obtener este
-tipo de información. Ya hay un plan para agregar mayores capacidades
-de reflexibilidad [DNG6842]_, y un pequeño avance en este sentido en la
-`versión 1.001`_, pero con algunos problemas [DNG6890]_ [DNG6893]_.
+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.
-.. _`versión 1.001`: http://www.digitalmars.com/d/changelog.html#new1_001
+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.
-Se han propuesto otros métodos e implementaciones de recolector de basura,
-por ejemplo colectores con movimiento (*moving collectors*) [DNG42557]_
-y conteo de referencias [DNG38689]_. Pero D_ es un lenguaje muy particular
-en cuanto a la recolección de basura (al permitir :ref:d_low_level hay
-muchas consideraciones a las que otros lenguajes no deben enfrentarse) y no
-es sencillo pensar en otras implementaciones sin hacer modificaciones de
-base al lenguaje.
+.. [#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.
-Problemas para Implementar Colectores con Movimiento
+A priori, pareciera que la relación cantidad y complejidad de cambios sobre
+beneficios potenciales no fuera muy favorable a esta mejora.
-El principal problema es la capacidad de D_ de manipular punteros y
-otras estructuras de bajo nivel, como uniones. O incluso la capacidad
-de interactuar con C. Al mover un objeto de un área de memoria a otro,
-es necesario actualizar todos los punteros que apuntan a éste. En D_
-esta tarea no es trivial [DNG42564]_
+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.
-Problemas para Implementar Conteo de Referencias
-Este tipo de recolectores reparten la carga de la recolección de forma
-uniforme a lo largo (y a la par) de la ejecución del programa. El
-problema principal para implementar este tipo de recolección es
-la necesidad de soporte en el compilador (cada asignación debe ser
-acompañada por el incremento/decremento de contadores de referencia), a
-menos que se implemente en una biblioteca. Por otro lado, características
-como el rebanado de arreglos (ver :ref:d_high_level) son
-difíciles de proveer con el conteo de referencias, entre otros problemas
-[DNG38704]_.
+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 :
+.. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :
projects / z.facultad / 75.00 / informe.git / blobdiff