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
.. _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 *aasembly*, 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 la
+eficiencia 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 un objeto no es más referenciados, 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
+destruídos 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_problems:
+.. _dgc_good:
-Problemas y limitaciones
+Características destacadas
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-TODO
-
-
+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:
-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]_.
-
-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).
-
+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 especio (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áscio 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 contígua que generalmente
+ puede entrar en el cache o en pocas páginas de memoria acelerando
+ considerablemente la fase de marcado.
+
+
+
+.. _dgc_bad:
+Problemas y limitaciones
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-Soluciones Propuestas
+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.
-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]_.
-.. _`versión 1.001`: http://www.digitalmars.com/d/changelog.html#new1_001
+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 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 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]_.
+
+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*.
.. include:: links.rst
projects / z.facultad / 75.00 / informe.git / blobdiff