:Autor: Leandro Lucarella
:Fecha: Diciembre 2010
-:Organización: FIUBA
+:Organización: Facultad de Ingeniería, UBA
Introducción
==============================================================================
-Presentación
+Introducción
--------------------------------------------------
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
¿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
+* 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
-
-Estado del arte
-~~~~~~~~~~~~~~~
-* Medio siglo de investigación y desarrollo (3000+ publicaciones)
-* Objetivo
+.. r2b-note::
- * ↓ Tiempo total de ejecución
- * ↓ Cantidad de recolecciones
- * ↓ Tiempo de recolección
- * ↓ **Tiempo (máximo) de pausa**
+ 5 min / 7.5 min
-* Técnicas
+Recolector Actual de D
+~~~~~~~~~~~~~~~~~~~~~~
+* Marcado y barrido
- * Particiones
- * **Concurrencia**
- * Organización de memoria
- * **Precisión**
- * Análisis estático
+ * Marcado iterativo
+* Conservativo
-El lenguaje de programación D
---------------------------------------------------
+ * Con una pizca de *precisión* (``NO_SCAN``)
-Características generales
-~~~~~~~~~~~~~~~~~~~~~~~~~
-* Sintaxis tipo C/C++
-* Compilado
-* Sistema de tipos estático
-* Multi-paradigma
+* *Stop-the-world*
-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()``
+Recolector Actual - 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::
- * 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
+Recolector Actual - 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
+Concurrencia - 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()``
+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
- â\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
+Concurrencia - 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
-Diapositiva 2
+ 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)
+
+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*
+* Eficiencia del marcado preciso
+* Mejorar predicción de *early collection*
* Experimentar con ``clone(2)``
-* Eficiencia de marcado
+
+.. r2b-note::
+
+ 3 min / 87 min
Trabajos Relacionados
~~~~~~~~~~~~~~~~~~~~~
* *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.
+* *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
-* Precisión
+* \+ Precisión
* Concurrencia → *Lock* **global**
* Movimiento
+.. r2b-note::
+
+ 1.5 min / 92 min
+
Preguntas
~~~~~~~~~
¿?
~~~
¡Gracias!
+
.. vim: set et sw=4 sts=4 spell spelllang=es :
projects / z.facultad / 75.00 / presentacion.git / blobdiff