X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/887c4e445a96c5ad78db58117fd499c845ee8afe..3a178d636cec3c614651192513240e92d8bce4e9:/source/solucion.rst diff --git a/source/solucion.rst b/source/solucion.rst index d2184c1..7cf64b7 100644 --- a/source/solucion.rst +++ b/source/solucion.rst @@ -1,20 +1,16 @@ -.. Acá va lo que decidí hacer en base al análisis anterior y sus razones. - ESTADO: EMPEZADO - - .. _solucion: Solución adoptada ============================================================================ -Como hemos visto en :ref:`dgc_bad`, la mejora del recolector de basura puede -ser abordada desde múltiples flancos. 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: +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. @@ -38,6 +34,8 @@ se intenta abordar los demás problemas planteados siempre que sea posible hacerlo sin alejarse demasiado del objetivo principal. +.. highlight:: d + .. _sol_bench: Banco de pruebas @@ -141,8 +139,8 @@ El código fuente del programa es el siguiente:: indi[] = testPop1.individuals ~ testPop2.individuals; } version (everythingOk) { - indi[0..N1] = testPop1.individuals; - indi[N1..N2] = testPop2.individuals; + indi[0 .. N1] = testPop1.individuals; + indi[N1 .. N2] = testPop2.individuals; } } return 0; @@ -309,7 +307,7 @@ __ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&art 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 -punteros* que mantengan vivas celdas que en realidad ya no deberían ser +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 @@ -562,6 +560,8 @@ 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 @@ -883,7 +883,7 @@ Probablemente el caso más significativo, y por tanto el único que vale la pena mencionar, es la conversión de marcado iterativo a marcado recursivo y luego a un esquema híbrido. Como se describe en :ref:`dgc_bad`, el marcado iterativo tiene sus ventajas, pero tiene desventajas también. Al convertirlo a puramente -recursivo, se impracticable por resultar en errores de desbordamiento de pila. +recursivo, es impracticable por resultar en errores de desbordamiento de pila. Por lo tanto se prueba con un esquema híbrido, poniendo un límite a la recursividad, volviendo al algoritmo iterativo cuando se alcanza este límite. @@ -931,10 +931,10 @@ puede ver, por ejemplo, el tiempo total de ejecución de Dil_ al generar la documentación completa del código de Tango_, según varía el valor de ``MAX_DEPTH``. -.. fig:: fig:sol-mark-rec +.. flt:: fig:sol-mark-rec Análisis de tiempo total de ejecución en función del valor de - ``MAX_DEPTH``. + ``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 @@ -1084,18 +1084,14 @@ recolector. Marcado preciso ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -En paralelo con este trabajo, David Simcha comienza a explorar la posibilidad -de agregar precisión parcial al recolector, generando información sobre la -ubicación de los punteros para cada tipo [DBZ3463]_. Su trabajo se limita -a una implementación a nivel biblioteca de usuario y sobre `D 2.0`_. -Desafortunadamente su trabajo pasa desapercibido por un buen tiempo. +Para agregar el soporte de marcado preciso se aprovecha el trabajo realizado +por Vincent Lang (ver :ref:`dgc_via_art`) [DBZ3463]_, dado 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 son integrados al +compilador oficial). -Luego Vincent Lang (mejor conocido como *wm4* en la comunidad de D_), retoma -este trabajo, pero modificando el compilador DMD_ y trabajando con `D 1.0`_ -y Tango_, al igual que este trabajo. Dado el objetivo y entorno común, se abre -la posibilidad de adaptar los cambios de Vincent Lang a este trabajo, -utilizando una versión modificada de DMD_ (dado que los cambios aún no son -integrados al compilador oficial). +.. TODO: Apéndice con parches a DMD y Tango? Información de tipos provista por el compilador ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -1105,9 +1101,10 @@ memoria. Esta información se pasa como un puntero a un arreglo de palabras con la estructura mostrada en la figura :vref:`fig:sol-ptrmap` y que se describe a continuación. -.. fig:: fig:sol-ptrmap +.. flt:: fig:sol-ptrmap + :type: table - Estructura de la información de tipos provista por el compilador. + Estructura de la información de tipos provista por el compilador .. aafig:: :scale: 110 @@ -1137,7 +1134,9 @@ a continuación. 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:: +con un ejemplo. Dada la estructura: + +.. code-block:: d union U { ubyte ub; @@ -1167,9 +1166,9 @@ palabra sea realmente un puntero, pero indica que debe ser escaneado. El recolector debe debe ser conservativo en este caso, y escanear esa palabra como si fuera un puntero. -.. fig:: fig:sol-ptrmap-example +.. flt:: fig:sol-ptrmap-example - Ejemplo de estructura de información de tipos generada para el tipo ``S``. + Ejemplo de estructura de información de tipos generada para el tipo ``S`` .. aafig:: :textual: @@ -1227,10 +1226,10 @@ ese caso no hace falta directamente escanear ninguna palabra del bloque. En la figura :vref:`fig:sol-ptrmap-blk` se puede ver, como continuación del ejemplo anterior, como se almacenaría en memoria un objeto del tipo ``S``. -.. fig:: fig:sol-ptrmap-blk +.. flt:: fig:sol-ptrmap-blk Ejemplo de bloque que almacena un objeto de tipo ``S`` con información de - tipo. + tipo .. aafig:: :scale: 110 @@ -1381,11 +1380,12 @@ que la memoria sea compartida entre los procesos de forma explícita. Esto, sin embargo, no significa que la memoria física sea realmente duplicada; en general todos los sistemas operativos modernos (como Linux_) utilizan una -técnica llamada *copy-on-write* (*copiar-al-escribir* en castellano) que -retrasa la copia de memoria hasta que alguno de los dos procesos escribe en un -segmento. Recién en ese momento el sistema operativo realiza la copia de **ese -segmento solamente**. Es por esto que la operación puede ser muy eficiente, -y la copia de memoria es proporcional a la cantidad de cambios que hayan. +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 crear @@ -1584,7 +1584,7 @@ empezar la fase de marcado no sean barridas por tener ese bit activo:: pages = assign_pages(pool, number_of_pages) pages[0].block.free = true // Agregado pages[0].block_size = PAGE - foreach page in pages[1..end] + foreach page in pages[1 .. end] page.block_size = CONTINUATION return pages[0] @@ -1909,8 +1909,6 @@ que se especifique lo contrario), que se detallan a continuación. ``$dst_dir`` es el directorio donde almacenar los archivos generados y ``$tango_files`` es la lista de archivos fuente de Tango_. -.. highlight:: d - El resto de los programas se ejecutan sin parámetros (ver :ref:`sol_bench` para una descripción detallada sobre cada uno). @@ -1966,8 +1964,6 @@ todo conservative=0:fork=1:early_collect=1:eager_alloc=1 -.. highlight:: d - Métricas utilizadas ^^^^^^^^^^^^^^^^^^^ Para analizar los resultados se utilizan varias métricas. Las más importantes @@ -2055,37 +2051,10 @@ En los casos donde se utilizan otro tipo de métricas para evaluar aspectos particulares sobre alguna modificación se describe como se realiza la medición donde se utiliza la métrica especial. -Variabilidad de los resultados entre ejecuciones -^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ -Es de esperarse que haya una cierta variación en los resultados entre -corridas, dada la indeterminación inherente a los sistemas operativos de -tiempo compartido, que compiten por los recursos de la computadora. +.. flt:: t:sol-setarch + :type: table -Para minimizar esta variación se utilizan varias herramientas. En primer -lugar, se corren las pruebas estableciendo máxima prioridad (-19 en Linux_) al -proceso utilizando el comando :manpage:`nice(1)`. La variación en la -frecuencia del reloj los procesadores (para ahorrar energía) puede ser otra -fuente de variación, por lo que se usa el comando :manpage:`cpufreq-set(1)` -para establecer la máxima frecuencia disponible de manera fija. - -Sin embargo, a pesar de tomar estas precauciones, se sigue observando una -amplia variabilidad entre corridas. Además se observa una variación más -importante de la esperada no solo en el tiempo, también en el consumo de -memoria, lo que es más extraño. Esta variación se debe principalmente a que -Linux_ asigna el espacio de direcciones a los procesos con una componente -azarosa (por razones de seguridad). Además, por omisión, la llamada al sistema -:manpage:`mmap(2)` asigna direcciones de memoria altas primero, entregando -direcciones más bajas en llamadas subsiguientes [LWN90311]_. - -El comando :manpage:`setarch(8)` sirve para controlar éste y otros aspectos de -Linux_. La opción ``-L`` hace que se utilice un esquema de asignación de -direcciones antiguo, que no tiene una componente aleatoria y asigna primero -direcciones bajas. La opción ``-R`` solamente desactiva la componente azarosa -al momento de asignar direcciones. - -.. ftable:: t:sol-setarch - - Variación entre corridas para TBGC. + Variación entre corridas para TBGC 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 @@ -2093,7 +2062,7 @@ al momento de asignar direcciones. realizarse utilizando el desvío estándar en vez de la amplitud máxima, pero en este cuadro se quiere ilustrar la variación máxima, no la típica. - .. subtable:: + .. subflt:: Del tiempo total de ejecución. @@ -2115,7 +2084,7 @@ al momento de asignar direcciones. voronoi 0.886 0.003 0.006 ======== ======== ======== ======== - .. subtable:: + .. subflt:: Del consumo máximo de memoria. @@ -2137,197 +2106,164 @@ al momento de asignar direcciones. voronoi 0.001 0.000 0.000 ======== ======== ======== ======== -Ambas opciones, reducen notablemente la variación en los resultados (ver -cuadro :vref:`t:sol-setarch`). Esto probablemente se debe a la naturaleza -conservativa del recolector, dado que la probabilidad de tener *falsos -punteros* depende directamente de los valores de las direcciones de memoria, -aunque las pruebas en la que hay concurrencia involucrada, se siguen viendo -grandes variaciones, que probablemente estén vinculadas a problemas de -sincronización que se ven expuestos gracias al indeterminismo inherente a los -programas multi-hilo. - -Si bien se obtienen resultados más estables utilizando un esquema diferente al -utilizado por omisión, se decide no hacerlo dado que las mediciones serían -menos realistas. Los usuarios en general no usan esta opción y se presentaría -una visión más acotada sobre el comportamiento de los programas. Sin embargo, -para evaluar el este efecto en los resultados, siempre que sea posible se -analizan los resultados de un gran número de corridas observando -principalmente su mínima, media, máxima y desvío estándar. +.. flt:: fig:sol-bigarr-1cpu -.. Tamaño del ejecutable (XXX: SEGUN LAS PRUEBAS NO FUCKING CAMBIA!!!) - El tamaño del ejecutable es un factor importante. Cuanto más grande es el - ejecutable, más parecieran variar los resultados. Por ejemplo se observa un - incremento de la estabilidad de los resultados al eliminar toda información - de depuración (*debug*) del ejecutable, utilizando el comando - :manpage:`strip(1)` (*stripped*). En el cuadro :vref:`t:sol-exesize-tbgc` - se puede ver la reducción del tamaño del ejecutable para TBGC cuando se - elimina la información de depuración (4.25 veces más chico en promedio), - mientas que en el cuadro :vref:`t:sol-exesize-cdgc` se puede ver CDGC (4.6 - veces más chico en promedio). - .. ftable:: t:sol-exesize-tbgc - Reducción del tamaño del ejecutable para TBGC. - ======== ======== ======== ============== - Nombre Debug Stripped Debug/Stripped - ======== ======== ======== ============== - bh 586517 138060 4.248 - bigarr 547687 192004 2.852 - bisort 485857 115164 4.219 - conalloc 616613 149848 4.115 - concpu 616575 149848 4.115 - dil 7293277 1859208 3.923 - em3d 505019 116324 4.341 - mcore 461767 105748 4.367 - rnddata 2832935 1492588 1.898 - sbtree 526402 129860 4.054 - split 589353 144308 4.084 - tree 462009 105844 4.365 - tsp 544901 128412 4.243 - voronoi 601259 141112 4.261 - ======== ======== ======== ============== - .. ftable:: t:sol-exesize-cdgc - Reducción del tamaño del ejecutable para CDGC. - ======== ======== ======== =============== - Nombre Debug Stripped Debug/Stripped - ======== ======== ======== =============== - bh 736115 159884 4.604 - bigarr 697406 213832 3.261 - bisort 635537 136988 4.639 - conalloc 766328 171676 4.464 - concpu 766294 171676 4.464 - dil 7442657 1881028 3.957 - em3d 658827 142248 4.632 - mcore 611486 127576 4.793 - rnddata 2986736 1518512 1.967 - sbtree 680217 155784 4.366 - split 739072 166136 4.449 - tree 611728 127672 4.791 - tsp 694581 150236 4.623 - voronoi 750847 162936 4.608 - ======== ======== ======== =============== - TODO: Mostrar tiempos de corridas. - - -.. Resultados generales - ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - -.. Primero se presenta una visión global de los resultados, utilizando las - métricas más importantes. Para generar los gráficos se utilizan los valores - máximos (en blanco), mínimos (en negro), media y desvío estándar (en gris) - calculados en base a, como mínimo, 20 corridas (para algunos casos se hacen - hasta 50 corridas). - - -Resultados para pruebas sintizadas -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - -A continuación se presentan los resultados obtenidos para las pruebas -sintetizadas (ver :ref:`sol_bench_synth`). Se recuerda que este conjunto de -resultados es útil para analizar ciertos aspectos puntuales de las -modificaciones propuestas, pero en general distan mucho de como se comporta un -programa real, por lo que los resultados deben ser analizados teniendo esto -presente. - -``bigarr`` -^^^^^^^^^^ -.. fig:: fig:sol-bigarr-1cpu - - Resultados para ``bigarr`` (utilizando 1 procesador). + Resultados para ``bigarr`` (utilizando 1 procesador) Resultados para ``bigarr`` (utilizando 1 procesador). Se presenta el mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución) o 20 corridas (para el resto). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-bigarr-1cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-bigarr-1cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-bigarr-1cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-bigarr-1cpu.pdf - .. subfig:: + .. subflt:: Pausa real máxima (seg) .. image:: plots/pause-bigarr-1cpu.pdf -.. fig:: fig:sol-bigarr-4cpu +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. - Resultados para ``bigarr`` (utilizando 4 procesadores). +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). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-bigarr-4cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-bigarr-4cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-bigarr-4cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-bigarr-4cpu.pdf - .. subfig:: + .. subflt:: Pausa real máxima (seg) .. image:: plots/pause-bigarr-4cpu.pdf -En la figura :vref:`fig:sol-bigarr-1cpu` se pueden observar los resultados -para ``bigarr`` al utilizar un solo procesador. En ella se puede notar que el -tiempo total de ejecución en general aumenta al utilizar CDGC, esto es -esperable, dado esta prueba se limitan a usar servicios del recolector. Dado -que esta ejecución utiliza solo un procesador y por lo tanto no se puede sacar -provecho a la concurrencia, es de esperarse que el trabajo extra realizado por -las modificaciones se vea reflejado en los resultados. En la -:vref:`fig:sol-bigarr-4cpu` (resultados al utilizar 4 procesadores) se puede -observar como al usar solamente *eager allocation* se recupera un poco el -tiempo de ejecución, probablemente debido al incremento en la concurrencia -(aunque no se observa el mismo efecto al usar *early collection*). - -Observando el tiempo total de ejecución, no se esperaba un incremento tan -notorio al pasar de TBGC a una configuración equivalente de CDGC **cons**, -haciendo un breve análisis de las posibles causas, lo más probable parece ser -el incremento en la complejidad de la fase de marcado dada capacidad para -marcar de forma precisa (aunque no se use la opción, se paga el precio de la -complejidad extra y sin obtener los beneficios). Además se puede observar -como el agregado de precisión al marcado mejora un poco las cosas (donde sí se -obtiene rédito de la complejidad extra en el marcado). - En general se observa que al usar *eager allocation* el consumo de memoria y los tiempos de pausa se disparan mientras que la cantidad de recolecciones disminuye drásticamente. Lo que se observa es que el programa es @@ -2346,86 +2282,90 @@ incremento en el consumo de memoria, ya que el sistema operativo tiene que copiar tablas de memoria más grandes al efectuar el *fork* (ver :ref:`sol_fork`). -``concpu`` -^^^^^^^^^^ -.. fig:: fig:sol-concpu-1cpu +.. raw:: latex - Resultados para ``concpu`` (utilizando 1 procesador). + \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). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-concpu-1cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-concpu-1cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-concpu-1cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-concpu-1cpu.pdf - .. subfig:: + .. subflt:: Pausa real máxima (seg) .. image:: plots/pause-concpu-1cpu.pdf -.. fig:: fig:sol-concpu-4cpu +.. flt:: fig:sol-concpu-4cpu - Resultados para ``concpu`` (utilizando 4 procesadores). + Resultados para ``concpu`` (utilizando 4 procesadores) Resultados para ``concpu`` (utilizando 4 procesadores). Se presenta el mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución) o 20 corridas (para el resto). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-concpu-4cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-concpu-4cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-concpu-4cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-concpu-4cpu.pdf - .. subfig:: + .. 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 @@ -2470,143 +2410,143 @@ Sin embargo, no se encuentra una razón clara para explicar el crecimiento dramático en la cantidad de recolecciones solo al no usar marcado concurrente para 4 procesadores. -``conalloc`` -^^^^^^^^^^^^ -.. fig:: fig:sol-conalloc-1cpu +.. flt:: fig:sol-conalloc-1cpu - Resultados para ``conalloc`` (utilizando 1 procesador). + Resultados para ``conalloc`` (utilizando 1 procesador) Resultados para ``conalloc`` (utilizando 1 procesador). Se presenta el mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución) o 20 corridas (para el resto). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-conalloc-1cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-conalloc-1cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-conalloc-1cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-conalloc-1cpu.pdf - .. subfig:: + .. subflt:: Pausa real máxima (seg) .. image:: plots/pause-conalloc-1cpu.pdf -.. fig:: fig:sol-conalloc-4cpu +.. flt:: fig:sol-conalloc-4cpu - Resultados para ``conalloc`` (utilizando 4 procesadores). + Resultados para ``conalloc`` (utilizando 4 procesadores) Resultados para ``conalloc`` (utilizando 4 procesadores). Se presenta el mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución) o 20 corridas (para el resto). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-conalloc-4cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-conalloc-4cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-conalloc-4cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-conalloc-4cpu.pdf - .. subfig:: + .. subflt:: Pausa real máxima (seg) .. image:: plots/pause-conalloc-4cpu.pdf -En la figura :vref:`fig:sol-conalloc-1cpu` se pueden observar los resultados -para ``conalloc`` al utilizar un solo procesador. Los cambios con respecto -a lo observado para ``concpu`` son mínimos. El efecto de la mejoría al usar -marcado concurrente pero no *eager allocation* no se observa más, dado que -``conalloc`` pide memoria en todos los hilos, se crea un cuello de botella. Se -ve claramente como tampoco baja la cantidad de recolecciones hecha debido -a esto y se invierte la variabilidad entre los tiempos pico de pausa real -y *stop-the-world* (sin una razón obvia, pero probablemente relacionado que -todos los hilos piden memoria). - -Al utilizar 4 procesadores (figura :vref:`fig:sol-conalloc-4cpu`), más allá de -las diferencias mencionadas para 1 procesador, no se observan grandes cambios -con respecto a lo observado para ``concpu``, excepto que los tiempos de pausa -(real y *stop-the-world*) son notablemente más pequeños, lo que pareciera -confirmar un error en la medición de ``concpu``. - -``split`` -^^^^^^^^^ -.. fig:: fig:sol-split-1cpu +.. flt:: fig:sol-split-1cpu - Resultados para ``split`` (utilizando 1 procesador). + Resultados para ``split`` (utilizando 1 procesador) Resultados para ``split`` (utilizando 1 procesador). Se presenta el mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución) o 20 corridas (para el resto). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-split-1cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-split-1cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-split-1cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-split-1cpu.pdf - .. subfig:: + .. 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 @@ -2625,145 +2565,149 @@ incluso al usar *eager allocation*. Se omiten los resultados para más de un procesador por ser prácticamente idénticos para este análisis. -``mcore`` -^^^^^^^^^ -.. fig:: fig:sol-mcore-1cpu +.. raw:: latex - Resultados para ``mcore`` (utilizando 1 procesador). + \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). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-mcore-1cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-mcore-1cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-mcore-1cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-mcore-1cpu.pdf - .. subfig:: + .. subflt:: Pausa real máxima (seg) .. image:: plots/pause-mcore-1cpu.pdf -.. fig:: fig:sol-mcore-4cpu +.. flt:: fig:sol-mcore-4cpu - Resultados para ``mcore`` (utilizando 4 procesadores). + Resultados para ``mcore`` (utilizando 4 procesadores) Resultados para ``mcore`` (utilizando 4 procesadores). Se presenta el mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución) o 20 corridas (para el resto). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-mcore-4cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-mcore-4cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-mcore-4cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-mcore-4cpu.pdf - .. subfig:: + .. subflt:: Pausa real máxima (seg) .. image:: plots/pause-mcore-4cpu.pdf -El caso de ``mcore`` es interesante por ser, funcionalmente, una combinación -entre ``concpu`` y ``split``, con un agregado extra: el incremento notable de -la competencia por utilizar el recolector entre los múltiples hilos. - -Los efectos observados (en la figura :vref:`fig:sol-mcore-1cpu` para -1 procesador y en la figura :vref:`fig:sol-mcore-4cpu` para 4) confirman esto, -al ser una suma de los efectos observados para ``concpu`` y ``split``, con el -agregado de una particularidad extra por la mencionada competencia entre -hilos. A diferencia de ``concpu`` donde el incremento de procesadores resulta -en un decremento en el tiempo total de ejecución, en este caso resulta en una -disminución, dado que se necesita mucha sincronización entre hilos, por -utilizar todos de forma intensiva los servicios del recolector (y por lo tanto -competir por su *lock* global). - -Otro efecto común observado es que cuando el tiempo de pausa es muy pequeño -(del orden de los milisegundos), el marcado concurrente suele incrementarlo en -vez de disminuirlo. - -``rnddata`` -^^^^^^^^^^^ -.. fig:: fig:sol-rnddata-1cpu +.. flt:: fig:sol-rnddata-1cpu - Resultados para ``rnddata`` (utilizando 1 procesador). + Resultados para ``rnddata`` (utilizando 1 procesador) Resultados para ``rnddata`` (utilizando 1 procesador). Se presenta el mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución) o 20 corridas (para el resto). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-rnddata-1cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-rnddata-1cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-rnddata-1cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-rnddata-1cpu.pdf - .. subfig:: + .. 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 una +disminución, dado que se necesita mucha sincronización entre hilos, por +utilizar todos de forma intensiva los servicios del recolector (y por lo tanto +competir por su *lock* global). + +Otro efecto común observado es que cuando el tiempo de pausa es muy pequeño +(del orden de los milisegundos), el marcado concurrente suele incrementarlo en +vez de disminuirlo. + +``rnddata`` +^^^^^^^^^^^ 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 @@ -2786,12 +2730,12 @@ pagar si se necesitan tiempos de pausa muy pequeños). El aumento en el variación de los tiempos de ejecución al usar marcado preciso probablemente se debe a lo siguiente: con marcado conservativo, debe estar sobreviviendo a las recolecciones el total de memoria pedida por el programa, -debido a falsos punteros (por eso no se observa prácticamente variación en el +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 punteros, pero el +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 punteros, variando así la cantidad de +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 @@ -2807,79 +2751,67 @@ 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 pruebas pequeñas -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - -A continuación se presentan los resultados obtenidos para las pruebas pequeñas -(ver :ref:`sol_bench_small`). Se recuerda que si bien este conjunto de pruebas -se compone de programas reales, que efectúan una tarea útil, están diseñados -para ejercitar la asignación de memoria y que no son recomendados para evaluar -el desempeño de recolectores de basura. Sin embargo se las utiliza igual por -falta de programas más realistas, por lo que hay que tomarlas como un grado de -suspicacia. - -``bh`` -^^^^^^ -.. fig:: fig:sol-bh-1cpu - - Resultados para ``bh`` (utilizando 1 procesador). + Resultados para ``bh`` (utilizando 1 procesador) Resultados para ``bh`` (utilizando 1 procesador). Se presenta el mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución) o 20 corridas (para el resto). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-bh-1cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-bh-1cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-bh-1cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-bh-1cpu.pdf - .. subfig:: + .. subflt:: Pausa real máxima (seg) .. image:: plots/pause-bh-1cpu.pdf -En la figura :vref:`fig:sol-bh-1cpu` se pueden observar los resultados -para ``bh`` al utilizar un solo procesador. Ya en una prueba un poco más -realista se puede observar el efecto positivo del marcado preciso, en especial -en la cantidad de recolecciones efectuadas (aunque no se traduzca en un menor -consumo de memoria). +.. raw:: latex -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`). + \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. -.. ftable:: t:sol-prec-mem-bh +``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 Memoria pedida y asignada para ``bh`` según modo de marcado conservativo o preciso (acumulativo durante toda la vida del programa). @@ -2891,55 +2823,72 @@ opción ``malloc_stats_file`` (ver :ref:`sol_stats`). Preciso 302.54 472.26 169.72 (36%) ============== ============== ============== ================= -Más allá de esto, los resultados son muy similares a los obtenidos para -pruebas sintetizadas que se limitan a ejercitar el recolector (como ``bigarr`` -y ``sbtree``), lo que habla de lo mucho que también lo hace este pequeño -programa. - -No se muestran los resultados para más de un procesador por ser extremadamente -similares a los obtenidos utilizando solo uno. - -``bisort`` -^^^^^^^^^^ -.. fig:: fig:sol-bisort-1cpu +.. flt:: fig:sol-bisort-1cpu - Resultados para ``bisort`` (utilizando 1 procesador). + Resultados para ``bisort`` (utilizando 1 procesador) Resultados para ``bisort`` (utilizando 1 procesador). Se presenta el mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución) o 20 corridas (para el resto). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-bisort-1cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-bisort-1cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-bisort-1cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-bisort-1cpu.pdf - .. subfig:: + .. 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 @@ -2949,54 +2898,58 @@ caché de ``findSize()``). Otra diferencia notable es la considerable reducción del tiempo de pausa real al utilizar *early collection* (más de 3 veces menor en promedio comparado -a cuando se marca conservativamente, y más de 2 veces menor que cuando se hace -de forma precisa), lo que indica que la predicción de cuando se va a necesitar -una recolección es más efectiva que para ``split``. +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. -``em3d`` -^^^^^^^^ -.. fig:: fig:sol-em3d-1cpu +.. raw:: latex + + \clearpage - Resultados para ``em3d`` (utilizando 1 procesador). +.. 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). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-em3d-1cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-em3d-1cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-em3d-1cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-em3d-1cpu.pdf - .. subfig:: + .. 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 @@ -3005,138 +2958,138 @@ ayudar; por el contrario, aumentan levemente el tiempo de pausa real. Una vez más no se muestran los resultados para más de un procesador por ser extremadamente similares a los obtenidos utilizando solo uno. -``tsp`` -^^^^^^^^ -.. fig:: fig:sol-tsp-1cpu +.. flt:: fig:sol-tsp-1cpu - Resultados para ``tsp`` (utilizando 1 procesador). + Resultados para ``tsp`` (utilizando 1 procesador) Resultados para ``tsp`` (utilizando 1 procesador). Se presenta el mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución) o 20 corridas (para el resto). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-tsp-1cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-tsp-1cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-tsp-1cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-tsp-1cpu.pdf - .. subfig:: + .. subflt:: Pausa real máxima (seg) .. image:: plots/pause-tsp-1cpu.pdf -Los resultados para ``tsp`` (figura :vref:`fig:sol-tsp-1cpu`) son -prácticamente idénticos a los de ``bisort``. La única diferencia es que la -reducción del tiempo de pausa real es un poco menor. - -Esto confirma en cierta medida la poca utilidad de este juego de pruebas para -medir el rendimiento de un recolector, dado que evidentemente, si bien todas -resuelven problemas diferentes, realizan todas el mismo tipo de trabajo. +.. flt:: fig:sol-voronoi-1cpu -Una vez más no se muestran los resultados para más de un procesador por ser -extremadamente similares a los obtenidos utilizando solo uno. - -``voronoi`` -^^^^^^^^^^^ -.. fig:: fig:sol-voronoi-1cpu - - Resultados para ``voronoi`` (utilizando 1 procesador). + Resultados para ``voronoi`` (utilizando 1 procesador) Resultados para ``voronoi`` (utilizando 1 procesador). Se presenta el mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución) o 20 corridas (para el resto). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-voronoi-1cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-voronoi-1cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-voronoi-1cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-voronoi-1cpu.pdf - .. subfig:: + .. subflt:: Pausa real máxima (seg) .. image:: plots/pause-voronoi-1cpu.pdf -.. fig:: fig:sol-voronoi-4cpu +.. flt:: fig:sol-voronoi-4cpu - Resultados para ``voronoi`` (utilizando 4 procesadores). + Resultados para ``voronoi`` (utilizando 4 procesadores) Resultados para ``voronoi`` (utilizando 4 procesadores). Se presenta el mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución) o 20 corridas (para el resto). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-voronoi-4cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-voronoi-4cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-voronoi-4cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-voronoi-4cpu.pdf - .. subfig:: + .. 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. @@ -3148,10 +3101,10 @@ este caso no parece provenir toda la ganancia solo de ese cambio, dado que para TBGC se ve una variación entre los resultados muy grande que desaparece al cambiar a CDGC, esto no puede ser explicado por esa optimización. En general la disminución de la variación de los resultados hemos visto que está -asociada al incremento en la precisión en el marcado, dado que los falsos -punteros ponen una cuota de aleatoriedad importante. Pero este tampoco parece -ser el caso, ya que no se observan cambios apreciables al pasar a usar marcado -preciso. +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á @@ -3171,104 +3124,104 @@ al usar 4 (ver figura :vref:`fig:sol-voronoi-4cpu` disminuye levemente (además de otros cambios en el nivel de variación, pero en general las medias no cambian). - Resultados para pruebas reales ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -A continuación se presentan los resultados obtenidos para las pruebas reales -(ver :ref:`sol_bench_real`). Recordamos que solo se pudo halla un programa que -pueda ser utilizado a este fin, Dil_, y que el objetivo principal de este -trabajo se centra alrededor de obtener resultados positivos para este -programa, por lo que a pesar de ser una única prueba, se le presta particular -atención. - -``dil`` -^^^^^^^ -.. fig:: fig:sol-dil-1cpu +.. flt:: fig:sol-dil-1cpu - Resultados para ``dil`` (utilizando 1 procesador). + Resultados para ``dil`` (utilizando 1 procesador) Resultados para ``dil`` (utilizando 1 procesador). Se presenta el mínimos (en negro), la media centrada entre dos desvíos estándar (en gris), y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución) o 20 corridas (para el resto). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-dil-1cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-dil-1cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-dil-1cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-dil-1cpu.pdf - .. subfig:: + .. subflt:: Pausa real máxima (seg) .. image:: plots/pause-dil-1cpu.pdf -.. fig:: fig:sol-dil-4cpu +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. - Resultados para ``dil`` (utilizando 4 procesadores). +.. 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). - .. subfig:: + .. subflt:: Tiempo de ejecución (seg) .. image:: plots/time-dil-4cpu.pdf - .. subfig:: + .. subflt:: Cantidad de recolecciones .. image:: plots/ncol-dil-4cpu.pdf - .. subfig:: + .. subflt:: Uso máximo de memoria (MiB) .. image:: plots/mem-dil-4cpu.pdf - .. subfig:: + .. subflt:: *Stop-the-world* máximo (seg) .. image:: plots/stw-dil-4cpu.pdf - .. subfig:: + .. subflt:: Pausa real máxima (seg) .. image:: plots/pause-dil-4cpu.pdf -En la figura :vref:`fig:sol-dil-1cpu` se presentan los resultados para -``dil`` al utilizar un procesador. Una vez más vemos una mejoría inmediata del -tiempo total de ejecución al pasar de TBGC a CDGC, y una vez más se debe -principalmente al mal factor de ocupación del *heap* de TBGC, dado que -utilizando CDGC con la opción ``min_free=0`` se obtiene una media del orden de -los 80 segundos, bastante más alta que el tiempo obtenido para TBGC. - Sin embargo se observa un pequeño incremento del tiempo de ejecución al introducir marcado preciso, y un incremento bastante más importante (de alrededor del 30%) en el consumo máximo de memoria. Nuevamente, como pasa con @@ -3278,14 +3231,11 @@ información del tipo se guarda al final del bloque (ver :ref:`sol_precise`). En el cuadro :vref:`t:sol-prec-mem-dil` se puede observar la diferencia de memoria desperdiciada entre el modo conservativo y preciso. -El pequeño incremento en el tiempo total de ejecución podría estar dado por la -mayor probabilidad de tener *falsos punteros* debido al incremento del tamaño -del *heap*; se recuerda que el *stack* y memoria estática se siguen marcado de -forma conservativa, incluso en modo preciso. - -.. ftable:: t:sol-prec-mem-dil +.. 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 Memoria pedida y asignada para ``dil`` según modo de marcado conservativo o preciso (acumulativo durante toda la vida del programa). @@ -3297,6 +3247,11 @@ forma conservativa, incluso en modo preciso. 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 (cerca de un 60%, y más de un 200% comparado con TBGC) alrededor de la mitad) al empezar a usar *eager allocation*, acompañado como es usual de una baja en