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 * Copia de semi-espacio
  49 * **Marcado y barrido**
  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 para cada tipo
 268   de dato
 269
 270   * Indica si una *palabra* debe ser escaneada (uniones)
 271   * Indica si una palabra es un puntero
 272
 273 * Se pasa esa información al recolector al momento de pedir memoria
 274 * Recolector original utiliza esa información
 275
 276   * Almacena un puntero a la información al final del bloque
 277   * Utiliza la información para escanear solo palabras que son punteros (con
 278     seguridad o potencialmente)
 279
 280 Optimizaciones y Otras Mejoras Menores
 281 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 282 * Mejora del factor de ocupación del *heap*
 283 * Caché de consultas críticas para acelerar cuellos de botella
 284 * Reestructuración, modularización, simplificación y limpieza del código
 285 * Pre-asignación de memoria
 286 * Optimizaciones algorítmicas sobre búsquedas frecuentes
 287 * Registro de pedidos de memoria y recolecciones realizadas
 288
 289 Configurabilidad
 290 ~~~~~~~~~~~~~~~~
 291 * Configurable en *tiempo de arranque*
 292 * Vía variable de entorno (``D_GC_OPTS``)
 293 * Viejas opciones convertidas
 294
 295   * ``mem_stop``
 296   * ``sentinel``
 297
 298 * Nuevas opciones
 299
 300   * ``pre_alloc``
 301   * ``min_free``
 302   * ``malloc_stats_file``
 303   * ``collect_stats_file``
 304   * ``conservative``
 305   * ``fork``
 306   * ``eager_alloc``
 307   * ``early_collect``
 308
 309
 310
 311 Resultados
 312 ==============================================================================
 313
 314 Banco de Pruebas
 315 --------------------------------------------------
 316
 317 Generalidades
 318 ~~~~~~~~~~~~~
 319 * Múltiples corridas (20-50)
 320
 321   * Minimizar error en la medición
 322   * Resultados expresados en función de:
 323
 324     * Mínimo
 325     * Media
 326     * Máximo
 327     * Desvío estándar
 328
 329 * Minimizar variación entre corridas
 330
 331   * ``cpufreq-set(1)``
 332   * ``nice(1)``
 333   * ``ionice(1)``
 334
 335 Programas
 336 ~~~~~~~~~
 337 * Triviales (7)
 338
 339   * Ejercitar aspectos puntuales
 340   * No realizan una tarea útil
 341   * Casos patológicos
 342
 343 * Programas pequeños - *Olden Benchmark* (5)
 344
 345   * Relativamente pequeños (400-1000 *SLOC*)
 346   * Realizan una tarea útil
 347   * Manipulan mucho listas y árboles asignando mucha memoria
 348   * No son ideales para probar un *GC*
 349
 350 * Programas reales - **Dil** (1)
 351
 352   * Compilador de D escrito en D
 353   * Grande y complejo (32K+ *SLOC*, 86 módulos, 300+ *clases*)
 354   * Programado sin (limitaciones ni ventajas del) *GC* en mente
 355   * Manipulación de *strings*, arreglos dinámicos y asociativos
 356
 357 Métricas
 358 ~~~~~~~~
 359 * Tiempo total de ejecución
 360 * Tiempo máximo de *stop-the-world*
 361 * Tiempo máximo de pausa real
 362 * Cantidad máxima de memoria utilizada
 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 Cantidad Máxima de Memoria Utilizada
 379 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 380 .. image:: img/norm-hist-mem.pdf
 381     :width: 12.5cm
 382
 383 Tiempo Total de Ejecución
 384 ~~~~~~~~~~~~~~~~~~~~~~~~~
 385 .. image:: img/norm-hist-time.pdf
 386     :width: 12.5cm
 387
 388
 389
 390 Conclusión
 391 ==============================================================================
 392
 393 Conclusión
 394 --------------------------------------------------
 395
 396 Resumen
 397 ~~~~~~~
 398 * Objetivo principal
 399
 400   Minimizar tiempo de pausa para programas reales
 401
 402   Tiempo de pausa de Dil:
 403
 404   * *Stop-the-world* **160 veces menor** (1.66s → 0.01s)
 405   * Pausa real **40 veces menor** (1.7s → 0.045s)
 406
 407 * Objetivo secundario
 408
 409   No empeorar mucho el recolector actual en ningún aspecto
 410
 411   Utilización de memoria de Dil:
 412
 413   **50% mayor** (mucho *overhead* por marcado preciso)
 414
 415 * Yapa
 416
 417   Tiempo total de ejecución de Dil:
 418
 419   Casi **3 veces menor** (55s → 20s)
 420
 421 Problemas, Limitaciones y Puntos Pendientes
 422 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 423 * Explosión de uso de memoria con *eager allocation*
 424 * Eficiencia del marcado preciso
 425 * Mejorar predicción de *early collection*
 426 * Experimentar con ``clone(2)``
 427
 428 Trabajos Relacionados
 429 ~~~~~~~~~~~~~~~~~~~~~
 430 * *Memory Management in the D Programming Language*
 431
 432   Vladimir Panteleev. Proyecto de licenciatura, Universitatea Tehnică
 433   a Moldovei, 2009.
 434
 435 * *Integrate Precise Heap Scanning Into the GC*
 436
 437   David Simcha (GC + diseño) y Vincent Lang (compilador). No formal, *bug
 438   report*, 2009-2010.
 439
 440 * *Non-intrusive Cloning Garbage Collection with Stock Operating System Support*
 441
 442   Gustavo Rodriguez-Rivera y Vince Russo. Software Practiceand Experience
 443   Volumen 27, Número 8.  Agosto 1997.
 444
 445 Trabajos Futuros
 446 ~~~~~~~~~~~~~~~~
 447 * Organización de memoria
 448 * Barrido
 449 * Precisión
 450 * Concurrencia → *Lock* **global**
 451 * Movimiento
 452
 453 Preguntas
 454 ~~~~~~~~~
 455 ¿?
 456
 457 Fin
 458 ~~~
 459 ¡Gracias!
 460
 461
 462 .. vim: set et sw=4 sts=4 spell spelllang=es :