From: Leandro Lucarella Date: Sun, 5 Dec 2010 02:44:39 +0000 (-0300) Subject: Recorte de diapositivas para bajar a 40 min X-Git-Tag: defensa-tesis~10 X-Git-Url: https://git.llucax.com/z.facultad/75.00/presentacion.git/commitdiff_plain/7d81729c71b10be8a603fd924d7c665a20f211cf Recorte de diapositivas para bajar a 40 min --- diff --git a/Makefile b/Makefile index 3fce8cb..5fa5df3 100644 --- a/Makefile +++ b/Makefile @@ -2,7 +2,7 @@ O := .tmp R2B := ./rst2beamer.py -R2BTHEME := Darmstadt +R2BTHEME := Frankfurt R2BFLAGS := --halt=2 --lang es --codeblocks-use-pygments \ --input-encoding=utf-8 --output-encoding=utf-8 \ --overlaybullets= \ @@ -12,9 +12,6 @@ R2BFILTER := sed '/\\usepackage\[scaled=\.90\]{helvet}/d' DOT := dot DOTFLAGS := -AAFIG := aafigure -AAFIGFLAGS := --proportional - PDFLATEX := pdflatex PDFLATEXFLAGS := -halt-on-error -file-line-error @@ -33,7 +30,6 @@ comma := , imgs := $O/img/mark-sweep-0.pdf \ $(patsubst %.dot,$O/%.pdf,$(wildcard img/mark-sweep-*.dot)) \ - $O/img/heap.pdf \ $(patsubst %,$O/img/norm-hist-%.pdf,$(PLOTS)) # Verbosity flag (empty show nice messages, non-empty use make messages) @@ -70,9 +66,6 @@ $O/notas.tex: presentacion.rst $(R2B) $O/img/%.pdf: img/%.dot $(DOT) $(DOTFLAGS) -Tpdf -o $@ $< -$O/img/%.pdf: img/%.aafig - $(AAFIG) $(AAFIGFLAGS) -t pdf -o $@ $< - $O/img/norm-hist-%.csv: img/raw-hist-%.csv $(if $V,@echo "norm $< > $@") $V $(AWK) -F, -v m=`cut -d, -f4 $< | $(STATS) '$$1' '%(max)s'` \ @@ -91,8 +84,6 @@ $O/img/norm-hist-%.pdf: $O/img/norm-hist-%.eps $O/img/%.pdf: img/%.pdf cp $< $@ -$O/heap.pdf: AAFIGFLAGS += -s 1.4 -a 0.8 - .PHONY: clean clean: $(RM) -r $O diff --git a/img/heap.aafig b/img/heap.aafig deleted file mode 100644 index 46ae265..0000000 --- a/img/heap.aafig +++ /dev/null @@ -1,47 +0,0 @@ - -+----------------------------------------------------------------------+ -| Heap | -+======================================================================+ -| "Pool 0" "Pool 1" "Pool 2" "Pool 3" ... "Pool N" | -| +----------+ +----------+ +----------+ +----------+ +----------+ | -| | Página 0 | | Página 0 | | Página 0 | | Página 0 | ... | Página 0 | | -| | (8x512) | | (4x1024) | | (64x64) | | (2x2048) | ... | (1x4096) | | -| |+--------+| |+--------+| |+--------+| |+--------+| |+--------+| | -| || Bloque || || || ||qqqqqqqq|| || || || || | -| |+--------+| || Bloque || ||qqqqqqqq|| || || || || | -| || Bloque || || || ||qqqqqqqq|| || || || || | -| |+--------+| |+--------+| ||qqqqqqqq|| || Bloque || || || | -| || Bloque || || || ||qqqqqqqq|| || || || || | -| |+--------+| || Bloque || ||qqqqqqqq|| || || || || | -| || Bloque || || || ||qqqqqqqq|| || || || || | -| |+--------+| |+--------+| ||qqqqqqqq|| |+--------+| || Bloque || | -| || Bloque || || || ||qqqqqqqq|| || || || || | -| |+--------+| || Bloque || ||qqqqqqqq|| || || || || | -| || Bloque || || || ||qqqqqqqq|| || || || || | -| |+--------+| |+--------+| ||qqqqqqqq|| || Bloque || || || | -| || Bloque || || || ||qqqqqqqq|| || || || || | -| |+--------+| || Bloque || ||qqqqqqqq|| || || || || | -| || Bloque || || || ||qqqqqqqq|| || || || || | -| |+--------+| |+--------+| |+--------+| |+--------+| |+--------+| | -| | Página 1 | | Página 1 | +----------+ | Página 1 | ... | Página 1 | | -| | (16x256) | | (8x512) | | (32x128) | ... | (1x4096) | | -| |+--------+| |+--------+| |+--------+| |+--------+| | -| |+--------+| || Bloque || ||nnnnnnnn|| || || | -| |+--------+| |+--------+| ||nnnnnnnn|| || || | -| |+--------+| || Bloque || ||nnnnnnnn|| || || | -| |+--------+| |+--------+| ||nnnnnnnn|| || || | -| |+--------+| || Bloque || ||nnnnnnnn|| || || | -| |+--------+| |+--------+| ||nnnnnnnn|| || || | -| |+--------+| || Bloque || ||nnnnnnnn|| || || | -| |+--------+| |+--------+| ||nnnnnnnn|| || Bloque || | -| |+--------+| || Bloque || ||nnnnnnnn|| || || | -| |+--------+| |+--------+| ||nnnnnnnn|| || || | -| |+--------+| || Bloque || ||nnnnnnnn|| || || | -| |+--------+| |+--------+| ||nnnnnnnn|| || || | -| |+--------+| || Bloque || ||nnnnnnnn|| || || | -| |+--------+| |+--------+| ||nnnnnnnn|| || || | -| |+--------+| || Bloque || ||nnnnnnnn|| || || | -| |+--------+| |+--------+| |+--------+| ... |+--------+| | -| +----------+ +----------+ +----------+ +----------+ | -+----------------------------------------------------------------------+ - 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