X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/15b868186b7ca1853b52a34ace0865f1cc24c677..6c0df59:/source/conclusion.rst?ds=sidebyside diff --git a/source/conclusion.rst b/source/conclusion.rst index 88b5cd1..7df0af3 100644 --- a/source/conclusion.rst +++ b/source/conclusion.rst @@ -2,7 +2,7 @@ .. 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: TERMINADO .. _conclusion: @@ -10,47 +10,440 @@ 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. + + + +.. _con_pending: + +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 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 - -* 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. -* 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). -* Hacer preciso el static data por el tema de los TypeInfo's que ocupan mucha - memoria que debe ser escaneada. +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 punteros* + 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. + +.. include:: links.rst .. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :