Simplificar Makefile

[z.facultad/75.00/presentacion.git] / presentacion.rst

==========================
Recolección de Basura en D
==========================

:Autor: Leandro Lucarella
:Fecha: Diciembre 2010
:Organización: FIUBA


Introducción
==============================================================================

Introducción
--------------------------------------------------

Motivación
~~~~~~~~~~
* Recolección de basura
* Lenguaje de programación D
* Investigación + aplicación
* Software Libre

.. r2b-note::

    1 min de presentación

    1.5 min / 2.5 min

Recolección de Basura
~~~~~~~~~~~~~~~~~~~~~
¿Qué?

* Administración automática de memoria

¿Para qué?

* Simplificar interfaces
* Evitar errores de memoria
* Mejorar eficiencia (**!**)

¿Cómo?

* 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
~~~~~~~~~~~~~~~~~~~~~~~~~
* Marcado y barrido

  * Marcado iterativo

* Conservativo

  * Con una pizca de *precisión* (``NO_SCAN``)

* *Stop-the-world*

  * Durante el marcado (en teoría)

* *Lock* global

  * Muy propenso a extender el tiempo de *stop-the-world* en la práctica

.. r2b-note::

    3 min / 33 min

Lo Bueno
~~~~~~~~
* Anda :)
* Organización del *heap* (< fragmentación)
* Marcado iterativo (!\ *overflow*)
* *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

Lo feo

* 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
==============================================================================

Modificaciones Propuestas
--------------------------------------------------

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)``)

.. r2b-note::

    2.5 min / 44 min

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

.. r2b-note::

    2.5 min / 46.5 min

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

  ↑ Consumo de memoria

  ↓ 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
* 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)

.. r2b-note::

    3.5 min / 56.5 min

    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
~~~~~~~~~~~~~
* 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



Resultados
==============================================================================

Resultados
--------------------------------------------------

Tiempo Máximo de Stop-The-World
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.. image:: img/norm-hist-stw.pdf
    :width: 12.5cm

.. r2b-note::

    5.5 min / 67.5 min

    Explicar brevemente división de pruebas (cual es trivial, pequeña, real)

Tiempo Máximo de Pausa Real
~~~~~~~~~~~~~~~~~~~~~~~~~~~
.. image:: img/norm-hist-pause.pdf
    :width: 12.5cm

.. r2b-note::

    2 min / 69.5 min

    Explicar que donde hay grandes diferencias, es por tiempo de barrido

Cantidad Máxima de Memoria Utilizada
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.. image:: img/norm-hist-mem.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

.. r2b-note::

    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



Conclusión
==============================================================================

Conclusión
--------------------------------------------------

Resumen
~~~~~~~
* 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
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Explosión de uso de memoria con *eager allocation*
* Eficiencia del marcado preciso
* 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*

  Vladimir Panteleev. Proyecto de licenciatura, Universitatea Tehnică
  a Moldovei, 2009.

* *Integrate Precise Heap Scanning Into the GC*

  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
* Concurrencia → *Lock* **global**
* Movimiento

.. r2b-note::

    1.5 min / 92 min

Preguntas
~~~~~~~~~
¿?

Fin
~~~
¡Gracias!


.. vim: set et sw=4 sts=4 spell spelllang=es :