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 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
 363
 364 Gráficos de Corridas
 365 --------------------------------------------------
 366
 367 Tiempo Máximo de Stop-The-World
 368 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 369 .. image:: img/norm-hist-stw.pdf
 370     :width: 12.5cm
 371
 372 Tiempo Máximo de Pausa Real
 373 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
 374 .. image:: img/norm-hist-pause.pdf
 375     :width: 12.5cm
 376
 377 Cantidad Máxima de Memoria Utilizada
 378 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 379 .. image:: img/norm-hist-mem.pdf
 380     :width: 12.5cm
 381
 382 Tiempo Total de Ejecución
 383 ~~~~~~~~~~~~~~~~~~~~~~~~~
 384 .. image:: img/norm-hist-time.pdf
 385     :width: 12.5cm
 386
 387
 388
 389 Conclusión
 390 ==============================================================================
 391
 392 Conclusión
 393 --------------------------------------------------
 394
 395 Resumen
 396 ~~~~~~~
 397 * Objetivo principal
 398
 399   Minimizar tiempo de pausa para programas reales
 400
 401   Tiempo de pausa de Dil:
 402
 403   * *Stop-the-world* **160 veces menor** (1.66s → 0.01s)
 404   * Pausa real **40 veces menor** (1.7s → 0.045s)
 405
 406 * Objetivo secundario
 407
 408   No empeorar mucho el recolector actual en ningún aspecto
 409
 410   Utilización de memoria de Dil:
 411
 412   **50% mayor** (mucho *overhead* por marcado preciso)
 413
 414 * Yapa
 415
 416   Tiempo total de ejecución de Dil:
 417
 418   Casi **3 veces menor** (55s → 20s)
 419
 420 Problemas, Limitaciones y Puntos Pendientes
 421 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 422 * Explosión de uso de memoria con *eager allocation*
 423 * Eficiencia del marcado preciso
 424 * Mejorar predicción de *early collection*
 425 * Experimentar con ``clone(2)``
 426
 427 Trabajos Relacionados
 428 ~~~~~~~~~~~~~~~~~~~~~
 429 * *Memory Management in the D Programming Language*
 430
 431   Vladimir Panteleev. Proyecto de licenciatura, Universitatea Tehnică
 432   a Moldovei, 2009.
 433
 434 * *Integrate Precise Heap Scanning Into the GC*
 435
 436   David Simcha (GC + diseño) y Vincent Lang (compilador). No formal, *bug
 437   report*, 2009-2010.
 438
 439 * *Non-intrusive Cloning Garbage Collection with Stock Operating System Support*
 440
 441   Gustavo Rodriguez-Rivera y Vince Russo. Software Practiceand Experience
 442   Volumen 27, Número 8.  Agosto 1997.
 443
 444 Trabajos Futuros
 445 ~~~~~~~~~~~~~~~~
 446 * Organización de memoria
 447 * Barrido
 448 * Precisión
 449 * Concurrencia → *Lock* **global**
 450 * Movimiento
 451
 452 Preguntas
 453 ~~~~~~~~~
 454 ¿?
 455
 456 Fin
 457 ~~~
 458 ¡Gracias!
 459
 460
 461 .. vim: set et sw=4 sts=4 spell spelllang=es :