X-Git-Url: https://git.llucax.com/z.facultad/75.00/presentacion.git/blobdiff_plain/3f0d137266f7938e3318e9bb2f6517775609b8d8..3f965dcd7fa6110f68cc8e993685f32fbf8616b4:/presentacion.rst diff --git a/presentacion.rst b/presentacion.rst index 38f3551..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 +* 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 -* Copia de semi-espacio -* **Marcado y barrido** - -.. 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()`` +* Análisis del grafo de conectividad del *heap* +* 50+ años de desarrollo +* 3000+ *papers* - → Finalización +.. 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 -~~~~~~~~~ +Recolector Actual de D +~~~~~~~~~~~~~~~~~~~~~~ * Marcado y barrido * Marcado iterativo @@ -159,68 +61,76 @@ 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 -~~~~~~~~ +Recolector Actual - 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) -Lo Malo y lo Feo -~~~~~~~~~~~~~~~~ +.. r2b-note:: + + 5 min / 38 min + +Recolector Actual - Lo Malo y lo Feo +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 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*) -* Minimiza tiempo de pausa realizando fase de marcado **concurrente** vía +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)``) -Problemas -~~~~~~~~~ +.. r2b-note:: + + 2.5 min / 44 min + +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 @@ -228,8 +138,12 @@ Problemas → Tiempo de pausa en la práctica ~= tiempo total de recolección -Eager Allocation -~~~~~~~~~~~~~~~~ +.. r2b-note:: + + 2.5 min / 46.5 min + +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 @@ -241,8 +155,12 @@ Eager Allocation ↓ Tiempo de pausa real -Early Collection -~~~~~~~~~~~~~~~~ +.. r2b-note:: + + 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 @@ -256,113 +174,36 @@ 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 para cada tipo - de dato + 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 - * 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`` - -* Nuevas opciones +.. r2b-note:: - * ``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 --------------------------------------------------- - -Generalidades -~~~~~~~~~~~~~ -* Múltiples corridas (20-50) - - * Minimizar error en la medición - * Resultados expresados en función de: - - * Mínimo - * Media - * Máximo - * Desvío estándar - -* Minimizar variación entre corridas - - * ``cpufreq-set(1)`` - * ``nice(1)`` - * ``ionice(1)`` - -Programas -~~~~~~~~~ -* Triviales (7) - - * Ejercitar aspectos puntuales - * No realizan una tarea útil - * Casos patológicos - -* Programas pequeños - *Olden Benchmark* (5) - - * 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* - -* 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 - - -Gráficos de Corridas +Resultados -------------------------------------------------- Tiempo Máximo de Stop-The-World @@ -370,21 +211,47 @@ Tiempo Máximo de Stop-The-World .. image:: img/norm-hist-stw.pdf :width: 12.5cm +.. r2b-note:: + + 5.5 min / 67.5 min + + Explicar brevemente división de pruebas (cual es trivial, pequeña, real) + Tiempo Máximo de Pausa Real ~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. image:: img/norm-hist-pause.pdf :width: 12.5cm +.. r2b-note:: + + 2 min / 69.5 min + + Explicar que donde hay grandes diferencias, es por tiempo de barrido + Cantidad Máxima de Memoria Utilizada ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. image:: img/norm-hist-mem.pdf :width: 12.5cm +.. r2b-note:: + + 3.5 min / 73 min + + Enganchar lo anterior con la relación con el consumo de memoria + 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 + Conclusión @@ -418,6 +285,10 @@ Resumen Casi **3 veces menor** (55s → 20s) +.. r2b-note:: + + 4 min / 84 min + Problemas, Limitaciones y Puntos Pendientes ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ * Explosión de uso de memoria con *eager allocation* @@ -425,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* @@ -442,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 ~~~~~~~~~ ¿?