.. Acá va lo que decidí hacer en base al análisis anterior y sus razones.
- ESTADO: EMPEZADO
+ ESTADO: TERMINADO
.. _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.
hacerlo sin alejarse demasiado del objetivo principal.
+.. highlight:: d
+
.. _sol_bench:
Banco de pruebas
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;
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::
}
__ 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``
lectura más cercana a la realidad del uso de un recolector.
+.. highlight:: pcode
+
.. _sol_mod:
Modificaciones propuestas
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
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
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
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;
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
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
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]
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)
``$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).
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
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
projects / z.facultad / 75.00 / informe.git / blobdiff