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 Banco de Pruebas
 210 ~~~~~~~~~~~~~~~~
 211 * Programas
 212
 213   * 7 *Micro-benchmarks*
 214   * 5 *Olden Benchmark* (400-1000 *SLOC*)
 215   * Dil (32K+ *SLOC*, 86 módulos, 300+ *clases*)
 216
 217 * Métricas
 218
 219   * Tiempo total de ejecución
 220   * Tiempo máximo de *stop-the-world*
 221   * Tiempo máximo de pausa real
 222   * Cantidad máxima de memoria utilizada
 223
 224 Tiempo Máximo de Stop-The-World
 225 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 226 .. image:: img/norm-hist-stw.pdf
 227     :width: 12.5cm
 228
 229 .. r2b-note::
 230
 231     5.5 min / 67.5 min
 232
 233     Explicar brevemente división de pruebas (cual es trivial, pequeña, real)
 234
 235 Tiempo Máximo de Pausa Real
 236 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
 237 .. image:: img/norm-hist-pause.pdf
 238     :width: 12.5cm
 239
 240 .. r2b-note::
 241
 242     2 min / 69.5 min
 243
 244     Explicar que donde hay grandes diferencias, es por tiempo de barrido
 245
 246 Cantidad Máxima de Memoria Utilizada
 247 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 248 .. image:: img/norm-hist-mem.pdf
 249     :width: 12.5cm
 250
 251 .. r2b-note::
 252
 253     3.5 min / 73 min
 254
 255     Enganchar lo anterior con la relación con el consumo de memoria
 256
 257 Tiempo Total de Ejecución
 258 ~~~~~~~~~~~~~~~~~~~~~~~~~
 259 .. image:: img/norm-hist-time.pdf
 260     :width: 12.5cm
 261
 262 .. r2b-note::
 263
 264     7 min / 80 min
 265
 266     * mcore y split bajan mucho por caché de tamaño
 267     * rnddata baja mucho por marcado preciso
 268     * bigarr y sbtree suben porque no hacen más que alocar
 269
 270
 271
 272 Conclusión
 273 ==============================================================================
 274
 275 Conclusión
 276 --------------------------------------------------
 277
 278 Resumen
 279 ~~~~~~~
 280 * Objetivo principal
 281
 282   Minimizar tiempo de pausa para programas reales
 283
 284   Tiempo de pausa de Dil:
 285
 286   * *Stop-the-world* **160 veces menor** (1.66s → 0.01s)
 287   * Pausa real **40 veces menor** (1.7s → 0.045s)
 288
 289 * Objetivo secundario
 290
 291   No empeorar mucho el recolector actual en ningún aspecto
 292
 293   Utilización de memoria de Dil:
 294
 295   **50% mayor** (213MiB → 307MiB)
 296
 297   (mucho *overhead* por marcado preciso)
 298
 299 * Yapa
 300
 301   Tiempo total de ejecución de Dil:
 302
 303   Casi **3 veces menor** (55s → 20s)
 304
 305 .. r2b-note::
 306
 307     4 min / 84 min
 308
 309 Problemas, Limitaciones y Puntos Pendientes
 310 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 311 * Explosión de uso de memoria con *eager allocation*
 312 * Eficiencia del marcado preciso
 313 * Mejorar predicción de *early collection*
 314 * Experimentar con ``clone(2)``
 315
 316 .. r2b-note::
 317
 318     3 min / 87 min
 319
 320 Trabajos Relacionados
 321 ~~~~~~~~~~~~~~~~~~~~~
 322 * *Memory Management in the D Programming Language*
 323
 324   Vladimir Panteleev. Proyecto de licenciatura, Universitatea Tehnică
 325   a Moldovei, 2009.
 326
 327 * *Integrate Precise Heap Scanning Into the GC*
 328
 329   David Simcha (GC + diseño) y Vincent Lang (compilador). No formal, *bug
 330   report*, 2009-2010.
 331
 332 * *Non-intrusive Cloning Garbage Collection with Stock Operating System Support*
 333
 334   Gustavo Rodriguez-Rivera y Vince Russo. Software Practiceand Experience
 335   Volumen 27, Número 8.  Agosto 1997.
 336
 337 .. r2b-note::
 338
 339     1.5 min / 88.5 min
 340
 341 Trabajos Futuros
 342 ~~~~~~~~~~~~~~~~
 343 * Organización de memoria
 344 * Barrido
 345 * \+ Precisión
 346 * Concurrencia → *Lock* **global**
 347 * Movimiento
 348
 349 .. r2b-note::
 350
 351     1.5 min / 92 min
 352
 353 Preguntas
 354 ~~~~~~~~~
 355 ¿?
 356
 357 Fin
 358 ~~~
 359 ¡Gracias!
 360
 361
 362 .. vim: set et sw=4 sts=4 spell spelllang=es :