From: Leandro Lucarella Date: Thu, 30 Sep 2010 23:41:04 +0000 (-0300) Subject: Terminar sección de mejoras propuestas X-Git-Tag: entrega-2010-10-08~6 X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/commitdiff_plain/17d0a2cd3cd5bccc6f59bd4dec8717059c0c113d Terminar sección de mejoras propuestas --- diff --git a/source/dgc.rst b/source/dgc.rst index faf4bd6..14d78aa 100644 --- a/source/dgc.rst +++ b/source/dgc.rst @@ -1514,6 +1514,8 @@ participación y observación del grupo de noticias, de donde se obtuvieron los principales problemas percibidos por la comunidad que utiliza el lenguaje. +.. _dgc_bad_code: + Complejidad del código y documentación ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ El análisis del código fue muy complicado debido a la falta de documentación diff --git a/source/glosario.rst b/source/glosario.rst index 9dbfe53..5f2383f 100644 --- a/source/glosario.rst +++ b/source/glosario.rst @@ -509,6 +509,23 @@ Glosario banco de pruebas utilizado para medir y comparar el rendimiento de un programa, algoritmo o proceso en general. + BNF + Notación de Backus-Naur, una meta-sintaxis usada para expresar + gramáticas libres de contexto. + + CSV + Formato simple para almacenar datos en forma de tabla, separados por + comas (de ahí el nombre, en inglés *Comma separated values**) en un + archivo de texto. Cada línea del archivo es interpretada como una fila + de datos relacionados, y cada valor de separado por comas como una + columna. + + POSIX + Familia de estándares de llamadas al sistema operativo definidos por la + IEEE y especificados formalmente en IEEE 1003. El nombre proviene del + acrónimo de *Portable Operating System Interface*, agregando la X final + como representación de *UNIX*, como seña de identidad de la API. + .. include:: links.rst diff --git a/source/referencias.rst b/source/referencias.rst index b4346e0..f7a48db 100644 --- a/source/referencias.rst +++ b/source/referencias.rst @@ -66,6 +66,12 @@ __ http://www-plan.cs.colorado.edu/diwan/cbgc.pdf Dynamic Data Structures on Distributed Memory Machines. Transactions on Programming Languages and Systems, volúmen 17, número 2. Marzo 1995. +.. [CMK01] B. Cahoon and K. S. McKinley. `Data Flow Analysis for Software + Prefetching Linked Data Structures in Java`__. International Conference on + Parallel Architectures and Compilation Techniques (PACT). Barcelona, + España. Septiembre 2001. +__ ftp://ftp.cs.umass.edu/pub/osl/papers/pact01-prefetch.ps.gz + .. [BH86] J. Barnes and P. Hut. A hierarchical o(N log N) force-calculation algorithm. Nature Volumen 324, páginas 446-449. Diciembre 1986. @@ -296,6 +302,15 @@ __ http://www.digitalmars.com/d/archives/digitalmars/D/announce/ANN_WeakObjectRe __ http://www.digitalmars.com/d/archives/digitalmars/D/announce/Blaze_2.0_15246.html +.. Bugzilla +.. ~~~~~~~~ + +.. [DBZ3463] David Simcha, et ál. `Integrate Precise Heap Scanning Into the + GC`__. The D Programming Language Issue Tracking System. Issue 3463. + Noviembre 2009. +__ http://d.puremagic.com/issues/show_bug.cgi?id=3463 + + .. include:: links.rst .. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=en : diff --git a/source/sol-mark-rec-dil.pdf b/source/sol-mark-rec-dil.pdf new file mode 100644 index 0000000..bde07b9 Binary files /dev/null and b/source/sol-mark-rec-dil.pdf differ diff --git a/source/solucion.rst b/source/solucion.rst index b27ffbb..9d82b89 100644 --- a/source/solucion.rst +++ b/source/solucion.rst @@ -550,7 +550,1205 @@ lectura más cercana a la realidad del uso de un recolector. Modificaciones propuestas ---------------------------------------------------------------------------- -TODO +Se decide realizar todas las modificaciones al recolector actual de forma +progresiva e incremental, partiendo como base del recolector de la versión +0.99.9 de Tango_. Las razones que motivan esta decisión son varias; por un +lado es lo más apropiado dados los requerimientos claves mencionados al +principio de este capítulo. Por ejemplo, al hacer cambios incrementales es más +fácil comprobar que la eficiencia no se aleja mucho del actual con cada +modificación y una modificación gradual impone menos resistencia a la +aceptación del nuevo recolector. + +Además la construcción de un recolector de cero es una tarea difícil +considerando que un error en el recolector es extremadamente complejo de +rastrear, dado que en general el error se detecta en el *mutator* y en una +instancia muy posterior al origen real del error. Esto ha sido comprobado de +forma práctica, dado que, a modo de ejercicio para interiorizarse en el +funcionamiento del *runtime* de D_, primero se ha construido desde cero una +implementación de un recolector *naïve*, resultando muy difícil su depuración +por las razones mencionadas. Por el contrario, comenzar con un recolector en +funcionamiento como base hace más sencillo tanto probar cada pequeña +modificación para asegurar que no introduce fallos, como encontrar y reparar +los fallos cuando estos se producen, ya que el código incorrecto introducido +está bien aislado e identificado. + +A continuación se hace un recorrido sobre cada una de las mejoras propuestas, +y en los casos en los que la mejora propone un cambio algorítmico, se analiza +la corrección del algoritmo resultante, partiendo de la base de que el +algoritmo tomado como punto de partida es un marcado y barrido que utiliza la +abstracción tricolor para hacer la fase de marcado de forma iterativa (ver +:ref:`gc_mark_sweep` y :ref:`gc_intro_tricolor`), cuya corrección ya está +probada en la literatura preexistente. + + +.. _sol_config: + +Configurabilidad +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Una de las primeras mejoras propuestas es la posibilidad de configurar el +recolector de forma más sencilla. El requerimiento mínimo es la posibilidad de +configurar el recolector sin necesidad de recompilarlo. La complejidad de esto +surge de que el recolector debe ser transparente para el programa del usuario. + +Configurar el recolector en tiempo de compilación del programa del usuario +probablemente requeriría modificar el compilador, y además, si bien es una +mejora sustancial a la configuración en tiempo de compilación del recolector, +no termina de ser completamente conveniente para realizar pruebas reiteradas +con un mismo programa para encontrar los mejores valores de configuración para +ese programa en particular. + +Por otro lado, permitir configurar el recolector en tiempo de ejecución, una +vez que su estructura interna ya fue definida y creada, puede ser no solo +tedioso y complejo, además ineficiente, por lo tanto esta opción también se +descarta. + +Finalmente, lo que parece ser más apropiado para un recolector, es permitir la +configuración en tiempo de inicialización. Es decir, configurar el recolectar +sin necesidad de recompilar ni el programa del usuario ni el recolector, pero +antes de que el programa del usuario inicie, de manera que una vez iniciado el +recolector con ciertos parámetros, éstos no cambien nunca más en durante la +vida del programa. + +Este esquema provee la mejor relación entre configurabilidad, conveniencia, +eficiencia y simplicidad. Una posibilidad para lograr esto es utilizar +parámetros de línea de comandos, sin embargo no parece ni sencillo (proveer +una forma de leer los parámetros de línea de comandos requiere cambios en el +*runtime*) ni apropiado (el recolector debería ser lo más transparente posible +para el programa del usuario). + +Otra posibilidad es utilizar variables de entorno, que parece ser la opción +más sencilla y apropiada. Sencilla porque las variables de entorno pueden ser +leídas directamente al inicializar el recolector sin necesidad de cooperación +alguna del *runtime*, a través de :manpage:`getenv(3)`. Apropiada porque, si +bien el problema de invasión del programa del usuario también existe, es una +práctica más frecuente y aceptada la configuración de módulos internos +o bibliotecas compartidas a través de variables de entorno. + +Por último, antes de comenzar a usar este esquema de configuración, se +verifica que tomar ciertas decisiones en tiempo de ejecución no impacten en la +eficiencia del recolector. Para esto se convierten algunas opciones que antes +eran solo seleccionables en tiempo de compilación del recolector para que +puedan ser seleccionables en tiempo de inicialización y se comprueba que no +hay una penalización apreciable. + + +.. _sol_config_spec: + +Especificación de opciones +^^^^^^^^^^^^^^^^^^^^^^^^^^ +Para especificar opciones de configuración, hay que hacerlo a través de la +variable de entorno de nombre :envvar:`D_GC_OPTS`. El valor de esa variable es +interpretado de la siguiente manera (en formato similar a :term:`BNF`): + +.. productionlist:: + D_GC_OPTS: `option` ( ':' `option` )* + option: `name` [ '=' `value` ] + name: `namec` `namec`* + value: `valuec`* + namec: `valuec` - '=' + valuec: [0x01-0xFF] - ':' + +Es decir, se compone de una lista de opciones separadas por **:**. Cada opción +se especifica con un nombre, opcionalmente seguido por un valor (separados por +**=**). + +El valor de una opción puede ser un texto arbitrario (exceptuando los +caracteres ``'\0'`` y ``':'`` y de longitud máxima 255), pero cada opción lo +interpreta de forma particular. Como caso general, hay opciones booleanas, que +toman como valor verdadero un cualquier número distinto de 0 (o si el valor es +vació, es decir, solo se indica el nombre de la opción), y como valor falso +cualquier otro texto. + +A continuación se listan las opciones reconocidas por el recolector (indicando +el formato del valor de la opción de tener uno especial): + +``mem_stomp`` + Esta es una opción (booleana) disponible en el recolector original, pero + que se cambia para que sea configurable en tiempo de inicialización + (estando desactivada por omisión). Activa la opción ``MEMSTOMP`` descripta + en :ref:`dgc_debug`. + +``sentinel`` + Esta opción es también booleana (desactivada por omisión), está disponible + en el recolector original, y se la cambia para sea configurable en tiempo + de inicialización. Activa la opción ``SENTINEL`` descripta en + :ref:`dgc_debug`. + +``pre_alloc`` + Esta opción permite crear una cierta cantidad de *pools* de un tamaño + determinado previo a que inicie el programa. Si se especifica solo un + número, se crea un *pool* con ese tamaño en MiB. Si, en cambio, se + especifica una cadena del tipo ``3x1``, el primer número indica la cantidad + de *pools* y el segundo el tamaño en MiB de cada uno (3 *pools* de 1MiB en + este caso). Ver :ref:`sol_pre_alloc` para más detalles sobre la utilidad de + esta opción. + +``min_free`` + El valor de esta opción indica el porcentaje mínimo porcentaje del *heap* + que debe quedar libre luego de una recolección. Siendo un porcentaje, solo + se aceptan valores entre 0 y 100, siendo su valor por omisión 5. Ver + :ref:`sol_ocup` para más detalles sobre su propósito. + +``malloc_stats_file`` + Esta opción sirve para especificar un archivo en el cual escribir un + reporte de todas la operaciones de pedido de memoria realizadas por el + programa (durante su tiempo de vida). Ver :ref:`sol_stats` para más + detalles sobre la información provista y el formato del reporte. + +``collect_stats_file`` + Esta opción sirve para especificar un archivo en el cual escribir un + reporte de todas las recolecciones hechas durante el tiempo de vida del + programa. Ver :ref:`sol_stats` para más detalles sobre la información + provista y el formato del reporte. + +``conservative`` + Esta opción booleana permite desactivar el escaneo preciso del *heap*, + forzando al recolector a ser completamente conservativo (excepto por los + bloques con el atributo ``NO_SCAN`` que siguen sin ser escaneados). Ver + :ref:`sol_precise` para más detalles sobre la existencia de esta opción. + +``fork`` + Esta opción booleana (activada por omisión) permite seleccionar si el + recolector debe correr la fase de marcado en paralelo o no (es decir, si el + recolector corre de forma concurrente con el *mutator*). Para más detalles + ver :ref:`sol_fork`. + +``eager_alloc`` + Esta opción booleana (activada por omisión), sólo puede estar activa si + ``fork`` también está activa y sirve para indicar al recolector que reserve + un nuevo *pool* de memoria cuando una petición no puede ser satisfecha, + justo antes de lanzar la recolección concurrente. Ver + :ref:`sol_eager_alloc` para más detalles sobre el propósito de esta opción. + +``early_collect`` + Esta opción booleana (desactivada por omisión), también sólo puede estar + activa si ``fork`` está activa y sirve para indicar al recolector que lance + una recolección (concurrente) antes de que la memoria libre se termine (la + recolección temprana será disparada cuando el porcentaje de memoria libre + sea menor a ``min_free``). Ver :ref:`sol_early_collect` para más detalles + sobre el propósito de esta opción. + +Cualquier opción o valor no reconocido es ignorado por el recolector. Se +utilizan los valores por omisión de las opciones que no fueron especificadas, +o cuyos valores no pudieron ser interpretados correctamente. + +Para cambiar la configuración del recolector se puede invocar el programa de +la siguiente manera (usando un intérprete de comandos del tipo *bourne +shell*): + +.. code-block:: none + + D_GC_OPTS=conservative:eager_alloc=0:early_collect=1:pre_alloc=2x5 ./programa + +En este ejemplo, se activan las opciones ``conservative`` y ``early_collect``, +se desactiva ``eager_alloc`` y se crean 2 *pools* de 5MiB cada uno al +inicializar el recolector. + + +Reestructuración y cambios menores +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Si bien se decide no comenzar una implementación desde cero, se ha mostrado +(ver :ref:`dgc_bad_code`) que la implementación actual es lo suficientemente +desprolija como para complicar su modificación. Es por esto que se hacen +algunas reestructuraciones básicas del código, reescribiendo o saneando de +forma incremental todas aquellas partes que complican su evolución. + +Además de las modificaciones puramente estéticas (aunque no por eso menos +valuables, ya que la legibilidad y simplicidad del código son un factor +fundamental a la hora de ser mantenido o extendido), se hacen otras pequeñas +mejoras, que se detallan a continuación. + +Remoción de memoria encomendada +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Si bien a nivel de eficiencia este cambio no tuvo impacto alguno (cuando en un +principio se especuló con que podría dar alguna ganancia en este sentido), se +elimina el concepto de memoria *encomendada* para quitar complejidad al +código. + +Esta mejora no afecta a la corrección del algoritmo, ya que a nivel lógico el +recolector solo ve la memoria *encomendada*. + +Micro-optimizaciones +^^^^^^^^^^^^^^^^^^^^ +Si bien se realizan varias micro-optimizaciones, probablemente la más +relevante es la inclusión de un caché de tamaño de bloque para el método +``findSize()`` de un *pool*. Esto acelera considerablemente las operaciones +que necesitan pedir el tamaño de un bloque reiteradamente, por ejemplo, al +añadir nuevos elementos a un arreglo dinámico. + +Esta mejora tampoco afecta a la corrección del algoritmo, ya que nuevamente no +afecta su comportamiento a nivel lógico, solo cambia detalles en la +implementación de forma transparentes para el algoritmo de recolección. + +Optimizaciones sobre ``findPool()`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Al analizar los principales cuellos de botella del recolector, es notoria la +cantidad de tiempo que pasa ejecutando la función ``findPool()``, que dado un +puntero devuelve el *pool* de memoria al cual pertenece. Es por esto que se +minimiza el uso de esta función. Además, dado que los *pools* de memoria están +ordenados por el puntero de comienzo del bloque de memoria manejado por el +*pool*, se cambia la búsqueda (originalmente lineal) por una búsqueda binaria. +Finalmente, dado que la lista de libre está construida almacenando el puntero +al siguiente en las mismas celdas que componen la lista, se almacena también +el puntero al *pool* al que dicha celda pertenece (dado que la celda más +pequeña es de 16 bytes, podemos garantizar que caben dos punteros, incluso +para arquitecturas de 64 bits). De esta manera no es necesario usar +``findPool()`` al quitar una celda de la lista de libres. + +Una vez más, la mejora no afecta la corrección del código. + +.. _sol_pre_alloc: + +Pre-asignación de memoria +^^^^^^^^^^^^^^^^^^^^^^^^^ +Esta opción permite crear una cierta cantidad de *pools* de un tamaño +determinado previo a que inicie el programa. Normalmente el recolector no +reserva memoria hasta que el programa lo pida. Esto puede llegar a evitar +que un programa haga muchas recolecciones al comenzar, hasta que haya +cargado su conjunto de datos de trabajo. + +Se han analizado varios valores por omisión pero ninguno es consistentemente +mejor que comenzar sin memoria asignada, por lo tanto no se cambia el +comportamiento original, pero se agrega una opción (ver ``pre_alloc`` en +:ref:`sol_config_spec`) para que el usuario pueda experimentar con cada +programa en particular si esta opción es beneficiosa. + +Esta opción tampoco cambia la corrección del algoritmo de recolección, solo +sus condiciones iniciales. + +.. _sol_ocup: + +Mejora del factor de ocupación del *heap* +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +El factor de ocupación del *heap* debe ser apropiado por dos razones. Por un +lado, si el *heap* está demasiado ocupado todo el tiempo, serán necesarias +muchas recolecciones que, aunque pequeñas dado que la memoria utilizada es +poca, puede llegar a ser extremadamente ineficiente en casos patológicos (ver +:ref:`dgc_bad_ocup`). Por otro lado, si el tamaño del *heap* es extremadamente +grande (en comparación con el tamaño real del grupo de trabajo del programa), +se harán pocas recolecciones pero cada una es muy costosa, porque el algoritmo +de marcado y barrido es :math:`O(\lvert Heap \rvert)` (ver +:ref:`gc_mark_sweep`). Además la afinidad del caché va a ser extremadamente +pobre. + +Para mantener el factor de ocupación dentro de límites razonables, se agrega +la opción ``min_free`` (ver :ref:`sol_config_spec`). Esta opción indica el +recolector cual debe ser el porcentaje mínimo del *heap* que debe quedar libre +luego de una recolección. En caso de no cumplirse, se pide más memoria al +sistema operativo para cumplir este requerimiento. Además, luego de cada +recolección se verifica que el tamaño del *heap* no sea mayor a ``min_free``, +para evitar que el *heap* crezca de forma descontrolada. Si es mayor +a ``min_free`` se intenta minimizar el uso de memoria liberando *pools* que +estén completamente desocupados, mientras que el factor de ocupación siga +siendo mayor a ``min_free``. Si liberar un *pool* implica pasar ese límite, no +se libera y se pasa a analizar el siguiente y así sucesivamente. + +Esta modificación no afecta a la corrección del algoritmo, ya que no lo afecta +directamente. + +Modificaciones descartadas +^^^^^^^^^^^^^^^^^^^^^^^^^^ +Se realizan varias otras modificaciones, con la esperanza de mejorar la +eficiencia del recolector, pero que, al contrario de lo esperado, empeoran la +eficiencia o la mejoran de forma muy marginal en comparación con la +complejidad agregada. + +Probablemente el caso más significativo, y por tanto el único que vale la pena +mencionar, es la conversión de marcado iterativo a marcado recursivo y luego +a un esquema híbrido. Como se describe en :ref:`dgc_bad`, el marcado iterativo +tiene sus ventajas, pero tiene desventajas también. Al convertirlo a puramente +recursivo, se impracticable por resultar en errores de desbordamiento de pila. + +Por lo tanto se prueba con un esquema híbrido, poniendo un límite a la +recursividad, volviendo al algoritmo iterativo cuando se alcanza este límite. + +La implementación del algoritmo híbrido consiste en los siguientes cambios +sobre el algoritmo original (ver :ref:`dgc_algo_mark`):: + + function mark_phase() is + global more_to_scan = false + global depth = 0 // Agregado + 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() + + function mark_range(begin, end) is + pointer = begin + global depth++ // Agregado + 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 + if (global depth > MAX_DEPTH) // + more_to_scan = true // + else // Agregado + foreach ptr in block.words // + mark(ptr) // + global depth-- // + +Al analizar los resultados de de esta modificación, se observa una mejoría muy +level, para valores de ``MAX_DEPTH`` mayores a cero (en algunos casos bastante +mayores) y en general para ``MAX_DEPTH`` cero (es decir, usando el algoritmo +de forma completamente iterativa) los resultados son peores, dado que se paga +el trabajo extra sin ganancia alguna. En la figura :vref:`fig:sol-mark-rec` se +puede ver, por ejemplo, el tiempo total de ejecución de Dil_ al generar la +documentación completa del código de Tango_, según varía el valor de +``MAX_DEPTH``. + +.. fig:: fig:sol-mark-rec + + Análisis de tiempo total de ejecución en función del valor de + ``MAX_DEPTH``. + + Tiempo total de ejecución de Dil_ al generar la documentación completa del + código de Tango_ en función del valor de ``MAX_DEPTH``. El rombo no + pertenece a ningún nivel de recursividad, representa el tiempo de ejecución + del algoritmo original (puramente iterativo). + + .. image:: sol-mark-rec-dil.pdf + + +Dado que aumentar el nivel máximo de recursividad significa un uso mayor del +*stack*, y que esto puede impactar en el usuario (si el usuario tuviera un +programa que esté al borde de consumir todo el *stack*, el recolector podría +hacer fallar al programa de una forma inesperada para el usuario, problema que +sería muy difícil de depurar para éste), y que los resultados obtenidos no son +rotundamente superiores a los resultados sin esta modificación, se opta por no +incluir este cambio. Tampoco vale la pena incluirlo como una opción con valor +por omisión 0 porque, como se ha dicho, para este caso el resultado es incluso +peor que sin la modificación. + +Esta modificación mantiene la corrección del recolector dado que tampoco +modifica el algoritmo sino su implementación. Además ambos casos extremos son +correctos (si ``MAX_DEPTH`` es 0, el algoritmo es puramente iterativo y si +pudiera ser infinito resultaría en el algoritmo puramente recursivo). + + +.. _sol_stats: + +Recolección de estadísticas +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Un requerimiento importante, tanto para evaluar los resultados de este trabajo +como para analizar el comportamiento de los programas estudiados, es la +recolección de estadísticas. Hay muchos aspectos que pueden ser analizados +a la hora de evaluar un recolector, y es por esto que se busca que la +recolección de datos sea lo más completa posible. + +Con este objetivo, se decide recolectar datos sobre lo que, probablemente, +sean las operaciones más importantes del recolector: asignación de memoria +y recolección. + +Todos los datos recolectados son almacenados en archivos que se especifican +a través de opciones del recolector (ver :ref:`sol_config_spec`). Los archivos +especificados debe poder ser escritos (y creados de ser necesario) por el +recolector (de otra forma se ignora la opción). El conjunto de datos +recolectados son almacenados en formato :term:`CSV` en el archivo, comenzando +con una cabecera que indica el significado de cada columna. + +Los datos recolectados tienen en general 4 tipos de valores diferentes: + +Tiempo + Se guarda en segundos como número de punto flotante (por ejemplo ``0.12``). + +Puntero + Se guarda en forma hexadecimal (por ejemplo ``0xa1b2c3d4``). + +Tamaño + Se guarda como un número decimal, expresado en bytes (por ejemplo ``32``). + +Indicador + Se guarda como el número ``0`` si es falso o ``1`` si es verdadero. + +Esta modificación mantiene la corrección del recolector dado que no hay cambio +algorítmico alguno. + +Asignación de memoria +^^^^^^^^^^^^^^^^^^^^^ +La recolección de datos sobre asignación de memoria se activa asignando un +nombre de archivo a la opción ``malloc_stats_file``. Por cada asignación de +memoria pedida por el programa (es decir, por cada llamada a la función +``gc_malloc()``) se guarda una fila con los siguientes datos: + +1. Cantidad de segundos que pasaron desde que empezó el programa (*timestamp*). +2. Tiempo total que tomó la asignación de memoria. +3. Valor del puntero devuelto por la asignación. +4. Tamaño de la memoria pedida por el programa. +5. Si esta petición de memoria disparó una recolección o no. +6. Si debe ejecutarse un *finalizador* sobre el objeto (almacenado en la + memoria pedida) cuando ésta no sea más alcanzable (cuando sea barrido). +7. Si objeto carece de punteros (es decir, no debe ser escaneada). +8. Si objeto no debe ser movido por el recolector. +9. Puntero a la información sobre la ubicación de los punteros del objeto. +10. Tamaño del tipo del objeto. +11. Primera palabra con los bits que indican que palabras del tipo deben ser + escaneados punteros y cuales no (en hexadecimal). +12. Primera palabra con los bits que indican que palabras del tipo son + punteros garantizados (en hexadecimal). + +Como puede apreciarse, la mayor parte de esta información sirve más para +analizar el programa que el recolector. Probablemente solo el punto 2 sea de +interés para analizar como se comporta el recolector. + +El punto 8 es completamente inútil, ya que el compilador nunca provee esta +información, pero se la deja por si en algún momento comienza a hacerlo. Los +puntos 9 a 12 provee información sobre el tipo del objeto almacenado, útil +para un marcado preciso (ver :ref:`sol_precise`). + +El punto 6 indica, indirectamente, cuales de los objetos asignados son +*pesados*, ya que éstos son los únicos que pueden tener un *finalizador*. +Además, a través de los puntos 4 y 10 es posible inferir si lo que va +almacenarse es un objeto solo o un arreglo de objetos. + +Recolección de basura +^^^^^^^^^^^^^^^^^^^^^ +Los datos sobre las recolecciones realizadas se guardan al asignar un nombre +de archivo a la opción ``collect_stats_file``. Cada vez que se dispara una +recolección [#solcollect]_ (es decir, cada vez que se llama a la función +``fullcollect()``) se guarda una fila con los siguientes datos: + +1. Cantidad de segundos que pasaron desde que empezó el programa (*timestamp*). +2. Tiempo total que tomó la asignación de memoria que disparó la recolección. +3. Tiempo total que tomó la recolección. +4. Tiempo total que deben pausarse todos los hilos (tiempo de + *stop-the-world*). +5. Cantidad de memoria usada antes de la recolección. +6. Cantidad de memoria libre antes de la recolección. +7. Cantidad de memoria desperdiciada antes de la recolección. +8. Cantidad de memoria utilizada por el mismo recolector antes de la + recolección (para sus estructuras internas). +9. Cantidad de memoria usada después de la recolección. +10. Cantidad de memoria libre después de la recolección. +11. Cantidad de memoria desperdiciada [#solwaste]_ después de la recolección. +12. Cantidad de memoria utilizada por el mismo recolector después de la + recolección. + +Si bien el punto 4 parece ser el más importante para un programa que necesita +baja latencia, dado el *lock* global del recolector, el punto 2 es +probablemente el valor más significativo en este aspecto, dado que, a menos +que el programa en cuestión utilice muy poco el recolector en distintos hilos, +los hilos se verán pausados de todas formas cuando necesiten utilizar el +recolector. + +.. [#solcollect] Esto es en el sentido más amplio posible. Por ejemplo, cuando + se utiliza marcado concurrente (ver :ref:`sol_fork`), se guarda esta + información incluso si ya hay una recolección activa, pero el tiempo de + pausa de los hilos será -1 para indicar que en realidad nunca fueron + pausados. + +.. [#solwaste] Memoria *desperdiciada* se refiere a memoria que directamente + no puede utilizarse debido a la fragmentación. Si por ejemplo, se piden 65 + bytes de memoria, dada la organización del *heap* en bloques (ver + :ref:`dgc_org`), el recolector asignará un bloque de 128 bytes, por lo + tanto 63 bytes quedarán desperdiciados. + + +.. _sol_precise: + +Marcado preciso +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +En paralelo con este trabajo, David Simcha comienza a explorar 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. + +Luego 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_, al igual que este trabajo. Dado el objetivo y entorno común, se abre +la posibilidad de adaptar los cambios de Vincent Lang a este trabajo, +utilizando una versión modificada de DMD_ (dado que los cambios aún no son +integrados al compilador oficial). + +Información de tipos provista por el compilador +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Con éstas modificaciones, el compilador en cada asignación le pasa al +recolector información sobre los punteros del tipo para el cual se pide la +memoria. Esta información se pasa como un puntero a un arreglo de palabras con +la estructura mostrada en la figura :vref:`fig:sol-ptrmap` y que se describe +a continuación. + +.. fig:: fig:sol-ptrmap + + Estructura de la información de tipos provista por el compilador. + + .. aafig:: + :scale: 110 + + /----- ptrmap + | + V + +-------------+----------------------------+----------------------------+ + | "Tamaño en" | "Bits indicando si la" | "Bits indicando si" | + | "cantidad" | "palabra en una posición" | "la palabra en una" | + | "de" | "debe escanearse como" | "posición es" | + | "palabras" | "si fuera un puntero" | "un puntero" | + +-------------+----------------------------+----------------------------+ + + | | | | + +----- 1 -----+------- ceil(N/BPW) --------+------- ceil(N/BPW) --------+ + | | | | + +* La primera palabra indica el tamaño, en **cantidad de palabras**, del tipo + para el cual se pide la memoria (:math:`N`). +* Las siguientes :math:`ceil(\frac{N}{BPW})` palabras indican, + como un conjunto de bits, qué palabras deben ser escaneadas por el + recolector como si fueran punteros (donde :math:`BPW` indica la cantidad de + bits por palabra, por ejemplo 32 para x86). +* Las siguientes :math:`ceil(\frac{N}{BPW})` palabras son otro conjunto de + bits indicando qué palabras son realmente punteros. + +Los conjuntos de bits guardan la información sobre la primera palabra en el +bit menos significativo. Dada la complejidad de la representación, se ilustra +con un ejemplo. Dada la estructura:: + + union U { + ubyte ub; + void* ptr; + } + + struct S + { + void* begin1; // 1 word + byte[size_t.sizeof * 14 + 1] bytes; // 15 words + // el compilador agrega bytes de "padding" para alinear + void* middle; // 1 word + size_t[14] ints; // 14 words + void* end1; // 1 words + // hasta acá se almacenan los bits en la primera palabra + void* begin2; // 1 words + int i; // 1 word + U u; // 1 word + S* s; // 1 word + } + +El compilador genera la estructura que se muestra en la figura +:vref:`fig:sol-ptrmap-example` (asumiendo una arquitectura de 32 bits). Como +puede apreciarse, el miembro ``u``, al ser una unión entre un puntero y un +dato común, el compilador no puede asegurar que lo que se guarda en esa +palabra sea realmente un puntero, pero indica que debe ser escaneado. El +recolector debe debe ser conservativo en este caso, y escanear esa palabra +como si fuera un puntero. + +.. fig:: fig:sol-ptrmap-example + + Ejemplo de estructura de información de tipos generada para el tipo ``S``. + + .. aafig:: + :textual: + :aspect: 55 + :scale: 110 + + /---- "bit de 'end1'" + | + | /---- "bit de 'middle'" + | | + | "bits de" | "bits de" /---- "bit de 'begin1'" + | "'ints'" | "'bytes'" | + |/------------\|/-------------\| + V| |V| |V + +----------------------------------+ + | 00000000000000000000000000100100 | "Tamaño en cantidad de palabras (36)" + +==================================+ --\ + | 10000000000000010000000000000001 | | "Bits que indican si hay que" + +----------------------------------+ | "escanear una palabra según" + | 00000000000000000000000000001101 | | "su posición" + +==================================+ --+ + | 10000000000000010000000000000001 | | "Bits que indican si hay un" + +----------------------------------+ | "puntero en la palabra según" + | 00000000000000000000000000001001 | | "su posición" + +----------------------------------+ --/ + | |AAAA + \--------------------------/|||| + "bits de relleno" |||| + |||| + "bit de 's'" |||| + | |||| + \---------------/||\---- "bit de 'begin2'" + || + /---------------/\---- "bit de 'i'" + | + "bit de 'u'" + +Si una implementación quisiera mover memoria (ver :ref:`gc_moving`), debería +mantener inmóvil a cualquier objeto que sea apuntado por una palabra de estas +características, ya que no es seguro actualizar la palabra con la nueva +posición el objeto movido. Es por esta razón que se provee desglosada la +información sobre lo que hay que escanear, y lo que es realmente un puntero +(que puede ser actualizado de forma segura por el recolector de ser +necesario). + +Implementación en el recolector +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +La implementación está basada en la idea original de David Simcha, pero +partiendo de la implementación de Vincent Lang (que está basada en Tango_) +y consiste en almacenar el puntero a la estructura con la descripción del tipo +generada por el compilador al final del bloque de datos. Este puntero solo se +almacena si el bloque solicitado no tiene el atributo ``NO_SCAN``, dado que en +ese caso no hace falta directamente escanear ninguna palabra del bloque. + +En la figura :vref:`fig:sol-ptrmap-blk` se puede ver, como continuación del +ejemplo anterior, como se almacenaría en memoria un objeto del tipo ``S``. + +.. fig:: fig:sol-ptrmap-blk + + Ejemplo de bloque que almacena un objeto de tipo ``S`` con información de + tipo. + + .. aafig:: + :scale: 110 + + | | + +------------------------ 256 bytes -----------------------------+ + | | + + +----------------------------------+-----------------------+-----+ + | | | | + | Objeto | Desperdicio | Ptr | + | | | | + +----------------------------------+-----------------------+-----+ + + | | | | + +------------ 144 bytes -----------+------ 108 bytes ------+- 4 -+ + | | | | + +Un problema evidente de este esquema es que si el tamaño de un objeto se +aproxima mucho al tamaño de bloque (difiere en menos de una palabra), el +objeto ocupará el doble de memoria. + +El algoritmo de marcado se cambia de la siguiente forma:: + + // Agregado + global conservative_scan = [1, 1, 0] + + // Agregado + function must_scan_word(pos, bits) is + return bits[pos / BITS_PER_WORD] & (1 << (pos % BITS_PER_WORD)) + + function mark_range(begin, end, ptrmap) is // Modificado + number_of_words_in_type = ptrmap[0] // Agregado + size_t* scan_bits = ptrmap + 1 // Agregado + pointer = begin + while pointer < end + foreach word_pos in 0..number_of_words_in_type // + if not must_scan_word(n, scan_bits) // Agregado + continue // + [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 += number_of_words_in_type // Modificado + + 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 // obj grande // + begin = cast(byte*) page // + end = find_big_object_end(pool, page) // + else // objeto pequeño // + begin = block.begin // + end = block.end // Modificado + ptrmap = global conservative_scan // + if NO_SCAN not in block.attrs // + end -= size_t.sizeof // + ptrmap = cast(size_t*) *end // + mark_range(begin, end, ptrmap) // + + function mark_static_data() is + mark_range(static_data.begin, static_data.end, + global conservative_scan) // Agregado + + function mark_stacks() is + foreach thread in threads + mark_range(thread.stack.begin, thread.stack.end, + global conservative_scan) // Agregado + + function mark_user_roots() is + foreach root_range in user_roots + mark_range(root_range.begin, root_range.end, + global conservative_scan) // Agregado + +Las funciones de asignación de memoria se modifican de forma similar, para +guardar el puntero a la información de tipos. Esta implementación utiliza solo +la información sobre que palabras hay que tratar como punteros (deben ser +escaneadas); la información sobre qué palabras son efectivamente punteros no +se utiliza ya que no se mueven celdas. + +El algoritmo sigue siendo correcto, puesto que solamente se dejan de escanear +palabras que el compilador sabe que no pueden ser punteros. Si bien el +lenguaje permite almacenar punteros en una variable que no lo sea, esto es +comportamiento indefinido por lo tanto un programa que lo hace no es +considerado correcto, por lo cual el recolector tampoco debe ser correcto en +esas circunstancias. + +Cabe destacar que la información de tipos solo se provee para objetos +almacenados en el *heap*, el área de memoria estática, registros del +procesador y la pila de todos los hilos siguen siendo escaneados de forma +completamente conservativa. Se puede forzar el escaneo puramente conservativo +utilizando la opción ``conservative`` (ver :ref:`sol_config_spec`). + + +.. _sol_fork: + +Marcado concurrente +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Finalmente se procede al objetivo primario de este trabajo, hacer que la fase +más costosa del recolector (el marcado) pueda correr de manera concurrente con +el *mutator*, con el objeto principal de disminuir el tiempo de pausa. + +Cabe aclarar, una vez más, que si bien los recolectores concurrentes buscan +disminuir solo el tiempo de *stop-the-world*, en este caso es también +fundamental disminuir el tiempo máximo que está tomado el *lock* global, dado +que ese tiempo puede convertirse en una pausa para todos los threads que +requieran servicios del recolector. + +Se decide basar la implementación en el *paper* "Non-intrusive Cloning Garbage +Collector with Stock Operating System Support" [RODR97]_ por las siguientes +razones principales: + +* Su implementación encaja de forma bastante natural con el diseño del + recolector actual, por lo que requiere pocos cambios, lo que hace más + factible su aceptación. +* Está basado en la llamada al sistema :manpage:`fork(2)`, que no solo está + muy bien soportada (y de manera muy eficiente) en Linux_, debe estar + soportada en cualquier sistema operativo :term:`POSIX`. +* No necesita instrumentar el código incluyendo barreras de memoria para + informar al recolector cuando cambia el grafo de conectividad. Este es un + aspecto fundamental, dada la filosofía de D_ de no pagar el precio de cosas + que no se usan. La penalización en la eficiencia solo se paga cuando corre + el recolector. Este aspecto también es crítico a la hora de evaluar la + aceptación de la solución por parte de la comunidad. +* Dada su sencillez general, no es difícil ofrecer el algoritmo concurrente + como una opción, de manera que el usuario pueda optar por usarlo o no. + +Llamada al sistema *fork* +^^^^^^^^^^^^^^^^^^^^^^^^^ +El término *fork* proviene del inglés y significa *tenedor* de manera textual, +pero se lo utiliza como analogía de una bifurcación. La operación crea una +copia (llamada *hijo*) del proceso que la ejecuta (llamado *padre*). + +El punto más importante es que se crea un espacio de direcciones de memoria +separado para el proceso hijo y una copia exacta de todos los segmentos de +memoria del proceso padre. Es por esto que cualquier modificación que se haga +en el proceso padre, no se refleja en el proceso hijo (y viceversa), a menos +que la memoria sea compartida entre los procesos de forma explícita. + +Esto, sin embargo, no significa que la memoria física sea realmente duplicada; +en general todos los sistemas operativos modernos (como Linux_) utilizan una +técnica llamada *copy-on-write* (*copiar-al-escribir* en castellano) que +retrasa la copia de memoria hasta que alguno de los dos procesos escribe en un +segmento. Recién en ese momento el sistema operativo realiza la copia de **ese +segmento solamente**. Es por esto que la operación puede ser muy eficiente, +y la copia de memoria es proporcional a la cantidad de cambios que hayan. + +:manpage:`fork(2)` tiene otra propiedad importante de mencionar: detiene todos +los hilos de ejecución en el proceso hijo. Es decir, el proceso hijo se crear +con un solo hilo (el hilo que ejecutó la operación de :manpage:`fork(2)`). + +Algoritmo +^^^^^^^^^ +Lo que propone el algoritmo es muy sencillo, utilizar la llamada al sistema +:manpage:`fork(2)` para crear una *fotografía* de la memoria del proceso en un +nuevo proceso. En el proceso padre sigue corriendo el *mutator* y en el +proceso hijo se corre la fase de marcado. El *mutator* puede modificar el +grafo de conectividad pero los cambios quedan aislados el hijo (el marcado), +que tiene una visión consistente e inmutable de la memoria. El sistema +operativo duplica las páginas que modifica el padre bajo demanda, por lo tanto +la cantidad de memoria física realmente copiada es proporcional a la cantidad +y dispersión de los cambios que haga el *mutator*. + +La corrección del algoritmo se mantiene gracias a que la siguiente invariante +se preserva: + + Cuando una celda se convierte en basura, permanece como basura hasta ser + reciclada por el recolector. + +Es decir, el *mutator* no puede *resucitar* una celda *muerta* y esta +invariante se mantiene al correr la fase de marcado sobre una vista inmutable +de la memoria. El único efecto introducido es que el algoritmo toma una +aproximación más conservativa. Es decir, lo que sí puede pasar es que una +celda que pasó a estar *muerta* una vez que la fase de marcado se inició, pero +antes de que ésta termine, la celda no se reciclará hasta la próxima +recolección, dado que este algoritmo no incluye una comunicación entre +*mutator* y recolector para notificar cambios en el grafo de conectividad. +Pero esto no afecta la corrección del algoritmo, ya que un recolector es +correcto cuando nunca recicla celdas *vivas*. + +La única comunicación necesaria entre el *mutator* y el recolector son los +bits de marcado (ver :ref:`dgc_impl`), dado que la fase de barrido debe correr +en el proceso padre. No es necesaria ningún tipo de sincronización entre +*mutator* y recolector más allá de que uno espera a que el otro finalice. + +Además de almacenar el conjunto de bits ``mark`` en memoria compartida entre +el proceso padre e hijo (necesario para la fase de barrido), las +modificaciones necesarias para hacer la fase de marcado concurrente son las +siguientes [#solforkerr]_:: + + function collect() is + stop_the_world() + child_pid = fork() + fflush(null) // evita que se duplique la salida de los FILE* abiertos + if child_pid is 0 // proceso hijo + mark_phase() + exit(0) // termina el proceso hijo + // proceso padre + start_the_world() + wait(child_pid) + sweep() + + function mark_phase() is + global more_to_scan = false + // Borrado: 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() + // Borrado: start_the_world() + +Como se puede observar, el cambio es extremadamente sencillo. Sigue siendo +necesario un tiempo mínimo de pausa (básicamente el tiempo que tarda la +llamada al sistema operativo :manpage:`fork(2)`) para guardar una vista +consistente de los registros del CPU y *stacks* de los hilos. Si bien el +conjunto de bits ``mark`` es compartido por el proceso padre e hijo dado que +es necesario para *comunicar* las fases de marcado y barrido, cabe notar que +nunca son utilizados de forma concurrente (la fase de barrido espera que la +fase de marcado termine antes de usar dichos bits), por lo tanto no necesitan +ningún tipo de sincronización y nunca habrá más de una recolección en proceso +debido al *lock* global del recolector. + +A pesar de que con estos cambios el recolector técnicamente corre de forma +concurrente, se puede apreciar que para un programa con un solo hilo el +tiempo máximo de pausa seguirá siendo muy grande, incluso más grande que antes +dado el trabajo extra que impone crear un nuevo proceso y duplicar las páginas +de memoria modificadas. Lo mismo le pasará a cualquier hilo que necesite hacer +uso del recolector mientras hay una recolección en proceso, debido al *lock* +global. + +Para bajar este tiempo de pausa se experimenta con dos nuevas mejoras, que se +describen a continuación, cuyo objetivo es correr la fase de marcado de forma +concurrente a **todos** los hilos, incluyendo el hilo que la disparó. + +.. [#solforkerr] Se omite el manejo de errores y la activación/desactivación + del marcado concurrente a través de opciones del recolector para facilitar + la comprensión del algoritmo y los cambios realizados. Si devuelve con + error la llamada a ``fork()`` o ``waitpid()``, se vuelve al esquema + *stop-the-world* como si se hubiera desactivado el marcado concurrente + utilizando la opción del recolector ``fork=0``. + + +.. _sol_eager_alloc: + +Creación ansiosa de *pools* +^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Esta mejora, que puede ser controlada a través de la opción ``eager_alloc`` +(ver :ref:`sol_config_spec`), consiste en crear un nuevo *pool* cuando un +pedido de memoria no puede ser satisfecho, justo después de lanzar la +recolección. Esto permite al recolector satisfacer la petición de memoria +inmediatamente, corriendo la fase de marcado de forma realmente concurrente, +incluso para programas con un solo hilo o programas cuyos hilos usan +frecuentemente servicios del recolector. El precio a pagar es un mayor uso de +memoria de forma temporal (y el trabajo extra de crear y eliminar *pools* más +frecuentemente), pero es esperable que el tiempo máximo de pausa **real** se +vea drásticamente disminuido. + +A simple vista las modificaciones necesarias para su implementación parecieran +ser las siguientes:: + + // Agregado + global mark_pid = 0 + + // Agregado + function mark_is_running() is + return global mark_pid != 0 + + function collect() is + if mark_is_running() // + finished = try_wait(global mark_pid) // + if finished // Agregado + mark_pid = 0 // + sweep() // + return // + stop_the_world() + child_pid = fork() + fflush(null) + if child_pid is 0 // proceso hijo + mark_phase() + exit(0) + // proceso padre + start_the_world() + // Borrado: wait(child_pid) + global mark_pid = child_pid + +Sin embargo con sólo estas modificaciones el algoritmo deja de ser correcto, +ya que tres cosas problemáticas pueden suceder: + +1. Puede llamarse a la función ``minimize()`` mientras hay una fase de marcado + corriendo en paralelo. Esto puede provocar que se libere un *pool* mientras + se lo está usando en la fase de marcado, lo que no sería un problema + (porque el proceso de marcado tiene una copia) si no fuera porque los bits + de marcado, que son compartidos por los procesos, se liberan con el *pool*. +2. Si un bloque libre es asignado después de que la fase de marcado comienza, + pero antes de que termine, ese bloque será barrido dado la función + ``rebuild_free_lists()`` puede reciclar páginas si todos sus bloques tienen + el bit ``freebits`` activo (ver :ref:`dgc_algo_sweep`). +3. El *pool* creado ansiosamente, tendrá sus bits de marcado sin activar, por + lo que en la fase de barrido será interpretado como memoria libre, incluso + cuando puedan estar siendo utilizados por el *mutator*. + +El punto 1 sencillamente hace que el programa finalice con una violación de +segmento (en el mejor caso) y 2 y 3 pueden desembocar en la liberación de una +celda alcanzable por el *mutator*. + +El punto 1 se resuelve a través de la siguiente modificación:: + + function minimize() is + if mark_is_running() // Agregado + return // + 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) + +La resolución del punto 2 es un poco más laboriosa, ya que hay que mantener +actualizado los ``freebits``, de forma que las celdas asignadas después de +empezar la fase de marcado no sean barridas por tener ese bit activo:: + + 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.free = true // Agregado + pages[0].block_size = PAGE + foreach page in pages[1..end] + page.block_size = CONTINUATION + return pages[0] + + 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 + block.free = true // Agregado + free_lists[page.block_size].link(block) + + function mark_phase() is + global more_to_scan = false + // Borrado: clear_mark_scan_bits() + // Borrado: mark_free_lists() + clear_scan_bits() // Agregado + mark_free() // + 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() + + // Agregado + function clear_scan_bits() is + // La implementación real limpia los bits en bloques de forma eficiente + foreach pool in heap + foreach page in pool + foreach block in page + block.scan = false + + // Agregado + function mark_free() is + // La implementación real copia los bits en bloques de forma eficiente + foreach pool in heap + foreach page in pool + foreach block in page + block.mark = block.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.block.free = true // Agregado + page = cast(byte*) page + PAGE_SIZE + while page < pool_end and page.block_size is CONTINUATION + + 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 + block.free = false // Agregado + return cast(void*) block + + funciones new_pool(number_of_pages = 1) is + pool = alloc(pool.sizeof) + if pool is null + return null + pool.number_of_pages = number_of_pages + pool.pages = alloc(number_of_pages * PAGE_SIZE) + if pool.pages is null + free(pool) + return null + heap.add(pool) + foreach page in pool + page.block_size = FREE + foreach block in page // + block.free = true // Agregado + block.mark = true // + return pool + +Finalmente, el punto número tres puede ser solucionado con el siguiente +pequeño cambio:: + + funciones new_pool(number_of_pages = 1) is + pool = alloc(pool.sizeof) + if pool is null + return null + pool.number_of_pages = number_of_pages + pool.pages = alloc(number_of_pages * PAGE_SIZE) + if pool.pages is null + free(pool) + return null + heap.add(pool) + foreach page in pool + page.block_size = FREE + foreach block in page // Agregado + block.mark = true // + return pool + +La solución es conservativa porque, por un lado evita la liberación de *pools* +mientras haya una recolección en curso (lo que puede hacer que el consumo de +memoria sea un poco mayor al requerido) y por otro asegura que, como se +mencionó anteriormente, los cambios hechos al grafo de conectividad luego de +iniciar la fase de marcado y antes de que ésta termine, no serán detectados +por el recolector hasta la próxima recolección (marcar todos los bloques de +un nuevo *pool* como el bit ``mark`` asegura que que la memoria no sea +recolectada por la fase de barrido cuando termine el marcado). + +Estas modificaciones son las que hacen que el algoritmo siga siendo correcto, +asegurando que no se van a liberar celdas *vivas* (a expensas de diferir la +liberación de algunas celdas *muertas* por algún tiempo). + + +.. _sol_early_collect: + +Recolección temprana +^^^^^^^^^^^^^^^^^^^^ +Esta mejora, que puede ser controlada a través de la opción ``early_collect`` +(ver :ref:`sol_config_spec`), consiste en lanzar una recolección preventiva, +antes de que una petición de memoria falle. El momento en que se lanza la +recolección es controlado por la opción ``min_free`` (ver :ref:`sol_ocup`). + +De esta forma también puede correr de forma realmente concurrente el *mutator* +y el recolector, al menos hasta que se acabe la memoria, en cuyo caso, a menos +que la opción ``eager_alloc`` (ver :ref:`sol_eager_alloc`) también esté +activada, se deberá esperar a que la fase de marcado termine para recuperar +memoria en la fase de barrido. + +Para facilitar la comprensión de esta mejora se muestran sólo los cambios +necesarios si no se utiliza la opción ``eager_alloc``:: + + function collect(early = false) is // Modificado + if mark_is_running() + finished = try_wait(global mark_pid) + if finished + mark_pid = 0 + sweep() + return // + else if early // Agregado + return // + stop_the_world() + child_pid = fork() + fflush(null) + if child_pid is 0 // proceso hijo + mark_phase() + exit(0) + // proceso padre + start_the_world() + if early // + global mark_pid = child_pid // + else // Agregado + wait(child_pid) // + sweep() // + + // Agregado + function early_collect() is + if not collect_in_progress() and (percent_free < min_free) + collect(true) + + 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 + early_collect() // Agregado + return cast(void*) block + +Es de esperarse que cuando no está activa la opción ``eager_alloc`` por un +lado el tiempo de pausa máximo no sea tan chico como cuando sí lo está (dado +que si la recolección no se lanza de forma suficientemente temprana se va +a tener que esperar que la fase de marcado termine), y por otro que se hagan +más recolecciones de lo necesario (cuando pasa lo contrario, se recolecta más +temprano de lo que se debería). Sin embargo, también es de esperarse que el +consumo de memoria sea un poco menor que al usar la opción ``eager_alloc``. + +En cuanto a la corrección del algoritmo, éste solamente presenta los problemas +número 1 y 2 mencionados en :ref:`sol_eager_alloc`, dado que jamás se crean +nuevos *pools* y la solución es la ya presentada, por lo tanto el algoritmo +sigue siendo correcto con los cuidados pertinentes.