Introducción
==============================================================================
-Presentación
+Introducción
--------------------------------------------------
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
¿Para qué?
* Simplificar interfaces
-* Mejorar eficiencia (**!**)
* Evitar errores de memoria
-
- * *Dangling pointers*
- * *Memory leaks*
- * *Double free*
+* Mejorar eficiencia (**!**)
¿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
-==============================================================================
-
-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
* *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
+.. r2b-note::
-Lo Bueno, lo Malo y lo Feo
---------------------------------------------------
+ 3 min / 33 min
Lo Bueno
~~~~~~~~
* Anda :)
-* Organización del *heap* (*two-level allocation*)
+* Organización del *heap* (< fragmentación)
* Marcado iterativo (!\ *overflow*)
-* *Bit set* para indicadores (caché)
+* *Bitset* para bits de marca (*cache friendly*)
(bueno != perfecto)
+.. r2b-note::
+
+ 5 min / 38 min
+
Lo Malo y lo Feo
~~~~~~~~~~~~~~~~
Lo malo
* ↓ 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
-* 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
==============================================================================
-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
* 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
→ 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
↓ 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
↓ 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
-
- * 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
+ 3.5 min / 56.5 min
- * 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)
+ 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)
-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
+* 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
==============================================================================
-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)``
-
-Programas
-~~~~~~~~~
-* Triviales (7)
-
- * Ejercitar aspectos puntuales
- * No realizan una tarea útil
- * Casos patológicos
+Tiempo Máximo de Stop-The-World
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+.. image:: img/norm-hist-stw.pdf
+ :width: 12.5cm
-* Programas pequeños - *Olden Benchmark* (5)
+.. r2b-note::
- * 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*
+ 5.5 min / 67.5 min
-* Programas reales - **Dil** (1)
+ Explicar brevemente división de pruebas (cual es trivial, pequeña, real)
- * 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 Máximo de Pausa Real
+~~~~~~~~~~~~~~~~~~~~~~~~~~~
+.. image:: img/norm-hist-pause.pdf
+ :width: 12.5cm
-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
-* Cantidad total de recolecciones realizadas
+.. r2b-note::
+ 2 min / 69.5 min
-Gráficos de Corridas
---------------------------------------------------
+ Explicar que donde hay grandes diferencias, es por tiempo de barrido
-Tiempo Máximo de Stop-The-World
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-.. image:: img/norm-hist-stw.pdf
+Cantidad Máxima de Memoria Utilizada
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+.. image:: img/norm-hist-mem.pdf
:width: 12.5cm
-Tiempo Máximo de Pausa Real
-~~~~~~~~~~~~~~~~~~~~~~~~~~~
-.. image:: img/norm-hist-pause.pdf
- :width: 12.5cm
+.. r2b-note::
+ 3.5 min / 73 min
+
+ 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
-Cantidad total de recolecciones realizadas
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-.. image:: img/norm-hist-ncol.pdf
- :width: 12.5cm
+.. r2b-note::
-Cantidad máxima de memoria utilizada
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-.. image:: img/norm-hist-mem.pdf
- :width: 12.5cm
+ 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
Resumen
~~~~~~~
-* Recolección de basura → Inagotable
-* D → Multi-paradigma → Desafío
-* Recolección de basura en D → Fértil
-* Mejoras propuestas → Efectivas
-* Resultados → Positivos: Esperados + Inesperados
+* Objetivo principal
+
+ Minimizar tiempo de pausa para programas reales
+
+ 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)
+
+.. r2b-note::
+
+ 4 min / 84 min
Problemas, Limitaciones y Puntos Pendientes
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* 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*
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
-* Precisión
+* \+ Precisión
* Concurrencia → *Lock* **global**
* Movimiento
+.. r2b-note::
+
+ 1.5 min / 92 min
+
Preguntas
~~~~~~~~~
¿?
projects / z.facultad / 75.00 / presentacion.git / blobdiff