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
 ==============================================================================
 
 
 
 
 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.
 
   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
 Trabajos Futuros
 ~~~~~~~~~~~~~~~~
 * Organización de memoria