Motivación
~~~~~~~~~~
* Recolección de basura
-* Lenguaje de programación **D**
+* Lenguaje de programación D
* Utilidad → Software Libre → Contribución
¿Cómo?
-Algoritmos clásicos
+Algoritmos Clásicos
~~~~~~~~~~~~~~~~~~~
* Conteo de referencias
-* **Marcado y barrido**
* Copia de semi-espacio
+* **Marcado y barrido**
.. raw:: latex
.. 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
* 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
-Recolector de basura de D
+Recolector de Basura de D
==============================================================================
-Implementación actual
+Implementación Actual
--------------------------------------------------
-Organización del heap
+Organización del Heap
~~~~~~~~~~~~~~~~~~~~~
*Heap* → *Pools* → Páginas → Bloques + Listas de libres
* Muy propenso a extender el tiempo de *stop-the-world* en la práctica
-Lo bueno, lo malo y lo feo
+Lo Bueno, lo Malo y lo Feo
--------------------------------------------------
-Lo bueno
+Lo Bueno
~~~~~~~~
* Anda :)
* Organización del *heap* (*two-level allocation*)
(bueno != perfecto)
-Lo malo y lo feo
+Lo Malo y lo Feo
~~~~~~~~~~~~~~~~
Lo malo
* Comienza con un solo hilo (el que llamó a ``fork(2)``)
* Muy eficiente
-Algoritmo principal
+Algoritmo Principal
~~~~~~~~~~~~~~~~~~~
* Basado en el trabajo de Gustavo Rodriguez-Rivera y Vince Russo (*Non-intrusive
Cloning Garbage Collector with Stock Operating System Support*)
→ Tiempo de pausa en la práctica ~= tiempo total de recolección
-Eager allocation
+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
↓ Tiempo de pausa real
-Early collection
+Early Collection
~~~~~~~~~~~~~~~~
* Dispara una recolección *preventiva* antes de que se agote la memoria
* Permite al programa (**todos** sus hilos) seguir trabajando mientras la
↓ Tiempo de pausa real (no garantizado)
-Otras mejoras
+Otras Mejoras
--------------------------------------------------
Precisión
* Utiliza la información para escanear solo palabras que son punteros (con
seguridad o potencialmente)
-Optimizaciones y otras mejoras menores
+Optimizaciones y Otras Mejoras Menores
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Mejora del factor de ocupación del *heap*
* Caché de consultas críticas para acelerar cuellos de botella
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
+
+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
-Tiempo de Ejecución
+
+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
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
-Problemas, limitaciones y Puntos Pendientes
+ 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*
+* Eficiencia del marcado preciso
+* Mejorar predicción de *early collection*
* Experimentar con ``clone(2)``
-* Eficiencia de marcado
Trabajos Relacionados
~~~~~~~~~~~~~~~~~~~~~
~~~
¡Gracias!
+
.. vim: set et sw=4 sts=4 spell spelllang=es :
projects / z.facultad / 75.00 / presentacion.git / blobdiff