Simplificar Makefile

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

diff --git a/presentacion.rst b/presentacion.rst
index 41a6e6113247f8e7acca3392c81022df661c3724..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
 --------------------------------------------------
 
 Motivación
 ~~~~~~~~~~
 * Recolección de basura

-* Lenguaje de programación **D**
-* Utilidad → Software Libre → Contribución
+* Lenguaje de programación D
+* 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,273 +36,269 @@ 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
+* Análisis del grafo de conectividad del *heap*
+* 50+ años de desarrollo
+* 3000+ *papers*

 
 

-    \multiinclude[format=pdf,graphics={height=4.5cm}]{img/mark-sweep}
-
-.. dummy: para que ande bien el raw de arriba
+.. r2b-note::

 
 

-Estado del arte
-~~~~~~~~~~~~~~~
-* Medio siglo de investigación y desarrollo (3000+ publicaciones)
-* Objetivo
+    5 min / 7.5 min

 
 

-  * ↓ Tiempo total de ejecución
-  * ↓ Cantidad de recolecciones
-  * ↓ Tiempo de recolección
-  * ↓ **Tiempo (máximo) de pausa**
+Recolector de Basura de D
+~~~~~~~~~~~~~~~~~~~~~~~~~
+* Marcado y barrido

 
 

-* Técnicas
+  * Marcado iterativo

 
 

-  * Particiones
-  * **Concurrencia**
-  * Organización de memoria
-  * **Precisión**
-  * Análisis estático
+* Conservativo

 
 

+  * Con una pizca de *precisión* (``NO_SCAN``)

 
 

-El lenguaje de programación D
---------------------------------------------------
+* *Stop-the-world*

 
 

-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++
+  * Durante el marcado (en teoría)

 
 

-  * ``asm``
-  * ``union``
-  * ``extern (C)``
-  * ``malloc()``
+* *Lock* global

 
 

-* Programación de alto nivel ← Python/Ruby/Perl
+  * Muy propenso a extender el tiempo de *stop-the-world* en la práctica

 
 

-  * *GC*
-  * ``T[]``, ``T[K]``
+.. r2b-note::

 
 

-* Orientación a objetos ← Java
+    3 min / 33 min

 
 

-  * ``~this()``
+Lo Bueno
+~~~~~~~~
+* Anda :)
+* Organización del *heap* (< fragmentación)
+* Marcado iterativo (!\ *overflow*)
+* *Bitset* para bits de marca (*cache friendly*)

 
 

-* Programación genérica y meta-programación ← C++
-* Programación por contratos ← Eiffel
+(bueno != perfecto)

 
 .. r2b-note::
 
 
 .. r2b-note::
 

-    * Programación de bajo nivel (*system-programming*) ← C/C++
-
-      * **asm**, ``goto``, **align**, ``struct``, **union**, **link-compitble con C**,
-        **malloc**
+    5 min / 38 min

 
 

-    * Programación de alto nivel ← Python/Ruby/Perl
+Lo Malo y lo Feo
+~~~~~~~~~~~~~~~~
+Lo malo

 
 

-      * **GC**, module/import, ``delegate``, ``lazy``, *strings*, **arreglos dinámicos
-        y asociativos**, ddoc, inferencia de tipos (ltd), ``foreach``
+* ↓ Configurabilidad (*no silver bullet*)
+* ↓ Precisión (información de tipos) → Memoria inmortal
+* ↓ Concurrencia → Grandes pausas
+* ↓ Control sobre el factor de ocupación del *heap*

 
 

-    * Orientación a objetos ← Java
+  → Casos patológicos

 
 

-      * Más Java que C++: semántica de referencia, métodos siempre virtuales, herencia
-        simple + interfaces, clases anidadas, **destructores**... + Properties
+Lo feo

 
 

-    * Programación genérica y meta-programación ← C++
+* El código (complejo, intrincado, duplicado, poco documentado)

 
 

-      * ``static if``, ``typeof``, (*variadic*) ``tamplate``, *CTFE*, (*string*)
-        ``mixin``\ s, expresiones ``is``
+  → Difícil de mantener, modificar y mejorar

 
 

-    * Programación por contratos ← Eiffel
+.. r2b-note::

 
 

-      * Excepciones, ``assert``, pre/post condiciones, ``invariant``, ``unittest``,
-        ``scope``, inicialización garantizada, *RAII*, ``synchronized``
+    3.5 min / 41.5 min

 
 
 
 
 
 

-Recolección de Basura en D
+Modificaciones Propuestas

 ==============================================================================
 
 ==============================================================================
 

-Requerimientos
+Modificaciones Propuestas

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

-Según paradigma
-~~~~~~~~~~~~~~~
-* Programación de bajo nivel
+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
+* Proceso hijo realiza fase de marcado
+* Se comunican resultados vía memoria compartida
+* Sincronización mínima (``fork(2)`` + ``waitpid(2)``)

 
 

