X-Git-Url: https://git.llucax.com/z.facultad/75.00/presentacion.git/blobdiff_plain/39db1a27fc811db16e2fc51cf39ab3771a7c23a3..3f965dcd7fa6110f68cc8e993685f32fbf8616b4:/presentacion.rst diff --git a/presentacion.rst b/presentacion.rst index 41a6e61..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,273 +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 - -.. raw:: latex +* Análisis del grafo de conectividad del *heap* +* 50+ años de desarrollo +* 3000+ *papers* - \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 +.. r2b-note:: - * ↓ Tiempo total de ejecución - * ↓ Cantidad de recolecciones - * ↓ Tiempo de recolección - * ↓ **Tiempo (máximo) de pausa** + 5 min / 7.5 min -* Técnicas +Recolector Actual de D +~~~~~~~~~~~~~~~~~~~~~~ +* Marcado y barrido - * Particiones - * **Concurrencia** - * Organización de memoria - * **Precisión** - * Análisis estático + * Marcado iterativo +* Conservativo -El lenguaje de programación D --------------------------------------------------- + * Con una pizca de *precisión* (``NO_SCAN``) -Características generales -~~~~~~~~~~~~~~~~~~~~~~~~~ -* Sintaxis tipo C/C++ -* Compilado -* Sistema de tipos estático -* Multi-paradigma +* *Stop-the-world* -Paradigmas -~~~~~~~~~~ -* Programación de bajo nivel (*system-programming*) ← C/C++ + * Durante el marcado (en teoría) - * ``asm`` - * ``union`` - * ``extern (C)`` - * ``malloc()`` +* *Lock* global -* Programación de alto nivel ← Python/Ruby/Perl + * Muy propenso a extender el tiempo de *stop-the-world* en la práctica - * *GC* - * ``T[]``, ``T[K]`` +.. r2b-note:: -* Orientación a objetos ← Java + 3 min / 33 min - * ``~this()`` +Recolector Actual - Lo Bueno +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +* Anda :) +* Organización del *heap* (< fragmentación) +* Marcado iterativo (!\ *overflow*) +* *Bitset* para bits de marca (*cache friendly*) -* Programación genérica y meta-programación ← C++ -* Programación por contratos ← Eiffel +(bueno != perfecto) .. r2b-note:: - * Programación de bajo nivel (*system-programming*) ← C/C++ - - * **asm**, ``goto``, **align**, ``struct``, **union**, **link-compitble con C**, - **malloc** + 5 min / 38 min - * Programación de alto nivel ← Python/Ruby/Perl +Recolector Actual - Lo Malo y lo Feo +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Lo malo - * **GC**, module/import, ``delegate``, ``lazy``, *strings*, **arreglos dinámicos - y asociativos**, ddoc, inferencia de tipos (ltd), ``foreach`` +* ↓ Configurabilidad (*no silver bullet*) +* ↓ Precisión (información de tipos) → Memoria inmortal +* ↓ Concurrencia → Grandes pausas +* ↓ Control sobre el factor de ocupación del *heap* - * Orientación a objetos ← Java + → Casos patológicos - * Más Java que C++: semántica de referencia, métodos siempre virtuales, herencia - simple + interfaces, clases anidadas, **destructores**... + Properties +Lo feo - * Programación genérica y meta-programación ← C++ +* El código (complejo, intrincado, duplicado, poco documentado) - * ``static if``, ``typeof``, (*variadic*) ``tamplate``, *CTFE*, (*string*) - ``mixin``\ s, expresiones ``is`` + → Difícil de mantener, modificar y mejorar - * Programación por contratos ← Eiffel +.. r2b-note:: - * Excepciones, ``assert``, pre/post condiciones, ``invariant``, ``unittest``, - ``scope``, inicialización garantizada, *RAII*, ``synchronized`` + 3.5 min / 41.5 min -Recolección de Basura en D +Modificaciones Propuestas ============================================================================== -Requerimientos +Modificaciones Propuestas -------------------------------------------------- -Según paradigma -~~~~~~~~~~~~~~~ -* Programación de bajo nivel +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)``) - * ``asm`` - * ``union`` - * ``extern (C)`` - * ``malloc()`` +.. r2b-note:: - → Conservativo + Manipulación de *root set* + 2.5 min / 44 min -* Programación de alto nivel ← Python/Ruby/Perl +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) - * ``T[]``, ``T[K]`` +→ Tiempo de pausa en la práctica ~= tiempo total de recolección - → Punteros interiores +.. r2b-note:: -* Orientación a objetos ← Java + 2.5 min / 46.5 min - * ``~this()`` +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 - → Finalización + ↑ Consumo de memoria + ↓ Tiempo de pausa real -Implementación Actual --------------------------------------------------- +.. r2b-note:: -Organización del heap -~~~~~~~~~~~~~~~~~~~~~ -.. image:: img/heap.pdf - :height: 7cm + 6.5 min / 53 min -Diapositiva 2 -~~~~~~~~~~~~~ -Diapositiva 2 +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 + ↑ Consumo de procesador (potencialmente) -Lo Bueno, lo Malo y lo Feo --------------------------------------------------- + ↓ Tiempo de pausa real (no garantizado) -Diapositiva 1 -~~~~~~~~~~~~~ -Diapositiva 1 +.. r2b-note:: + + 3.5 min / 56.5 min -Diapositiva 2 + 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) + +Otras Mejoras ~~~~~~~~~~~~~ -Diapositiva 2 +* 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*) +.. 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 → Acierto -* Resultados → 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 ~~~~~~~~~~~~~~~~~~~~~ @@ -310,17 +309,30 @@ Trabajos Relacionados * *Integrate Precise Heap Scanning Into the GC* - David Simcha (GC + diseño) + Vincent Lang (compilador). No formal, *bug + 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 ~~~~~~~~~ ¿? @@ -329,4 +341,5 @@ Fin ~~~ ¡Gracias! + .. vim: set et sw=4 sts=4 spell spelllang=es :