X-Git-Url: https://git.llucax.com/z.facultad/75.00/presentacion.git/blobdiff_plain/9894a76113749670dd708db1356c9853cf5f43ca..3f965dcd7fa6110f68cc8e993685f32fbf8616b4:/presentacion.rst diff --git a/presentacion.rst b/presentacion.rst index 3e39603..113ec0a 100644 --- a/presentacion.rst +++ b/presentacion.rst @@ -5,27 +5,30 @@ Recolección de Basura en D :Autor: Leandro Lucarella :Fecha: Diciembre 2010 -:Organización: FIUBA +:Organización: Facultad de Ingeniería, UBA Introducción ============================================================================== -Presentación +Introducción -------------------------------------------------- Motivación ~~~~~~~~~~ * Recolección de basura -* Lenguaje de programación **D** -* Utilidad → Software Libre → Contribución +* Lenguaje de programación D +* 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,258 +36,269 @@ 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 +* Análisis del grafo de conectividad del *heap* +* 50+ años de desarrollo +* 3000+ *papers* -.. raw:: latex +.. r2b-note:: - \multiinclude[format=pdf,graphics={height=4.5cm}]{img/mark-sweep} + 5 min / 7.5 min -.. dummy: para que ande bien el raw de arriba +Recolector Actual de D +~~~~~~~~~~~~~~~~~~~~~~ +* Marcado y barrido -Estado del arte -~~~~~~~~~~~~~~~ -* Medio siglo de investigación y desarrollo (3000+ publicaciones) -* Objetivo + * Marcado iterativo - * ↓ Tiempo total de ejecución - * ↓ Cantidad de recolecciones - * ↓ Tiempo de recolección - * ↓ **Tiempo (máximo) de pausa** +* Conservativo -* Técnicas + * Con una pizca de *precisión* (``NO_SCAN``) - * Particiones - * **Concurrencia** - * Organización de memoria - * **Precisión** - * Análisis estático +* *Stop-the-world* + * Durante el marcado (en teoría) -El lenguaje de programación D --------------------------------------------------- +* *Lock* global -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++ + * Muy propenso a extender el tiempo de *stop-the-world* en la práctica - * ``asm`` - * ``union`` - * ``extern (C)`` - * ``malloc()`` +.. r2b-note:: - → Conservativo + Manipulación de *root set* + 3 min / 33 min -* Programación de alto nivel ← Python/Ruby/Perl +Recolector Actual - Lo Bueno +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +* Anda :) +* Organización del *heap* (< fragmentación) +* Marcado iterativo (!\ *overflow*) +* *Bitset* para bits de marca (*cache friendly*) - * *GC* - * ``T[]``, ``T[K]`` +(bueno != perfecto) - → Punteros interiores +.. r2b-note:: -* Orientación a objetos ← Java + 5 min / 38 min - * ``~this()`` +Recolector Actual - Lo Malo y lo Feo +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Lo malo - → Finalización +* ↓ 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 +Lo feo +* 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 +============================================================================== +Modificaciones Propuestas +-------------------------------------------------- +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 +* Proceso hijo realiza fase de marcado +* Se comunican resultados vía memoria compartida +* Sincronización mínima (``fork(2)`` + ``waitpid(2)``) -Recolección de Basura en D -============================================================================== +.. r2b-note:: -Requerimientos --------------------------------------------------- + 2.5 min / 44 min -Según paradigma -~~~~~~~~~~~~~~~ -* Programación de bajo nivel +Concurrencia - 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) - * ``asm`` - * ``union`` - * ``extern (C)`` - * ``malloc()`` +→ Tiempo de pausa en la práctica ~= tiempo total de recolección - → Conservativo + Manipulación de *root set* +.. r2b-note:: -* Programación de alto nivel ← Python/Ruby/Perl + 2.5 min / 46.5 min - * ``T[]``, ``T[K]`` +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 - → Punteros interiores + ↑ Consumo de memoria -* Orientación a objetos ← Java + ↓ Tiempo de pausa real - * ``~this()`` +.. r2b-note:: - → Finalización + 6.5 min / 53 min +Concurrencia - 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 -Implementación Actual --------------------------------------------------- + ↑ Consumo de procesador (potencialmente) -Organización del heap -~~~~~~~~~~~~~~~~~~~~~ -.. image:: img/heap.pdf - :height: 7cm + ↓ Tiempo de pausa real (no garantizado) -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 +.. r2b-note:: + 3.5 min / 56.5 min -Lo Bueno, lo Malo y lo Feo --------------------------------------------------- + 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) -Diapositiva 1 +Otras Mejoras ~~~~~~~~~~~~~ -Diapositiva 1 +* 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*) -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 +.. r2b-note:: + 2 min / 58.5 min -Modificaciones Propuestas + +Resultados ============================================================================== -Precisión +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 -Concurrencia --------------------------------------------------- + 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 -Optimizaciones --------------------------------------------------- + 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 + Enganchar lo anterior con la relación con el consumo de memoria -Resultados -============================================================================== +Tiempo Total de Ejecución +~~~~~~~~~~~~~~~~~~~~~~~~~ +.. image:: img/norm-hist-time.pdf + :width: 12.5cm -Banco de Pruebas --------------------------------------------------- +.. r2b-note:: -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 + 7 min / 80 min -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 + * 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 -Tiempo de Stop-The-World --------------------------------------------------- -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 +Conclusión +============================================================================== -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 +Conclusión +-------------------------------------------------- +Resumen +~~~~~~~ +* Objetivo principal -Tiempo de Pausa Real --------------------------------------------------- + Minimizar tiempo de pausa para programas reales -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 + Tiempo de pausa de Dil: -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 + * *Stop-the-world* **160 veces menor** (1.66s → 0.01s) + * Pausa real **40 veces menor** (1.7s → 0.045s) +* Objetivo secundario -Tiempo de Ejecución --------------------------------------------------- + No empeorar mucho el recolector actual en ningún aspecto -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 + Utilización de memoria de Dil: -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 + **50% mayor** (mucho *overhead* por marcado preciso) +* Yapa -Conclusión -============================================================================== + Tiempo total de ejecución de Dil: -Conclusión --------------------------------------------------- + Casi **3 veces menor** (55s → 20s) -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 +.. r2b-note:: + + 4 min / 84 min -Problemas, limitaciones y Puntos Pendientes +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 + +.. r2b-note:: + + 3 min / 87 min Trabajos Relacionados ~~~~~~~~~~~~~~~~~~~~~ @@ -298,14 +312,27 @@ 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. + +.. 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 ~~~~~~~~~ ¿? @@ -314,4 +341,5 @@ Fin ~~~ ¡Gracias! + .. vim: set et sw=4 sts=4 spell spelllang=es :