X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/b0956c037ae52da777b06705157486067755ec2c..fe08991bc0d4322fa06b341bf99f01b23a8357ac:/source/solucion.rst diff --git a/source/solucion.rst b/source/solucion.rst index ea56dfe..2cd924c 100644 --- a/source/solucion.rst +++ b/source/solucion.rst @@ -1,51 +1,3297 @@ -.. Acá va lo que decidí hacer en base al análisis anterior y sus razones. - ESTADO: SIN EMPEZAR - - -.. _ref_solucion: +.. _solucion: Solución adoptada ============================================================================ -TODO +Como hemos visto en :ref:`dgc`, la mejora del recolector de basura puede ser +abordada desde múltiples flancos, con varias alternativas viables. Por lo +tanto, para reducir la cantidad de posibilidades hay que tener en cuenta uno +de los principales objetivos de este trabajo: encontrar una solución que tenga +una buena probabilidad de ser adoptada por el lenguaje, o alguno de sus +compiladores al menos. Para asegurar esto, la solución debe tener un alto +grado de aceptación en la comunidad, lo que implica algunos puntos claves: +* La eficiencia general de la solución no debe ser notablemente peor, en + ningún aspecto, que la implementación actual. +* Los cambios no deben ser drásticos. +* La solución debe atacar de forma efectiva al menos uno de los problemas + principales del recolector actual. +Bajo estos requerimientos, se concluye que probablemente el área más fértil +para explorar sea la falta de concurrencia por cumplir todos estos puntos: -Recolector naive de referencia ----------------------------------------------------------------------------- +* Si bien hay evidencia en la literatura sobre el incremento del tiempo de + ejecución total de ejecución de un programa al usar algoritmos concurrentes, + éste no es, en general, muy grande comparativamente. +* Existen algoritmos de recolección concurrente que no requieren ningún grado + de cooperación por parte del lenguaje o el compilador. +* La falta de concurrencia y los largos tiempos de pausa es una de las + críticas más frecuentes al recolector actual por parte de la comunidad. + +A pesar de ser la concurrencia la veta principal a explorar en este trabajo, +se intenta abordar los demás problemas planteados siempre que sea posible +hacerlo sin alejarse demasiado del objetivo principal. -TODO +.. highlight:: d +.. _sol_bench: -Set de benchmarks y recolección de estadísticas +Banco de pruebas ---------------------------------------------------------------------------- -TODO +Teniendo en cuenta que uno de los objetivos principales es no empeorar la +eficiencia general de forma notable, la confección de un banco de pruebas es +un aspecto fundamental, para poder comprobar con cada cambio que la eficiencia +final no se vea notablemente afectada. +La confección de un banco de pruebas no es una tarea trivial, mucho menos para +un lenguaje con el nivel de fragmentación que tuvo D_ (que hace que a fines +prácticos hayan 3 versiones del lenguaje compitiendo), y cuya masa crítica de +usuarios es de aficionados que usualmente abandonan los proyectos, quedando +obsoletos rápidamente. +Con el objetivo de confeccionar este banco de pruebas, desde el comienzo del +trabajo se han recolectado (usando como fuente principalmente el grupo de +noticias de D_ [#benchmod]_) programas triviales sintetizados con el único +propósito de mostrar problemas con el recolector de basura. Otros programas de +este estilo fueron escritos explícitamente para este trabajo. -Reescritura del GC actual ----------------------------------------------------------------------------- +Además se han recolectado algunos pequeños programas portados de otros +lenguajes de programación, que si bien son pequeños y tienen como objetivo +ejercitar el recolector de basura, son programas reales que resuelven un +problema concreto, lo que otorga un juego de pruebas un poco más amplio que +los programas triviales. -TODO +.. [#benchmod] Cabe destacar que en general todos los programas recolectados + han sido modificados levemente para ajustarlos mejor a las necesidades del + banco de prueba (entre las modificaciones más frecuentes se encuentran la + conversión de Phobos_ a Tango_ y la eliminación de mensajes por salida + estándar). +Pero probablemente lo más importante para confeccionar un banco de pruebas +verdaderamente útil es disponer de programas reales, que hayan sido diseñados +con el único objetivo de hacer su trabajo, sin pensar en como impacta el +recolector sobre ellos (ni ellos sobre el recolector). Estos programas proveen +las pruebas más realistas y amplias. Desgraciadamente no hay muchos programas +reales escritos en D_ disponibles públicamente, y no se encontró en la +comunidad tampoco una muestra de voluntad por compartir programas privados +para usar como banco de pruebas en este trabajo. +Por lo tanto el banco de pruebas que se conformó como una mezcla de estas tres +grandes categorías. -Conversión a "cloning GC" ----------------------------------------------------------------------------- -TODO +.. _sol_bench_synth: +Pruebas sintetizadas +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Este es el juego de programas triviales, escritos con el único objetivo de +ejercitar un área particular y acotada del recolector. -Resultados + +``bigarr`` +^^^^^^^^^^ +Su objetivo es ejercitar la manipulación de arreglos de tamaño considerable +que almacenan objetos de tamaño pequeño o mediano. Esta prueba fue hallada__ +en el grupo de noticias de D_ y escrita por Babele Dunnit y aunque +originalmente fue concebido para mostrar un problema con la concatenación de +arreglos (como se aprecia en la sentencia ``version(loseMemory)``), ejercita +los aspectos más utilizados del del recolector: manipulación de arreglos +y petición e memoria. Es una de las pruebas que más estresa al recolector ya +que todo el trabajo que realiza el programa es utilizar sus servicios. + +Código fuente:: + + const IT = 300; + const N1 = 20_000; + const N2 = 40_000; + + class Individual + { + Individual[20] children; + } + + class Population + { + void grow() + { + foreach (inout individual; individuals) + individual = new Individual; + } + Individual[N1] individuals; + } + + version = loseMemory; + + int main(char[][] args) + { + Population testPop1 = new Population; + Population testPop2 = new Population; + Individual[N2] indi; + for (int i = 0; i < IT; i++) { + testPop1.grow(); + testPop2.grow(); + version (loseMemory) { + indi[] = testPop1.individuals ~ testPop2.individuals; + } + version (everythingOk) { + indi[0 .. N1] = testPop1.individuals; + indi[N1 .. N2] = testPop2.individuals; + } + } + return 0; + } + +__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=54084 + + +``concpu`` y ``conalloc`` +^^^^^^^^^^^^^^^^^^^^^^^^^ +Estos dos programas fueron escritos especialmente para este trabajo con el fin +de ejercitar la interacción entre el recolector y un *mutator* con varios +hilos. La única diferencia entre ellos es que ``concpu`` lanza hilos que hacen +trabajar de forma intensiva el procesador pero que no utilizan servicios del +recolector, salvo en el hilo principal, mientras que ``conalloc`` utiliza +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 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 realizar una tarea que necesite +trabajar con una versión estática de la memoria del programa. + +Se espera ``concpu`` sea capaz de explotar cualquier reducción en el tiempo de +*stop-the-world*, ya que los hilos solo son interrumpidos por este tipo de +pausa. Por otro lado, se espera que ``conalloc`` sea afectado por el tiempo +máximo de pausa, que podrían sufrir los hilos incluso cuando el *mundo* sigue +su marcha, debido al *lock* global del recolector y que los hilos usan +servicios de éste. + +Código fuente de ``concpu``:: + + import tango.core.Thread: Thread; + import tango.core.Atomic: Atomic; + import tango.io.device.File: File; + import tango.util.digest.Sha512: Sha512; + import tango.util.Convert: to; + + auto N = 100; + auto NT = 2; + ubyte[] BYTES; + Atomic!(int) running; + + void main(char[][] args) + { + auto fname = args[0]; + if (args.length > 3) + fname = args[3]; + if (args.length > 2) + NT = to!(int)(args[2]); + if (args.length > 1) + N = to!(int)(args[1]); + N /= NT; + running.store(NT); + BYTES = cast(ubyte[]) File.get(fname); + auto threads = new Thread[NT]; + foreach(ref thread; threads) { + thread = new Thread(&doSha); + thread.start(); + } + while (running.load()) { + auto a = new void[](BYTES.length / 4); + a[] = cast(void[]) BYTES[]; + Thread.yield(); + } + foreach(thread; threads) + thread.join(); + } + + void doSha() + { + auto sha = new Sha512; + for (size_t i = 0; i < N; i++) + sha.update(BYTES); + running.decrement(); + } + +El código de ``conalloc`` es igual excepto por la función ``doSha()``, que es +de la siguiente manera:: + + void doSha() + { + for (size_t i = 0; i < N; i++) { + auto sha = new Sha512; + sha.update(BYTES); + } + running.decrement(); + } + + +``mcore`` +^^^^^^^^^ +Escrito por David Schima y también hallado__ en el grupo de noticias de D_, +este programa pretende mostrar como afecta el *lock* global del recolector +en ambientes *multi-core*, incluso cuando a simple vista parecen no utilizarse +servicios del recolector:: + + import tango.core.Thread; + + void main() + { + enum { nThreads = 4 }; + auto threads = new Thread[nThreads]; + foreach (ref thread; threads) { + thread = new Thread(&doAppending); + thread.start(); + } + foreach (thread; threads) + thread.join(); + } + + void doAppending() + { + uint[] arr; + for (size_t i = 0; i < 1_000_000; i++) + arr ~= i; + } + +__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=103563 + +El secreto está en que la concatenación de arreglos utiliza por detrás +servicios del recolector, por lo tanto un programa multi-hilo en el cual los +hilos (aparentemente) no comparten ningún estado, se puede ver +considerablemente afectado por el recolector (siendo este efecto más visible +en ambientes *multi-core* por el nivel de sincronización extra que significa +a nivel de *hardware*). Cabe destacar, sin embargo, que en Linux_ el efecto no +es tan notorio comparado al reporte de David Schima. + + +``split`` +^^^^^^^^^ +Este programa trivial lee un archivo de texto y genera un arreglo de cadenas +de texto resultantes de partir el texto en palabras. Fue escrito por Leonardo +Maffi y también hallado__ en el grupo de noticias de D_. Su objetivo era +mostrar lo ineficiente que puede ser concatenar datos a un mismo arreglo +repetidas veces y ha desembocado en una pequeña optimización que sirvió para +paliar el problema de forma razonablemente efectiva [PAN09]_. + +Código fuente:: + + import tango.io.device.File: File; + import tango.text.Util: delimit; + import tango.util.Convert: to; + + int main(char[][] args) { + if (args.length < 2) + return 1; + auto txt = cast(byte[]) File.get(args[1]); + auto n = (args.length > 2) ? to!(uint)(args[2]) : 1; + if (n < 1) + n = 1; + while (--n) + txt ~= txt; + auto words = delimit!(byte)(txt, cast(byte[]) " \t\n\r"); + return !words.length; + } + +__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=67673 + + +``rnddata`` +^^^^^^^^^^^ +Este programa fue escrito por Oskar Linde y nuevamente hallado__ en el grupo +de noticias. Fue construido para mostrar como el hecho de que el recolector +sea conservativo puede hacer que al leer datos binarios hayan muchos *falsos +positivos* que mantengan vivas celdas que en realidad ya no deberían ser +accesibles desde el *root set* del grafo de conectividad. + +__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=46407 + +Código fuente:: + + import tango.math.random.Random; + + const IT = 125; // number of iterations, each creates an object + const BYTES = 1_000_000; // ~1MiB per object + const N = 50; // ~50MiB of initial objects + + class C + { + C c; // makes the compiler not set NO_SCAN + long[BYTES/long.sizeof] data; + } + + void main() { + auto rand = new Random(); + C[] objs; + objs.length = N; + foreach (ref o; objs) { + o = new C; + foreach (ref x; o.data) + rand(x); + } + for (int i = 0; i < IT; ++i) { + C o = new C; + foreach (ref x; o.data) + rand(x); + // do something with the data... + } + } + + +``sbtree`` +^^^^^^^^^^ +Este programa está basado en la prueba de nombre ``binary-trees`` de `The +Computer Language Benchmarks Game`__, una colección de 12 programas escritos +en alrededor de 30 lenguajes de programación para comparar su eficiencia +(medida en tiempo de ejecución, uso de memoria y cantidad de líneas de código) +[SHO10]_. De este juego de programas se utilizó solo ``binary-trees`` por ser +el único destinado a ejercitar el manejo de memoria. El programa sólo manipula +árboles binarios, creándolos y recorriéndolos inmediatamente (no realiza +ningún trabajo útil). La traducción a D_ fue realizada por Andrey Khropov +y fue hallada__ en el grupo de noticias. + +__ http://shootout.alioth.debian.org/ +__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=43991 + +Código fuente:: + + import tango.util.Convert; + alias char[] string; + + int main(string[] args) + { + int N = args.length > 1 ? to!(int)(args[1]) : 1; + int minDepth = 4; + int maxDepth = (minDepth + 2) > N ? minDepth + 2 : N; + int stretchDepth = maxDepth + 1; + int check = TreeNode.BottomUpTree(0, stretchDepth).ItemCheck; + TreeNode longLivedTree = TreeNode.BottomUpTree(0, maxDepth); + for (int depth = minDepth; depth <= maxDepth; depth += 2) { + int iterations = 1 << (maxDepth - depth + minDepth); + check = 0; + for (int i = 1; i <= iterations; i++) { + check += TreeNode.BottomUpTree(i, depth).ItemCheck; + check += TreeNode.BottomUpTree(-i, depth).ItemCheck; + } + } + return 0; + } + + class TreeNode + { + TreeNode left, right; + int item; + + this(int item, TreeNode left = null, TreeNode right = null) + { + this.item = item; + this.left = left; + this.right = right; + } + + static TreeNode BottomUpTree(int item, int depth) + { + if (depth > 0) + return new TreeNode(item, + BottomUpTree(2 * item - 1, depth - 1), + BottomUpTree(2 * item, depth - 1)); + return new TreeNode(item); + } + + int ItemCheck() + { + if (left) + return item + left.ItemCheck() - right.ItemCheck(); + return item; + } + } + + +.. _sol_bench_small: + +Programas pequeños +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Todos los pequeños programas utilizados como parte del banco de prueba +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 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 solicitando memoria para almacenar +datos y el resto usando los datos almacenados, por lo que en general están +acotados en tiempo por el uso de memoria (y no de procesador). + +__ 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 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 suspicacia 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. + +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). + + +``bh`` +^^^^^^ +Este programa computa las interacciones gravitatorias entre un número +:math:`N` de cuerpos en tiempo :math:`O(N log N)` y está basado en árboles +heterogéneos de 8 ramas, según el algoritmo descripto por Barnes & Hut +[BH86]_. + +Código fuente disponible en: +http://www.fantascienza.net/leonardo/js/dolden_bh.zip + + +``bisort`` +^^^^^^^^^^ +Este programa ordena :math:`N` números, donde :math:`N` es una potencia de 2, +usando un ordenamiento *Bitonic* adaptativo, un algoritmo paralelo óptimo para +computadoras con memoria compartida, según describen Bilardi & Nicolau +[BN98]_. Utiliza árboles binarios como principal estructuras de datos. + +Código fuente disponible en: +http://www.fantascienza.net/leonardo/js/dolden_bisort.zip + + +``em3d`` +^^^^^^^^ +Este programa modela la propagación de ondas electromagnéticas a través de +objetos en 3 dimensiones. Realiza un cálculo simple sobre un grafo irregular +bipartito (implementado utilizando listas simplemente enlazadas) cuyos nodos +representan valores de campo eléctrico y magnético. El algoritmo es el +descripto por Culler, et al. [CDG93]_. + +Código fuente disponible en: +http://www.fantascienza.net/leonardo/js/dolden_em3d.zip + + +``tsp`` +^^^^^^^ +Este programa implementa una heurística para resolver el problema del viajante +(*traveling salesman problem*) utilizando árboles binarios balanceados. El +algoritmo utilizado es el descripto por Karp [KAR77]_. + + +Código fuente disponible en: +http://www.fantascienza.net/leonardo/js/dolden_tsp.zip + + +``voronoï`` +^^^^^^^^^^^ +Este programa genera un conjunto aleatorio de puntos y computa su diagrama de +Voronoï, una construcción geométrica que permite construir una partición del +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* +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Dil_ (escrito en su mayor parte por Aziz Köksal y publicado bajo licencia +GPL_) es, lamentablemente, el único programa real hallado que, a pesar de +estar incompleto, es lo suficientemente grande, mantenido y estable como para +ser incluido en el banco de pruebas. Se trata de un compilador de D_ escrito +en D_ y está incompleto porque no puede generar código (falta implementar el +análisis semántico y la generación de código). Es principalmente utilizado +para generar documentación a partir del código. + +El programa está compuesto por: + +* 32.000 líneas de código fuente (aproximadamente). +* 86 módulos (o archivos). +* 322 diferentes tipos de datos definidos por el usuario, de los cuales 34 son + tipos *livianos* (``struct``) y 288 tipos polimórficos (``class``), de los + que 260 son subtipos (sub-clases). + +Puede observarse entonces que a pesar de ser incompleto, es una pieza de +software bastante compleja y de dimensión considerable. + +Además, al interpretar código fuente se hace un uso intensivo de cadenas de +texto que en general presentan problemas muy particulares por poder ser +objetos extremadamente pequeños y de tamaños poco convencionales (no múltiplos +de palabras, por ejemplo). A su vez, el texto interpretado es convertido a una +representación interna en forma de árbol (o *árbol de sintaxis abstracta*) +modelado por tipos *livianos* y polimórficos que están organizados en arreglos +dinámicos contiguos y asociativos (que usan muchos servicios del recolector). +Finalmente estos objetos son manipulados para obtener y generar la información +necesaria, creando y dejando de usar objetos constantemente (pero no como +única forma de procesamiento, como otras pruebas sintetizadas). + +Por último, a diferencia de muchos otros programas escritos en D_, que dadas +algunas de las ineficiencias del recolector invierten mucho trabajo en limitar +su uso, este programa no está escrito pensando en dichas limitaciones, por lo +que muestra un funcionamiento muy poco sesgado por estas infortunadas +circunstancias. + +Por todas estas razones, Dil_ es el ejemplar que tal vez mejor sirve a la hora +de medir de forma realista los resultados obtenidos o los avances realizados. +Si bien, como se ha dicho anteriormente, las demás pruebas del banco pueden +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. + + +.. highlight:: pcode + +.. _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` más adelante para más detalles sobre + la utilidad de esta opción. + +``min_free`` + El valor de esta opción indica el porcentaje mínimo 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` más adelante 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` más adelante + 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` más adelante 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` más adelante 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` más adelante. + +``eager_alloc`` + Esta opción booleana (activada por omisión), sólo puede estar activa si + ``fork`` también lo está 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` más + adelante 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` más adelante 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 ./prog + +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. En esencia es una extensión a una de las optimizaciones +propuestas por Vladimir Panteleev [PAN09]_, que propone un caché global para +todo el recolector en vez de uno por *pool*. + +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, lo que 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. La conversión a puramente +recursivo resulta impracticable dado que desemboca 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). 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``. + +.. flt:: 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 el 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 proveen 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 [#solwaste]_ 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 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 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Para agregar el soporte de marcado preciso se aprovecha el trabajo realizado +por Vincent Lang (ver :ref:`dgc_via_art`) [DBZ3463]_, gracias a que se basa en +`D 1.0`_ y Tango_, al igual que este trabajo. Dado el objetivo y entorno +común, se abre la posibilidad de adaptar sus cambios a este trabajo, +utilizando una versión modificada de DMD_ (dado que los cambios aún no están +integrados al compilador oficial todavía). + +.. TODO: Apéndice con parches a DMD y Tango? + +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. + +.. flt:: fig:sol-ptrmap + :type: table + + 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: + +.. code-block:: d + + 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. + +.. flt:: 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``. + +.. flt:: 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_ptrmap = [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(word_pos, 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_ptrmap // + 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_ptrmap) // Agregado + + function mark_stacks() is + foreach thread in threads + mark_range(thread.stack.begin, thread.stack.end, + global conservative_ptrmap) // Agregado + + function mark_user_roots() is + foreach root_range in user_roots + mark_range(root_range.begin, root_range.end, + global conservative_ptrmap) // 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 *COW* (de *copy-on-write* en inglés, *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 crea +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 del 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; una celda que pasó a estar *muerta* luego de +que se inicie la fase de marcado, pero antes de que termine, puede no ser +reciclada 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 necesario 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() + fflush(null) // evita que se duplique la salida de los FILE* abiertos + child_pid = fork() + 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() + fflush(null) + child_pid = fork() + 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 3 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 un 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`` también esté activada (ver +:ref:`sol_eager_alloc`), 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() + fflush(null) + child_pid = fork() + 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 +---------------------------------------------------------------------------- + +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) utilizando + 4 hilos (más el principal). + +``split`` + ``bible.txt 2`` + + Procesa dos veces un archivo de texto plano (de 4MiB de tamaño). + +``sbtree`` + ``16`` + + Construye á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_. + +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 + +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(1)`, 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. + +.. flt:: t:sol-setarch + :type: table + + 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. + + .. subflt:: + + 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 + ======== ======== ======== ======== + + .. subflt:: + + 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 + ======== ======== ======== ======== + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-bigarr-1cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-bigarr-1cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-bigarr-1cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-bigarr-1cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-bigarr-1cpu.pdf + +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. + +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 +positivos* 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. + + + +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`` +^^^^^^^^^^ +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). + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-bigarr-4cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-bigarr-4cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-bigarr-4cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-bigarr-4cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-bigarr-4cpu.pdf + +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`). + +.. raw:: latex + + \clearpage + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-concpu-1cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-concpu-1cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-concpu-1cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-concpu-1cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-concpu-1cpu.pdf + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-concpu-4cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-concpu-4cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-concpu-4cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-concpu-4cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-concpu-4cpu.pdf + +``concpu`` +^^^^^^^^^^ +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* (si se utiliza vuelve a aumentar, +incluso más que sin marcado concurrente). + +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. + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-conalloc-1cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-conalloc-1cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-conalloc-1cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-conalloc-1cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-conalloc-1cpu.pdf + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-conalloc-4cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-conalloc-4cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-conalloc-4cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-conalloc-4cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-conalloc-4cpu.pdf + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-split-1cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-split-1cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-split-1cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-split-1cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-split-1cpu.pdf + +``conalloc`` +^^^^^^^^^^^^ +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`` +^^^^^^^^^ +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. + +.. raw:: latex + + \clearpage + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-mcore-1cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-mcore-1cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-mcore-1cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-mcore-1cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-mcore-1cpu.pdf + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-mcore-4cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-mcore-4cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-mcore-4cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-mcore-4cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-mcore-4cpu.pdf + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-rnddata-1cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-rnddata-1cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-rnddata-1cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-rnddata-1cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-rnddata-1cpu.pdf + +``mcore`` +^^^^^^^^^ +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 un +incremento, 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`` +^^^^^^^^^^^ +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 positivos* (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 positivos*, 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 positivos*, 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. + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-bh-1cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-bh-1cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-bh-1cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-bh-1cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-bh-1cpu.pdf + +.. raw:: latex + + \clearpage + + +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`` +^^^^^^ +.. flt:: t:sol-prec-mem-bh + :type: table + + 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%) + ============== ============== ============== ================= + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-bisort-1cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-bisort-1cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-bisort-1cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-bisort-1cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-bisort-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`). + +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`` +^^^^^^^^^^ +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 de forma conservativa, 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. + +.. raw:: latex + + \clearpage + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-em3d-1cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-em3d-1cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-em3d-1cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-em3d-1cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-em3d-1cpu.pdf + +``em3d`` +^^^^^^^^ +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. + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-tsp-1cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-tsp-1cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-tsp-1cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-tsp-1cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-tsp-1cpu.pdf + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-voronoi-1cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-voronoi-1cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-voronoi-1cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-voronoi-1cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-voronoi-1cpu.pdf + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-voronoi-4cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-voronoi-4cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-voronoi-4cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-voronoi-4cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-voronoi-4cpu.pdf + +``tsp`` +^^^^^^^^ +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`` +^^^^^^^^^^^ +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 +positivos* 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 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. flt:: 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-dil-1cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-dil-1cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-dil-1cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-dil-1cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-dil-1cpu.pdf + +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`` +^^^^^^^ +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. + +.. flt:: fig:sol-dil-4cpu + :placement: t + + 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). + + .. subflt:: + + Tiempo de ejecución (seg) + + .. image:: plots/time-dil-4cpu.pdf + + .. subflt:: + + Cantidad de recolecciones + + .. image:: plots/ncol-dil-4cpu.pdf + + .. subflt:: + + Uso máximo de memoria (MiB) + + .. image:: plots/mem-dil-4cpu.pdf + + .. subflt:: + + *Stop-the-world* máximo (seg) + + .. image:: plots/stw-dil-4cpu.pdf + + .. subflt:: + + Pausa real máxima (seg) + + .. image:: plots/pause-dil-4cpu.pdf + +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. + +.. flt:: t:sol-prec-mem-dil + :type: table + :placement: b + + 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%) + ============== ============== ============== ================= + +El pequeño incremento en el tiempo total de ejecución podría estar dado por la +mayor probabilidad de tener *falsos positivos* 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. + +También se puede observar una gran disminución del tiempo total de ejecución +al empezar a usar *eager allocation* (cerca de un 60%, y más de un 200% +comparado con TBGC), 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 de +manera oficial 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_, por lo que se han +publicado los cambios necesarios en el sistema de seguimiento de mejoras +y se encuentran actualmente en etapa de revisión [TT1997]_. +.. include:: links.rst -.. vim: set ts=2 sts=2 sw=2 et tw=75 : +.. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :