X-Git-Url: https://git.llucax.com/z.facultad/75.00/presentacion.git/blobdiff_plain/bc39f01c85dacd01de7e95478e4aa30333d9be7d..3f0d137266f7938e3318e9bb2f6517775609b8d8:/presentacion.rst?ds=sidebyside diff --git a/presentacion.rst b/presentacion.rst index 16f0454..38f3551 100644 --- a/presentacion.rst +++ b/presentacion.rst @@ -17,7 +17,7 @@ Presentación Motivación ~~~~~~~~~~ * Recolección de basura -* Lenguaje de programación **D** +* Lenguaje de programación D * Utilidad → Software Libre → Contribución @@ -42,11 +42,11 @@ Introducción ¿Cómo? -Algoritmos clásicos +Algoritmos Clásicos ~~~~~~~~~~~~~~~~~~~ * Conteo de referencias -* **Marcado y barrido** * Copia de semi-espacio +* **Marcado y barrido** .. raw:: latex @@ -54,7 +54,7 @@ Algoritmos clásicos .. dummy: para que ande bien el raw de arriba -Estado del arte +Estado del Arte ~~~~~~~~~~~~~~~ * Medio siglo de investigación y desarrollo (3000+ publicaciones) * Objetivo @@ -73,10 +73,10 @@ Estado del arte * Análisis estático -El lenguaje de programación D +El Lenguaje de Programación D -------------------------------------------------- -Características generales +Características Generales ~~~~~~~~~~~~~~~~~~~~~~~~~ * Sintaxis tipo C/C++ * Compilado @@ -109,13 +109,13 @@ Paradigmas -Recolector de basura de D +Recolector de Basura de D ============================================================================== -Implementación actual +Implementación Actual -------------------------------------------------- -Organización del heap +Organización del Heap ~~~~~~~~~~~~~~~~~~~~~ *Heap* → *Pools* → Páginas → Bloques + Listas de libres @@ -166,10 +166,10 @@ Algoritmo * Muy propenso a extender el tiempo de *stop-the-world* en la práctica -Lo bueno, lo malo y lo feo +Lo Bueno, lo Malo y lo Feo -------------------------------------------------- -Lo bueno +Lo Bueno ~~~~~~~~ * Anda :) * Organización del *heap* (*two-level allocation*) @@ -178,7 +178,7 @@ Lo bueno (bueno != perfecto) -Lo malo y lo feo +Lo Malo y lo Feo ~~~~~~~~~~~~~~~~ Lo malo @@ -208,7 +208,7 @@ fork(2) * Comienza con un solo hilo (el que llamó a ``fork(2)``) * Muy eficiente -Algoritmo principal +Algoritmo Principal ~~~~~~~~~~~~~~~~~~~ * Basado en el trabajo de Gustavo Rodriguez-Rivera y Vince Russo (*Non-intrusive Cloning Garbage Collector with Stock Operating System Support*) @@ -228,7 +228,7 @@ Problemas → Tiempo de pausa en la práctica ~= tiempo total de recolección -Eager allocation +Eager Allocation ~~~~~~~~~~~~~~~~ * Crea un nuevo *pool* de memoria antes de lanzar el marcado concurrente * Devuelve memoria del nuevo *pool* al programa mientras termina el marcado @@ -241,7 +241,7 @@ Eager allocation ↓ Tiempo de pausa real -Early collection +Early Collection ~~~~~~~~~~~~~~~~ * Dispara una recolección *preventiva* antes de que se agote la memoria * Permite al programa (**todos** sus hilos) seguir trabajando mientras la @@ -257,16 +257,17 @@ Early collection ↓ Tiempo de pausa real (no garantizado) -Otras mejoras +Otras Mejoras -------------------------------------------------- Precisión ~~~~~~~~~ Adaptación del trabajo de Vincent Lang y David Simcha: -* Compilador genera información sobre ubicación de los punteros en un tipo +* Compilador genera información sobre ubicación de los punteros para cada tipo + de dato - * Indica si una *palabra* debe ser escaneada (uniones) + * Indica si una *palabra* debe ser escaneada * Indica si una palabra es un puntero * Se pasa esa información al recolector al momento de pedir memoria @@ -276,7 +277,7 @@ Adaptación del trabajo de Vincent Lang y David Simcha: * Utiliza la información para escanear solo palabras que son punteros (con seguridad o potencialmente) -Optimizaciones y otras mejoras menores +Optimizaciones y Otras Mejoras Menores ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ * Mejora del factor de ocupación del *heap* * Caché de consultas críticas para acelerar cuellos de botella @@ -313,49 +314,77 @@ Resultados Banco de Pruebas -------------------------------------------------- -Diapositiva 1 +Generalidades ~~~~~~~~~~~~~ -Diapositiva 1 +* Múltiples corridas (20-50) -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 + * Minimizar error en la medición + * Resultados expresados en función de: + * Mínimo + * Media + * Máximo + * Desvío estándar -Tiempo de Stop-The-World --------------------------------------------------- +* Minimizar variación entre corridas -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 + * ``cpufreq-set(1)`` + * ``nice(1)`` + * ``ionice(1)`` -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 +Programas +~~~~~~~~~ +* Triviales (7) + * Ejercitar aspectos puntuales + * No realizan una tarea útil + * Casos patológicos -Tiempo de Pausa Real --------------------------------------------------- +* Programas pequeños - *Olden Benchmark* (5) -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 + * Relativamente pequeños (400-1000 *SLOC*) + * Realizan una tarea útil + * Manipulan mucho listas y árboles asignando mucha memoria + * No son ideales para probar un *GC* -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 +* Programas reales - **Dil** (1) + * Compilador de D escrito en D + * Grande y complejo (32K+ *SLOC*, 86 módulos, 300+ *clases*) + * Programado sin (limitaciones ni ventajas del) *GC* en mente + * Manipulación de *strings*, arreglos dinámicos y asociativos + +Métricas +~~~~~~~~ +* Tiempo total de ejecución +* Tiempo máximo de *stop-the-world* +* Tiempo máximo de pausa real +* Cantidad máxima de memoria utilizada -Tiempo de Ejecución + +Gráficos de Corridas -------------------------------------------------- -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 +Tiempo Máximo de Stop-The-World +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. image:: img/norm-hist-stw.pdf + :width: 12.5cm + +Tiempo Máximo de Pausa Real +~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. image:: img/norm-hist-pause.pdf + :width: 12.5cm + +Cantidad Máxima de Memoria Utilizada +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. image:: img/norm-hist-mem.pdf + :width: 12.5cm + +Tiempo Total de Ejecución +~~~~~~~~~~~~~~~~~~~~~~~~~ +.. image:: img/norm-hist-time.pdf + :width: 12.5cm -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 Conclusión @@ -366,18 +395,35 @@ Conclusión Resumen ~~~~~~~ -* Recolección de basura → Inagotable -* D → Multi-paradigma → Desafío -* Recolección de basura en D → Fértil -* Mejoras propuestas → Efectivas -* Resultados → Positivos: Esperados + Inesperados +* Objetivo principal + + Minimizar tiempo de pausa para programas reales + + Tiempo de pausa de Dil: + + * *Stop-the-world* **160 veces menor** (1.66s → 0.01s) + * Pausa real **40 veces menor** (1.7s → 0.045s) + +* Objetivo secundario -Problemas, limitaciones y Puntos Pendientes + No empeorar mucho el recolector actual en ningún aspecto + + Utilización de memoria de Dil: + + **50% mayor** (mucho *overhead* por marcado preciso) + +* Yapa + + Tiempo total de ejecución de Dil: + + Casi **3 veces menor** (55s → 20s) + +Problemas, Limitaciones y Puntos Pendientes ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -* Predicción de *early collection* * Explosión de uso de memoria con *eager allocation* +* Eficiencia del marcado preciso +* Mejorar predicción de *early collection* * Experimentar con ``clone(2)`` -* Eficiencia de marcado Trabajos Relacionados ~~~~~~~~~~~~~~~~~~~~~ @@ -412,4 +458,5 @@ Fin ~~~ ¡Gracias! + .. vim: set et sw=4 sts=4 spell spelllang=es :