+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).
projects / z.facultad / 75.00 / informe.git / blobdiff