Recorte de diapositivas para bajar a 40 min

diff --git a/Makefile b/Makefile
index 3fce8cb1d2512d71c83c771435167c6945ce0dfe..5fa5df33a96ebcfc1f0705a0dfd9e01bf390a4be 100644 (file)
--- 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 (file)
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 e9a218a4fd3a8c2cf034d9684bd4df4c0c6619d6..ca553ceec75a2c259678ec0ef5792895f0f0cee9 100644 (file)
--- 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