X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/af3cc91ddf531e9eb73f3dac73b15ab317a3cbb2..482caf6211b4e4bc4fc99907eaf3d364a7348984:/source/solucion.rst?ds=sidebyside diff --git a/source/solucion.rst b/source/solucion.rst index 32a94bd..d5563dc 100644 --- a/source/solucion.rst +++ b/source/solucion.rst @@ -1,6 +1,6 @@ .. Acá va lo que decidí hacer en base al análisis anterior y sus razones. - ESTADO: EMPEZADO + ESTADO: TERMINADO .. _solucion: @@ -8,13 +8,13 @@ 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 +38,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 +143,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; @@ -279,8 +281,8 @@ 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 apalear el problema de forma razonablemente efectiva. +repetidas veces y ha desembocado en una pequeña optimización que sirvió para +paliar el problema de forma razonablemente efectiva [PAN09]_. El código es el siguiente:: @@ -302,7 +304,6 @@ El código es el siguiente:: } __ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=67673 -__ http://d.puremagic.com/issues/show_bug.cgi?id=1923 ``rnddata`` @@ -563,6 +564,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 @@ -799,7 +802,9 @@ 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. +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 @@ -1083,18 +1088,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 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -1136,7 +1137,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; @@ -1380,11 +1383,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 @@ -1431,8 +1435,8 @@ siguientes [#solforkerr]_:: function collect() is stop_the_world() - child_pid = fork() 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 @@ -1583,7 +1587,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] @@ -1727,8 +1731,8 @@ necesarios si no se utiliza la opción ``eager_alloc``:: else if early // Agregado return // stop_the_world() - child_pid = fork() fflush(null) + child_pid = fork() if child_pid is 0 // proceso hijo mark_phase() exit(0) @@ -1908,8 +1912,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). @@ -1965,8 +1967,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 @@ -2153,67 +2153,6 @@ para evaluar el este efecto en los resultados, siempre que sea posible se analizan los resultados de un gran número de corridas observando principalmente su mínima, media, máxima y desvío estándar. -.. Tamaño del ejecutable (XXX: SEGUN LAS PRUEBAS NO FUCKING CAMBIA!!!) - El tamaño del ejecutable es un factor importante. Cuanto más grande es el - ejecutable, más parecieran variar los resultados. Por ejemplo se observa un - incremento de la estabilidad de los resultados al eliminar toda información - de depuración (*debug*) del ejecutable, utilizando el comando - :manpage:`strip(1)` (*stripped*). En el cuadro :vref:`t:sol-exesize-tbgc` - se puede ver la reducción del tamaño del ejecutable para TBGC cuando se - elimina la información de depuración (4.25 veces más chico en promedio), - mientas que en el cuadro :vref:`t:sol-exesize-cdgc` se puede ver CDGC (4.6 - veces más chico en promedio). - .. ftable:: t:sol-exesize-tbgc - Reducción del tamaño del ejecutable para TBGC. - ======== ======== ======== ============== - Nombre Debug Stripped Debug/Stripped - ======== ======== ======== ============== - bh 586517 138060 4.248 - bigarr 547687 192004 2.852 - bisort 485857 115164 4.219 - conalloc 616613 149848 4.115 - concpu 616575 149848 4.115 - dil 7293277 1859208 3.923 - em3d 505019 116324 4.341 - mcore 461767 105748 4.367 - rnddata 2832935 1492588 1.898 - sbtree 526402 129860 4.054 - split 589353 144308 4.084 - tree 462009 105844 4.365 - tsp 544901 128412 4.243 - voronoi 601259 141112 4.261 - ======== ======== ======== ============== - .. ftable:: t:sol-exesize-cdgc - Reducción del tamaño del ejecutable para CDGC. - ======== ======== ======== =============== - Nombre Debug Stripped Debug/Stripped - ======== ======== ======== =============== - bh 736115 159884 4.604 - bigarr 697406 213832 3.261 - bisort 635537 136988 4.639 - conalloc 766328 171676 4.464 - concpu 766294 171676 4.464 - dil 7442657 1881028 3.957 - em3d 658827 142248 4.632 - mcore 611486 127576 4.793 - rnddata 2986736 1518512 1.967 - sbtree 680217 155784 4.366 - split 739072 166136 4.449 - tree 611728 127672 4.791 - tsp 694581 150236 4.623 - voronoi 750847 162936 4.608 - ======== ======== ======== =============== - TODO: Mostrar tiempos de corridas. - - -.. Resultados generales - ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - -.. Primero se presenta una visión global de los resultados, utilizando las - métricas más importantes. Para generar los gráficos se utilizan los valores - máximos (en blanco), mínimos (en negro), media y desvío estándar (en gris) - calculados en base a, como mínimo, 20 corridas (para algunos casos se hacen - hasta 50 corridas). Resultados para pruebas sintizadas @@ -2226,8 +2165,6 @@ 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). @@ -2306,47 +2243,6 @@ presente. .. image:: plots/pause-bigarr-4cpu.pdf -En la figura :vref:`fig:sol-bigarr-1cpu` se pueden observar los resultados -para ``bigarr`` al utilizar un solo procesador. En ella se puede notar que el -tiempo total de ejecución en general aumenta al utilizar CDGC, esto es -esperable, dado esta prueba se limitan a usar servicios del recolector. Dado -que esta ejecución utiliza solo un procesador y por lo tanto no se puede sacar -provecho a la concurrencia, es de esperarse que el trabajo extra realizado por -las modificaciones se vea reflejado en los resultados. En la -:vref:`fig:sol-bigarr-4cpu` (resultados al utilizar 4 procesadores) se puede -observar como al usar solamente *eager allocation* se recupera un poco el -tiempo de ejecución, probablemente debido al incremento en la concurrencia -(aunque no se observa el mismo efecto al usar *early collection*). - -Observando el tiempo total de ejecución, no se esperaba un incremento tan -notorio al pasar de TBGC a una configuración equivalente de CDGC **cons**, -haciendo un breve análisis de las posibles causas, lo más probable parece ser -el incremento en la complejidad de la fase de marcado dada capacidad para -marcar de forma precisa (aunque no se use la opción, se paga el precio de la -complejidad extra y sin obtener los beneficios). Además se puede observar -como el agregado de precisión al marcado mejora un poco las cosas (donde sí se -obtiene rédito de la complejidad extra en el marcado). - -En general se observa que al usar *eager allocation* el consumo de memoria -y los tiempos de pausa se disparan mientras que la cantidad de recolecciones -disminuye drásticamente. Lo que se observa es que el programa es -más veloz pidiendo memoria que recolectándola, por lo que crece mucho el -consumo de memoria. Como consecuencia la fase de barrido (que no corre en -paralelo al *mutator* como la fase de marcado) empieza a ser predominante en -el tiempo de pausa por ser tan grande la cantidad de memoria a barrer. Este -efecto se ve tanto al usar 1 como 4 procesadores, aunque el efecto es mucho -más nocivo al usar 1 debido a la alta variabilidad que impone la competencia -entre el *mutator* y recolector al correr de forma concurrente. - -Sin embargo, el tiempo de *stop-the-world* es siempre considerablemente más -pequeño al utilizar marcado concurrente en CDGC, incluso cuando se utiliza -*eager allocation*, aunque en este caso aumenta un poco, también debido al -incremento en el consumo de memoria, ya que el sistema operativo tiene que -copiar tablas de memoria más grandes al efectuar el *fork* (ver -:ref:`sol_fork`). - -``concpu`` -^^^^^^^^^^ .. fig:: fig:sol-concpu-1cpu Resultados para ``concpu`` (utilizando 1 procesador). @@ -2425,52 +2321,6 @@ copiar tablas de memoria más grandes al efectuar el *fork* (ver .. image:: plots/pause-concpu-4cpu.pdf -En la figura :vref:`fig:sol-concpu-1cpu` se pueden observar los resultados -para ``concpu`` al utilizar un solo procesador. En ella se aprecia que el -tiempo total de ejecución disminuye levemente al usar marcado concurrente -mientras no se utilice *eager allocation* pero aumenta al utilizarlo. - -Con respecto a la cantidad de recolecciones, uso máximo de memoria y tiempo de -*stop-the-world* se ve un efecto similar al descripto para ``bigarr`` (aunque -magnificado), pero sorprendentemente el tiempo total de pausa se dispara, -además con una variabilidad sorprendente, cuando se usa marcado concurrente -(pero no *eager allocation*). Una posible explicación podría ser que al -realizarse el *fork*, el sistema operativo muy probablemente entregue el -control del único procesador disponible al resto de los hilos que compiten por -él, por lo que queda mucho tiempo pausado en esa operación aunque realmente no -esté haciendo trabajo alguno (simplemente no tiene tiempo de procesador para -correr). Este efecto se cancela al usar *eager allocation* dado que el -*mutator* nunca se bloquea esperando que el proceso de marcado finalice. - -Además se observa una caída importante en la cantidad de recolecciones al -utilizar marcado concurrente. Esto probablemente se deba a que solo un hilo -pide memoria (y por lo tanto dispara recolecciones), mientras los demás hilos -también estén corriendo. Al pausarse todos los hilos por menos tiempo, el -trabajo se hace más rápido (lo que explica la disminución del tiempo total de -ejecución) y son necesarias menos recolecciones, por terminar más rápido -también el hilo que las dispara. - -En la :vref:`fig:sol-concpu-4cpu` se pueden ver los resultados al utilizar -4 procesadores, donde el panorama cambia sustancialmente. El efecto mencionado -en el párrafo anterior no se observa más (pues el sistema operativo tiene más -procesadores para asignar a los hilos) pero todos los resultados se vuelven -más variables. Los tiempos de *stop-the-world* y pausa real (salvo por lo -recién mencionado) crecen notablemente, al igual que su variación. No se -encuentra una razón evidente para esto; podría ser un error en la medición -dado que al utilizar todos los procesadores disponibles del *hardware*, -cualquier otro proceso que compita por tiempo de procesador puede afectarla -más fácilmente. - -El tiempo total de ejecución crece considerablemente, como se espera, dado que -el programa aprovecha los múltiples hilos que pueden correr en paralelo en -procesadores diferentes. - -Sin embargo, no se encuentra una razón clara para explicar el crecimiento -dramático en la cantidad de recolecciones solo al no usar marcado concurrente -para 4 procesadores. - -``conalloc`` -^^^^^^^^^^^^ .. fig:: fig:sol-conalloc-1cpu Resultados para ``conalloc`` (utilizando 1 procesador). @@ -2549,24 +2399,6 @@ para 4 procesadores. .. image:: plots/pause-conalloc-4cpu.pdf -En la figura :vref:`fig:sol-conalloc-1cpu` se pueden observar los resultados -para ``conalloc`` al utilizar un solo procesador. Los cambios con respecto -a lo observado para ``concpu`` son mínimos. El efecto de la mejoría al usar -marcado concurrente pero no *eager allocation* no se observa más, dado que -``conalloc`` pide memoria en todos los hilos, se crea un cuello de botella. Se -ve claramente como tampoco baja la cantidad de recolecciones hecha debido -a esto y se invierte la variabilidad entre los tiempos pico de pausa real -y *stop-the-world* (sin una razón obvia, pero probablemente relacionado que -todos los hilos piden memoria). - -Al utilizar 4 procesadores (figura :vref:`fig:sol-conalloc-4cpu`), más allá de -las diferencias mencionadas para 1 procesador, no se observan grandes cambios -con respecto a lo observado para ``concpu``, excepto que los tiempos de pausa -(real y *stop-the-world*) son notablemente más pequeños, lo que pareciera -confirmar un error en la medición de ``concpu``. - -``split`` -^^^^^^^^^ .. fig:: fig:sol-split-1cpu Resultados para ``split`` (utilizando 1 procesador). @@ -2606,26 +2438,6 @@ confirmar un error en la medición de ``concpu``. .. image:: plots/pause-split-1cpu.pdf -Este es el primer caso donde se aprecia la sustancial mejora proporcionada por -una pequeña optimización, el caché de ``findSize()`` (ver -:ref:`sol_minor_findsize`). En la figura :vref:`fig:sol-split-1cpu` se puede -observar con claridad como, para cualquier configuración de CDGC, hay una -caída notable en el tiempo total de ejecución. Sin embargo, a excepción de -cuando se utiliza *eager allocation*, la cantidad de recolecciones y memoria -usada permanece igual. - -La utilización de *eager allocation* mejora (aunque de forma apenas -apreciable) el tiempo de ejecución, la cantidad de recolecciones baja a un -tercio y el tiempo de pausa real cae dramáticamente. Al usar marcado -concurrente ya se observa una caída determinante en el tiempo de -*stop-the-world*. Todo esto sin verse afectado el uso máximo de memoria, -incluso al usar *eager allocation*. - -Se omiten los resultados para más de un procesador por ser prácticamente -idénticos para este análisis. - -``mcore`` -^^^^^^^^^ .. fig:: fig:sol-mcore-1cpu Resultados para ``mcore`` (utilizando 1 procesador). @@ -2704,26 +2516,6 @@ idénticos para este análisis. .. image:: plots/pause-mcore-4cpu.pdf -El caso de ``mcore`` es interesante por ser, funcionalmente, una combinación -entre ``concpu`` y ``split``, con un agregado extra: el incremento notable de -la competencia por utilizar el recolector entre los múltiples hilos. - -Los efectos observados (en la figura :vref:`fig:sol-mcore-1cpu` para -1 procesador y en la figura :vref:`fig:sol-mcore-4cpu` para 4) confirman esto, -al ser una suma de los efectos observados para ``concpu`` y ``split``, con el -agregado de una particularidad extra por la mencionada competencia entre -hilos. A diferencia de ``concpu`` donde el incremento de procesadores resulta -en un decremento en el tiempo total de ejecución, en este caso resulta en una -disminución, dado que se necesita mucha sincronización entre hilos, por -utilizar todos de forma intensiva los servicios del recolector (y por lo tanto -competir por su *lock* global). - -Otro efecto común observado es que cuando el tiempo de pausa es muy pequeño -(del orden de los milisegundos), el marcado concurrente suele incrementarlo en -vez de disminuirlo. - -``rnddata`` -^^^^^^^^^^^ .. fig:: fig:sol-rnddata-1cpu Resultados para ``rnddata`` (utilizando 1 procesador). @@ -2763,6 +2555,153 @@ vez de disminuirlo. .. image:: plots/pause-rnddata-1cpu.pdf +``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). + +En general se observa que al usar *eager allocation* el consumo de memoria +y los tiempos de pausa se disparan mientras que la cantidad de recolecciones +disminuye drásticamente. Lo que se observa es que el programa es +más veloz pidiendo memoria que recolectándola, por lo que crece mucho el +consumo de memoria. Como consecuencia la fase de barrido (que no corre en +paralelo al *mutator* como la fase de marcado) empieza a ser predominante en +el tiempo de pausa por ser tan grande la cantidad de memoria a barrer. Este +efecto se ve tanto al usar 1 como 4 procesadores, aunque el efecto es mucho +más nocivo al usar 1 debido a la alta variabilidad que impone la competencia +entre el *mutator* y recolector al correr de forma concurrente. + +Sin embargo, el tiempo de *stop-the-world* es siempre considerablemente más +pequeño al utilizar marcado concurrente en CDGC, incluso cuando se utiliza +*eager allocation*, aunque en este caso aumenta un poco, también debido al +incremento en el consumo de memoria, ya que el sistema operativo tiene que +copiar tablas de memoria más grandes al efectuar el *fork* (ver +:ref:`sol_fork`). + +``concpu`` +^^^^^^^^^^ +En la figura :vref:`fig:sol-concpu-1cpu` se pueden observar los resultados +para ``concpu`` al utilizar un solo procesador. En ella se aprecia que el +tiempo total de ejecución disminuye levemente al usar marcado concurrente +mientras no se utilice *eager allocation* pero aumenta al utilizarlo. + +Con respecto a la cantidad de recolecciones, uso máximo de memoria y tiempo de +*stop-the-world* se ve un efecto similar al descripto para ``bigarr`` (aunque +magnificado), pero sorprendentemente el tiempo total de pausa se dispara, +además con una variabilidad sorprendente, cuando se usa marcado concurrente +(pero no *eager allocation*). Una posible explicación podría ser que al +realizarse el *fork*, el sistema operativo muy probablemente entregue el +control del único procesador disponible al resto de los hilos que compiten por +él, por lo que queda mucho tiempo pausado en esa operación aunque realmente no +esté haciendo trabajo alguno (simplemente no tiene tiempo de procesador para +correr). Este efecto se cancela al usar *eager allocation* dado que el +*mutator* nunca se bloquea esperando que el proceso de marcado finalice. + +Además se observa una caída importante en la cantidad de recolecciones al +utilizar marcado concurrente. Esto probablemente se deba a que solo un hilo +pide memoria (y por lo tanto dispara recolecciones), mientras los demás hilos +también estén corriendo. Al pausarse todos los hilos por menos tiempo, el +trabajo se hace más rápido (lo que explica la disminución del tiempo total de +ejecución) y son necesarias menos recolecciones, por terminar más rápido +también el hilo que las dispara. + +En la :vref:`fig:sol-concpu-4cpu` se pueden ver los resultados al utilizar +4 procesadores, donde el panorama cambia sustancialmente. El efecto mencionado +en el párrafo anterior no se observa más (pues el sistema operativo tiene más +procesadores para asignar a los hilos) pero todos los resultados se vuelven +más variables. Los tiempos de *stop-the-world* y pausa real (salvo por lo +recién mencionado) crecen notablemente, al igual que su variación. No se +encuentra una razón evidente para esto; podría ser un error en la medición +dado que al utilizar todos los procesadores disponibles del *hardware*, +cualquier otro proceso que compita por tiempo de procesador puede afectarla +más fácilmente. + +El tiempo total de ejecución crece considerablemente, como se espera, dado que +el programa aprovecha los múltiples hilos que pueden correr en paralelo en +procesadores diferentes. + +Sin embargo, no se encuentra una razón clara para explicar el crecimiento +dramático en la cantidad de recolecciones solo al no usar marcado concurrente +para 4 procesadores. + +``conalloc`` +^^^^^^^^^^^^ +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. + +``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 @@ -2810,16 +2749,6 @@ trabajo. Resultados para pruebas pequeñas ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -A continuación se presentan los resultados obtenidos para las pruebas pequeñas -(ver :ref:`sol_bench_small`). Se recuerda que si bien este conjunto de pruebas -se compone de programas reales, que efectúan una tarea útil, están diseñados -para ejercitar la asignación de memoria y que no son recomendados para evaluar -el desempeño de recolectores de basura. Sin embargo se las utiliza igual por -falta de programas más realistas, por lo que hay que tomarlas como un grado de -suspicacia. - -``bh`` -^^^^^^ .. fig:: fig:sol-bh-1cpu Resultados para ``bh`` (utilizando 1 procesador). @@ -2859,23 +2788,16 @@ suspicacia. .. image:: plots/pause-bh-1cpu.pdf -En la figura :vref:`fig:sol-bh-1cpu` se pueden observar los resultados -para ``bh`` al utilizar un solo procesador. Ya en una prueba un poco más -realista se puede observar el efecto positivo del marcado preciso, en especial -en la cantidad de recolecciones efectuadas (aunque no se traduzca en un menor -consumo de memoria). - -Sin embargo se observa también un efecto nocivo del marcado preciso en el -consumo de memoria que intuitivamente debería disminuir, pero crece, y de -forma considerable (unas 3 veces en promedio). La razón de esta particularidad -es el incremento en el espacio necesario para almacenar objetos debido a que -el puntero a la información del tipo se guarda al final del bloque (ver -:ref:`sol_precise`). En el cuadro :vref:`t:sol-prec-mem-bh` se puede observar -la cantidad de memoria pedida por el programa, la cantidad de memoria -realmente asignada por el recolector (y la memoria desperdiciada) cuando se -usa marcado conservativo y preciso. Estos valores fueron tomados usando la -opción ``malloc_stats_file`` (ver :ref:`sol_stats`). +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`` +^^^^^^ .. ftable:: t:sol-prec-mem-bh Memoria pedida y asignada para ``bh`` según modo de marcado. @@ -2890,16 +2812,12 @@ 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. +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). -``bisort`` -^^^^^^^^^^ .. fig:: fig:sol-bisort-1cpu Resultados para ``bisort`` (utilizando 1 procesador). @@ -2939,24 +2857,17 @@ similares a los obtenidos utilizando solo uno. .. image:: plots/pause-bisort-1cpu.pdf -La figura :vref:`fig:sol-bisort-1cpu` muestra los resultados para ``bisort`` -al utilizar 1 procesador. En este caso el parecido es con los resultados para -la prueba sintetizada ``split``, con la diferencia que el tiempo de ejecución -total prácticamente no varía entre TBGC y CDGC, ni entre las diferentes -configuraciones del último (evidentemente en este caso no se aprovecha el -caché de ``findSize()``). - -Otra diferencia notable es la considerable reducción del tiempo de pausa real -al utilizar *early collection* (más de 3 veces menor en promedio comparado -a cuando se marca conservativamente, y más de 2 veces menor que cuando se hace -de forma precisa), lo que indica que la predicción de cuando se va a necesitar -una recolección es más efectiva que para ``split``. - -No se muestran los resultados para más de un procesador por ser extremadamente -similares a los obtenidos utilizando solo uno. +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`). -``em3d`` -^^^^^^^^ .. fig:: fig:sol-em3d-1cpu Resultados para ``em3d`` (utilizando 1 procesador). @@ -2996,16 +2907,23 @@ similares a los obtenidos utilizando solo uno. .. image:: plots/pause-em3d-1cpu.pdf -Los resultados para ``em3d`` (figura :vref:`fig:sol-em3d-1cpu`) son -sorprendentemente similares a los de ``bisort``. La única diferencia es que en -este caso el marcado preciso y el uso de *early collection** no parecen -ayudar; por el contrario, aumentan levemente el tiempo de pausa real. +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. -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. +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()``). -``tsp`` -^^^^^^^^ .. fig:: fig:sol-tsp-1cpu Resultados para ``tsp`` (utilizando 1 procesador). @@ -3045,19 +2963,22 @@ extremadamente similares a los obtenidos utilizando solo uno. .. 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. +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``. -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. +No se muestran los resultados para más de un procesador por ser extremadamente +similares a los obtenidos utilizando solo uno. -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. +``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. -``voronoi`` -^^^^^^^^^^^ .. fig:: fig:sol-voronoi-1cpu Resultados para ``voronoi`` (utilizando 1 procesador). @@ -3136,6 +3057,24 @@ extremadamente similares a los obtenidos utilizando solo uno. .. image:: plots/pause-voronoi-4cpu.pdf +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`` +^^^^^^^^ +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. @@ -3170,19 +3109,9 @@ al usar 4 (ver figura :vref:`fig:sol-voronoi-4cpu` disminuye levemente (además de otros cambios en el nivel de variación, pero en general las medias no cambian). - Resultados para pruebas reales ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -A continuación se presentan los resultados obtenidos para las pruebas reales -(ver :ref:`sol_bench_real`). Recordamos que solo se pudo halla un programa que -pueda ser utilizado a este fin, Dil_, y que el objetivo principal de este -trabajo se centra alrededor de obtener resultados positivos para este -programa, por lo que a pesar de ser una única prueba, se le presta particular -atención. - -``dil`` -^^^^^^^ .. fig:: fig:sol-dil-1cpu Resultados para ``dil`` (utilizando 1 procesador). @@ -3222,6 +3151,22 @@ atención. .. 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. + .. fig:: fig:sol-dil-4cpu Resultados para ``dil`` (utilizando 4 procesadores). @@ -3261,13 +3206,6 @@ atención. .. 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 @@ -3277,11 +3215,6 @@ información del tipo se guarda al final del bloque (ver :ref:`sol_precise`). En el cuadro :vref:`t:sol-prec-mem-dil` se puede observar la diferencia de memoria desperdiciada entre el modo conservativo y preciso. -El pequeño incremento en el tiempo total de ejecución podría estar dado por la -mayor probabilidad de tener *falsos punteros* debido al incremento del tamaño -del *heap*; se recuerda que el *stack* y memoria estática se siguen marcado de -forma conservativa, incluso en modo preciso. - .. ftable:: t:sol-prec-mem-dil Memoria pedida y asignada para ``dil`` según modo de marcado. @@ -3296,6 +3229,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 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. + 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