X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/af3cc91ddf531e9eb73f3dac73b15ab317a3cbb2..ea3821c336ddc868ed82ca992543869922068290:/source/solucion.rst?ds=inline diff --git a/source/solucion.rst b/source/solucion.rst index 32a94bd..2907da2 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