Completar secciones de "Recolector de basura de D" y "Mejoras propuestas"

diff --git a/presentacion.rst b/presentacion.rst
index 3e396031f877d9310038fb392b334e5db529dd98..16f04540904f384c18621f28fa1f61c3577c29e9 100644 (file)
--- a/presentacion.rst
+++ b/presentacion.rst
@@ -109,108 +109,201 @@ Paradigmas
 
 
 
+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
 
-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
 ==============================================================================
 
-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``
 
 
 
@@ -298,6 +391,11 @@ Trabajos Relacionados
   David Simcha (GC + diseño) y Vincent Lang (compilador). No formal, *bug
   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