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