presentacion.rst

   1
   2 ==========================
   3 Recolección de Basura en D
   4 ==========================
   5
   6 :Autor: Leandro Lucarella
   7 :Fecha: Diciembre 2010
   8 :Organización: Facultad de Ingeniería, UBA
   9
  10
  11 Introducción
  12 ==============================================================================
  13
  14 Introducción
  15 --------------------------------------------------
  16
  17 Motivación
  18 ~~~~~~~~~~
  19 * Recolección de basura
  20 * Lenguaje de programación D
  21 * Investigación + aplicación
  22 * Software Libre
  23
  24 .. r2b-note::
  25
  26     1 min de presentación
  27
  28     1.5 min / 2.5 min
  29
  30 Recolección de Basura
  31 ~~~~~~~~~~~~~~~~~~~~~
  32 ¿Qué?
  33
  34 * Administración automática de memoria
  35
  36 ¿Para qué?
  37
  38 * Simplificar interfaces
  39 * Evitar errores de memoria
  40 * Mejorar eficiencia (**!**)
  41
  42 ¿Cómo?
  43
  44 * Análisis del grafo de conectividad del *heap*
  45 * 50+ años de desarrollo
  46 * 3000+ *papers*
  47
  48 .. r2b-note::
  49
  50     5 min / 7.5 min
  51
  52 Recolector Actual de D
  53 ~~~~~~~~~~~~~~~~~~~~~~
  54 * Marcado y barrido
  55
  56   * Marcado iterativo
  57
  58 * Conservativo
  59
  60   * Con una pizca de *precisión* (``NO_SCAN``)
  61
  62 * *Stop-the-world*
  63
  64   * Durante el marcado (en teoría)
  65
  66 * *Lock* global
  67
  68   * Muy propenso a extender el tiempo de *stop-the-world* en la práctica
  69
  70 .. r2b-note::
  71
  72     3 min / 33 min
  73
  74 Recolector Actual - Lo Bueno
  75 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  76 * Anda :)
  77 * Organización del *heap* (< fragmentación)
  78 * Marcado iterativo (!\ *overflow*)
  79 * *Bitset* para bits de marca (*cache friendly*)
  80
  81 (bueno != perfecto)
  82
  83 .. r2b-note::
  84
  85     5 min / 38 min
  86
  87 Recolector Actual - Lo Malo y lo Feo
  88 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  89 Lo malo
  90
  91 * ↓ Configurabilidad (*no silver bullet*)
  92 * ↓ Precisión (información de tipos) → Memoria inmortal
  93 * ↓ Concurrencia → Grandes pausas
  94 * ↓ Control sobre el factor de ocupación del *heap*
  95
  96   → Casos patológicos
  97
  98 Lo feo
  99
 100 * El código (complejo, intrincado, duplicado, poco documentado)
 101
 102   → Difícil de mantener, modificar y mejorar
 103
 104 .. r2b-note::
 105
 106     3.5 min / 41.5 min
 107
 108
 109
 110 Modificaciones Propuestas
 111 ==============================================================================
 112
 113 Modificaciones Propuestas
 114 --------------------------------------------------
 115
 116 Concurrencia
 117 ~~~~~~~~~~~~
 118 * Algoritmo basado en el trabajo de Gustavo Rodriguez-Rivera y Vince Russo
 119   (*Non-intrusive Cloning Garbage Collector with Stock Operating System
 120   Support*)
 121 * Minimiza tiempo de pausa realizando fase de **marcado concurrente** vía
 122   ``fork(2)``
 123 * Proceso padre sigue corriendo el programa
 124 * Proceso hijo realiza fase de marcado
 125 * Se comunican resultados vía memoria compartida
 126 * Sincronización mínima (``fork(2)`` + ``waitpid(2)``)
 127
 128 .. r2b-note::
 129
 130     2.5 min / 44 min
 131
 132 Concurrencia - Problemas
 133 ~~~~~~~~~~~~~~~~~~~~~~~~
 134 * Hilo que disparó la recolección bloqueado hasta fin de recolección completa
 135   (marcado concurrente inclusive)
 136 * Otros hilos potencialmente bloqueados durante toda la recolección también
 137   (*lock* global)
 138
 139 → Tiempo de pausa en la práctica ~= tiempo total de recolección
 140
 141 .. r2b-note::
 142
 143     2.5 min / 46.5 min
 144
 145 Concurrencia - Eager Allocation
 146 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 147 * Pide más memoria al OS antes de lanzar el marcado concurrente
 148 * Devuelve memoria nueva al programa mientras termina el marcado
 149   concurrente
 150 * Permite al programa (**todos** sus hilos) seguir trabajando mientras se
 151   realiza el marcado concurrente
 152 * Compromiso
 153
 154   ↑ Consumo de memoria
 155
 156   ↓ Tiempo de pausa real
 157
 158 .. r2b-note::
 159
 160     6.5 min / 53 min
 161
 162 Concurrencia - Early Collection
 163 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 164 * Dispara una recolección *preventiva* antes de que se agote la memoria
 165 * Permite al programa (**todos** sus hilos) seguir trabajando mientras la
 166   recolección *preventiva* está en progreso
 167 * Si se agota la memoria antes de que la recolección *preventiva* finalice, se
 168   vuelve a bloquear
 169 * Combinable con *eager allocation* para evitar bloquear
 170 * Pueden realizarse más recolecciones de las necesarias
 171 * Compromiso
 172
 173   ↑ Consumo de procesador (potencialmente)
 174
 175   ↓ Tiempo de pausa real (no garantizado)
 176
 177 .. r2b-note::
 178
 179     3.5 min / 56.5 min
 180
 181     Si hago una recolección cuando queda 20% de memoria libre y nadie pide más
 182     memoria mientras se recolecta, es como si tuviera 20% menos de memoria
 183     disponible para el programa => más recolecciones => más consumo de CPU (y
 184     potencialmente run-time)
 185
 186 Otras Mejoras
 187 ~~~~~~~~~~~~~
 188 * Marcado semi-preciso del *heap*
 189 * Mejora del factor de ocupación del *heap*
 190 * Caché de consultas críticas para acelerar cuellos de botella
 191 * Reestructuración, modularización, simplificación y limpieza del código
 192 * Pre-asignación de memoria
 193 * Optimizaciones algorítmicas sobre búsquedas frecuentes
 194 * Registro de pedidos de memoria y recolecciones realizadas
 195 * Configurabilidad (en *tiempo de inicialización*)
 196
 197 .. r2b-note::
 198
 199     2 min / 58.5 min
 200
 201
 202
 203 Resultados
 204 ==============================================================================
 205
 206 Resultados
 207 --------------------------------------------------
 208
 209 Tiempo Máximo de Stop-The-World
 210 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 211 .. image:: img/norm-hist-stw.pdf
 212     :width: 12.5cm
 213
 214 .. r2b-note::
 215
 216     5.5 min / 67.5 min
 217
 218     Explicar brevemente división de pruebas (cual es trivial, pequeña, real)
 219
 220 Tiempo Máximo de Pausa Real
 221 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
 222 .. image:: img/norm-hist-pause.pdf
 223     :width: 12.5cm
 224
 225 .. r2b-note::
 226
 227     2 min / 69.5 min
 228
 229     Explicar que donde hay grandes diferencias, es por tiempo de barrido
 230
 231 Cantidad Máxima de Memoria Utilizada
 232 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 233 .. image:: img/norm-hist-mem.pdf
 234     :width: 12.5cm
 235
 236 .. r2b-note::
 237
 238     3.5 min / 73 min
 239
 240     Enganchar lo anterior con la relación con el consumo de memoria
 241
 242 Tiempo Total de Ejecución
 243 ~~~~~~~~~~~~~~~~~~~~~~~~~
 244 .. image:: img/norm-hist-time.pdf
 245     :width: 12.5cm
 246
 247 .. r2b-note::
 248
 249     7 min / 80 min
 250
 251     * mcore y split bajan mucho por caché de tamaño
 252     * rnddata baja mucho por marcado preciso
 253     * bigarr y sbtree suben porque no hacen más que alocar
 254
 255
 256
 257 Conclusión
 258 ==============================================================================
 259
 260 Conclusión
 261 --------------------------------------------------
 262
 263 Resumen
 264 ~~~~~~~
 265 * Objetivo principal
 266
 267   Minimizar tiempo de pausa para programas reales
 268
 269   Tiempo de pausa de Dil:
 270
 271   * *Stop-the-world* **160 veces menor** (1.66s → 0.01s)
 272   * Pausa real **40 veces menor** (1.7s → 0.045s)
 273
 274 * Objetivo secundario
 275
 276   No empeorar mucho el recolector actual en ningún aspecto
 277
 278   Utilización de memoria de Dil:
 279
 280   **50% mayor** (mucho *overhead* por marcado preciso)
 281
 282 * Yapa
 283
 284   Tiempo total de ejecución de Dil:
 285
 286   Casi **3 veces menor** (55s → 20s)
 287
 288 .. r2b-note::
 289
 290     4 min / 84 min
 291
 292 Problemas, Limitaciones y Puntos Pendientes
 293 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 294 * Explosión de uso de memoria con *eager allocation*
 295 * Eficiencia del marcado preciso
 296 * Mejorar predicción de *early collection*
 297 * Experimentar con ``clone(2)``
 298
 299 .. r2b-note::
 300
 301     3 min / 87 min
 302
 303 Trabajos Relacionados
 304 ~~~~~~~~~~~~~~~~~~~~~
 305 * *Memory Management in the D Programming Language*
 306
 307   Vladimir Panteleev. Proyecto de licenciatura, Universitatea Tehnică
 308   a Moldovei, 2009.
 309
 310 * *Integrate Precise Heap Scanning Into the GC*
 311
 312   David Simcha (GC + diseño) y Vincent Lang (compilador). No formal, *bug
 313   report*, 2009-2010.
 314
 315 * *Non-intrusive Cloning Garbage Collection with Stock Operating System Support*
 316
 317   Gustavo Rodriguez-Rivera y Vince Russo. Software Practiceand Experience
 318   Volumen 27, Número 8.  Agosto 1997.
 319
 320 .. r2b-note::
 321
 322     1.5 min / 88.5 min
 323
 324 Trabajos Futuros
 325 ~~~~~~~~~~~~~~~~
 326 * Organización de memoria
 327 * Barrido
 328 * \+ Precisión
 329 * Concurrencia → *Lock* **global**
 330 * Movimiento
 331
 332 .. r2b-note::
 333
 334     1.5 min / 92 min
 335
 336 Preguntas
 337 ~~~~~~~~~
 338 ¿?
 339
 340 Fin
 341 ~~~
 342 ¡Gracias!
 343
 344
 345 .. vim: set et sw=4 sts=4 spell spelllang=es :