Borrar notas.pdf en make clean-all

[z.facultad/75.00/presentacion.git] / presentacion.rst

diff --git a/presentacion.rst b/presentacion.rst
index 214474334107cf458a9a82f759809f30182c3380..ca553ceec75a2c259678ec0ef5792895f0f0cee9 100644 (file)
--- a/presentacion.rst
+++ b/presentacion.rst
@@ -11,21 +11,24 @@ Recolección de Basura en D
 Introducción
 ==============================================================================
 
 Introducción
 ==============================================================================
 

-Presentación
+Introducción

 --------------------------------------------------
 
 Motivación
 ~~~~~~~~~~
 * Recolección de basura
 * Lenguaje de programación D
 --------------------------------------------------
 
 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
 ¿Qué?
 
 * Administración automática de memoria


@@ -33,122 +36,21 @@ Introducción
 ¿Para qué?
 
 * Simplificar interfaces
 ¿Para qué?
 
 * Simplificar interfaces

-* Mejorar eficiencia (**!**)

 * Evitar errores de memoria
 * Evitar errores de memoria

-
-  * *Dangling pointers*
-  * *Memory leaks*
-  * *Double free*
+* Mejorar eficiencia (**!**)

 
 ¿Cómo?
 
 
 ¿Cómo?
 

-Algoritmos Clásicos
-~~~~~~~~~~~~~~~~~~~
-* Conteo de referencias
-* **Marcado y barrido**
-* Copia de semi-espacio
-
-.. 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()``
-
-  → Finalización
+* Análisis del grafo de conectividad del *heap*
+* 50+ años de desarrollo
+* 3000+ *papers*

 
 

+.. r2b-note::

 
 

+    5 min / 7.5 min

 
 Recolector de Basura de D
 
 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
-~~~~~~~~~
+~~~~~~~~~~~~~~~~~~~~~~~~~

 * Marcado y barrido
 
   * Marcado iterativo
 * Marcado y barrido
 
   * Marcado iterativo


@@ -159,25 +61,29 @@ Algoritmo
 
 * *Stop-the-world*
 
 
 * *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
 
 
 * *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
 ~~~~~~~~
 * Anda :)
 
 Lo Bueno
 ~~~~~~~~
 * Anda :)

-* Organización del *heap* (*two-level allocation*)
+* Organización del *heap* (< fragmentación)

 * Marcado iterativo (!\ *overflow*)
 * Marcado iterativo (!\ *overflow*)

-* *Bit set* para indicadores (caché)
+* *Bitset* para bits de marca (*cache friendly*)

 
 (bueno != perfecto)
 
 
 (bueno != perfecto)
 

+.. r2b-note::
+
+    5 min / 38 min
+

 Lo Malo y lo Feo
 ~~~~~~~~~~~~~~~~
 Lo malo
 Lo Malo y lo Feo
 ~~~~~~~~~~~~~~~~
 Lo malo


@@ -185,33 +91,33 @@ Lo malo
 * ↓ Configurabilidad (*no silver bullet*)
 * ↓ Precisión (información de tipos) → Memoria inmortal
 * ↓ Concurrencia → Grandes pausas
 * ↓ 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
 
 
 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
 ==============================================================================
 
 
 
 
 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*)
+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
 * Minimiza tiempo de pausa realizando fase de marcado **concurrente** vía
   ``fork(2)``
 * Proceso padre sigue corriendo el programa


@@ -219,6 +125,10 @@ Algoritmo Principal
 * Se comunican resultados vía memoria compartida
 * Sincronización mínima (``fork(2)`` + ``waitpid(2)``)
 
 * Se comunican resultados vía memoria compartida
 * Sincronización mínima (``fork(2)`` + ``waitpid(2)``)
 

+.. r2b-note::
+
+    2.5 min / 44 min
+

 Problemas
 ~~~~~~~~~
 * Hilo que disparó la recolección bloqueado hasta fin de recolección completa
 Problemas
 ~~~~~~~~~
 * Hilo que disparó la recolección bloqueado hasta fin de recolección completa


@@ -228,6 +138,10 @@ Problemas
 
 → Tiempo de pausa en la práctica ~= tiempo total de recolección
 
 
 → Tiempo de pausa en la práctica ~= tiempo total de recolección
 

+.. r2b-note::
+
+    2.5 min / 46.5 min
+

 Eager Allocation
 ~~~~~~~~~~~~~~~~
 * Crea un nuevo *pool* de memoria antes de lanzar el marcado concurrente
 Eager Allocation
 ~~~~~~~~~~~~~~~~
 * Crea un nuevo *pool* de memoria antes de lanzar el marcado concurrente


@@ -241,6 +155,10 @@ Eager Allocation
 
   ↓ Tiempo de pausa real
 
 
   ↓ Tiempo de pausa real
 

