Poner marcado y barrido al final para enganchar con animación

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

diff --git a/presentacion.rst b/presentacion.rst
index 41a6e6113247f8e7acca3392c81022df661c3724..192a7da159b61f72c8601ecdfe35b2cce3cd30fb 100644 (file)
--- a/presentacion.rst
+++ b/presentacion.rst
@@ -17,7 +17,7 @@ Presentación
 Motivación
 ~~~~~~~~~~
 * Recolección de basura
 Motivación
 ~~~~~~~~~~
 * Recolección de basura

-* Lenguaje de programación **D**
+* Lenguaje de programación D

 * Utilidad → Software Libre → Contribución
 
 
 * Utilidad → Software Libre → Contribución
 
 


@@ -42,11 +42,11 @@ Introducción
 
 ¿Cómo?
 
 
 ¿Cómo?
 

-Algoritmos clásicos
+Algoritmos Clásicos

 ~~~~~~~~~~~~~~~~~~~
 * Conteo de referencias
 ~~~~~~~~~~~~~~~~~~~
 * Conteo de referencias

-* **Marcado y barrido**

 * Copia de semi-espacio
 * Copia de semi-espacio

+* **Marcado y barrido**

 
 .. raw:: latex
 
 
 .. raw:: latex
 


@@ -54,7 +54,7 @@ Algoritmos clásicos
 
 .. dummy: para que ande bien el raw de arriba
 
 
 .. dummy: para que ande bien el raw de arriba
 

-Estado del arte
+Estado del Arte

 ~~~~~~~~~~~~~~~
 * Medio siglo de investigación y desarrollo (3000+ publicaciones)
 * Objetivo
 ~~~~~~~~~~~~~~~
 * Medio siglo de investigación y desarrollo (3000+ publicaciones)
 * Objetivo


@@ -73,10 +73,10 @@ Estado del arte
   * Análisis estático
 
 
   * Análisis estático
 
 

-El lenguaje de programación D
+El Lenguaje de Programación D

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

-Características generales
+Características Generales

 ~~~~~~~~~~~~~~~~~~~~~~~~~
 * Sintaxis tipo C/C++
 * Compilado
 ~~~~~~~~~~~~~~~~~~~~~~~~~
 * Sintaxis tipo C/C++
 * Compilado


@@ -92,140 +92,218 @@ Paradigmas
   * ``extern (C)``
   * ``malloc()``
 
   * ``extern (C)``
   * ``malloc()``
 

+  → Conservativo + Manipulación de *root set*
+

 * Programación de alto nivel ← Python/Ruby/Perl
 
   * *GC*
   * ``T[]``, ``T[K]``
 
 * Programación de alto nivel ← Python/Ruby/Perl
 
   * *GC*
   * ``T[]``, ``T[K]``
 

+  → Punteros interiores
+

 * Orientación a objetos ← Java
 
   * ``~this()``
 
 * Orientación a objetos ← Java
 
   * ``~this()``
 

-* Programación genérica y meta-programación ← C++
-* Programación por contratos ← Eiffel
-
-.. r2b-note::
-
-    * Programación de bajo nivel (*system-programming*) ← C/C++
+  → Finalización

 
 

-      * **asm**, ``goto``, **align**, ``struct``, **union**, **link-compitble con C**,
-        **malloc**

 
 

-    * Programación de alto nivel ← Python/Ruby/Perl

 
 

-      * **GC**, module/import, ``delegate``, ``lazy``, *strings*, **arreglos dinámicos
-        y asociativos**, ddoc, inferencia de tipos (ltd), ``foreach``
+Recolector de Basura de D
+==============================================================================

 
 

-    * Orientación a objetos ← Java
+Implementación Actual
+--------------------------------------------------

 
 

-      * Más Java que C++: semántica de referencia, métodos siempre virtuales, herencia
-        simple + interfaces, clases anidadas, **destructores**... + Properties
+Organización del Heap
+~~~~~~~~~~~~~~~~~~~~~
+*Heap* → *Pools* → Páginas → Bloques + Listas de libres

 
 

-    * Programación genérica y meta-programación ← C++
+.. image:: img/heap.pdf
+    :height: 6.7cm

 
 

-      * ``static if``, ``typeof``, (*variadic*) ``tamplate``, *CTFE*, (*string*)
-        ``mixin``\ s, expresiones ``is``
+Bloques
+~~~~~~~
+* Tamaño fijo (por página)

 
 

