-.. 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
-
-
.. _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
+.. _con_pending:
+
+Puntos pendientes, problemas y limitaciones
----------------------------------------------------------------------------
-TODO
+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.
-* Opciones log_file/verbose
-* Lazy sweeping.
-* Concurrent sweeping (lanzar fase de sweep en un thread que no pertenezca al
- mutator).
-* Continuous collection (lanzar un thread que esté haciendo fullcollect() en
- un loop). Lo bueno es que el sweep podría correr en ese thread, bajando aún
- 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).
+* 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.
+
+ .. flt:: t:con-staticsize
+ :type: table
+
+ 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 positivos*, 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.
+
+ .. flt:: t:con-binsize
+ :type: table
+
+ 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 ha penetrado en ámbitos académicos, se ha encontrado un solo
+trabajo de investigación relacionado. Sin embargo se ha encontrado otro
+trabajo que si bien no es formal, ha sido de mucha importancia para el
+desarrollo de este trabajo.
+
+A continuación se describen ambos.
+
+* *Memory Management in the D Programming Language* [PAN09]_.
+
+ Tesis de licenciatura de Vladimir Panteleev cuya resumen traducido es el
+ siguiente:
+
+ Este reporte describe el estudio de las técnicas de manejo automático de
+ memoria, su implementación en el lenguaje de programación D_, y el
+ trabajo para mejorar el estado del manejo de memoria.
+
+ Si bien plantea pequeñas optimizaciones para el recolector de basura
+ (algunas utilizadas en este trabajo), se centra principalmente en el
+ desarrollo de Diamond, una utilidad para depuración de manejo de memoria en
+ D_.
+
+* Integración de marcado preciso del *heap* al recolector de basura
+ [DBZ3463]_.
+
+ Ya citado varias veces en este trabajo, fue comenzado por David Simcha
+ y publicado en el sistema de seguimiento de fallas de D_ que se limita a una
+ implementación a nivel biblioteca de usuario y sobre `D 2.0`_. Vincent Lang
+ (mejor conocido como *wm4* en la comunidad de D_) da continuidad a este
+ trabajo pero modificando el compilador DMD_ y trabajando con `D 1.0`_
+ y Tango_.
+
+ El soporte de marcado preciso presentado en este trabajo se basa en las
+ modificaciones hechas al compilador DMD_ por Vincent Lang (que aún no fueron
+ integradas de forma oficial).
-* Diamond:
- http://thecybershadow.net/d/Memory_Management_in_the_D_Programming_Language.pdf
Trabajos futuros
----------------------------------------------------------------------------
-TODO
+En la sección :ref:`con_pending` se mencionan varios aspectos de este trabajo
+que podrían verse beneficiados por trabajos futuros, sin embargo se trata en
+general de pequeñas optimizaciones o mejoras de alcance muy limitado.
+
+A continuación se recopilan varios otros aspectos identificados durante el
+desarrollo del presente trabajo, pero que requieren un nivel de análisis
+y, potencialmente, de desarrollo mayor a los ya presentados en la sección
+mencionada.
+
+* Mejoras en la organización de memoria del recolector.
+
+ Si bien se ha mencionado en un principio la organización actual como un
+ aspecto positivo del recolector, varios resultados han demostrado
+ deficiencias importantes. El nivel de espacio desperdiciado por la división
+ de memoria en bloques puede ser muy significativa y la forma en la que se
+ almacena la información de tipos para el marcado preciso puede incluso
+ acentuarlo todavía más (como se demuestra en los resultados para ``bh``
+ y ``dil``).
+
+ Este problema no solo afecta al consumo de memoria, además genera un efecto
+ dominó por el incremento de la probabilidad de tener *falsos positivos*
+ y perjudica al tiempo total de ejecución por empeorar la localidad de
+ referencia del caché y por hacer que se prolongue la recolección de basura
+ por tener que marcar y barrer más memoria.
+
+ Una posible alternativa es tener una lista de libres por **tipo**, cuyo
+ tamaño de bloque sea exactamente igual al tamaño del tipo que almacena. La
+ información de tipo se almacenaría entonces solo una vez y no habría
+ desperdicio de memoria alguno dejando de lado un posible relleno para
+ completar una página. Este esquema debería tener algún tipo de guarda para
+ programas con una cantidad exuberante de tipos de datos.
+
+ También podría ser conveniente separar los bloques marcados como ``NO_SCAN``
+ de los que sí deben ser marcados, de manera que no necesite almacenar
+ directamente los bits de ``mark`` , ``scan`` y ``noscan``. También se podría
+ proponer algún área de memoria especial para almacenar cadenas de texto
+ (como un caso especial de lo anterior) por tener estas características muy
+ particular (largos muy variables, cambian de tamaño de forma relativamente
+ frecuente, etc.). Las posibilidades son enormes.
+
+* Mejoras en la fase de barrido.
+
+ En este trabajo todas las mejoras propuestas se encargaron de la fase de
+ marcado, pero mucho se pude mejorar en la fase de barrido también. Por un
+ lado se podría agregar barrido perezoso para disminuir aún más el tiempo de
+ pausa real. Se ha mostrado que en muchos casos los tiempos de pausa pueden
+ ser considerablemente altos debido a que la fase de barrido no se realiza en
+ paralelo como el marcado.
+
+ Otra forma de disminuir el tiempo de pausa real sería realizar un barrido
+ concurrente también. Esto no puede realizarse en otro proceso porque el
+ barrido es el encargado de ejecutar los *finalizadores*, pero sí se podría
+ barrer en otro hilo y, por ejemplo, seguir utilizando *eager allocation*
+ hasta que el barrido finalice.
+
+* Mejoras en la precisión del marcado.
+
+ Como se mencionó anteriormente, el área de memoria estática se marca de
+ forma conservativa dada la falta de información de tipos de ésta. Sin
+ embargo es bastante razonable pensar en que el compilador genere información
+ de tipos para el área de memoria estática o que al menos informe mejor al
+ recolector que partes deben ser consideradas parte del *root set* y cuales
+ no. Dado que la memoria estática crece de forma considerable con el
+ incremento de la cantidad de tipos definidos por el usuario, ya solo esa
+ división puede hacer una diferencia importante; en especial considerando
+ como aumenta la memoria estática solamente por usar más tipos de datos en el
+ recolector.
+
+ También podría explorarse el agregado de precisión al *stack* pero esto es
+ realmente muy complicado dado que la única solución que pareciera viable es
+ el uso de *shadow stack* [HEND02]_ que requiere un trabajo extra por cada
+ llamado a función, cosa que va en contra de la filosofía de D_ de pagar solo
+ por lo que se usa. Sin embargo podría explorarse agregar un esquema de ese
+ tipo como una opción del compilador, de forma que el usuario pueda decidir
+ si vale la pena para una aplicación particular o no.
+
+* Mejoras en la concurrencia.
+
+ El *lock* global del recolector es otro aspecto que demostró ser
+ problemático. Podrían analizarse formas de minimizar la necesidad de usar
+ *locks* o de hacerlo de forma más granular, de manera que algunas
+ operaciones del recolector puedan ser ejecutadas en paralelo. También se
+ podría experimentar con el uso de estructura de datos libres de *locks*
+ (*lock-free*).
+
+ Otra forma de minimizar la sincronización es utilizando *pools* por hilo, de
+ manera de poder alocar memoria de forma concurrente y hasta explorar la
+ posibilidad de efectuar recolecciones locales a un solo hilo; aunque esto
+ último probablemente sea equivalente a implementar un recolector de basura
+ con particiones (por ejemplo generacional).
+
+* Recolección con movimiento.
+
+ La información de tipos provista por el trabajo hecho por Vincent Lang
+ [DBZ3463]_ es suficientemente completa como para poder implementar un
+ recolector con movimiento. La efectividad de un recolector de estas
+ características en D_ está por comprobarse, dado que cualquier celda
+ apuntada por alguna palabra que debió ser marcada de forma conservativa debe
+ quedar inmóvil, por lo que gran parte del éxito de un recolector con
+ movimiento en D_ está supeditado a la proporción de celdas que queden
+ inmóviles. Sin embargo sea muy probablemente un área que valga la pena
+ explorar.
-* Cambiar el layout de memoria (mostrar lo encontrado en el post). Se podría
- usar un tamaño de bloque por cada tipo de dato (y por lo tanto una lista de
- libres por cada tipo de dato). Esto podría ahorrar muchos bits (mark,
- freebits, scan, etc.), el puntero al pointer mask se guardaría una sola vez,
- no hay ningún desperdicio de espacio salvo algún padding, pero podrían haber
- esquemas donde ni siquiera (si siempre se alocan tantas páginas como sean
- necesarias para evitar el padding para un tamaño de bloque). Un tipo de dato
- NO_SCAN no alocaría directamente bits de noscan, mark y scan. Se podría
- tratar de forma especial a strings.
-* Hacer preciso el static data por el tema de los TypeInfo's que ocupan mucha
- memoria que debe ser escaneada.
+.. include:: links.rst
.. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :
projects / z.facultad / 75.00 / informe.git / blobdiff