-  * ``asm``
-  * ``union``
-  * ``extern (C)``
-  * ``malloc()``
+.. r2b-note::

 
 

-  → Conservativo + Manipulación de *root set*
+    2.5 min / 44 min

 
 

-* Programación de alto nivel ← Python/Ruby/Perl
+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)

 
 

-  * ``T[]``, ``T[K]``
+→ Tiempo de pausa en la práctica ~= tiempo total de recolección

 
 

-  → Punteros interiores
+.. r2b-note::

 
 

-* Orientación a objetos ← Java
+    2.5 min / 46.5 min

 
 

-  * ``~this()``
+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

 
 

-  â\86\92 Finalización
+  â\86\91 Consumo de memoria

 
 

+  ↓ Tiempo de pausa real

 
 

-Implementación Actual
---------------------------------------------------
+.. r2b-note::

 
 

-Organización del heap
-~~~~~~~~~~~~~~~~~~~~~
-.. image:: img/heap.pdf
-    :height: 7cm
+    6.5 min / 53 min

 
 

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

 
 

-Lo Bueno, lo Malo y lo Feo
---------------------------------------------------
+  ↓ Tiempo de pausa real (no garantizado)

 
 

-Diapositiva 1
-~~~~~~~~~~~~~
-Diapositiva 1
+.. r2b-note::
+
+    3.5 min / 56.5 min
+
+    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)

 
 

-Diapositiva 2
+Otras Mejoras

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

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

 
 

-Modificaciones Propuestas
+
+
+Resultados

 ==============================================================================
 
 ==============================================================================
 

-Precisión
+Resultados

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

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

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2
+.. r2b-note::

 
 

+    5.5 min / 67.5 min

 
 

-Concurrencia
---------------------------------------------------
+    Explicar brevemente división de pruebas (cual es trivial, pequeña, real)

 
 

-Diapositiva 1
-~~~~~~~~~~~~~
-Diapositiva 1
+Tiempo Máximo de Pausa Real
+~~~~~~~~~~~~~~~~~~~~~~~~~~~
+.. image:: img/norm-hist-pause.pdf
+    :width: 12.5cm

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2
+.. r2b-note::

 
 

+    2 min / 69.5 min

 
 

-Optimizaciones
---------------------------------------------------
+    Explicar que donde hay grandes diferencias, es por tiempo de barrido

 
 

-Diapositiva 1
-~~~~~~~~~~~~~
-Diapositiva 1
+Cantidad Máxima de Memoria Utilizada
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+.. image:: img/norm-hist-mem.pdf
+    :width: 12.5cm

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2
+.. r2b-note::

 
 

+    3.5 min / 73 min

 
 

+    Enganchar lo anterior con la relación con el consumo de memoria

 
 

-Resultados
-==============================================================================
+Tiempo Total de Ejecución
+~~~~~~~~~~~~~~~~~~~~~~~~~
+.. image:: img/norm-hist-time.pdf
+    :width: 12.5cm

 
 

-Banco de Pruebas
---------------------------------------------------
+.. r2b-note::

 
 

-Diapositiva 1
-~~~~~~~~~~~~~
-Diapositiva 1
+    7 min / 80 min

 
 

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

 
 
 
 

-Tiempo de Stop-The-World
---------------------------------------------------

 
 

-Diapositiva 1
-~~~~~~~~~~~~~
-Diapositiva 1
+Conclusión
+==============================================================================

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2
+Conclusión
+--------------------------------------------------

 
 

+Resumen
+~~~~~~~
+* Objetivo principal

 
 

-Tiempo de Pausa Real
---------------------------------------------------
+  Minimizar tiempo de pausa para programas reales

 
 

-Diapositiva 1
-~~~~~~~~~~~~~
-Diapositiva 1
+  Tiempo de pausa de Dil:

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2
+  * *Stop-the-world* **160 veces menor** (1.66s → 0.01s)
+  * Pausa real **40 veces menor** (1.7s → 0.045s)

 
 

+* Objetivo secundario

 
 

-Tiempo de Ejecución
---------------------------------------------------
+  No empeorar mucho el recolector actual en ningún aspecto

 
 

-Diapositiva 1
-~~~~~~~~~~~~~
-Diapositiva 1
+  Utilización de memoria de Dil:

 
 

-Diapositiva 2
-~~~~~~~~~~~~~
-Diapositiva 2
+  **50% mayor** (mucho *overhead* por marcado preciso)

 
 

+* Yapa

 
 

-Conclusión
-==============================================================================
+  Tiempo total de ejecución de Dil:

 
 

-Conclusión
---------------------------------------------------
+  Casi **3 veces menor** (55s → 20s)

 
 

-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
+.. r2b-note::
+
+    4 min / 84 min

 
 

-Problemas, limitaciones y Puntos Pendientes
+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
+
+.. r2b-note::
+
+    3 min / 87 min

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


@@ -310,17 +309,30 @@ 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.
+
+.. 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
 ~~~~~~~~~
 ¿?


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

+

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