X-Git-Url: https://git.llucax.com/z.facultad/75.00/presentacion.git/blobdiff_plain/9894a76113749670dd708db1356c9853cf5f43ca..79995bad473c09e1bc2152464ea821c19285ce4e:/presentacion.rst diff --git a/presentacion.rst b/presentacion.rst index 3e39603..192a7da 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,108 +109,201 @@ Paradigmas +Recolector de Basura de D +============================================================================== +Implementación Actual +-------------------------------------------------- +Organización del Heap +~~~~~~~~~~~~~~~~~~~~~ +*Heap* → *Pools* → Páginas → Bloques + Listas de libres +.. image:: img/heap.pdf + :height: 6.7cm +Bloques +~~~~~~~ +* Tamaño fijo (por página) + * Potencias de 2 + * De 16 a 4096 bytes + * Más de 4096 (una página) + * Objeto **grande** + * Múltiplo de páginas: 4096, 8192, ... + * En páginas contiguas (y mismo *pool*) +* Indicadores (*bit sets* en *pool*) + * Marcado -Recolección de Basura en D -============================================================================== + * *mark* + * *scan* + * *noscan* -Requerimientos --------------------------------------------------- + * Barrido -Según paradigma -~~~~~~~~~~~~~~~ -* Programación de bajo nivel + * *free* + * *finals* - * ``asm`` - * ``union`` - * ``extern (C)`` - * ``malloc()`` +Algoritmo +~~~~~~~~~ +* Marcado y barrido - → Conservativo + Manipulación de *root set* + * Marcado iterativo -* Programación de alto nivel ← Python/Ruby/Perl +* Conservativo - * ``T[]``, ``T[K]`` + * Con una pizca de *precisión* (``NO_SCAN``) - → Punteros interiores +* *Stop-the-world* -* Orientación a objetos ← Java + * Durante el marcado, en teoría - * ``~this()`` +* *Lock* global - → Finalización + * Muy propenso a extender el tiempo de *stop-the-world* en la práctica -Implementación Actual +Lo Bueno, lo Malo y lo Feo -------------------------------------------------- -Organización del heap -~~~~~~~~~~~~~~~~~~~~~ -.. image:: img/heap.pdf - :height: 7cm +Lo Bueno +~~~~~~~~ +* Anda :) +* Organización del *heap* (*two-level allocation*) +* Marcado iterativo (!\ *overflow*) +* *Bit set* para indicadores (caché) -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 +(bueno != perfecto) +Lo Malo y lo Feo +~~~~~~~~~~~~~~~~ +Lo malo -Lo Bueno, lo Malo y lo Feo --------------------------------------------------- +* ↓ Configurabilidad (*no silver bullet*) +* ↓ Precisión (información de tipos) → Memoria inmortal +* ↓ Concurrencia → Grandes pausas +* ↓ Control sobre el factor de ocupación del *heap* → casos patológicos -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 +Lo feo -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 +* El código (complejo, intrincado, duplicado, poco documentado) → Difícil de + mantener, modificar y mejorar Modificaciones Propuestas ============================================================================== -Precisión +Concurrencia -------------------------------------------------- -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 +fork(2) +~~~~~~~ +* Hijo *nace* con una *fotografía* de la memoria del padre +* Aisla modificaciones en la memoria de padre e hijo +* Minimiza copia efectiva de memoria (*COW*) +* Comienza con un solo hilo (el que llamó a ``fork(2)``) +* Muy eficiente -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 +Algoritmo Principal +~~~~~~~~~~~~~~~~~~~ +* Basado en el trabajo de Gustavo Rodriguez-Rivera y Vince Russo (*Non-intrusive + Cloning Garbage Collector with Stock Operating System Support*) +* Minimiza tiempo de pausa realizando fase de marcado **concurrente** vía + ``fork(2)`` +* Proceso padre sigue corriendo el programa +* Proceso hijo realiza fase de marcado +* Se comunican resultados vía memoria compartida +* Sincronización mínima (``fork(2)`` + ``waitpid(2)``) + +Problemas +~~~~~~~~~ +* Hilo que disparó la recolección bloqueado hasta fin de recolección completa + (marcado concurrente inclusive) +* Otros hilos potencialmente bloqueados durante toda la recolección también + (*lock* global) +→ Tiempo de pausa en la práctica ~= tiempo total de recolección -Concurrencia --------------------------------------------------- +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 + concurrente +* Permite al programa (**todos** sus hilos) seguir trabajando mientras se + realiza el marcado concurrente +* Compromiso -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 + ↑ Consumo de memoria -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 + ↓ Tiempo de pausa real +Early Collection +~~~~~~~~~~~~~~~~ +* Dispara una recolección *preventiva* antes de que se agote la memoria +* Permite al programa (**todos** sus hilos) seguir trabajando mientras la + recolección *preventiva* está en progreso +* Si se agota la memoria antes de que la recolección *preventiva* finalice, se + vuelve a bloquear +* Combinable con *eager allocation* para evitar bloquear +* Pueden realizarse más recolecciones de las necesarias +* Compromiso + + ↑ Consumo de procesador (potencialmente) + + ↓ Tiempo de pausa real (no garantizado) -Optimizaciones + +Otras Mejoras -------------------------------------------------- -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 +Precisión +~~~~~~~~~ +Adaptación del trabajo de Vincent Lang y David Simcha: -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 +* Compilador genera información sobre ubicación de los punteros en un tipo + + * Indica si una *palabra* debe ser escaneada (uniones) + * Indica si una palabra es un puntero + +* Se pasa esa información al recolector al momento de pedir memoria +* Recolector original utiliza esa información + + * Almacena un puntero a la información al final del bloque + * Utiliza la información para escanear solo palabras que son punteros (con + seguridad o potencialmente) + +Optimizaciones y Otras Mejoras Menores +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +* Mejora del factor de ocupación del *heap* +* Caché de consultas críticas para acelerar cuellos de botella +* Reestructuración, modularización, simplificación y limpieza del código +* Pre-asignación de memoria +* Optimizaciones algorítmicas sobre búsquedas frecuentes +* Registro de pedidos de memoria y recolecciones realizadas + +Configurabilidad +~~~~~~~~~~~~~~~~ +* Configurable en *tiempo de arranque* +* Vía variable de entorno (``D_GC_OPTS``) +* Viejas opciones convertidas + + * ``mem_stop`` + * ``sentinel`` + +* Nuevas opciones + + * ``pre_alloc`` + * ``min_free`` + * ``malloc_stats_file`` + * ``collect_stats_file`` + * ``conservative`` + * ``fork`` + * ``eager_alloc`` + * ``early_collect`` @@ -220,49 +313,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 @@ -273,18 +394,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: -Problemas, limitaciones y Puntos Pendientes + * *Stop-the-world* **160 veces menor** (1.66s → 0.01s) + * Pausa real **40 veces menor** (1.7s → 0.045s) + +* Objetivo secundario + + 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 ~~~~~~~~~~~~~~~~~~~~~ @@ -298,6 +436,11 @@ Trabajos Relacionados David Simcha (GC + diseño) y Vincent Lang (compilador). No formal, *bug report*, 2009-2010. +* *Non-intrusive Cloning Garbage Collection with Stock Operating System Support* + + Gustavo Rodriguez-Rivera y Vince Russo. Software Practiceand Experience + Volumen 27, Número 8. Agosto 1997. + Trabajos Futuros ~~~~~~~~~~~~~~~~ * Organización de memoria @@ -314,4 +457,5 @@ Fin ~~~ ¡Gracias! + .. vim: set et sw=4 sts=4 spell spelllang=es :