X-Git-Url: https://git.llucax.com/z.facultad/75.00/presentacion.git/blobdiff_plain/72c1f3780eefedb994aa6d24273d19d31b244b5f..cb85e119316f91a9510313c3d7a9ed4eaf2dbe7c:/presentacion.rst diff --git a/presentacion.rst b/presentacion.rst index e9a218a..ca553ce 100644 --- a/presentacion.rst +++ b/presentacion.rst @@ -11,14 +11,15 @@ 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:: @@ -26,12 +27,8 @@ Motivación 1.5 min / 2.5 min - Recolección de Basura --------------------------------------------------- - -Introducción -~~~~~~~~~~~~ +~~~~~~~~~~~~~~~~~~~~~ ¿Qué? * Administración automática de memoria @@ -39,152 +36,21 @@ Introducción ¿Para qué? * Simplificar interfaces -* Mejorar eficiencia (**!**) * Evitar errores de memoria - - * *Dangling pointers* - * *Memory leaks* - * *Double free* +* Mejorar eficiencia (**!**) ¿Cómo? -.. r2b-note:: - - 5 min / 7.5 min - -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 - -.. r2b-note:: - - 5 min / 12.5 min - -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 - -.. r2b-note:: - - 6 min / 18.5 min - - Empieza con John McCarthy en 1959 - - -El Lenguaje de Programación D --------------------------------------------------- - -Características Generales -~~~~~~~~~~~~~~~~~~~~~~~~~ -* Sintaxis tipo C/C++ -* Compilado -* Sistema de tipos estático -* Multi-paradigma +* Análisis del grafo de conectividad del *heap* +* 50+ años de desarrollo +* 3000+ *papers* .. r2b-note:: - 1 min / 19.5 min - -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 - -.. r2b-note:: - - 4.5 min / 24 min - - + 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 - -.. r2b-note:: - - 2.5 min / 26.5 min - -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* - -.. r2b-note:: - - 3.5 min / 30 min - -Algoritmo -~~~~~~~~~ +~~~~~~~~~~~~~~~~~~~~~~~~~ * Marcado y barrido * Marcado iterativo @@ -195,7 +61,7 @@ Algoritmo * *Stop-the-world* - * Durante el marcado, en teoría + * Durante el marcado (en teoría) * *Lock* global @@ -205,16 +71,12 @@ Algoritmo 3 min / 33 min - -Lo Bueno, lo Malo y lo Feo --------------------------------------------------- - 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) @@ -229,12 +91,15 @@ 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:: @@ -245,25 +110,14 @@ Lo feo 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 - -.. r2b-note:: - - 3.5 min / 44 min - -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 @@ -329,127 +183,27 @@ Early Collection disponible para el programa => más recolecciones => más consumo de CPU (y potencialmente run-time) - Otras Mejoras --------------------------------------------------- - -Precisión -~~~~~~~~~ -Adaptación del trabajo de Vincent Lang y David Simcha: - -* Compilador genera información sobre ubicación de los punteros para cada tipo - de dato - - * 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) - -.. r2b-note:: - - 2 min / 58.5 min - -Optimizaciones y Otras Mejoras Menores -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +~~~~~~~~~~~~~ +* 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 / 60.5 min - -Configurabilidad -~~~~~~~~~~~~~~~~ -* Configurable en *tiempo de arranque* -* Vía variable de entorno (``D_GC_OPTS=fork=0 ./prog``) -* Viejas opciones convertidas - - * ``mem_stop`` - * ``sentinel`` - -* Nuevas opciones - - * ``pre_alloc`` - * ``min_free`` - * ``malloc_stats_file`` - * ``collect_stats_file`` - * ``conservative`` - * ``fork`` - * ``eager_alloc`` - * ``early_collect`` - -.. r2b-note:: - - 1.5 min / 62 min + 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)`` - -* 4 *cores* - -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 @@ -571,7 +325,7 @@ Trabajos Futuros ~~~~~~~~~~~~~~~~ * Organización de memoria * Barrido -* Precisión +* \+ Precisión * Concurrencia → *Lock* **global** * Movimiento