X-Git-Url: https://git.llucax.com/z.facultad/75.00/presentacion.git/blobdiff_plain/544e90427fec08ffcbe531983e86a3dbb997fe83..cb85e119316f91a9510313c3d7a9ed4eaf2dbe7c:/presentacion.rst diff --git a/presentacion.rst b/presentacion.rst index beae120..ca553ce 100644 --- a/presentacion.rst +++ b/presentacion.rst @@ -11,21 +11,24 @@ Recolección de Basura en D Introducción ============================================================================== -Presentación +Introducción -------------------------------------------------- Motivación ~~~~~~~~~~ * Recolección de basura * Lenguaje de programación D -* Utilidad → Software Libre → Contribución +* Investigación + aplicación +* Software Libre +.. r2b-note:: -Recolección de Basura --------------------------------------------------- + 1 min de presentación -Introducción -~~~~~~~~~~~~ + 1.5 min / 2.5 min + +Recolección de Basura +~~~~~~~~~~~~~~~~~~~~~ ¿Qué? * Administración automática de memoria @@ -33,122 +36,21 @@ Introducción ¿Para qué? * Simplificar interfaces -* Mejorar eficiencia (**!**) * Evitar errores de memoria - - * *Dangling pointers* - * *Memory leaks* - * *Double free* +* Mejorar eficiencia (**!**) ¿Cómo? -Algoritmos Clásicos -~~~~~~~~~~~~~~~~~~~ -* Conteo de referencias -* **Marcado y barrido** -* Copia de semi-espacio - -.. raw:: latex - - \multiinclude[format=pdf,graphics={height=4.5cm}]{img/mark-sweep} - -.. dummy: para que ande bien el raw de arriba - -Estado del Arte -~~~~~~~~~~~~~~~ -* Medio siglo de investigación y desarrollo (3000+ publicaciones) -* Objetivo - - * ↓ Tiempo total de ejecución - * ↓ Cantidad de recolecciones - * ↓ Tiempo de recolección - * ↓ **Tiempo (máximo) de pausa** - -* Técnicas - - * Particiones - * **Concurrencia** - * Organización de memoria - * **Precisión** - * Análisis estático - - -El Lenguaje de Programación D --------------------------------------------------- - -Características Generales -~~~~~~~~~~~~~~~~~~~~~~~~~ -* Sintaxis tipo C/C++ -* Compilado -* Sistema de tipos estático -* Multi-paradigma - -Paradigmas -~~~~~~~~~~ -* Programación de bajo nivel (*system-programming*) ← C/C++ - - * ``asm`` - * ``union`` - * ``extern (C)`` - * ``malloc()`` - - → Conservativo + Manipulación de *root set* - -* Programación de alto nivel ← Python/Ruby/Perl - - * *GC* - * ``T[]``, ``T[K]`` - - → Punteros interiores - -* Orientación a objetos ← Java - - * ``~this()`` - - → Finalización +* Análisis del grafo de conectividad del *heap* +* 50+ años de desarrollo +* 3000+ *papers* +.. r2b-note:: + 5 min / 7.5 min 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 - - * *mark* - * *scan* - * *noscan* - - * Barrido - - * *free* - * *finals* - -Algoritmo -~~~~~~~~~ +~~~~~~~~~~~~~~~~~~~~~~~~~ * Marcado y barrido * Marcado iterativo @@ -159,25 +61,29 @@ Algoritmo * *Stop-the-world* - * Durante el marcado, en teoría + * Durante el marcado (en teoría) * *Lock* global * Muy propenso a extender el tiempo de *stop-the-world* en la práctica +.. r2b-note:: -Lo Bueno, lo Malo y lo Feo --------------------------------------------------- + 3 min / 33 min Lo Bueno ~~~~~~~~ * Anda :) -* Organización del *heap* (*two-level allocation*) +* Organización del *heap* (< fragmentación) * Marcado iterativo (!\ *overflow*) -* *Bit set* para indicadores (caché) +* *Bitset* para bits de marca (*cache friendly*) (bueno != perfecto) +.. r2b-note:: + + 5 min / 38 min + Lo Malo y lo Feo ~~~~~~~~~~~~~~~~ Lo malo @@ -185,33 +91,33 @@ Lo malo * ↓ 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 +* ↓ Control sobre el factor de ocupación del *heap* + + → Casos patológicos Lo feo -* El código (complejo, intrincado, duplicado, poco documentado) → Difícil de - mantener, modificar y mejorar +* El código (complejo, intrincado, duplicado, poco documentado) + + → Difícil de mantener, modificar y mejorar + +.. r2b-note:: + + 3.5 min / 41.5 min Modificaciones Propuestas ============================================================================== -Concurrencia +Modificaciones Propuestas -------------------------------------------------- -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 - -Algoritmo Principal -~~~~~~~~~~~~~~~~~~~ -* Basado en el trabajo de Gustavo Rodriguez-Rivera y Vince Russo (*Non-intrusive - Cloning Garbage Collector with Stock Operating System Support*) +Concurrencia +~~~~~~~~~~~~ +* Algoritmo 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 @@ -219,6 +125,10 @@ Algoritmo Principal * Se comunican resultados vía memoria compartida * Sincronización mínima (``fork(2)`` + ``waitpid(2)``) +.. r2b-note:: + + 2.5 min / 44 min + Problemas ~~~~~~~~~ * Hilo que disparó la recolección bloqueado hasta fin de recolección completa @@ -228,6 +138,10 @@ Problemas → Tiempo de pausa en la práctica ~= tiempo total de recolección +.. r2b-note:: + + 2.5 min / 46.5 min + Eager Allocation ~~~~~~~~~~~~~~~~ * Crea un nuevo *pool* de memoria antes de lanzar el marcado concurrente @@ -241,6 +155,10 @@ Eager Allocation ↓ Tiempo de pausa real +.. r2b-note:: + + 6.5 min / 53 min + Early Collection ~~~~~~~~~~~~~~~~ * Dispara una recolección *preventiva* antes de que se agote la memoria @@ -256,106 +174,84 @@ Early Collection ↓ Tiempo de pausa real (no garantizado) +.. r2b-note:: -Otras Mejoras --------------------------------------------------- - -Precisión -~~~~~~~~~ -Adaptación del trabajo de Vincent Lang y David Simcha: + 3.5 min / 56.5 min -* Compilador genera información sobre ubicación de los punteros en un tipo + Si hago una recolección cuando queda 20% de memoria libre y nadie pide más + memoria mientras se recolecta, es como si tuviera 20% menos de memoria + disponible para el programa => más recolecciones => más consumo de CPU (y + potencialmente run-time) - * 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 -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Otras Mejoras +~~~~~~~~~~~~~ +* Marcado semi-preciso del *heap* * 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 (en *tiempo de inicialización*) -Configurabilidad -~~~~~~~~~~~~~~~~ -* Configurable en *tiempo de arranque* -* Vía variable de entorno (``D_GC_OPTS``) -* Viejas opciones convertidas - - * ``mem_stop`` - * ``sentinel`` +.. r2b-note:: -* Nuevas opciones - - * ``pre_alloc`` - * ``min_free`` - * ``malloc_stats_file`` - * ``collect_stats_file`` - * ``conservative`` - * ``fork`` - * ``eager_alloc`` - * ``early_collect`` + 2 min / 58.5 min Resultados ============================================================================== -Banco de Pruebas +Resultados -------------------------------------------------- -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 +Tiempo Máximo de Stop-The-World +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. image:: img/norm-hist-stw.pdf + :width: 12.5cm -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 +.. r2b-note:: + 5.5 min / 67.5 min -Tiempo de Stop-The-World --------------------------------------------------- + Explicar brevemente división de pruebas (cual es trivial, pequeña, real) -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 +Tiempo Máximo de Pausa Real +~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. image:: img/norm-hist-pause.pdf + :width: 12.5cm -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 +.. r2b-note:: + 2 min / 69.5 min -Tiempo de Pausa Real --------------------------------------------------- + Explicar que donde hay grandes diferencias, es por tiempo de barrido -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 +Cantidad Máxima de Memoria Utilizada +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. image:: img/norm-hist-mem.pdf + :width: 12.5cm -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 +.. r2b-note:: + 3.5 min / 73 min -Tiempo de Ejecución --------------------------------------------------- + Enganchar lo anterior con la relación con el consumo de memoria -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 +Tiempo Total de Ejecución +~~~~~~~~~~~~~~~~~~~~~~~~~ +.. image:: img/norm-hist-time.pdf + :width: 12.5cm + +.. r2b-note:: + + 7 min / 80 min + + * mcore y split bajan mucho por caché de tamaño + * rnddata baja mucho por marcado preciso + * bigarr y sbtree suben porque no hacen más que alocar -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 Conclusión @@ -366,11 +262,32 @@ 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 + + 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) + +.. r2b-note:: + + 4 min / 84 min Problemas, Limitaciones y Puntos Pendientes ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -379,6 +296,10 @@ Problemas, Limitaciones y Puntos Pendientes * Mejorar predicción de *early collection* * Experimentar con ``clone(2)`` +.. r2b-note:: + + 3 min / 87 min + Trabajos Relacionados ~~~~~~~~~~~~~~~~~~~~~ * *Memory Management in the D Programming Language* @@ -396,14 +317,22 @@ Trabajos Relacionados Gustavo Rodriguez-Rivera y Vince Russo. Software Practiceand Experience Volumen 27, Número 8. Agosto 1997. +.. r2b-note:: + + 1.5 min / 88.5 min + Trabajos Futuros ~~~~~~~~~~~~~~~~ * Organización de memoria * Barrido -* Precisión +* \+ Precisión * Concurrencia → *Lock* **global** * Movimiento +.. r2b-note:: + + 1.5 min / 92 min + Preguntas ~~~~~~~~~ ¿?