X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/c410a685943a1d4df7556ad0e8912a0394d47b5b..af3cc91ddf531e9eb73f3dac73b15ab317a3cbb2:/source/solucion.rst?ds=inline diff --git a/source/solucion.rst b/source/solucion.rst index b27ffbb..32a94bd 100644 --- a/source/solucion.rst +++ b/source/solucion.rst @@ -38,6 +38,8 @@ se intenta abordar los demás problemas planteados siempre que sea posible hacerlo sin alejarse demasiado del objetivo principal. +.. _sol_bench: + Banco de pruebas ---------------------------------------------------------------------------- @@ -83,6 +85,8 @@ Por lo tanto el banco de pruebas que se conformó como una mezcla de estas tres grandes categorías. +.. _sol_bench_synth: + Pruebas sintetizadas ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -158,7 +162,7 @@ servicios del recolector en todos los hilos lanzados. El objetivo de estos programas es medir el impacto de las pausas del recolector. Se espera medir dos tipos de pausa principales, por un lado el -tiempo máximo de pausa total, que puede involucrar a más de un hilo y por otro +tiempo máximo de pausa real, que puede involucrar a más de un hilo y por otro el tiempo de *stop-the-world*, es decir, el tiempo en que los hilos son efectivamente pausados por el recolector para tomar una *foto* de la pila y registros para agregarlos al *root set*. @@ -412,6 +416,8 @@ El código fuente es el siguiente:: } +.. _sol_bench_small: + Programas pequeños ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -420,7 +426,7 @@ provienen del `Olden Benchmark`__ [CAR95]_. Estos programas fueron diseñados para probar el lenguaje de programación Olden__; un lenguaje diseñado para paralelizar programas automáticamente en arquitecturas con memoria distribuida. Son programas relativamente pequeños (entre 400 y 1000 líneas de -código fuente cada uno) que realizan una tarea secuencial que aloca +código fuente cada uno) que realizan una tarea secuencial que asigna estructuras de datos dinámicamente. Las estructuras están usualmente organizadas como listas o árboles, y muy raramente como arreglos. Los programas pasan la mayor parte del tiempo alocando datos y el resto usando los @@ -431,16 +437,25 @@ __ http://www.irisa.fr/caps/people/truong/M2COct99/Benchmarks/Olden/Welcome.html __ http://www.martincarlisle.com/olden.html La traducción a D_ fue realizada por Leonardo Maffi y están basadas a su vez -en la traducción de este juego de pruebas a Java_, JOlden__ [CMK01]_. En -general (salvo para el programa ``voronoï``) está disponible el código fuente -portado a D_, Java_ y Python_, e incluso varias versiones con distintas +en la traducción de este juego de pruebas a Java_, JOlden__ [CMK01]_. En Java_ +no se recomienda utilizar este conjunto de pruebas para medir la eficiencia +del recolector de basura, dado que se han creado mejores pruebas para este +propósito, como DaCapo__ [BLA06]_, sin embargo, dada la falta de programas +disponibles en general, y de un conjunto de pruebas especialmente diseñado +para evaluar el recolector de basura en D_, se decide utilizarlas en este +trabajo de todos modos. Sin embargo sus resultados deben ser interpretados con +una pizca de sal por lo mencionado anteriormente. + +__ http://www-ali.cs.umass.edu/DaCapo/benchmarks.html +__ http://www.dacapobench.org/ + +En general (salvo para el programa ``voronoï``) está disponible el código +fuente portado a D_, Java_ y Python_, e incluso varias versiones con distintas optimizaciones para reducir el consumo de tiempo y memoria. Además provee comparaciones de tiempo entre todas ellas. Los programas utilizados en este banco de pruebas son la versión traducida más literalmente de Java_ a D_, ya que hace un uso más intensivo del recolector que las otras versiones. -__ http://www-ali.cs.umass.edu/DaCapo/benchmarks.html - A continuación se da una pequeña descripción de cada uno de los 5 programas traducidos y los enlaces en donde encontrar el código fuente (y las comparaciones de tiempos estar disponibles). @@ -500,6 +515,8 @@ plano euclídeo, utilizando el algoritmo descripto por Guibas & Stolfi [GS85]_. Código fuente disponible en: http://codepad.org/xGDCS3KO +.. _sol_bench_real: + Programas *reales* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -546,19 +563,2780 @@ ser útiles para encontrar problemas muy particulares, está es la que da una lectura más cercana a la realidad del uso de un recolector. +.. _sol_mod: 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 *no-encomendada* +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Se elimina la distinción entre memoria *encomendada* y *no-encomendada* (ver +:ref:`dgc_committed`), pasando a estar *encomendada* toda la memoria +administrada por el recolector. + +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*. + +.. _sol_minor_findsize: + +Caché de ``Pool.findSize()`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Se crea 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'" -\ + | | "Significado" + | /---- "bit de 'middle'" | "de bits" + | | | "en la" + | "bits de" | "bits de" /---- "bit de 'begin1'" | "primera" + | "'ints'" | "'bytes'" | | "palabra" + |/------------\|/-------------\| -/ + 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" |||| | + |||| | "Significado" + "bit de 's'" |||| | "de bits" + | |||| | "en la" + \---------------/||\---- "bit de 'begin2'" | "segunda" + || | "palabra" + /---------------/\---- "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* (*eager allocation*) +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +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 (*early collection*) +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +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. Resultados ---------------------------------------------------------------------------- -TODO +Los resultados de las modificación propuestas en la sección anterior (ver +:ref:`sol_mod`) se evalúan utilizando el conjunto de pruebas mencionado en la +sección :ref:`sol_bench`). + +En esta sección se describe la forma en la que el conjunto de pruebas es +utilizado, la forma en la que se ejecutan los programas para recolectar dichos +resultados y las métricas principales utilizadas para analizarlos. + +A fines prácticos, y haciendo alusión al nombre utilizado por Tango_, en esta +sección se utiliza el nombre **TBGC** (acrónimo para el nombre en inglés +*Tango Basic Garbage Collector*) para hacer referencia al recolector original +provisto por Tango_ 0.99.9 (que, recordamos, es el punto de partida de este +trabajo). Por otro lado, y destacando la principal modificación propuesta por +este trabajo, haremos referencia al recolector resultante de éste utilizando +el nombre **CDGC** (acrónimo para el nombre en inglés *Concurrent D Garbage +Collector*). + + +Ejecución del conjunto de pruebas +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Dado el indeterminismo inherente a los sistemas operativos de tiempo +compartido modernos, se hace un particular esfuerzo por obtener resultados lo +más estable posible. + +Hardware y software utilizado +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Para realizar las pruebas se utiliza el siguiente hardware: + +* Procesador Intel(R) Core(TM)2 Quad CPU Q8400 @ 2.66GHz. +* 2GiB de memoria RAM. + +El entorno de software es el siguiente: + +* Sistema operativo Debian_ Sid (para arquitectura *amd64*). +* Linux_ 2.6.35.7. +* DMD_ 1.063 modificado para proveer información de tipos al recolector (ver + :ref:`sol_precise`). +* *Runtime* Tango_ 0.99.9 modificado para utilizar la información de tipos + provista por el compilador modificado. +* GCC_ 4.4.5. +* Embedded GNU_ C Library 2.11.2. + +Si bien el sistema operativo utiliza arquitectura *amd64*, dado que DMD_ +todavía no soporta 64 bits, se compila y corren los programas de D_ en 32 +bits. + +Opciones del compilador +^^^^^^^^^^^^^^^^^^^^^^^ +Los programas del conjunto de pruebas se compilan utilizando las siguientes +opciones del compilador DMD_: + +``-O`` + Aplica optimizaciones generales. + +``-inline`` + Aplica la optimización de expansión de funciones. Consiste en sustituir la + llamada a función por el cuerpo de la función (en general solo para + funciones pequeñas). + +``-release`` + No genera el código para verificar pre y post-condiciones, invariantes de + representación, operaciones fuera de los límites de un arreglo y + *assert*\ 's en general (ver :ref:`d_dbc`). + +Parámetros de los programas +^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Los programas de prueba se ejecutan siempre con los mismos parámetros (a menos +que se especifique lo contrario), que se detallan a continuación. + +.. highlight:: none + +``conalloc`` + ``40 4 bible.txt`` + + Procesa 40 veces un archivo de texto plano (de 4MiB de tamaño) [#solbible]_ + utilizando 4 hilos (más el principal). + +``concpu`` + ``40 4 bible.txt`` + + Procesa 40 veces un archivo de texto plano (de 4MiB de tamaño) [#solbible]_ + utilizando 4 hilos (más el principal). + +``split`` + ``bible.txt 2`` + + Procesa dos veces un archivo de texto plano (de 4MiB de tamaño) + [#solbible]_. + +``sbtree`` + ``16`` + + Construyen árboles con profundidad máxima 16. + +``bh`` + ``-b 4000`` + + Computa las interacciones gravitatorias entre 4.000 cuerpos. + +``bisort`` + ``-s 2097151`` + + Ordena alrededor de 2 millones de números (exactamente :math:`2^21 + = 2097151`). + +``em3d`` + ``-n 4000 -d 300 -i 74`` + + Realiza 74 iteraciones para modelar 4.000 nodos con grado 300. + +``tsp`` + ``-c 1000000`` + + Resuelve el problema del viajante a través de una heurística para un + millón de ciudades. + +``voronoi`` + ``-n 30000`` + + Se construye un diagrama con 30.000 nodos. + +``dil`` + ``ddoc $dst_dir -hl --kandil -version=Tango -version=TangoDoc + -version=Posix -version=linux $tango_files`` + + Genera la documentación de todo el código fuente de Tango_ 0.99.9, donde + ``$dst_dir`` es el directorio donde almacenar los archivos generados + y ``$tango_files`` es la lista de archivos fuente de Tango_. + +.. highlight:: d + +El resto de los programas se ejecutan sin parámetros (ver :ref:`sol_bench` +para una descripción detallada sobre cada uno). + +.. [#solbible] El archivo contiene la Biblia completa, la versión traducida al + inglés autorizada por el Rey Jaime o Jacobo (*Authorized King James + Version* en inglés). Obtenida de: http://download.o-bible.com:8080/kjv.gz + +Recolectores y configuraciones utilizadas +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +En general se presentan resultados para TBGC y varias configuraciones de CDGC, +de manera de poder tener una mejor noción de que mejoras y problemas puede +introducir cada una de las modificaciones más importantes. + +CDGC se utiliza con siguientes configuraciones: + +.. highlight:: none + +cons + En modo conservativo. Específicamente, utilizando el juego de opciones:: + + conservative=1:fork=0:early_collect=0:eager_alloc=0 + +prec + En modo preciso (ver :ref:`sol_precise`). Específicamente, utilizando el + juego de opciones:: + + conservative=0:fork=0:early_collect=0:eager_alloc=0 + +fork + En modo preciso activando el marcado concurrente (ver :ref:`sol_fork`). + Específicamente, utilizando el juego de opciones:: + + conservative=0:fork=1:early_collect=0:eager_alloc=0 + +ecol + En modo preciso activando el marcado concurrente con recolección temprana + (ver :ref:`sol_early_collect`). Específicamente, utilizando el juego de + opciones:: + + conservative=0:fork=1:early_collect=1:eager_alloc=0 + +eall + En modo preciso activando el marcado concurrente con creación ansiosa de + *pools* (ver :ref:`sol_eager_alloc`). Específicamente, utilizando el juego + de opciones:: + + conservative=0:fork=1:early_collect=0:eager_alloc=1 + +todo + En modo preciso activando el marcado concurrente con recolección temprana + y creación ansiosa de *pools*. Específicamente, utilizando el juego de + opciones:: + + conservative=0:fork=1:early_collect=1:eager_alloc=1 + +.. highlight:: d + +Métricas utilizadas +^^^^^^^^^^^^^^^^^^^ +Para analizar los resultados se utilizan varias métricas. Las más importantes +son: + +* Tiempo total de ejecución. +* Tiempo máximo de *stop-the-world*. +* Tiempo máximo de pausa real. +* Cantidad máxima de memoria utilizada. +* Cantidad total de recolecciones realizadas. + +El tiempo total de ejecución es una buena medida del **rendimiento** general +del recolector, mientras que la cantidad total de recolecciones realizadas +suele ser una buena medida de su **eficacia** [#soleficacia]_. + +Los tiempos máximos de pausa, *stop-the-world* y real, son una buena medida de +la **latencia** del recolector; el segundo siendo una medida más realista dado +que es raro que los demás hilos no utilicen servicios del recolector mientras +hay una recolección en curso. Esta medida es particularmente importante para +programas que necesiten algún nivel de ejecución en *tiempo-real*. + +En general el consumo de tiempo y espacio es un compromiso, cuando se consume +menos tiempo se necesita más espacio y viceversa. La cantidad máxima de +memoria utilizada nos da un parámetro de esta relación. + +.. [#soleficacia] Esto no es necesariamente cierto para recolectores con + particiones (ver :ref:`gc_part`) o incrementales (ver :ref:`gc_inc`), dado + que en ese caso podría realizar muchas recolecciones pero cada una muy + velozmente. + +Métodología de medición +^^^^^^^^^^^^^^^^^^^^^^^ +Para medir el tiempo total de ejecución se utiliza el comando +:manpage:`time(1)` con la especificación de formato ``%e``, siendo la medición +más realista porque incluye el tiempo de carga del ejecutable, inicialización +del *runtime* de D_ y del recolector. + +Todas las demás métricas se obtienen utilizando la salida generada por la +opción ``collect_stats_file`` (ver :ref:`sol_stats`), por lo que no pueden ser +medidos para TBGC. Sin embargo se espera que para esos casos los resultados no +sean muy distintos a CDGC utilizando la configuración **cons** (ver sección +anterior). + +Cabe destacar que las corridas para medir el tiempo total de ejecución no son +las mismas que al utilizar la opción ``collect_stats_file``; cuando se mide el +tiempo de ejecución no se utiliza esa opción porque impone un trabajo extra +importante y perturbaría demasiado la medición del tiempo. Sin embargo, los +tiempos medidos internamente al utilizar la opción ``collect_stats_file`` son +muy precisos, dado que se hace un particular esfuerzo para que no se haga un +trabajo extra mientras se está midiendo el tiempo. + +Al obtener el tiempo de *stop-the-world* se ignoran los apariciones del valor +``-1``, que indica que se solicitó una recolección pero que ya había otra en +curso, por lo que no se pausan los hilos realmente. Como tiempo de pausa real +(ver :ref:`sol_fork` para más detalles sobre la diferencia con el tiempo de +*stop-the-world*) se toma el valor del tiempo que llevó la asignación de +memoria que disparó la recolección. + +Para medir la cantidad de memoria máxima se calcula el valor máximo de la +sumatoria de: memoria usada, memoria libre, memoria desperdiciada y memoria +usada por el mismo recolector (es decir, el total de memoria pedida por el +programa al sistema operativo, aunque no toda este siendo utilizada por el +*mutator* realmente). + +Por último, la cantidad total de recolecciones realizadas se calcula contando +la cantidad de entradas del archivo generado por ``collect_stats_file``, +ignorando la cabecera y las filas cuyo valor de tiempo de *stop-the-world* es +``-1``, debido a que en ese caso no se disparó realmente una recolección dado +que ya había una en curso. + +Además, ciertas pruebas se corren variando la cantidad de procesadores +utilizados, para medir el impacto de la concurrencia en ambientes con un +procesador solo y con múltiples procesadores. Para esto se utiliza el comando +:manpage:`taskset`, que establece la *afinidad* de un proceso, *atándolo* +a correr en un cierto conjunto de procesadores. Si bien las pruebas se +realizan utilizando 1, 2, 3 y 4 procesadores, los resultados presentados en +general se limitan a 1 y 4 procesadores, ya que no se observan diferencias +sustanciales al utilizar 2 o 3 procesadores con respecto a usar 4 (solamente +se ven de forma más atenuadas las diferencias entre la utilización de +1 o 4 procesadores). Dado que de por sí ya son muchos los datos a procesar +y analizar, agregar más resultados que no aportan información valiosa termina +resultando contraproducente. + +En los casos donde se utilizan otro tipo de métricas para evaluar aspectos +particulares sobre alguna modificación se describe como se realiza la medición +donde se utiliza la métrica especial. + +Variabilidad de los resultados entre ejecuciones +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Es de esperarse que haya una cierta variación en los resultados entre +corridas, dada la indeterminación inherente a los sistemas operativos de +tiempo compartido, que compiten por los recursos de la computadora. + +Para minimizar esta variación se utilizan varias herramientas. En primer +lugar, se corren las pruebas estableciendo máxima prioridad (-19 en Linux_) al +proceso utilizando el comando :manpage:`nice(1)`. La variación en la +frecuencia del reloj los procesadores (para ahorrar energía) puede ser otra +fuente de variación, por lo que se usa el comando :manpage:`cpufreq-set(1)` +para establecer la máxima frecuencia disponible de manera fija. + +Sin embargo, a pesar de tomar estas precauciones, se sigue observando una +amplia variabilidad entre corridas. Además se observa una variación más +importante de la esperada no solo en el tiempo, también en el consumo de +memoria, lo que es más extraño. Esta variación se debe principalmente a que +Linux_ asigna el espacio de direcciones a los procesos con una componente +azarosa (por razones de seguridad). Además, por omisión, la llamada al sistema +:manpage:`mmap(2)` asigna direcciones de memoria altas primero, entregando +direcciones más bajas en llamadas subsiguientes [LWN90311]_. + +El comando :manpage:`setarch(8)` sirve para controlar éste y otros aspectos de +Linux_. La opción ``-L`` hace que se utilice un esquema de asignación de +direcciones antiguo, que no tiene una componente aleatoria y asigna primero +direcciones bajas. La opción ``-R`` solamente desactiva la componente azarosa +al momento de asignar direcciones. + +.. ftable:: t:sol-setarch + + Variación entre corridas para TBGC. + + Variación entre corridas para TBGC. La medición está efectuada utilizando + los valores máximo, mínimo y media estadística de 20 corridas, utilizando + la siguiente métrica: :math:`\frac{max - min}{\mu}`. La medida podría + realizarse utilizando el desvío estándar en vez de la amplitud máxima, pero + en este cuadro se quiere ilustrar la variación máxima, no la típica. + + .. subtable:: + + Del tiempo total de ejecución. + + ======== ======== ======== ======== + Programa Normal ``-R`` ``-L`` + ======== ======== ======== ======== + bh 0.185 0.004 0.020 + bigarr 0.012 0.002 0.016 + bisort 0.006 0.003 0.006 + conalloc 0.004 0.004 0.004 + concpu 0.272 0.291 0.256 + dil 0.198 0.128 0.199 + em3d 0.006 0.033 0.029 + mcore 0.009 0.009 0.014 + rnddata 0.015 0.002 0.011 + sbtree 0.012 0.002 0.012 + split 0.025 0.000 0.004 + tsp 0.071 0.068 0.703 + voronoi 0.886 0.003 0.006 + ======== ======== ======== ======== + + .. subtable:: + + Del consumo máximo de memoria. + + ======== ======== ======== ======== + Programa Normal ``-R`` ``-L`` + ======== ======== ======== ======== + bh 0.001 0.000 0.001 + bigarr 0.001 0.000 0.001 + bisort 0.000 0.000 0.000 + conalloc 0.753 0.000 0.001 + concpu 0.002 0.000 0.001 + dil 0.055 0.028 0.013 + em3d 0.000 0.001 0.001 + mcore 0.447 0.482 0.460 + rnddata 0.000 0.000 0.000 + sbtree 0.000 0.000 0.000 + split 0.000 0.000 0.000 + tsp 0.000 0.001 0.000 + voronoi 0.001 0.000 0.000 + ======== ======== ======== ======== + +Ambas opciones, reducen notablemente la variación en los resultados (ver +cuadro :vref:`t:sol-setarch`). Esto probablemente se debe a la naturaleza +conservativa del recolector, dado que la probabilidad de tener *falsos +punteros* depende directamente de los valores de las direcciones de memoria, +aunque las pruebas en la que hay concurrencia involucrada, se siguen viendo +grandes variaciones, que probablemente estén vinculadas a problemas de +sincronización que se ven expuestos gracias al indeterminismo inherente a los +programas multi-hilo. + +Si bien se obtienen resultados más estables utilizando un esquema diferente al +utilizado por omisión, se decide no hacerlo dado que las mediciones serían +menos realistas. Los usuarios en general no usan esta opción y se presentaría +una visión más acotada sobre el comportamiento de los programas. Sin embargo, +para evaluar el este efecto en los resultados, siempre que sea posible se +analizan los resultados de un gran número de corridas observando +principalmente su mínima, media, máxima y desvío estándar. + +.. Tamaño del ejecutable (XXX: SEGUN LAS PRUEBAS NO FUCKING CAMBIA!!!) + El tamaño del ejecutable es un factor importante. Cuanto más grande es el + ejecutable, más parecieran variar los resultados. Por ejemplo se observa un + incremento de la estabilidad de los resultados al eliminar toda información + de depuración (*debug*) del ejecutable, utilizando el comando + :manpage:`strip(1)` (*stripped*). En el cuadro :vref:`t:sol-exesize-tbgc` + se puede ver la reducción del tamaño del ejecutable para TBGC cuando se + elimina la información de depuración (4.25 veces más chico en promedio), + mientas que en el cuadro :vref:`t:sol-exesize-cdgc` se puede ver CDGC (4.6 + veces más chico en promedio). + .. ftable:: t:sol-exesize-tbgc + Reducción del tamaño del ejecutable para TBGC. + ======== ======== ======== ============== + Nombre Debug Stripped Debug/Stripped + ======== ======== ======== ============== + bh 586517 138060 4.248 + bigarr 547687 192004 2.852 + bisort 485857 115164 4.219 + conalloc 616613 149848 4.115 + concpu 616575 149848 4.115 + dil 7293277 1859208 3.923 + em3d 505019 116324 4.341 + mcore 461767 105748 4.367 + rnddata 2832935 1492588 1.898 + sbtree 526402 129860 4.054 + split 589353 144308 4.084 + tree 462009 105844 4.365 + tsp 544901 128412 4.243 + voronoi 601259 141112 4.261 + ======== ======== ======== ============== + .. ftable:: t:sol-exesize-cdgc + Reducción del tamaño del ejecutable para CDGC. + ======== ======== ======== =============== + Nombre Debug Stripped Debug/Stripped + ======== ======== ======== =============== + bh 736115 159884 4.604 + bigarr 697406 213832 3.261 + bisort 635537 136988 4.639 + conalloc 766328 171676 4.464 + concpu 766294 171676 4.464 + dil 7442657 1881028 3.957 + em3d 658827 142248 4.632 + mcore 611486 127576 4.793 + rnddata 2986736 1518512 1.967 + sbtree 680217 155784 4.366 + split 739072 166136 4.449 + tree 611728 127672 4.791 + tsp 694581 150236 4.623 + voronoi 750847 162936 4.608 + ======== ======== ======== =============== + TODO: Mostrar tiempos de corridas. + + +.. Resultados generales + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. Primero se presenta una visión global de los resultados, utilizando las + métricas más importantes. Para generar los gráficos se utilizan los valores + máximos (en blanco), mínimos (en negro), media y desvío estándar (en gris) + calculados en base a, como mínimo, 20 corridas (para algunos casos se hacen + hasta 50 corridas). + + +Resultados para pruebas sintizadas +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +A continuación se presentan los resultados obtenidos para las pruebas +sintetizadas (ver :ref:`sol_bench_synth`). Se recuerda que este conjunto de +resultados es útil para analizar ciertos aspectos puntuales de las +modificaciones propuestas, pero en general distan mucho de como se comporta un +programa real, por lo que los resultados deben ser analizados teniendo esto +presente. + +``bigarr`` +^^^^^^^^^^ +.. fig:: fig:sol-bigarr-1cpu + + Resultados para ``bigarr`` (utilizando 1 procesador). + + Resultados para ``bigarr`` (utilizando 1 procesador). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-bigarr-1cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-bigarr-1cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-bigarr-1cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-bigarr-1cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-bigarr-1cpu.pdf + +.. fig:: fig:sol-bigarr-4cpu + + Resultados para ``bigarr`` (utilizando 4 procesadores). + + Resultados para ``bigarr`` (utilizando 4 procesadores). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-bigarr-4cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-bigarr-4cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-bigarr-4cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-bigarr-4cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-bigarr-4cpu.pdf + +En la figura :vref:`fig:sol-bigarr-1cpu` se pueden observar los resultados +para ``bigarr`` al utilizar un solo procesador. En ella se puede notar que el +tiempo total de ejecución en general aumenta al utilizar CDGC, esto es +esperable, dado esta prueba se limitan a usar servicios del recolector. Dado +que esta ejecución utiliza solo un procesador y por lo tanto no se puede sacar +provecho a la concurrencia, es de esperarse que el trabajo extra realizado por +las modificaciones se vea reflejado en los resultados. En la +:vref:`fig:sol-bigarr-4cpu` (resultados al utilizar 4 procesadores) se puede +observar como al usar solamente *eager allocation* se recupera un poco el +tiempo de ejecución, probablemente debido al incremento en la concurrencia +(aunque no se observa el mismo efecto al usar *early collection*). + +Observando el tiempo total de ejecución, no se esperaba un incremento tan +notorio al pasar de TBGC a una configuración equivalente de CDGC **cons**, +haciendo un breve análisis de las posibles causas, lo más probable parece ser +el incremento en la complejidad de la fase de marcado dada capacidad para +marcar de forma precisa (aunque no se use la opción, se paga el precio de la +complejidad extra y sin obtener los beneficios). Además se puede observar +como el agregado de precisión al marcado mejora un poco las cosas (donde sí se +obtiene rédito de la complejidad extra en el marcado). + +En general se observa que al usar *eager allocation* el consumo de memoria +y los tiempos de pausa se disparan mientras que la cantidad de recolecciones +disminuye drásticamente. Lo que se observa es que el programa es +más veloz pidiendo memoria que recolectándola, por lo que crece mucho el +consumo de memoria. Como consecuencia la fase de barrido (que no corre en +paralelo al *mutator* como la fase de marcado) empieza a ser predominante en +el tiempo de pausa por ser tan grande la cantidad de memoria a barrer. Este +efecto se ve tanto al usar 1 como 4 procesadores, aunque el efecto es mucho +más nocivo al usar 1 debido a la alta variabilidad que impone la competencia +entre el *mutator* y recolector al correr de forma concurrente. + +Sin embargo, el tiempo de *stop-the-world* es siempre considerablemente más +pequeño al utilizar marcado concurrente en CDGC, incluso cuando se utiliza +*eager allocation*, aunque en este caso aumenta un poco, también debido al +incremento en el consumo de memoria, ya que el sistema operativo tiene que +copiar tablas de memoria más grandes al efectuar el *fork* (ver +:ref:`sol_fork`). + +``concpu`` +^^^^^^^^^^ +.. fig:: fig:sol-concpu-1cpu + + Resultados para ``concpu`` (utilizando 1 procesador). + + Resultados para ``concpu`` (utilizando 1 procesador). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-concpu-1cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-concpu-1cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-concpu-1cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-concpu-1cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-concpu-1cpu.pdf + +.. fig:: fig:sol-concpu-4cpu + + Resultados para ``concpu`` (utilizando 4 procesadores). + + Resultados para ``concpu`` (utilizando 4 procesadores). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-concpu-4cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-concpu-4cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-concpu-4cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-concpu-4cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-concpu-4cpu.pdf + +En la figura :vref:`fig:sol-concpu-1cpu` se pueden observar los resultados +para ``concpu`` al utilizar un solo procesador. En ella se aprecia que el +tiempo total de ejecución disminuye levemente al usar marcado concurrente +mientras no se utilice *eager allocation* pero aumenta al utilizarlo. + +Con respecto a la cantidad de recolecciones, uso máximo de memoria y tiempo de +*stop-the-world* se ve un efecto similar al descripto para ``bigarr`` (aunque +magnificado), pero sorprendentemente el tiempo total de pausa se dispara, +además con una variabilidad sorprendente, cuando se usa marcado concurrente +(pero no *eager allocation*). Una posible explicación podría ser que al +realizarse el *fork*, el sistema operativo muy probablemente entregue el +control del único procesador disponible al resto de los hilos que compiten por +él, por lo que queda mucho tiempo pausado en esa operación aunque realmente no +esté haciendo trabajo alguno (simplemente no tiene tiempo de procesador para +correr). Este efecto se cancela al usar *eager allocation* dado que el +*mutator* nunca se bloquea esperando que el proceso de marcado finalice. + +Además se observa una caída importante en la cantidad de recolecciones al +utilizar marcado concurrente. Esto probablemente se deba a que solo un hilo +pide memoria (y por lo tanto dispara recolecciones), mientras los demás hilos +también estén corriendo. Al pausarse todos los hilos por menos tiempo, el +trabajo se hace más rápido (lo que explica la disminución del tiempo total de +ejecución) y son necesarias menos recolecciones, por terminar más rápido +también el hilo que las dispara. + +En la :vref:`fig:sol-concpu-4cpu` se pueden ver los resultados al utilizar +4 procesadores, donde el panorama cambia sustancialmente. El efecto mencionado +en el párrafo anterior no se observa más (pues el sistema operativo tiene más +procesadores para asignar a los hilos) pero todos los resultados se vuelven +más variables. Los tiempos de *stop-the-world* y pausa real (salvo por lo +recién mencionado) crecen notablemente, al igual que su variación. No se +encuentra una razón evidente para esto; podría ser un error en la medición +dado que al utilizar todos los procesadores disponibles del *hardware*, +cualquier otro proceso que compita por tiempo de procesador puede afectarla +más fácilmente. + +El tiempo total de ejecución crece considerablemente, como se espera, dado que +el programa aprovecha los múltiples hilos que pueden correr en paralelo en +procesadores diferentes. + +Sin embargo, no se encuentra una razón clara para explicar el crecimiento +dramático en la cantidad de recolecciones solo al no usar marcado concurrente +para 4 procesadores. + +``conalloc`` +^^^^^^^^^^^^ +.. fig:: fig:sol-conalloc-1cpu + + Resultados para ``conalloc`` (utilizando 1 procesador). + + Resultados para ``conalloc`` (utilizando 1 procesador). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-conalloc-1cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-conalloc-1cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-conalloc-1cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-conalloc-1cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-conalloc-1cpu.pdf + +.. fig:: fig:sol-conalloc-4cpu + + Resultados para ``conalloc`` (utilizando 4 procesadores). + + Resultados para ``conalloc`` (utilizando 4 procesadores). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-conalloc-4cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-conalloc-4cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-conalloc-4cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-conalloc-4cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-conalloc-4cpu.pdf + +En la figura :vref:`fig:sol-conalloc-1cpu` se pueden observar los resultados +para ``conalloc`` al utilizar un solo procesador. Los cambios con respecto +a lo observado para ``concpu`` son mínimos. El efecto de la mejoría al usar +marcado concurrente pero no *eager allocation* no se observa más, dado que +``conalloc`` pide memoria en todos los hilos, se crea un cuello de botella. Se +ve claramente como tampoco baja la cantidad de recolecciones hecha debido +a esto y se invierte la variabilidad entre los tiempos pico de pausa real +y *stop-the-world* (sin una razón obvia, pero probablemente relacionado que +todos los hilos piden memoria). + +Al utilizar 4 procesadores (figura :vref:`fig:sol-conalloc-4cpu`), más allá de +las diferencias mencionadas para 1 procesador, no se observan grandes cambios +con respecto a lo observado para ``concpu``, excepto que los tiempos de pausa +(real y *stop-the-world*) son notablemente más pequeños, lo que pareciera +confirmar un error en la medición de ``concpu``. + +``split`` +^^^^^^^^^ +.. fig:: fig:sol-split-1cpu + + Resultados para ``split`` (utilizando 1 procesador). + + Resultados para ``split`` (utilizando 1 procesador). Se presenta el mínimos + (en negro), la media centrada entre dos desvíos estándar (en gris), y el + máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución) + o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-split-1cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-split-1cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-split-1cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-split-1cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-split-1cpu.pdf + +Este es el primer caso donde se aprecia la sustancial mejora proporcionada por +una pequeña optimización, el caché de ``findSize()`` (ver +:ref:`sol_minor_findsize`). En la figura :vref:`fig:sol-split-1cpu` se puede +observar con claridad como, para cualquier configuración de CDGC, hay una +caída notable en el tiempo total de ejecución. Sin embargo, a excepción de +cuando se utiliza *eager allocation*, la cantidad de recolecciones y memoria +usada permanece igual. + +La utilización de *eager allocation* mejora (aunque de forma apenas +apreciable) el tiempo de ejecución, la cantidad de recolecciones baja a un +tercio y el tiempo de pausa real cae dramáticamente. Al usar marcado +concurrente ya se observa una caída determinante en el tiempo de +*stop-the-world*. Todo esto sin verse afectado el uso máximo de memoria, +incluso al usar *eager allocation*. + +Se omiten los resultados para más de un procesador por ser prácticamente +idénticos para este análisis. + +``mcore`` +^^^^^^^^^ +.. fig:: fig:sol-mcore-1cpu + + Resultados para ``mcore`` (utilizando 1 procesador). + + Resultados para ``mcore`` (utilizando 1 procesador). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-mcore-1cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-mcore-1cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-mcore-1cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-mcore-1cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-mcore-1cpu.pdf + +.. fig:: fig:sol-mcore-4cpu + + Resultados para ``mcore`` (utilizando 4 procesadores). + + Resultados para ``mcore`` (utilizando 4 procesadores). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-mcore-4cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-mcore-4cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-mcore-4cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-mcore-4cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-mcore-4cpu.pdf + +El caso de ``mcore`` es interesante por ser, funcionalmente, una combinación +entre ``concpu`` y ``split``, con un agregado extra: el incremento notable de +la competencia por utilizar el recolector entre los múltiples hilos. + +Los efectos observados (en la figura :vref:`fig:sol-mcore-1cpu` para +1 procesador y en la figura :vref:`fig:sol-mcore-4cpu` para 4) confirman esto, +al ser una suma de los efectos observados para ``concpu`` y ``split``, con el +agregado de una particularidad extra por la mencionada competencia entre +hilos. A diferencia de ``concpu`` donde el incremento de procesadores resulta +en un decremento en el tiempo total de ejecución, en este caso resulta en una +disminución, dado que se necesita mucha sincronización entre hilos, por +utilizar todos de forma intensiva los servicios del recolector (y por lo tanto +competir por su *lock* global). + +Otro efecto común observado es que cuando el tiempo de pausa es muy pequeño +(del orden de los milisegundos), el marcado concurrente suele incrementarlo en +vez de disminuirlo. + +``rnddata`` +^^^^^^^^^^^ +.. fig:: fig:sol-rnddata-1cpu + + Resultados para ``rnddata`` (utilizando 1 procesador). + + Resultados para ``rnddata`` (utilizando 1 procesador). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-rnddata-1cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-rnddata-1cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-rnddata-1cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-rnddata-1cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-rnddata-1cpu.pdf + +En la figura :vref:`fig:sol-rnddata-1cpu` se presentan los resultados para +``rnddata`` utilizando 1 procesador. Una vez más estamos ante un caso en el +cual se observa claramente la mejoría gracias a una modificación en particular +principalmente. En esta caso es el marcado preciso. Se puede ver claramente +como mejora el tiempo de total de ejecución a algo más que la mitad (en +promedio, aunque se observa una anomalía donde el tiempo baja hasta más de +3 veces). Sin embargo, a menos que se utilice *eager allocation* o *early +collection* (que en este caso prueba ser muy efectivo), la cantidad de +recolecciones aumenta considerablemente. + +La explicación puede ser hallada en el consumo de memoria, que baja unas +3 veces en promedio usando marcado preciso que además hace disminuir +drásticamente (unas 10 veces) el tiempo de pausa (real y *stop-the-world*). El +tiempo de *stop-the-world* disminuye unas 10 veces más al usar marcado +concurrente y el tiempo de pausa real al usar *eager allocation*, pero en este +caso el consumo de memoria aumenta también bastante (aunque no tanto como +disminuye el tiempo de pausa, por lo que puede ser un precio que valga la pena +pagar si se necesitan tiempos de pausa muy pequeños). + +El aumento en el variación de los tiempos de ejecución al usar marcado preciso +probablemente se debe a lo siguiente: con marcado conservativo, debe estar +sobreviviendo a las recolecciones el total de memoria pedida por el programa, +debido a falsos punteros (por eso no se observa prácticamente variación en el +tiempo de ejecución y memoria máxima consumida); al marcar con precisión +parcial, se logra disminuir mucho la cantidad de falsos punteros, pero el +*stack* y la memoria estática, se sigue marcado de forma conservativa, por lo +tanto dependiendo de los valores (aleatorios) generados por la prueba, aumenta +o disminuye la cantidad de falsos punteros, variando así la cantidad de +memoria consumida y el tiempo de ejecución. + +No se muestran los resultados para más de un procesador por ser demasiado +similares a los obtenidos utilizando solo uno. + +``sbtree`` +^^^^^^^^^^ +Los resultados para ``sbtree`` son tan similares a los obtenidos con +``bigarr`` que directamente se omiten por completo, dado que no aportan ningún +tipo de información nueva. Por un lado es esperable, dado que ambas pruebas se +limitan prácticamente a pedir memoria, la única diferencia es que una pide +objetos grandes y otra objetos pequeños, pero esta diferencia parece no +afectar la forma en la que se comportan los cambios introducidos en este +trabajo. + + +Resultados para pruebas pequeñas +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +A continuación se presentan los resultados obtenidos para las pruebas pequeñas +(ver :ref:`sol_bench_small`). Se recuerda que si bien este conjunto de pruebas +se compone de programas reales, que efectúan una tarea útil, están diseñados +para ejercitar la asignación de memoria y que no son recomendados para evaluar +el desempeño de recolectores de basura. Sin embargo se las utiliza igual por +falta de programas más realistas, por lo que hay que tomarlas como un grado de +suspicacia. + +``bh`` +^^^^^^ +.. fig:: fig:sol-bh-1cpu + + Resultados para ``bh`` (utilizando 1 procesador). + + Resultados para ``bh`` (utilizando 1 procesador). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-bh-1cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-bh-1cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-bh-1cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-bh-1cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-bh-1cpu.pdf + +En la figura :vref:`fig:sol-bh-1cpu` se pueden observar los resultados +para ``bh`` al utilizar un solo procesador. Ya en una prueba un poco más +realista se puede observar el efecto positivo del marcado preciso, en especial +en la cantidad de recolecciones efectuadas (aunque no se traduzca en un menor +consumo de memoria). + +Sin embargo se observa también un efecto nocivo del marcado preciso en el +consumo de memoria que intuitivamente debería disminuir, pero crece, y de +forma considerable (unas 3 veces en promedio). La razón de esta particularidad +es el incremento en el espacio necesario para almacenar objetos debido a que +el puntero a la información del tipo se guarda al final del bloque (ver +:ref:`sol_precise`). En el cuadro :vref:`t:sol-prec-mem-bh` se puede observar +la cantidad de memoria pedida por el programa, la cantidad de memoria +realmente asignada por el recolector (y la memoria desperdiciada) cuando se +usa marcado conservativo y preciso. Estos valores fueron tomados usando la +opción ``malloc_stats_file`` (ver :ref:`sol_stats`). + +.. ftable:: t:sol-prec-mem-bh + + Memoria pedida y asignada para ``bh`` según modo de marcado. + + Memoria pedida y asignada para ``bh`` según modo de marcado conservativo + o preciso (acumulativo durante toda la vida del programa). + + ============== ============== ============== ================= + Memoria Pedida (MiB) Asignada (MiB) Desperdicio (MiB) + ============== ============== ============== ================= + Conservativo 302.54 354.56 52.02 (15%) + Preciso 302.54 472.26 169.72 (36%) + ============== ============== ============== ================= + +Más allá de esto, los resultados son muy similares a los obtenidos para +pruebas sintetizadas que se limitan a ejercitar el recolector (como ``bigarr`` +y ``sbtree``), lo que habla de lo mucho que también lo hace este pequeño +programa. + +No se muestran los resultados para más de un procesador por ser extremadamente +similares a los obtenidos utilizando solo uno. + +``bisort`` +^^^^^^^^^^ +.. fig:: fig:sol-bisort-1cpu + + Resultados para ``bisort`` (utilizando 1 procesador). + + Resultados para ``bisort`` (utilizando 1 procesador). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-bisort-1cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-bisort-1cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-bisort-1cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-bisort-1cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-bisort-1cpu.pdf + +La figura :vref:`fig:sol-bisort-1cpu` muestra los resultados para ``bisort`` +al utilizar 1 procesador. En este caso el parecido es con los resultados para +la prueba sintetizada ``split``, con la diferencia que el tiempo de ejecución +total prácticamente no varía entre TBGC y CDGC, ni entre las diferentes +configuraciones del último (evidentemente en este caso no se aprovecha el +caché de ``findSize()``). + +Otra diferencia notable es la considerable reducción del tiempo de pausa real +al utilizar *early collection* (más de 3 veces menor en promedio comparado +a cuando se marca conservativamente, y más de 2 veces menor que cuando se hace +de forma precisa), lo que indica que la predicción de cuando se va a necesitar +una recolección es más efectiva que para ``split``. + +No se muestran los resultados para más de un procesador por ser extremadamente +similares a los obtenidos utilizando solo uno. + +``em3d`` +^^^^^^^^ +.. fig:: fig:sol-em3d-1cpu + + Resultados para ``em3d`` (utilizando 1 procesador). + + Resultados para ``em3d`` (utilizando 1 procesador). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-em3d-1cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-em3d-1cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-em3d-1cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-em3d-1cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-em3d-1cpu.pdf + +Los resultados para ``em3d`` (figura :vref:`fig:sol-em3d-1cpu`) son +sorprendentemente similares a los de ``bisort``. La única diferencia es que en +este caso el marcado preciso y el uso de *early collection** no parecen +ayudar; por el contrario, aumentan levemente el tiempo de pausa real. + +Una vez más no se muestran los resultados para más de un procesador por ser +extremadamente similares a los obtenidos utilizando solo uno. + +``tsp`` +^^^^^^^^ +.. fig:: fig:sol-tsp-1cpu + + Resultados para ``tsp`` (utilizando 1 procesador). + + Resultados para ``tsp`` (utilizando 1 procesador). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-tsp-1cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-tsp-1cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-tsp-1cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-tsp-1cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-tsp-1cpu.pdf + +Los resultados para ``tsp`` (figura :vref:`fig:sol-tsp-1cpu`) son +prácticamente idénticos a los de ``bisort``. La única diferencia es que la +reducción del tiempo de pausa real es un poco menor. + +Esto confirma en cierta medida la poca utilidad de este juego de pruebas para +medir el rendimiento de un recolector, dado que evidentemente, si bien todas +resuelven problemas diferentes, realizan todas el mismo tipo de trabajo. + +Una vez más no se muestran los resultados para más de un procesador por ser +extremadamente similares a los obtenidos utilizando solo uno. + +``voronoi`` +^^^^^^^^^^^ +.. fig:: fig:sol-voronoi-1cpu + + Resultados para ``voronoi`` (utilizando 1 procesador). + + Resultados para ``voronoi`` (utilizando 1 procesador). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-voronoi-1cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-voronoi-1cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-voronoi-1cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-voronoi-1cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-voronoi-1cpu.pdf + +.. fig:: fig:sol-voronoi-4cpu + + Resultados para ``voronoi`` (utilizando 4 procesadores). + + Resultados para ``voronoi`` (utilizando 4 procesadores). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-voronoi-4cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-voronoi-4cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-voronoi-4cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-voronoi-4cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-voronoi-4cpu.pdf + +En la figura :vref:`fig:sol-voronoi-1cpu` se presentan los resultados para +``voronoi``, probablemente la prueba más interesante de este conjunto de +pruebas pequeñas. + +Por un lado se puede observar una vez más como baja dramáticamente el tiempo +total de ejecución cuando se empieza a utilizar CDGC. Ya se ha visto que esto +es común en programas que se benefician del caché de ``findSize()``, pero en +este caso no parece provenir toda la ganancia solo de ese cambio, dado que +para TBGC se ve una variación entre los resultados muy grande que desaparece +al cambiar a CDGC, esto no puede ser explicado por esa optimización. En +general la disminución de la variación de los resultados hemos visto que está +asociada al incremento en la precisión en el marcado, dado que los falsos +punteros ponen una cuota de aleatoriedad importante. Pero este tampoco parece +ser el caso, ya que no se observan cambios apreciables al pasar a usar marcado +preciso. + +Lo que se observa en esta oportunidad es un caso patológico de un mal factor +de ocupación del *heap* (ver :ref:`sol_ocup`). Lo que muy probablemente está +sucediendo con TBGC es que luego de ejecutar una recolección, se libera muy +poco espacio, entonces luego de un par de asignaciones, es necesaria una nueva +recolección. En este caso es donde dificulta la tarea de analizar los +resultados la falta de métricas para TBGC, dado que no se pueden observar la +cantidad de recolecciones ni de consumo máximo de memoria. Sin embargo es +fácil corroborar esta teoría experimentalmente, gracias a la opción +``min_free``. Utilizando la ``min_free=0`` para emular el comportamiento de +TBGC (se recuerda que el valor por omisión es ``min_free=5``), se obtiene una +media de 4 segundos, mucho más parecida a lo obtenido para TBGC. + +Otra particularidad de esta prueba es que al utilizar *early collection* el +tiempo de pausa real aumenta notablemente al usar un procesador, mientras que +al usar 4 (ver figura :vref:`fig:sol-voronoi-4cpu` disminuye levemente (además +de otros cambios en el nivel de variación, pero en general las medias no +cambian). + + +Resultados para pruebas reales +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +A continuación se presentan los resultados obtenidos para las pruebas reales +(ver :ref:`sol_bench_real`). Recordamos que solo se pudo halla un programa que +pueda ser utilizado a este fin, Dil_, y que el objetivo principal de este +trabajo se centra alrededor de obtener resultados positivos para este +programa, por lo que a pesar de ser una única prueba, se le presta particular +atención. + +``dil`` +^^^^^^^ +.. fig:: fig:sol-dil-1cpu + + Resultados para ``dil`` (utilizando 1 procesador). + + Resultados para ``dil`` (utilizando 1 procesador). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-dil-1cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-dil-1cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-dil-1cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-dil-1cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-dil-1cpu.pdf + +.. fig:: fig:sol-dil-4cpu + + Resultados para ``dil`` (utilizando 4 procesadores). + + Resultados para ``dil`` (utilizando 4 procesadores). Se presenta el + mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), + y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de + ejecución) o 20 corridas (para el resto). + + .. subfig:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-dil-4cpu.pdf + + .. subfig:: + + Cantidad de recolecciones + + .. image:: plots/ncol-dil-4cpu.pdf + + .. subfig:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-dil-4cpu.pdf + + .. subfig:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-dil-4cpu.pdf + + .. subfig:: + + Pausa real máxima (seg) + + .. image:: plots/pause-dil-4cpu.pdf + +En la figura :vref:`fig:sol-dil-1cpu` se presentan los resultados para +``dil`` al utilizar un procesador. Una vez más vemos una mejoría inmediata del +tiempo total de ejecución al pasar de TBGC a CDGC, y una vez más se debe +principalmente al mal factor de ocupación del *heap* de TBGC, dado que +utilizando CDGC con la opción ``min_free=0`` se obtiene una media del orden de +los 80 segundos, bastante más alta que el tiempo obtenido para TBGC. + +Sin embargo se observa un pequeño incremento del tiempo de ejecución al +introducir marcado preciso, y un incremento bastante más importante (de +alrededor del 30%) en el consumo máximo de memoria. Nuevamente, como pasa con +la prueba ``bh``, el efecto es probablemente producto del incremento en el +espacio necesario para almacenar objetos debido a que el puntero a la +información del tipo se guarda al final del bloque (ver :ref:`sol_precise`). +En el cuadro :vref:`t:sol-prec-mem-dil` se puede observar la diferencia de +memoria desperdiciada entre el modo conservativo y preciso. + +El pequeño incremento en el tiempo total de ejecución podría estar dado por la +mayor probabilidad de tener *falsos punteros* debido al incremento del tamaño +del *heap*; se recuerda que el *stack* y memoria estática se siguen marcado de +forma conservativa, incluso en modo preciso. + +.. ftable:: t:sol-prec-mem-dil + + Memoria pedida y asignada para ``dil`` según modo de marcado. + + Memoria pedida y asignada para ``dil`` según modo de marcado conservativo + o preciso (acumulativo durante toda la vida del programa). + + ============== ============== ============== ================= + Memoria Pedida (MiB) Asignada (MiB) Desperdicio (MiB) + ============== ============== ============== ================= + Conservativo 307.48 399.94 92.46 (23%) + Preciso 307.48 460.24 152.76 (33%) + ============== ============== ============== ================= + +También se puede observar una gran disminución del tiempo total de ejecución +(cerca de un 60%, y más de un 200% comparado con TBGC) alrededor de la mitad) +al empezar a usar *eager allocation*, acompañado como es usual de una baja en +la cantidad de recolecciones realizadas (esta vez mayor, de más de 3 veces) +y de una caída drástica del tiempo de pausa real (alrededor de 40 veces más +pequeño); todo esto con un incremento marginal en el consumo total de memoria +(aproximadamente un 5%). En este caso el uso de *early collection* apenas +ayuda a bajar el tiempo de pausa real en un 20% en promedio aproximadamente. +El tiempo de *stop-the-world* cae dramáticamente al empezar a realizar la fase +de marcado de manera concurrente; es 200 veces más pequeño. + +Al utilizar 4 procesadores (ver figura :vref:`fig:sol-dil-4cpu`), hay algunos +pequeños cambios. El tiempo total de ejecución es reducido todavía más (un 20% +que cuando se usa 1 procesador) cuando se utiliza *eager allocation*. Además +al utilizar *early collection*, hay otra pequeña ganancia de alrededor del +10%, tanto para el tiempo total de ejecución como para el tiempo de pausa +real. + + +.. _sol_accept: + +Aceptación +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Los avances de este trabajo fueron comunicados regularmente a la comunidad de +D_ a través de un blog [LMTDGC]_ y del grupo de noticias de D_. Los +comentarios hechos sobre el primero son en general positivos y denotan una +buena recepción por parte de la comunidad a las modificaciones propuestas. + +Una vez agregado el marcado concurrente se hace un anuncio en el grupo de +noticias que también muestra buenos comentarios y aceptación, en particular +por parte de Sean Kelly, encargado de mantener el *runtime* de `D 2.0`_, que +comienza a trabajar en adaptar el recolector con idea de tal vez incluirlo en +el futuro [NGA19235]_. Poco después Sean Kelly publica una versión preliminar +de la adaptación en la lista de correos que coordina el desarrollo del +*runtime* de `D 2.0`_ [DRT117]_. + +También se ha mostrado interés de incluirlo en Tango_, aunque no se han ha +comenzado aún con la adaptación, pero debería ser trivial dado que este +trabajo se desarrolla usando Tango_ (y el recolector está basado en el de +Tango_) [TT1997]_. .. include:: links.rst