presentacion.rst

   1
   2 ==========================
   3 Recolección de Basura en D
   4 ==========================
   5
   6 :Autor: Leandro Lucarella
   7 :Fecha: Diciembre 2010
   8 :Organización: FIUBA
   9
  10
  11 Introducción
  12 ==============================================================================
  13
  14 Presentación
  15 --------------------------------------------------
  16
  17 Motivación
  18 ~~~~~~~~~~
  19 * Recolección de basura
  20 * Lenguaje de programación D
  21 * Utilidad → Software Libre → Contribución
  22
  23
  24 Recolección de Basura
  25 --------------------------------------------------
  26
  27 Introducción
  28 ~~~~~~~~~~~~
  29 ¿Qué?
  30
  31 * Administración automática de memoria
  32
  33 ¿Para qué?
  34
  35 * Simplificar interfaces
  36 * Mejorar eficiencia (**!**)
  37 * Evitar errores de memoria
  38
  39   * *Dangling pointers*
  40   * *Memory leaks*
  41   * *Double free*
  42
  43 ¿Cómo?
  44
  45 Algoritmos Clásicos
  46 ~~~~~~~~~~~~~~~~~~~
  47 * Conteo de referencias
  48 * **Marcado y barrido**
  49 * Copia de semi-espacio
  50
  51 .. raw:: latex
  52
  53     \multiinclude[format=pdf,graphics={height=4.5cm}]{img/mark-sweep}
  54
  55 .. dummy: para que ande bien el raw de arriba
  56
  57 Estado del Arte
  58 ~~~~~~~~~~~~~~~
  59 * Medio siglo de investigación y desarrollo (3000+ publicaciones)
  60 * Objetivo
  61
  62   * ↓ Tiempo total de ejecución
  63   * ↓ Cantidad de recolecciones
  64   * ↓ Tiempo de recolección
  65   * ↓ **Tiempo (máximo) de pausa**
  66
  67 * Técnicas
  68
  69   * Particiones
  70   * **Concurrencia**
  71   * Organización de memoria
  72   * **Precisión**
  73   * Análisis estático
  74
  75
  76 El Lenguaje de Programación D
  77 --------------------------------------------------
  78
  79 Características Generales
  80 ~~~~~~~~~~~~~~~~~~~~~~~~~
  81 * Sintaxis tipo C/C++
  82 * Compilado
  83 * Sistema de tipos estático
  84 * Multi-paradigma
  85
  86 Paradigmas
  87 ~~~~~~~~~~
  88 * Programación de bajo nivel (*system-programming*) ← C/C++
  89
  90   * ``asm``
  91   * ``union``
  92   * ``extern (C)``
  93   * ``malloc()``
  94
  95   → Conservativo + Manipulación de *root set*
  96
  97 * Programación de alto nivel ← Python/Ruby/Perl
  98
  99   * *GC*
 100   * ``T[]``, ``T[K]``
 101
 102   → Punteros interiores
 103
 104 * Orientación a objetos ← Java
 105
 106   * ``~this()``
 107
 108   → Finalización
 109
 110
 111
 112 Recolector de Basura de D
 113 ==============================================================================
 114
 115 Implementación Actual
 116 --------------------------------------------------
 117
 118 Organización del Heap
 119 ~~~~~~~~~~~~~~~~~~~~~
 120 *Heap* → *Pools* → Páginas → Bloques + Listas de libres
 121
 122 .. image:: img/heap.pdf
 123     :height: 6.7cm
 124
 125 Bloques
 126 ~~~~~~~
 127 * Tamaño fijo (por página)
 128
 129   * Potencias de 2
 130   * De 16 a 4096 bytes
 131   * Más de 4096 (una página)
 132
 133     * Objeto **grande**
 134     * Múltiplo de páginas: 4096, 8192, ...
 135     * En páginas contiguas (y mismo *pool*)
 136
 137 * Indicadores (*bit sets* en *pool*)
 138
 139   * Marcado
 140
 141     * *mark*
 142     * *scan*
 143     * *noscan*
 144
 145   * Barrido
 146
 147     * *free*
 148     * *finals*
 149
 150 Algoritmo
 151 ~~~~~~~~~
 152 * Marcado y barrido
 153
 154   * Marcado iterativo
 155
 156 * Conservativo
 157
 158   * Con una pizca de *precisión* (``NO_SCAN``)
 159
 160 * *Stop-the-world*
 161
 162   * Durante el marcado, en teoría
 163
 164 * *Lock* global
 165
 166   * Muy propenso a extender el tiempo de *stop-the-world* en la práctica
 167
 168
 169 Lo Bueno, lo Malo y lo Feo
 170 --------------------------------------------------
 171
 172 Lo Bueno
 173 ~~~~~~~~
 174 * Anda :)
 175 * Organización del *heap* (*two-level allocation*)
 176 * Marcado iterativo (!\ *overflow*)
 177 * *Bit set* para indicadores (caché)
 178
 179 (bueno != perfecto)
 180
 181 Lo Malo y lo Feo
 182 ~~~~~~~~~~~~~~~~
 183 Lo malo
 184
 185 * ↓ Configurabilidad (*no silver bullet*)
 186 * ↓ Precisión (información de tipos) → Memoria inmortal
 187 * ↓ Concurrencia → Grandes pausas
 188 * ↓ Control sobre el factor de ocupación del *heap* → casos patológicos
 189
 190 Lo feo
 191
 192 * El código (complejo, intrincado, duplicado, poco documentado) → Difícil de
 193   mantener, modificar y mejorar
 194
 195
 196
 197 Modificaciones Propuestas
 198 ==============================================================================
 199
 200 Concurrencia
 201 --------------------------------------------------
 202
 203 fork(2)
 204 ~~~~~~~
 205 * Hijo *nace* con una *fotografía* de la memoria del padre
 206 * Aisla modificaciones en la memoria de padre e hijo
 207 * Minimiza copia efectiva de memoria (*COW*)
 208 * Comienza con un solo hilo (el que llamó a ``fork(2)``)
 209 * Muy eficiente
 210
 211 Algoritmo Principal
 212 ~~~~~~~~~~~~~~~~~~~
 213 * Basado en el trabajo de Gustavo Rodriguez-Rivera y Vince Russo (*Non-intrusive
 214   Cloning Garbage Collector with Stock Operating System Support*)
 215 * Minimiza tiempo de pausa realizando fase de marcado **concurrente** vía
 216   ``fork(2)``
 217 * Proceso padre sigue corriendo el programa
 218 * Proceso hijo realiza fase de marcado
 219 * Se comunican resultados vía memoria compartida
 220 * Sincronización mínima (``fork(2)`` + ``waitpid(2)``)
 221
 222 Problemas
 223 ~~~~~~~~~
 224 * Hilo que disparó la recolección bloqueado hasta fin de recolección completa
 225   (marcado concurrente inclusive)
 226 * Otros hilos potencialmente bloqueados durante toda la recolección también
 227   (*lock* global)
 228
 229 → Tiempo de pausa en la práctica ~= tiempo total de recolección
 230
 231 Eager Allocation
 232 ~~~~~~~~~~~~~~~~
 233 * Crea un nuevo *pool* de memoria antes de lanzar el marcado concurrente
 234 * Devuelve memoria del nuevo *pool* al programa mientras termina el marcado
 235   concurrente
 236 * Permite al programa (**todos** sus hilos) seguir trabajando mientras se
 237   realiza el marcado concurrente
 238 * Compromiso
 239
 240   ↑ Consumo de memoria
 241
 242   ↓ Tiempo de pausa real
 243
 244 Early Collection
 245 ~~~~~~~~~~~~~~~~
 246 * Dispara una recolección *preventiva* antes de que se agote la memoria
 247 * Permite al programa (**todos** sus hilos) seguir trabajando mientras la
 248   recolección *preventiva* está en progreso
 249 * Si se agota la memoria antes de que la recolección *preventiva* finalice, se
 250   vuelve a bloquear
 251 * Combinable con *eager allocation* para evitar bloquear
 252 * Pueden realizarse más recolecciones de las necesarias
 253 * Compromiso
 254
 255   ↑ Consumo de procesador (potencialmente)
 256
 257   ↓ Tiempo de pausa real (no garantizado)
 258
 259
 260 Otras Mejoras
 261 --------------------------------------------------
 262
 263 Precisión
 264 ~~~~~~~~~
 265 Adaptación del trabajo de Vincent Lang y David Simcha:
 266
 267 * Compilador genera información sobre ubicación de los punteros en un tipo
 268
 269   * Indica si una *palabra* debe ser escaneada (uniones)
 270   * Indica si una palabra es un puntero
 271
 272 * Se pasa esa información al recolector al momento de pedir memoria
 273 * Recolector original utiliza esa información
 274
 275   * Almacena un puntero a la información al final del bloque
 276   * Utiliza la información para escanear solo palabras que son punteros (con
 277     seguridad o potencialmente)
 278
 279 Optimizaciones y Otras Mejoras Menores
 280 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 281 * Mejora del factor de ocupación del *heap*
 282 * Caché de consultas críticas para acelerar cuellos de botella
 283 * Reestructuración, modularización, simplificación y limpieza del código
 284 * Pre-asignación de memoria
 285 * Optimizaciones algorítmicas sobre búsquedas frecuentes
 286 * Registro de pedidos de memoria y recolecciones realizadas
 287
 288 Configurabilidad
 289 ~~~~~~~~~~~~~~~~
 290 * Configurable en *tiempo de arranque*
 291 * Vía variable de entorno (``D_GC_OPTS``)
 292 * Viejas opciones convertidas
 293
 294   * ``mem_stop``
 295   * ``sentinel``
 296
 297 * Nuevas opciones
 298
 299   * ``pre_alloc``
 300   * ``min_free``
 301   * ``malloc_stats_file``
 302   * ``collect_stats_file``
 303   * ``conservative``
 304   * ``fork``
 305   * ``eager_alloc``
 306   * ``early_collect``
 307
 308
 309
 310 Resultados
 311 ==============================================================================
 312
 313 Banco de Pruebas
 314 --------------------------------------------------
 315
 316 Generalidades
 317 ~~~~~~~~~~~~~
 318 * Múltiples corridas (20-50)
 319
 320   * Minimizar error en la medición
 321   * Resultados expresados en función de:
 322
 323     * Mínimo
 324     * Media
 325     * Máximo
 326     * Desvío estándar
 327
 328 * Minimizar variación entre corridas
 329
 330   * ``cpufreq-set(1)``
 331   * ``nice(1)``
 332   * ``ionice(1)``
 333
 334 Programas
 335 ~~~~~~~~~
 336 * Triviales (7)
 337
 338   * Ejercitar aspectos puntuales
 339   * No realizan una tarea útil
 340   * Casos patológicos
 341
 342 * Programas pequeños - *Olden Benchmark* (5)
 343
 344   * Relativamente pequeños (400-1000 *SLOC*)
 345   * Realizan una tarea útil
 346   * Manipulan mucho listas y árboles asignando mucha memoria
 347   * No son ideales para probar un *GC*
 348
 349 * Programas reales - **Dil** (1)
 350
 351   * Compilador de D escrito en D
 352   * Grande y complejo (32K+ *SLOC*, 86 módulos, 300+ *clases*)
 353   * Programado sin (limitaciones ni ventajas del) *GC* en mente
 354   * Manipulación de *strings*, arreglos dinámicos y asociativos
 355
 356 Métricas
 357 ~~~~~~~~
 358 * Tiempo total de ejecución
 359 * Tiempo máximo de *stop-the-world*
 360 * Tiempo máximo de pausa real
 361 * Cantidad máxima de memoria utilizada
 362 * Cantidad total de recolecciones realizadas
 363
 364
 365 Gráficos de Corridas
 366 --------------------------------------------------
 367
 368 Tiempo Máximo de Stop-The-World
 369 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 370 .. image:: img/norm-hist-stw.pdf
 371     :width: 12.5cm
 372
 373 Tiempo Máximo de Pausa Real
 374 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
 375 .. image:: img/norm-hist-pause.pdf
 376     :width: 12.5cm
 377
 378
 379 Tiempo Total de Ejecución
 380 ~~~~~~~~~~~~~~~~~~~~~~~~~
 381 .. image:: img/norm-hist-time.pdf
 382     :width: 12.5cm
 383
 384 Cantidad total de recolecciones realizadas
 385 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 386 .. image:: img/norm-hist-ncol.pdf
 387     :width: 12.5cm
 388
 389 Cantidad máxima de memoria utilizada
 390 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 391 .. image:: img/norm-hist-mem.pdf
 392     :width: 12.5cm
 393
 394
 395
 396 Conclusión
 397 ==============================================================================
 398
 399 Conclusión
 400 --------------------------------------------------
 401
 402 Resumen
 403 ~~~~~~~
 404 * Objetivo principal
 405
 406   Minimizar tiempo de pausa para programas reales
 407
 408   Tiempo de pausa de Dil:
 409
 410   * *Stop-the-world* **160 veces menor** (1.66s → 0.01s)
 411   * Pausa real **40 veces menor** (1.7s → 0.045s)
 412
 413 * Objetivo secundario
 414
 415   No empeorar mucho el recolector actual en ningún aspecto
 416
 417   Utilización de memoria de Dil:
 418
 419   **50% mayor** (mucho *overhead* por marcado preciso)
 420
 421 * Yapa
 422
 423   Tiempo total de ejecución de Dil:
 424
 425   Casi **3 veces menor** (55s → 20s)
 426
 427 Problemas, Limitaciones y Puntos Pendientes
 428 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 429 * Explosión de uso de memoria con *eager allocation*
 430 * Eficiencia del marcado preciso
 431 * Mejorar predicción de *early collection*
 432 * Experimentar con ``clone(2)``
 433
 434 Trabajos Relacionados
 435 ~~~~~~~~~~~~~~~~~~~~~
 436 * *Memory Management in the D Programming Language*
 437
 438   Vladimir Panteleev. Proyecto de licenciatura, Universitatea Tehnică
 439   a Moldovei, 2009.
 440
 441 * *Integrate Precise Heap Scanning Into the GC*
 442
 443   David Simcha (GC + diseño) y Vincent Lang (compilador). No formal, *bug
 444   report*, 2009-2010.
 445
 446 * *Non-intrusive Cloning Garbage Collection with Stock Operating System Support*
 447
 448   Gustavo Rodriguez-Rivera y Vince Russo. Software Practiceand Experience
 449   Volumen 27, Número 8.  Agosto 1997.
 450
 451 Trabajos Futuros
 452 ~~~~~~~~~~~~~~~~
 453 * Organización de memoria
 454 * Barrido
 455 * Precisión
 456 * Concurrencia → *Lock* **global**
 457 * Movimiento
 458
 459 Preguntas
 460 ~~~~~~~~~
 461 ¿?
 462
 463 Fin
 464 ~~~
 465 ¡Gracias!
 466
 467
 468 .. vim: set et sw=4 sts=4 spell spelllang=es :