+.. r2b-note::
+
+    6.5 min / 53 min
+

 Early Collection
 ~~~~~~~~~~~~~~~~
 * Dispara una recolección *preventiva* antes de que se agote la memoria
 Early Collection
 ~~~~~~~~~~~~~~~~
 * Dispara una recolección *preventiva* antes de que se agote la memoria


@@ -256,133 +174,83 @@ Early Collection
 
   ↓ Tiempo de pausa real (no garantizado)
 
 
   ↓ Tiempo de pausa real (no garantizado)
 

+.. r2b-note::

 
 

-Otras Mejoras
---------------------------------------------------
-
-Precisión
-~~~~~~~~~
-Adaptación del trabajo de Vincent Lang y David Simcha:
-
-* Compilador genera información sobre ubicación de los punteros en un tipo
+    3.5 min / 56.5 min

 
 

-  * Indica si una *palabra* debe ser escaneada (uniones)
-  * Indica si una palabra es un puntero
+    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)

 
 

-* 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
 * 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``
+.. r2b-note::

 
 

-* Nuevas opciones
-
-  * ``pre_alloc``
-  * ``min_free``
-  * ``malloc_stats_file``
-  * ``collect_stats_file``
-  * ``conservative``
-  * ``fork``
-  * ``eager_alloc``
-  * ``early_collect``
+    2 min / 58.5 min

 
 
 
 Resultados
 ==============================================================================
 
 
 
 
 Resultados
 ==============================================================================
 

-Banco de Pruebas
+Resultados

 --------------------------------------------------
 
 --------------------------------------------------
 

-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)``
+Tiempo Máximo de Stop-The-World
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+.. image:: img/norm-hist-stw.pdf
+    :width: 12.5cm

 
 

-Programas
-~~~~~~~~~
-* Triviales (7)
+.. r2b-note::

 
 

-  * Ejercitar aspectos puntuales
-  * No realizan una tarea útil
-  * Casos patológicos
+    5.5 min / 67.5 min

 
 

-* Programas pequeños - *Olden Benchmark* (5)
+    Explicar brevemente división de pruebas (cual es trivial, pequeña, real)

 
 

-  * 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*
+Tiempo Máximo de Pausa Real
+~~~~~~~~~~~~~~~~~~~~~~~~~~~
+.. image:: img/norm-hist-pause.pdf
+    :width: 12.5cm

 
 

-* Programas reales - **Dil** (1)
+.. r2b-note::

 
 

-  * 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
+    2 min / 69.5 min

 
 

-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
+    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

 
 

-Gráficos de Corridas
---------------------------------------------------
+.. r2b-note::

 
 

-Tiempo Máximo de Stop-The-World
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-.. image:: img/norm-hist-stw.pdf
-    :width: 12.5cm
+    3.5 min / 73 min

 
 

-Tiempo Máximo de Pausa Real
-~~~~~~~~~~~~~~~~~~~~~~~~~~~
-.. image:: img/norm-hist-pause.pdf
-    :width: 12.5cm
+    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
 
 
 Tiempo Total de Ejecución
 ~~~~~~~~~~~~~~~~~~~~~~~~~
 .. image:: img/norm-hist-time.pdf
     :width: 12.5cm
 

-Cantidad Máxima de Memoria Utilizada
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-.. image:: img/norm-hist-mem.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

 
 
 
 
 
 


@@ -417,6 +285,10 @@ Resumen
 
   Casi **3 veces menor** (55s → 20s)
 
 
   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*
 Problemas, Limitaciones y Puntos Pendientes
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 * Explosión de uso de memoria con *eager allocation*


@@ -424,6 +296,10 @@ Problemas, Limitaciones y Puntos Pendientes
 * Mejorar predicción de *early collection*
 * Experimentar con ``clone(2)``
 
 * 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*
 Trabajos Relacionados
 ~~~~~~~~~~~~~~~~~~~~~
 * *Memory Management in the D Programming Language*


@@ -441,14 +317,22 @@ Trabajos Relacionados
   Gustavo Rodriguez-Rivera y Vince Russo. Software Practiceand Experience
   Volumen 27, Número 8.  Agosto 1997.
 
   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
 Trabajos Futuros
 ~~~~~~~~~~~~~~~~
 * Organización de memoria
 * Barrido

-* Precisión
+* \+ Precisión

 * Concurrencia → *Lock* **global**
 * Movimiento
 
 * Concurrencia → *Lock* **global**
 * Movimiento
 

+.. r2b-note::
+
+    1.5 min / 92 min
+

 Preguntas
 ~~~~~~~~~
 ¿?
 Preguntas
 ~~~~~~~~~
 ¿?