.. Se presentan las conclusiones del trabajo, comparando los resultados
obtenidos con el punto de partida. Se mencionan puntos pendientes o
nuevas líneas de investigación.
- ESTADO: SIN EMPEZAR
+ ESTADO: EMPEZADO
.. _conclusion:
Conclusión
============================================================================
-TODO
+Durante el desarrollo de este trabajo se introdujo al lenguaje de programación
+D_ y a los conceptos básicos de recolección de basura. Luego se analizó el
+recolector de basura actual y se señalaron sus principales falencias,
+proponiendo un conjunto de modificaciones con el objeto de subsanarlas.
+Para evaluar los resultados de las modificaciones se construyó un banco de
+pruebas variado para poder analizar tanto aspectos particulares como el
+funcionamiento de programas reales; y se establecieron métricas para
+cuantificar dichos resultados.
+
+El objetivo principal fue bajar la latencia del recolector, es decir el tiempo
+máximo de pausa real, y se pudo comprobar que, salvo en casos muy
+particulares, esto fue conseguido de manera contundente (con tiempos de pausa
+hasta 200 veces menores que el recolector original de D_). La inclusión del
+marcado concurrente demostró ser una aproximación correcta al problema.
+
+La aceptación de la solución por parte de la comunidad también ha sido un
+objetivo importante de este trabajo, y si bien en este sentido sigue siendo un
+trabajo en curso, la recepción ha sido ampliamente positiva por parte de la
+comunidad y se espera que el resultado de este trabajo sea incorporado en el
+corto plazo tanto a `D 1.0`_ a través de Tango_, como a `D 2.0`_.
+
+Además de los objetivos principales se cumplieron otros objetivos anexos, pero
+no por eso menos importantes. Para la aplicación real el tiempo total de
+ejecución se ha reducido hasta casi una tercera parte, y para otras
+aplicaciones pequeñas se ha reducido más de 17 veces. Estos resultados han
+sido particularmente sorprendentes, siendo que la reducción del tiempo total
+de ejecución no ha sido parte del objetivo principal y no se habían encontrado
+referencias en la bibliografía de casos similares (por el contrario, en
+general la baja de la latencia suele estar acompañada de una suba en el tiempo
+total de ejecución).
+
+Se ha podido experimentar además con el marcado preciso, otro de los problemas
+del recolector más presentes en la comunidad. Los resultados obtenidos son
+variados, encontrando casos donde se consigue una mejoría notoria y otros en
+donde la forma de almacenar la información de tipos produce resultados poco
+satisfactorios.
+
+La mayor flexibilidad del recolector al ser configurable también ha demostrado
+ser útil. Por un lado para este mismo trabajo, al permitir realizar mediciones
+sobre el mismo binario utilizando diferentes configuraciones. Por otro, la
+amplia gama de resultados dispares obtenidos son una buena muestra de que no
+existen *balas de plata*, y cada programa tiene necesidades particulares en
+cuanto a recolección de basura. Por lo tanto, distintos programas pueden verse
+beneficiados o perjudicados por diferentes configuraciones. Esto hace que la
+posibilidad de configurar el recolector en tiempo de inicialización sea
+particularmente ventajoso.
+
+Finalmente, algunas optimizaciones muy pequeñas demostraron ser también muy
+valiosas para algunos casos particulares, logrando reducciones en el tiempo
+total de ejecución de hasta 5 veces.
+
+
+
+Puntos pendientes, problemas y limitaciones
+----------------------------------------------------------------------------
+
+Si bien los objetivos de este trabajo han sido alcanzados con éxito, hay
+varias pequeñas mejoras que han quedado pendientes y algunos problemas
+y limitaciones conocidas. A continuación se describe cada una de ellos.
+
+* Emisión de mensajes informativos para depuración.
+
+ Entre las herramientas de depuración que provee el recolector, no se ha
+ mencionado la posibilidad de emitir opcionalmente mensajes informativos para
+ ayudar a depurar tanto problemas en el recolector como en el programa que lo
+ usa. El recolector actual tiene esa posibilidad pero es elegible en tiempo de
+ compilación. En este trabajo se agregaron las opciones en tiempo de
+ inicialización ``log_file`` y ``verbose`` con el propósito de poder elegir un
+ archivo en donde guardar los mensajes informativos y el nivel de detalle de
+ dichos mensajes respectivamente, pero finalmente nunca se implementaron.
+
+* Predicción para estimar cuando lanzar una recolección temprana.
+
+ Las recolecciones se lanzan de manera temprana según la opción ``min_free``.
+ Una mejor aproximación podría ser predecir cuando se va a agotar la memoria
+ libre de forma adaptativa, calculando la tasa de asignación de memoria
+ y el tiempo total que tomó la recolección. Esta estimación se podría mejorar
+ guardando un historial de que tan acertada fue para recolecciones pasadas. La
+ predicción ideal debería ser capaz de:
+
+ * Evitar tiempos de pausa (es decir, que la recolección temprana termine antes
+ de que se agote la memoria libre).
+ * No realizar recolecciones innecesarias (es decir, no lanzar recolecciones
+ tempranas si el programa no está pidiendo memoria a una tasa suficientemente
+ alta).
+
+* Explosión del uso de memoria con creación ansiosa de *pools*.
+
+ Se ha observado que en situaciones muy particulares, al usar creación
+ ansiosa de *pools* (o *eager allocation*), el uso de memoria crece
+ desmesuradamente. Si bien este efecto se ve principalmente en las pruebas
+ sintetizadas con tal fin, algunos programas reales lo sufren también, pero
+ en general se puede atenuar utilizando también *early collection*.
+ Recordemos además, que lo analizado es el consumo **máximo** de memoria, por
+ lo que una ráfaga de pedidos de memoria podría crear un pico, pero durante
+ la mayor parte del transcurso del programa el consumo de memoria podría ser
+ mucho menor. Queda pendiente analizar los casos puntuales con alguna métrica
+ más detallada sobre el progreso del uso de memoria.
+
+ También queda pendiente buscar alguna estimación de cuándo es conveniente
+ utilizar *eager allocation* de forma adaptativa, dado que en general se ve
+ que cuando explota el consumo de memoria, también explota el tiempo de
+ pausa, lo que quita gran parte del sentido de usar *eager allocation* en
+ primer lugar. Estimando de alguna manera cuanto va a crecer el tiempo de
+ pausa debido a esta opción, se podría desactivar temporalmente cuando no
+ haya ganancia en el tiempo de pausa para evitar esta explosión ante ráfagas
+ de pedidos de memoria.
+
+* Reestructuración y limpieza del código.
+
+ Si bien se han hecho muchas mejoras a nivel de estructura y limpieza de
+ código, ha quedado mucho pendiente. Todavía hay bastante repetición en el
+ código y se mantiene la arquitectura básica del recolector.
+
+* Experimentación con la llamada al sistema :manpage:`clone(2)`.
+
+ Linux_ implementa la llamada al sistema :manpage:`fork(2)` a través de otra de
+ más bajo nivel llamada :manpage:`clone(2)`. :manpage:`clone(2)` permite una
+ granularidad a la hora de indicar que partes del proceso deben ser copiadas al
+ hijo y cuales deben ser compartidas mucho mayor que :manpage:`fork(2)`. Por
+ ejemplo, se puede compartir toda la memoria del proceso, siendo este el
+ mecanismo por el cual Linux_ implementa los hilos. Para este trabajo podría
+ ser beneficioso usar :manpage:`clone(2)` para evitar copiar otro tipo de
+ estructuras dado que el proceso
+ hijo, al correr solo la fase de marcado, nunca va a interferir el *mutator*.
+ Se podría experimentar no copiando las siguientes estructuras, por ejemplo:
+
+ ``CLONE_FILES``
+ Tabla de descriptores de archivo.
+ ``CLONE_FS``
+ Tabla de sistemas de archivo montados.
+
+ ``CLONE_IO``
+ Contextos de entrada/salida.
+
+ ``CLONE_SIGHAND``
+ Tabla de manejadores de señales.
+
+* Uso de memoria compartida.
+
+ Al realizar marcado concurrente, si el *mutator* usa memoria compartida entre
+ procesos que almacene punteros al *heap* podría haber problemas, dado que la
+ fase de barrido no estaría trabajando con una *fotografía* de la memoria. El
+ grafo de conectividad podría efectivamente cambiar mientras se corre la fase
+ de barrido y por lo tanto el algoritmo deja de ser correcto, existiendo la
+ posibilidad de que se reciclen celdas *vivas*.
+
+ Dado que el usuario debe registrar cualquier puntero que no sea parte de la
+ memoria estática, *stack* o *heap* del recolector como parte del *root set*,
+ se podría agregar un parámetro extra a la función de registro que indique si
+ los punteros agregados residen en memoria compartida. De este modo, al momento
+ de hacer el :manpage:`fork(2)`, el recolector debería realizar una copia de
+ esos punteros mientras todos los hilos están pausados para obtener
+ efectivamente una *fotografía* estable del *root set*.
+
+* Condición de carrera al utilizar :manpage:`fork(2)`.
+
+ Existe una condición de carrera si se lanzan hilos usando directamente las
+ llamadas al sistema operativo, es decir si no se lanzan a través del soporte
+ de hilos de D_, si el hilo lanzado utiliza archivos con *buffer* de
+ C (``FILE*``). Esto se debe a la siguiente porción de código (introducida por
+ el marcado concurrente)::
+
+ function collect() is
+ stop_the_world()
+ fflush(null) // <-------------------------
+ child_pid = fork()
+ if child_pid is 0
+ mark_phase()
+ exit(0)
+ // proceso padre
+ start_the_world()
+ wait(child_pid)
+ sweep()
+
+ La llamada a :manpage:`fflush(3)` es necesaria para evitar que los archivos
+ con *buffer* escriban su contenido dos veces al dispositivo, ya que la llamada
+ a :manpage:`fork(2)` duplica el *buffer*, y si bien el archivo no se usa en el
+ proceso con la fase de marcado, la biblioteca estándar de C escribe todos los
+ *buffers* pendientes al terminar el proceso. Esto funciona para los hilos
+ registrados por D_ gracias a que :manpage:`fflush(3)` se llama cuando todos
+ los hilos están pausados, si no un hilo podría escribir al *buffer* justo
+ después de llamar a :manpage:`fflush(3)` pero antes de llamar
+ a :manpage:`fflush(2)`. Es por esto que si hay hilos no registrados por D_ que
+ utilicen manejo de archivos con *buffer* de C, esta condición sí se puede dar
+ y se pueden observar contenidos duplicados en dichos archivos.
+
+ Esta condición de carrera no tiene una solución simple, pero es de esperarse
+ que no sea un problema real dado que no es un escenario común. Sin embargo
+ eventualmente debería analizarse alguna solución más robusta.
+
+* Soporte de referencias débiles.
+
+ Tango_ 0.99.9 incluye soporte de referencias débiles. Si bien se incorporó
+ el código para manejar las referencias débiles, se espera que no funcione
+ correctamente con CDGC (no se ha podido comprobar por la falta de programas
+ de prueba que lo utilicen). La razón es que el soporte de referencias
+ débiles de Tango_ 0.99.9 se basa en la premisa de que la fase de marcado
+ corre con todos los hilos pausados, sin embargo al utilizar marcado
+ concurrente, esto no es más cierto. Parecen haber soluciones viables a este
+ problema pero no se han analizado en profundidad aún.
+
+* Pérdida de rendimiento con respecto al recolector original.
+
+ Se ha observado también que, al no utilizar algunas optimizaciones de CDGC
+ (como la mejora del factor de ocupación del *heap*), éste puede tener un
+ rendimiento bastante menor a TBGC. Si bien no se ha investigado en
+ profundidad las causas de esta pérdida de rendimiento, se han identificado
+ algunos factores que podrían ser determinantes.
+
+ Por un lado, se ha observado que la mayor parte del tiempo extra que utiliza
+ CDGC proviene de la fase de marcado, en particular de los cambios
+ introducidos por el marcado preciso. Si bien se puede desactivar el marcado
+ preciso, la lógico en tiempo de ejecución no cambia, por lo que se paga el
+ precio sin obtener los beneficios. Queda pendiente analizar en más detalle
+ las causas de esto y posibles optimizaciones para subsanarlo.
+
+ .. ftable:: t:con-staticsize
+
+ Aumento del tamaño de la memoria estática (bytes).
+
+ ======== ======== ======== =========== ===========
+ Programa TBGC CDGC CDGC-TBGC CDGC/TBGC
+ ======== ======== ======== =========== ===========
+ bh 22208 27604 5396 1.243
+ bigarr 18820 24212 5392 1.287
+ bisort 19836 25232 5396 1.272
+ conalloc 25816 31208 5392 1.209
+ concpu 25816 31208 5392 1.209
+ dil 416900 422300 5400 1.013
+ em3d 20988 26380 5392 1.257
+ mcore 18564 23988 5424 1.292
+ rnddata 188940 194332 5392 1.029
+ sbtree 22196 27588 5392 1.243
+ split 24312 29736 5424 1.223
+ tree 18660 24084 5424 1.291
+ tsp 20772 26168 5396 1.260
+ voronoi 21184 26580 5396 1.255
+ ======== ======== ======== =========== ===========
+
+ Además se ha observado un crecimiento importante en el tamaño del área de
+ memoria estática del programa. En el cuadro :vref:`t:con-staticsize` se
+ puede observar dicho crecimiento para cada uno de los programas del banco de
+ pruebas. Esto se debe a que el recolector original está escrito de una forma
+ muy primitiva, usando muy pocos tipos de datos definidos por el usuario,
+ mientras que CDGC utiliza varias más, incluyendo algunos parametrizados. D_
+ guarda la información de tipos en el área de memoria estática y se genera
+ mucha información por cada tipo. Además no separa el área de memoria
+ estática que debe ser utilizada como parte del *root set* de la que no (no
+ hay necesidad de que la información de tipos sea parte del *root set*). Esto
+ causa que por cada recolección, se tenga que visitar bastante más memoria y,
+ lo que es probablemente peor, que aumente la probabilidad de encontrar
+ *falsos punteros*, dado que este área de memoria se marca siempre de forma
+ conservativa.
+
+ Finalmente, en el cuadro :vref:`t:con-binsize` también se puede observar un
+ incremento en el tamaño del binario, lo que puede ser otra causa de la
+ pérdida de rendimiento, dado que puede afectar a la localidad de referencia
+ del caché, por ejemplo.
+
+ .. ftable:: t:con-binsize
+
+ Aumento del tamaño del binario (bytes).
+
+ ======== ======== ======== =========== ===========
+ Programa TBGC CDGC CDGC-TBGC CDGC/TBGC
+ ======== ======== ======== =========== ===========
+ bh 138060 159884 21824 1.158
+ bigarr 192004 213832 21828 1.114
+ bisort 115164 136988 21824 1.190
+ conalloc 149848 171676 21828 1.146
+ concpu 149848 171676 21828 1.146
+ dil 1859208 1881028 21820 1.012
+ em3d 116324 142248 25924 1.223
+ mcore 105748 127576 21828 1.206
+ rnddata 1492588 1518512 25924 1.017
+ sbtree 129860 155784 25924 1.200
+ split 144308 166136 21828 1.151
+ tree 105844 127672 21828 1.206
+ tsp 128412 150236 21824 1.170
+ voronoi 141112 162936 21824 1.155
+ ======== ======== ======== =========== ===========
Trabajos relacionados
----------------------------------------------------------------------------
-TODO
+Dado que D_ no está muy difundido en ámbitos académicos, la cantidad de
+trabajos relacionados es muy pequeña, sin embargo los hay, y a continuación se
+describen.
-* Diamond:
+* Diamond [PAN09]_:
http://thecybershadow.net/d/Memory_Management_in_the_D_Programming_Language.pdf
más el tiempo máximo de pausa (aunque esto se puede hacer más allá de hacer
continuous collection, ver "concurrent sweeping"), lo malo es que tal vez se
estaría recolectando demasiado sin ninguna ganancia substancial.
-* Medir mejor cuando lanzar una recolección cuando se usa early collection
- (por ejemplo medir la tasa de alocación y el tiempo de recolección y así
- hallar el momento ideal para lanzar la recolección).
-* Emprolijar todavía más el código (o reescribirlo).
* Hacer preciso el static data por el tema de los TypeInfo's que ocupan mucha
memoria que debe ser escaneada.
+* Tratar de remover el *lock* global.
+* Implementar un recolector con movimiento.
+
+.. include:: links.rst
-.. vim: set ts=3 sts=3 sw=3 et tw=78 :
+.. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :
projects / z.facultad / 75.00 / informe.git / blobdiff