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 Diapositiva 1
 317 ~~~~~~~~~~~~~
 318 Diapositiva 1
 319
 320 Diapositiva 2
 321 ~~~~~~~~~~~~~
 322 Diapositiva 2
 323
 324
 325 Tiempo de Stop-The-World
 326 --------------------------------------------------
 327
 328 Diapositiva 1
 329 ~~~~~~~~~~~~~
 330 Diapositiva 1
 331
 332 Diapositiva 2
 333 ~~~~~~~~~~~~~
 334 Diapositiva 2
 335
 336
 337 Tiempo de Pausa Real
 338 --------------------------------------------------
 339
 340 Diapositiva 1
 341 ~~~~~~~~~~~~~
 342 Diapositiva 1
 343
 344 Diapositiva 2
 345 ~~~~~~~~~~~~~
 346 Diapositiva 2
 347
 348
 349 Tiempo de Ejecución
 350 --------------------------------------------------
 351
 352 Diapositiva 1
 353 ~~~~~~~~~~~~~
 354 Diapositiva 1
 355
 356 Diapositiva 2
 357 ~~~~~~~~~~~~~
 358 Diapositiva 2
 359
 360
 361 Conclusión
 362 ==============================================================================
 363
 364 Conclusión
 365 --------------------------------------------------
 366
 367 Resumen
 368 ~~~~~~~
 369 * Recolección de basura → Inagotable
 370 * D → Multi-paradigma → Desafío
 371 * Recolección de basura en D → Fértil
 372 * Mejoras propuestas → Efectivas
 373 * Resultados → Positivos: Esperados + Inesperados
 374
 375 Problemas, Limitaciones y Puntos Pendientes
 376 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 377 * Explosión de uso de memoria con *eager allocation*
 378 * Eficiencia del marcado preciso
 379 * Mejorar predicción de *early collection*
 380 * Experimentar con ``clone(2)``
 381
 382 Trabajos Relacionados
 383 ~~~~~~~~~~~~~~~~~~~~~
 384 * *Memory Management in the D Programming Language*
 385
 386   Vladimir Panteleev. Proyecto de licenciatura, Universitatea Tehnică
 387   a Moldovei, 2009.
 388
 389 * *Integrate Precise Heap Scanning Into the GC*
 390
 391   David Simcha (GC + diseño) y Vincent Lang (compilador). No formal, *bug
 392   report*, 2009-2010.
 393
 394 * *Non-intrusive Cloning Garbage Collection with Stock Operating System Support*
 395
 396   Gustavo Rodriguez-Rivera y Vince Russo. Software Practiceand Experience
 397   Volumen 27, Número 8.  Agosto 1997.
 398
 399 Trabajos Futuros
 400 ~~~~~~~~~~~~~~~~
 401 * Organización de memoria
 402 * Barrido
 403 * Precisión
 404 * Concurrencia → *Lock* **global**
 405 * Movimiento
 406
 407 Preguntas
 408 ~~~~~~~~~
 409 ¿?
 410
 411 Fin
 412 ~~~
 413 ¡Gracias!
 414
 415
 416 .. vim: set et sw=4 sts=4 spell spelllang=es :