-    * Programación por contratos ← Eiffel
+  * Potencias de 2
+  * De 16 a 4096 bytes
+  * Más de 4096 (una página)

 
 

-      * Excepciones, ``assert``, pre/post condiciones, ``invariant``, ``unittest``,
-        ``scope``, inicialización garantizada, *RAII*, ``synchronized``
+    * Objeto **grande**
+    * Múltiplo de páginas: 4096, 8192, ...
+    * En páginas contiguas (y mismo *pool*)

 
 

+* Indicadores (*bit sets* en *pool*)

 
 

+  * Marcado

 
 

-Recolección de Basura en D
-==============================================================================
+    * *mark*
+    * *scan*
+    * *noscan*

 
 

-Requerimientos
---------------------------------------------------
+  * Barrido

 
 

-Según paradigma
-~~~~~~~~~~~~~~~
-* Programación de bajo nivel
+    * *free*
+    * *finals*

 
 

-  * ``asm``
-  * ``union``
-  * ``extern (C)``
-  * ``malloc()``
+Algoritmo
+~~~~~~~~~
+* Marcado y barrido

 
 

-  → Conservativo + Manipulación de *root set*
+  * Marcado iterativo

 
 

-* Programación de alto nivel ← Python/Ruby/Perl
+* Conservativo

 
 

-  * ``T[]``, ``T[K]``
+  * Con una pizca de *precisión* (``NO_SCAN``)

 
 

-  → Punteros interiores
+* *Stop-the-world*

 
 

-* Orientación a objetos ← Java
+  * Durante el marcado, en teoría

 
 

-  * ``~this()``
+* *Lock* global

 
 

-  → Finalización
+  * Muy propenso a extender el tiempo de *stop-the-world* en la práctica

 
 
 
 

-Implementación Actual
+Lo Bueno, lo Malo y lo Feo

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

-Organización del heap
-~~~~~~~~~~~~~~~~~~~~~
-.. image:: img/heap.pdf
-    :height: 7cm
+Lo Bueno
+~~~~~~~~
+* Anda :)
+* Organización del *heap* (*two-level allocation*)
+* Marcado iterativo (!\ *overflow*)
+* *Bit set* para indicadores (caché)

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2
+(bueno != perfecto)

 
 

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

 
 

-Lo Bueno, lo Malo y lo Feo
---------------------------------------------------
+* ↓ 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

 
 

-Diapositiva 1
-~~~~~~~~~~~~~
-Diapositiva 1
+Lo feo

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2
+* El código (complejo, intrincado, duplicado, poco documentado) → Difícil de
+  mantener, modificar y mejorar

 
 
 
 Modificaciones Propuestas
 ==============================================================================
 
 
 
 
 Modificaciones Propuestas
 ==============================================================================
 

-Precisión
+Concurrencia

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

-Diapositiva 1
-~~~~~~~~~~~~~
-Diapositiva 1
+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

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2
+Algoritmo Principal
+~~~~~~~~~~~~~~~~~~~
+* 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)``)
+
+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)

 
 

+→ Tiempo de pausa en la práctica ~= tiempo total de recolección

 
 

-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

 
 

-Diapositiva 1
-~~~~~~~~~~~~~
-Diapositiva 1
+  ↑ Consumo de memoria

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2
+  ↓ Tiempo de pausa real
+
+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)
+
+  ↓ Tiempo de pausa real (no garantizado)

 
 
 
 

-Optimizaciones
+Otras Mejoras

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

-Diapositiva 1
-~~~~~~~~~~~~~
-Diapositiva 1
+Precisión
+~~~~~~~~~
+Adaptación del trabajo de Vincent Lang y David Simcha:

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2
+* Compilador genera información sobre ubicación de los punteros en un tipo
+
+  * Indica si una *palabra* debe ser escaneada (uniones)
+  * 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)
+
+Optimizaciones y Otras Mejoras Menores
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+* 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
+~~~~~~~~~~~~~~~~
+* Configurable en *tiempo de arranque*
+* Vía variable de entorno (``D_GC_OPTS``)
+* Viejas opciones convertidas
+
+  * ``mem_stop``
+  * ``sentinel``
+
+* Nuevas opciones
+
+  * ``pre_alloc``
+  * ``min_free``
+  * ``malloc_stats_file``
+  * ``collect_stats_file``
+  * ``conservative``
+  * ``fork``
+  * ``eager_alloc``
+  * ``early_collect``

 
 
 
 
 
 


