source/conclusion.rst

   1
   2 .. _conclusion:
   3
   4 Conclusión
   5 ============================================================================
   6
   7 Durante el desarrollo de este trabajo se introdujo al lenguaje de programación
   8 D_ y a los conceptos básicos de recolección de basura. Luego se analizó el
   9 recolector de basura actual y se señalaron sus principales falencias,
  10 proponiendo un conjunto de modificaciones con el objeto de subsanarlas.
  11 Para evaluar los resultados de las modificaciones se construyó un banco de
  12 pruebas variado para poder analizar tanto aspectos particulares como el
  13 funcionamiento de programas reales; y se establecieron métricas para
  14 cuantificar dichos resultados.
  15
  16 El objetivo principal fue bajar la latencia del recolector, es decir el tiempo
  17 máximo de pausa real, y se pudo comprobar que, salvo en casos muy
  18 particulares, esto fue conseguido de manera contundente (con tiempos de pausa
  19 hasta 200 veces menores que el recolector original de D_). La inclusión del
  20 marcado concurrente demostró ser una aproximación correcta al problema.
  21
  22 La aceptación de la solución por parte de la comunidad también ha sido un
  23 objetivo importante de este trabajo, y si bien en este sentido sigue siendo un
  24 trabajo en curso, la recepción ha sido ampliamente positiva por parte de la
  25 comunidad y se espera que el resultado de este trabajo sea incorporado en el
  26 corto plazo tanto a `D 1.0`_ a través de Tango_, como a `D 2.0`_.
  27
  28 Además de los objetivos principales se cumplieron otros objetivos anexos, pero
  29 no por eso menos importantes. Para la aplicación real el tiempo total de
  30 ejecución se ha reducido hasta casi una tercera parte, y para otras
  31 aplicaciones pequeñas se ha reducido más de 17 veces. Estos resultados han
  32 sido particularmente sorprendentes, siendo que la reducción del tiempo total
  33 de ejecución no ha sido parte del objetivo principal y no se habían encontrado
  34 referencias en la bibliografía de casos similares (por el contrario, en
  35 general la baja de la latencia suele estar acompañada de una suba en el tiempo
  36 total de ejecución).
  37
  38 Se ha podido experimentar además con el marcado preciso, otro de los problemas
  39 del recolector más presentes en la comunidad. Los resultados obtenidos son
  40 variados, encontrando casos donde se consigue una mejoría notoria y otros en
  41 donde la forma de almacenar la información de tipos produce resultados poco
  42 satisfactorios.
  43
  44 La mayor flexibilidad del recolector al ser configurable también ha demostrado
  45 ser útil. Por un lado para este mismo trabajo, al permitir realizar mediciones
  46 sobre el mismo binario utilizando diferentes configuraciones. Por otro, la
  47 amplia gama de resultados dispares obtenidos son una buena muestra de que no
  48 existen *balas de plata*, y cada programa tiene necesidades particulares en
  49 cuanto a recolección de basura. Por lo tanto, distintos programas pueden verse
  50 beneficiados o perjudicados por diferentes configuraciones. Esto hace que la
  51 posibilidad de configurar el recolector en tiempo de inicialización sea
  52 particularmente ventajoso.
  53
  54 Finalmente, algunas optimizaciones muy pequeñas demostraron ser también muy
  55 valiosas para algunos casos particulares, logrando reducciones en el tiempo
  56 total de ejecución de hasta 5 veces.
  57
  58
  59
  60 .. _con_pending:
  61
  62 Puntos pendientes, problemas y limitaciones
  63 ----------------------------------------------------------------------------
  64
  65 Si bien los objetivos de este trabajo han sido alcanzados con éxito, hay
  66 varias pequeñas mejoras que han quedado pendientes y algunos problemas
  67 y limitaciones conocidas. A continuación se describe cada una de ellos.
  68
  69 * Emisión de mensajes informativos para depuración.
  70
  71   Entre las herramientas de depuración que provee el recolector, no se ha
  72   mencionado la posibilidad de emitir opcionalmente mensajes informativos para
  73   ayudar a depurar tanto problemas en el recolector como en el programa que lo
  74   usa. El recolector actual tiene esa posibilidad pero es elegible en tiempo de
  75   compilación. En este trabajo se agregaron las opciones en tiempo de
  76   inicialización ``log_file`` y ``verbose`` con el propósito de poder elegir un
  77   archivo en donde guardar los mensajes informativos y el nivel de detalle de
  78   dichos mensajes respectivamente, pero finalmente nunca se implementaron.
  79
  80 * Predicción para estimar cuando lanzar una recolección temprana.
  81
  82   Las recolecciones se lanzan de manera temprana según la opción ``min_free``.
  83   Una mejor aproximación podría ser predecir cuando se va a agotar la memoria
  84   libre de forma adaptativa, calculando la tasa de asignación de memoria
  85   y el tiempo total que tomó la recolección. Esta estimación se podría mejorar
  86   guardando un historial de que tan acertada fue para recolecciones pasadas. La
  87   predicción ideal debería ser capaz de:
  88
  89   * Evitar tiempos de pausa (es decir, que la recolección temprana termine antes
  90     de que se agote la memoria libre).
  91   * No realizar recolecciones innecesarias (es decir, no lanzar recolecciones
  92     tempranas si el programa no está pidiendo memoria a una tasa suficientemente
  93     alta).
  94
  95 * Explosión del uso de memoria con creación ansiosa de *pools*.
  96
  97   Se ha observado que en situaciones muy particulares, al usar creación
  98   ansiosa de *pools* (o *eager allocation*), el uso de memoria crece
  99   desmesuradamente. Si bien este efecto se ve principalmente en las pruebas
 100   sintetizadas con tal fin, algunos programas reales lo sufren también, pero
 101   en general se puede atenuar utilizando también *early collection*.
 102   Recordemos además, que lo analizado es el consumo **máximo** de memoria, por
 103   lo que una ráfaga de pedidos de memoria podría crear un pico, pero durante
 104   la mayor parte del transcurso del programa el consumo de memoria podría ser
 105   mucho menor. Queda pendiente analizar los casos puntuales con alguna métrica
 106   más detallada sobre el progreso del uso de memoria.
 107
 108   También queda pendiente buscar alguna estimación de cuándo es conveniente
 109   utilizar *eager allocation* de forma adaptativa, dado que en general se ve
 110   que cuando explota el consumo de memoria, también explota el tiempo de
 111   pausa, lo que quita gran parte del sentido de usar *eager allocation* en
 112   primer lugar. Estimando de alguna manera cuanto va a crecer el tiempo de
 113   pausa debido a esta opción, se podría desactivar temporalmente cuando no
 114   haya ganancia en el tiempo de pausa para evitar esta explosión ante ráfagas
 115   de pedidos de memoria.
 116
 117 * Reestructuración y limpieza del código.
 118
 119   Si bien se han hecho muchas mejoras a nivel de estructura y limpieza de
 120   código, ha quedado mucho pendiente. Todavía hay bastante repetición en el
 121   código y se mantiene la arquitectura básica del recolector.
 122
 123 * Experimentación con la llamada al sistema :manpage:`clone(2)`.
 124
 125   Linux_ implementa la llamada al sistema :manpage:`fork(2)` a través de otra de
 126   más bajo nivel llamada :manpage:`clone(2)`. :manpage:`clone(2)` permite una
 127   granularidad a la hora de indicar que partes del proceso deben ser copiadas al
 128   hijo y cuales deben ser compartidas mucho mayor que :manpage:`fork(2)`. Por
 129   ejemplo, se puede compartir toda la memoria del proceso, siendo este el
 130   mecanismo por el cual Linux_ implementa los hilos. Para este trabajo podría
 131   ser beneficioso usar :manpage:`clone(2)` para evitar copiar otro tipo de
 132   estructuras dado que el proceso
 133   hijo, al correr solo la fase de marcado, nunca va a interferir el *mutator*.
 134   Se podría experimentar no copiando las siguientes estructuras, por ejemplo:
 135
 136   ``CLONE_FILES``
 137      Tabla de descriptores de archivo.
 138
 139   ``CLONE_FS``
 140      Tabla de sistemas de archivo montados.
 141
 142   ``CLONE_IO``
 143      Contextos de entrada/salida.
 144
 145   ``CLONE_SIGHAND``
 146      Tabla de manejadores de señales.
 147
 148 * Uso de memoria compartida.
 149
 150   Al realizar marcado concurrente, si el *mutator* usa memoria compartida entre
 151   procesos que almacene punteros al *heap* podría haber problemas, dado que la
 152   fase de barrido no estaría trabajando con una *fotografía* de la memoria. El
 153   grafo de conectividad podría efectivamente cambiar mientras se corre la fase
 154   de barrido y por lo tanto el algoritmo deja de ser correcto, existiendo la
 155   posibilidad de que se reciclen celdas *vivas*.
 156
 157   Dado que el usuario debe registrar cualquier puntero que no sea parte de la
 158   memoria estática, *stack* o *heap* del recolector como parte del *root set*,
 159   se podría agregar un parámetro extra a la función de registro que indique si
 160   los punteros agregados residen en memoria compartida. De este modo, al momento
 161   de hacer el :manpage:`fork(2)`, el recolector debería realizar una copia de
 162   esos punteros mientras todos los hilos están pausados para obtener
 163   efectivamente una *fotografía* estable del *root set*.
 164
 165 * Condición de carrera al utilizar :manpage:`fork(2)`.
 166
 167   Existe una condición de carrera si se lanzan hilos usando directamente las
 168   llamadas al sistema operativo, es decir si no se lanzan a través del soporte
 169   de hilos de D_, si el hilo lanzado utiliza archivos con *buffer* de
 170   C (``FILE*``). Esto se debe a la siguiente porción de código (introducida por
 171   el marcado concurrente)::
 172
 173      function collect() is
 174         stop_the_world()
 175         fflush(null) //    <-------------------------
 176         child_pid = fork()
 177         if child_pid is 0
 178            mark_phase()
 179            exit(0)
 180         // proceso padre
 181         start_the_world()
 182         wait(child_pid)
 183         sweep()
 184
 185   La llamada a :manpage:`fflush(3)` es necesaria para evitar que los archivos
 186   con *buffer* escriban su contenido dos veces al dispositivo, ya que la llamada
 187   a :manpage:`fork(2)` duplica el *buffer*, y si bien el archivo no se usa en el
 188   proceso con la fase de marcado, la biblioteca estándar de C escribe todos los
 189   *buffers* pendientes al terminar el proceso. Esto funciona para los hilos
 190   registrados por D_ gracias a que :manpage:`fflush(3)` se llama cuando todos
 191   los hilos están pausados, si no un hilo podría escribir al *buffer* justo
 192   después de llamar a :manpage:`fflush(3)` pero antes de llamar
 193   a :manpage:`fflush(2)`. Es por esto que si hay hilos no registrados por D_ que
 194   utilicen manejo de archivos con *buffer* de C, esta condición sí se puede dar
 195   y se pueden observar contenidos duplicados en dichos archivos.
 196
 197   Esta condición de carrera no tiene una solución simple, pero es de esperarse
 198   que no sea un problema real dado que no es un escenario común. Sin embargo
 199   eventualmente debería analizarse alguna solución más robusta.
 200
 201 * Soporte de referencias débiles.
 202
 203   Tango_ 0.99.9 incluye soporte de referencias débiles. Si bien se incorporó
 204   el código para manejar las referencias débiles, se espera que no funcione
 205   correctamente con CDGC (no se ha podido comprobar por la falta de programas
 206   de prueba que lo utilicen). La razón es que el soporte de referencias
 207   débiles de Tango_ 0.99.9 se basa en la premisa de que la fase de marcado
 208   corre con todos los hilos pausados, sin embargo al utilizar marcado
 209   concurrente, esto no es más cierto. Parecen haber soluciones viables a este
 210   problema pero no se han analizado en profundidad aún.
 211
 212 * Pérdida de rendimiento con respecto al recolector original.
 213
 214   Se ha observado también que, al no utilizar algunas optimizaciones de CDGC
 215   (como la mejora del factor de ocupación del *heap*), éste puede tener un
 216   rendimiento bastante menor a TBGC. Si bien no se ha investigado en
 217   profundidad las causas de esta pérdida de rendimiento, se han identificado
 218   algunos factores que podrían ser determinantes.
 219
 220   Por un lado, se ha observado que la mayor parte del tiempo extra que utiliza
 221   CDGC proviene de la fase de marcado, en particular de los cambios
 222   introducidos por el marcado preciso. Si bien se puede desactivar el marcado
 223   preciso, la lógico en tiempo de ejecución no cambia, por lo que se paga el
 224   precio sin obtener los beneficios. Queda pendiente analizar en más detalle
 225   las causas de esto y posibles optimizaciones para subsanarlo.
 226
 227   .. flt:: t:con-staticsize
 228      :type: table
 229
 230      Aumento del tamaño de la memoria estática (bytes)
 231
 232      ======== ======== ======== =========== ===========
 233      Programa TBGC     CDGC     CDGC-TBGC   CDGC/TBGC
 234      ======== ======== ======== =========== ===========
 235      bh       22208    27604    5396        1.243
 236      bigarr   18820    24212    5392        1.287
 237      bisort   19836    25232    5396        1.272
 238      conalloc 25816    31208    5392        1.209
 239      concpu   25816    31208    5392        1.209
 240      dil      416900   422300   5400        1.013
 241      em3d     20988    26380    5392        1.257
 242      mcore    18564    23988    5424        1.292
 243      rnddata  188940   194332   5392        1.029
 244      sbtree   22196    27588    5392        1.243
 245      split    24312    29736    5424        1.223
 246      tree     18660    24084    5424        1.291
 247      tsp      20772    26168    5396        1.260
 248      voronoi  21184    26580    5396        1.255
 249      ======== ======== ======== =========== ===========
 250
 251   Además se ha observado un crecimiento importante en el tamaño del área de
 252   memoria estática del programa. En el cuadro :vref:`t:con-staticsize` se
 253   puede observar dicho crecimiento para cada uno de los programas del banco de
 254   pruebas. Esto se debe a que el recolector original está escrito de una forma
 255   muy primitiva, usando muy pocos tipos de datos definidos por el usuario,
 256   mientras que CDGC utiliza varias más, incluyendo algunos parametrizados. D_
 257   guarda la información de tipos en el área de memoria estática y se genera
 258   mucha información por cada tipo. Además no separa el área de memoria
 259   estática que debe ser utilizada como parte del *root set* de la que no (no
 260   hay necesidad de que la información de tipos sea parte del *root set*). Esto
 261   causa que por cada recolección, se tenga que visitar bastante más memoria y,
 262   lo que es probablemente peor, que aumente la probabilidad de encontrar
 263   *falsos positivos*, dado que este área de memoria se marca siempre de forma
 264   conservativa.
 265
 266   Finalmente, en el cuadro :vref:`t:con-binsize` también se puede observar un
 267   incremento en el tamaño del binario, lo que puede ser otra causa de la
 268   pérdida de rendimiento, dado que puede afectar a la localidad de referencia
 269   del caché, por ejemplo.
 270
 271   .. flt:: t:con-binsize
 272      :type: table
 273
 274      Aumento del tamaño del binario (bytes)
 275
 276      ======== ======== ======== =========== ===========
 277      Programa TBGC     CDGC     CDGC-TBGC   CDGC/TBGC
 278      ======== ======== ======== =========== ===========
 279      bh       138060   159884   21824       1.158
 280      bigarr   192004   213832   21828       1.114
 281      bisort   115164   136988   21824       1.190
 282      conalloc 149848   171676   21828       1.146
 283      concpu   149848   171676   21828       1.146
 284      dil      1859208  1881028  21820       1.012
 285      em3d     116324   142248   25924       1.223
 286      mcore    105748   127576   21828       1.206
 287      rnddata  1492588  1518512  25924       1.017
 288      sbtree   129860   155784   25924       1.200
 289      split    144308   166136   21828       1.151
 290      tree     105844   127672   21828       1.206
 291      tsp      128412   150236   21824       1.170
 292      voronoi  141112   162936   21824       1.155
 293      ======== ======== ======== =========== ===========
 294
 295
 296 Trabajos relacionados
 297 ----------------------------------------------------------------------------
 298
 299 Dado que D_ no ha penetrado en ámbitos académicos, se ha encontrado un solo
 300 trabajo de investigación relacionado. Sin embargo se ha encontrado otro
 301 trabajo que si bien no es formal, ha sido de mucha importancia para el
 302 desarrollo de este trabajo.
 303
 304 A continuación se describen ambos.
 305
 306 * *Memory Management in the D Programming Language* [PAN09]_.
 307
 308   Tesis de licenciatura de Vladimir Panteleev cuya resumen traducido es el
 309   siguiente:
 310
 311       Este reporte describe el estudio de las técnicas de manejo automático de
 312       memoria, su implementación en el lenguaje de programación D_, y el
 313       trabajo para mejorar el estado del manejo de memoria.
 314
 315   Si bien plantea pequeñas optimizaciones para el recolector de basura
 316   (algunas utilizadas en este trabajo), se centra principalmente en el
 317   desarrollo de Diamond, una utilidad para depuración de manejo de memoria en
 318   D_.
 319
 320 * Integración de marcado preciso del *heap* al recolector de basura
 321   [DBZ3463]_.
 322
 323   Ya citado varias veces en este trabajo, fue comenzado por David Simcha
 324   y publicado en el sistema de seguimiento de fallas de D_ que se limita a una
 325   implementación a nivel biblioteca de usuario y sobre `D 2.0`_. Vincent Lang
 326   (mejor conocido como *wm4* en la comunidad de D_) da continuidad a este
 327   trabajo pero modificando el compilador DMD_ y trabajando con `D 1.0`_
 328   y Tango_.
 329
 330   El soporte de marcado preciso presentado en este trabajo se basa en las
 331   modificaciones hechas al compilador DMD_ por Vincent Lang (que aún no fueron
 332   integradas de forma oficial).
 333
 334
 335
 336 Trabajos futuros
 337 ----------------------------------------------------------------------------
 338
 339 En la sección :ref:`con_pending` se mencionan varios aspectos de este trabajo
 340 que podrían verse beneficiados por trabajos futuros, sin embargo se trata en
 341 general de pequeñas optimizaciones o mejoras de alcance muy limitado.
 342
 343 A continuación se recopilan varios otros aspectos identificados durante el
 344 desarrollo del presente trabajo, pero que requieren un nivel de análisis
 345 y, potencialmente, de desarrollo mayor a los ya presentados en la sección
 346 mencionada.
 347
 348 * Mejoras en la organización de memoria del recolector.
 349
 350   Si bien se ha mencionado en un principio la organización actual como un
 351   aspecto positivo del recolector, varios resultados han demostrado
 352   deficiencias importantes. El nivel de espacio desperdiciado por la división
 353   de memoria en bloques puede ser muy significativa y la forma en la que se
 354   almacena la información de tipos para el marcado preciso puede incluso
 355   acentuarlo todavía más (como se demuestra en los resultados para ``bh``
 356   y ``dil``).
 357
 358   Este problema no solo afecta al consumo de memoria, además genera un efecto
 359   dominó por el incremento de la probabilidad de tener *falsos positivos*
 360   y perjudica al tiempo total de ejecución por empeorar la localidad de
 361   referencia del caché y por hacer que se prolongue la recolección de basura
 362   por tener que marcar y barrer más memoria.
 363
 364   Una posible alternativa es tener una lista de libres por **tipo**, cuyo
 365   tamaño de bloque sea exactamente igual al tamaño del tipo que almacena. La
 366   información de tipo se almacenaría entonces solo una vez y no habría
 367   desperdicio de memoria alguno dejando de lado un posible relleno para
 368   completar una página. Este esquema debería tener algún tipo de guarda para
 369   programas con una cantidad exuberante de tipos de datos.
 370
 371   También podría ser conveniente separar los bloques marcados como ``NO_SCAN``
 372   de los que sí deben ser marcados, de manera que no necesite almacenar
 373   directamente los bits de ``mark`` , ``scan`` y ``noscan``. También se podría
 374   proponer algún área de memoria especial para almacenar cadenas de texto
 375   (como un caso especial de lo anterior) por tener estas características muy
 376   particular (largos muy variables, cambian de tamaño de forma relativamente
 377   frecuente, etc.). Las posibilidades son enormes.
 378
 379 * Mejoras en la fase de barrido.
 380
 381   En este trabajo todas las mejoras propuestas se encargaron de la fase de
 382   marcado, pero mucho se pude mejorar en la fase de barrido también. Por un
 383   lado se podría agregar barrido perezoso para disminuir aún más el tiempo de
 384   pausa real. Se ha mostrado que en muchos casos los tiempos de pausa pueden
 385   ser considerablemente altos debido a que la fase de barrido no se realiza en
 386   paralelo como el marcado.
 387
 388   Otra forma de disminuir el tiempo de pausa real sería realizar un barrido
 389   concurrente también. Esto no puede realizarse en otro proceso porque el
 390   barrido es el encargado de ejecutar los *finalizadores*, pero sí se podría
 391   barrer en otro hilo y, por ejemplo, seguir utilizando *eager allocation*
 392   hasta que el barrido finalice.
 393
 394 * Mejoras en la precisión del marcado.
 395
 396   Como se mencionó anteriormente, el área de memoria estática se marca de
 397   forma conservativa dada la falta de información de tipos de ésta. Sin
 398   embargo es bastante razonable pensar en que el compilador genere información
 399   de tipos para el área de memoria estática o que al menos informe mejor al
 400   recolector que partes deben ser consideradas parte del *root set* y cuales
 401   no. Dado que la memoria estática crece de forma considerable con el
 402   incremento de la cantidad de tipos definidos por el usuario, ya solo esa
 403   división puede hacer una diferencia importante; en especial considerando
 404   como aumenta la memoria estática solamente por usar más tipos de datos en el
 405   recolector.
 406
 407   También podría explorarse el agregado de precisión al *stack* pero esto es
 408   realmente muy complicado dado que la única solución que pareciera viable es
 409   el uso de *shadow stack* [HEND02]_ que requiere un trabajo extra por cada
 410   llamado a función, cosa que va en contra de la filosofía de D_ de pagar solo
 411   por lo que se usa. Sin embargo podría explorarse agregar un esquema de ese
 412   tipo como una opción del compilador, de forma que el usuario pueda decidir
 413   si vale la pena para una aplicación particular o no.
 414
 415 * Mejoras en la concurrencia.
 416
 417   El *lock* global del recolector es otro aspecto que demostró ser
 418   problemático. Podrían analizarse formas de minimizar la necesidad de usar
 419   *locks* o de hacerlo de forma más granular, de manera que algunas
 420   operaciones del recolector puedan ser ejecutadas en paralelo. También se
 421   podría experimentar con el uso de estructura de datos libres de *locks*
 422   (*lock-free*).
 423
 424   Otra forma de minimizar la sincronización es utilizando *pools* por hilo, de
 425   manera de poder alocar memoria de forma concurrente y hasta explorar la
 426   posibilidad de efectuar recolecciones locales a un solo hilo; aunque esto
 427   último probablemente sea equivalente a implementar un recolector de basura
 428   con particiones (por ejemplo generacional).
 429
 430 * Recolección con movimiento.
 431
 432   La información de tipos provista por el trabajo hecho por Vincent Lang
 433   [DBZ3463]_ es suficientemente completa como para poder implementar un
 434   recolector con movimiento. La efectividad de un recolector de estas
 435   características en D_ está por comprobarse, dado que cualquier celda
 436   apuntada por alguna palabra que debió ser marcada de forma conservativa debe
 437   quedar inmóvil, por lo que gran parte del éxito de un recolector con
 438   movimiento en D_ está supeditado a la proporción de celdas que queden
 439   inmóviles. Sin embargo sea muy probablemente un área que valga la pena
 440   explorar.
 441
 442
 443 .. include:: links.rst
 444
 445 .. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :