source/conclusion.rst

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