Agregar Problemas y limitaciones del recolector actual

[z.facultad/75.00/informe.git] / source / dgc.rst

diff --git a/source/dgc.rst b/source/dgc.rst
index 941a4fd1419451af34d0f530bac3e5f7a73d7f6b..a0b9ce525b8b6a8f195f06210e32760ee914d4f3 100644 (file)
--- a/source/dgc.rst
+++ b/source/dgc.rst
@@ -790,94 +790,713 @@ objetos sean finalizados.
 Detalles de implementación
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 Detalles de implementación
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 

-.. Acá diría por qué hay que reescribirlo para usar lo que está
+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á construído 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 la eficiencia es crítica 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.
+
+
+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.

 
 

-TODO
+   .. aafig::
+      :scale: 1.4
+      :aspect: 0.45

 
 

+                /---  "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 contínua 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*:

 
 

-Problemas y limitaciones
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-
-TODO
+.. 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 comunmente 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.

 
 
 
 

-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]_.
+Algoritmos
+^^^^^^^^^^
+Los algoritmos en la implementación real están considerablemente menos
+modularizados 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.

 
 

-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).
+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**
+
+   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 estas funciones:
+
+   *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``.
+
+   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**
+
+   Recordar que la ``pooltable`` siempre se mantiene ordenada según la
+   dirección de la primera página.
+
+   *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).
+
+**Recolección**
+
+   *mark(pbot, ptop)*:
+      marca un rango de memoria. Este método es análogo al ``mark()``
+      presentado en la sección :ref:`dgc_algo_mark` pero marca un rango
+      completo de memoria, lo que permite que sea considerablemente más
+      eficiente.
+
+   *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 desapilar, 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
+      considerablemente menos modularizada, 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.
+
+
+Memoria *encomendada*
+^^^^^^^^^^^^^^^^^^^^^
+El algoritmo actual divide un *pool* en dos áreas: memoria *encomendada*
+(*committed* en inglés) y *no-encomentada*. 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_problems:

 
 

-Soluciones Propuestas
-
-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]_.
+Problemas y limitaciones
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 
 

-.. _`versión 1.001`: http://www.digitalmars.com/d/changelog.html#new1_001
+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 3 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.
+
+
+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
+desprolija 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 están considerablemente menos modularizados 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 historicamente 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
+disminuído 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 mostro 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 [NGD86840]_ [NGD13301]_ [NGL8264]_
+[NGD69761]_ [NGD74624]_ [NGD88065]_

 
 

-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.
+.. [#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 y 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]_.

 
 

-Problemas para Implementar Colectores con Movimiento

 
 

-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]_
+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, historicamente una de las principales críticas
+al lenguaje [NGDN87831]_ [NGL3937]_ [NGD22968]_ [NGA15246]_ [NGD5622]_
+[NGD2547]_ [NGD18354]_.

 
 

-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]_.
+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 deterministicamente (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 deterministica. Es por esto que se ha sugerido permitir
+al destructor distinguir estos dos tipos de finalización [NGD89302]_.
+
+
+Eficiencia
+^^^^^^^^^^
+La eficiencia 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 de la ineficiencia 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.
+
+
+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:
+  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*. 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 inecesariamente. 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 incovenientes 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]_.

 
 
 .. include:: links.rst
 
 
 .. include:: links.rst