@@ -235,49 +313,77 @@ Resultados
 Banco de Pruebas
 --------------------------------------------------
 
 Banco de Pruebas
 --------------------------------------------------
 

-Diapositiva 1
+Generalidades

 ~~~~~~~~~~~~~
 ~~~~~~~~~~~~~

-Diapositiva 1
+* Múltiples corridas (20-50)

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2
+  * Minimizar error en la medición
+  * Resultados expresados en función de:

 
 

+    * Mínimo
+    * Media
+    * Máximo
+    * Desvío estándar

 
 

-Tiempo de Stop-The-World
---------------------------------------------------
+* Minimizar variación entre corridas

 
 

-Diapositiva 1
-~~~~~~~~~~~~~
-Diapositiva 1
+  * ``cpufreq-set(1)``
+  * ``nice(1)``
+  * ``ionice(1)``

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2
+Programas
+~~~~~~~~~
+* Triviales (7)

 
 

+  * Ejercitar aspectos puntuales
+  * No realizan una tarea útil
+  * Casos patológicos

 
 

-Tiempo de Pausa Real
---------------------------------------------------
+* Programas pequeños - *Olden Benchmark* (5)

 
 

-Diapositiva 1
-~~~~~~~~~~~~~
-Diapositiva 1
+  * 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*

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2
+* 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

 
 

-Tiempo de Ejecución
+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

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

-Diapositiva 1
-~~~~~~~~~~~~~
-Diapositiva 1
+Tiempo Máximo de Stop-The-World
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+.. image:: img/norm-hist-stw.pdf
+    :width: 12.5cm
+
+Tiempo Máximo de Pausa Real
+~~~~~~~~~~~~~~~~~~~~~~~~~~~
+.. image:: img/norm-hist-pause.pdf
+    :width: 12.5cm
+
+Cantidad Máxima de Memoria Utilizada
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+.. image:: img/norm-hist-mem.pdf
+    :width: 12.5cm
+
+Tiempo Total de Ejecución
+~~~~~~~~~~~~~~~~~~~~~~~~~
+.. image:: img/norm-hist-time.pdf
+    :width: 12.5cm

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2

 
 
 Conclusión
 
 
 Conclusión


@@ -288,18 +394,35 @@ Conclusión
 
 Resumen
 ~~~~~~~
 
 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
+* Objetivo principal
+
+  Minimizar tiempo de pausa para programas reales

 
 

-Problemas, limitaciones y Puntos Pendientes
+  Tiempo de pausa de Dil:
+
+  * *Stop-the-world* **160 veces menor** (1.66s → 0.01s)
+  * Pausa real **40 veces menor** (1.7s → 0.045s)
+
+* Objetivo secundario
+
+  No empeorar mucho el recolector actual en ningún aspecto
+
+  Utilización de memoria de Dil:
+
+  **50% mayor** (mucho *overhead* por marcado preciso)
+
+* Yapa
+
+  Tiempo total de ejecución de Dil:
+
+  Casi **3 veces menor** (55s → 20s)
+
+Problemas, Limitaciones y Puntos Pendientes

 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

-* Predicción de *early collection*

 * Explosión de uso de memoria con *eager allocation*
 * Explosión de uso de memoria con *eager allocation*

+* Eficiencia del marcado preciso
+* Mejorar predicción de *early collection*

 * Experimentar con ``clone(2)``
 * Experimentar con ``clone(2)``

-* Eficiencia de marcado

 
 Trabajos Relacionados
 ~~~~~~~~~~~~~~~~~~~~~
 
 Trabajos Relacionados
 ~~~~~~~~~~~~~~~~~~~~~


@@ -310,9 +433,14 @@ Trabajos Relacionados
 
 * *Integrate Precise Heap Scanning Into the GC*
 
 
 * *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.
 
   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.
+

 Trabajos Futuros
 ~~~~~~~~~~~~~~~~
 * Organización de memoria
 Trabajos Futuros
 ~~~~~~~~~~~~~~~~
 * Organización de memoria


@@ -329,4 +457,5 @@ Fin
 ~~~
 ¡Gracias!
 
 ~~~
 ¡Gracias!
 

+

 .. vim: set et sw=4 sts=4 spell spelllang=es :
 .. vim: set et sw=4 sts=4 spell spelllang=es :