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   .. flt:: t:con-staticsize
 234      :type: table
 235
 236      Aumento del tamaño de la memoria estática (bytes).
 237
 238      ======== ======== ======== =========== ===========
 239      Programa TBGC     CDGC     CDGC-TBGC   CDGC/TBGC
 240      ======== ======== ======== =========== ===========
 241      bh       22208    27604    5396        1.243
 242      bigarr   18820    24212    5392        1.287
 243      bisort   19836    25232    5396        1.272
 244      conalloc 25816    31208    5392        1.209
 245      concpu   25816    31208    5392        1.209
 246      dil      416900   422300   5400        1.013
 247      em3d     20988    26380    5392        1.257
 248      mcore    18564    23988    5424        1.292
 249      rnddata  188940   194332   5392        1.029
 250      sbtree   22196    27588    5392        1.243
 251      split    24312    29736    5424        1.223
 252      tree     18660    24084    5424        1.291
 253      tsp      20772    26168    5396        1.260
 254      voronoi  21184    26580    5396        1.255
 255      ======== ======== ======== =========== ===========
 256
 257   Además se ha observado un crecimiento importante en el tamaño del área de
 258   memoria estática del programa. En el cuadro :vref:`t:con-staticsize` se
 259   puede observar dicho crecimiento para cada uno de los programas del banco de
 260   pruebas. Esto se debe a que el recolector original está escrito de una forma
 261   muy primitiva, usando muy pocos tipos de datos definidos por el usuario,
 262   mientras que CDGC utiliza varias más, incluyendo algunos parametrizados. D_
 263   guarda la información de tipos en el área de memoria estática y se genera
 264   mucha información por cada tipo. Además no separa el área de memoria
 265   estática que debe ser utilizada como parte del *root set* de la que no (no
 266   hay necesidad de que la información de tipos sea parte del *root set*). Esto
 267   causa que por cada recolección, se tenga que visitar bastante más memoria y,
 268   lo que es probablemente peor, que aumente la probabilidad de encontrar
 269   *falsos punteros*, dado que este área de memoria se marca siempre de forma
 270   conservativa.
 271
 272   Finalmente, en el cuadro :vref:`t:con-binsize` también se puede observar un
 273   incremento en el tamaño del binario, lo que puede ser otra causa de la
 274   pérdida de rendimiento, dado que puede afectar a la localidad de referencia
 275   del caché, por ejemplo.
 276
 277   .. flt:: t:con-binsize
 278      :type: table
 279
 280      Aumento del tamaño del binario (bytes).
 281
 282      ======== ======== ======== =========== ===========
 283      Programa TBGC     CDGC     CDGC-TBGC   CDGC/TBGC
 284      ======== ======== ======== =========== ===========
 285      bh       138060   159884   21824       1.158
 286      bigarr   192004   213832   21828       1.114
 287      bisort   115164   136988   21824       1.190
 288      conalloc 149848   171676   21828       1.146
 289      concpu   149848   171676   21828       1.146
 290      dil      1859208  1881028  21820       1.012
 291      em3d     116324   142248   25924       1.223
 292      mcore    105748   127576   21828       1.206
 293      rnddata  1492588  1518512  25924       1.017
 294      sbtree   129860   155784   25924       1.200
 295      split    144308   166136   21828       1.151
 296      tree     105844   127672   21828       1.206
 297      tsp      128412   150236   21824       1.170
 298      voronoi  141112   162936   21824       1.155
 299      ======== ======== ======== =========== ===========
 300
 301
 302 Trabajos relacionados
 303 ----------------------------------------------------------------------------
 304
 305 Dado que D_ no ha penetrado en ámbitos académicos, se ha encontrado un solo
 306 trabajo de investigación relacionado. Sin embargo se ha encontrado otro
 307 trabajo que si bien no es formal, ha sido de mucha importancia para el
 308 desarrollo de este trabajo.
 309
 310 A continuación se describen ambos.
 311
 312 * *Memory Management in the D Programming Language* [PAN09]_.
 313
 314   Tesis de licenciatura de Vladimir Panteleev cuya resumen traducido es el
 315   siguiente:
 316
 317       Este reporte describe el estudio de las técnicas de manejo automático de
 318       memoria, su implementación en el lenguaje de programación D_, y el
 319       trabajo para mejorar el estado del manejo de memoria.
 320
 321   Si bien plantea pequeñas optimizaciones para el recolector de basura
 322   (algunas utilizadas en este trabajo), se centra principalmente en el
 323   desarrollo de Diamond, una utilidad para depuración de manejo de memoria en
 324   D_.
 325
 326 * Integración de marcado preciso del *heap* al recolector de basura
 327   [DBZ3463]_.
 328
 329   Ya citado varias veces en este trabajo, fue comenzado por David Simcha
 330   y publicado en el sistema de seguimiento de fallas de D_ que se limita a una
 331   implementación a nivel biblioteca de usuario y sobre `D 2.0`_. Vincent Lang
 332   (mejor conocido como *wm4* en la comunidad de D_) da continuidad a este
 333   trabajo pero modificando el compilador DMD_ y trabajando con `D 1.0`_
 334   y Tango_.
 335
 336   El soporte de marcado preciso presentado en este trabajo se basa en las
 337   modificaciones hechas al compilador DMD_ por Vincent Lang (que aún no fueron
 338   integradas de forma oficial).
 339
 340
 341
 342 Trabajos futuros
 343 ----------------------------------------------------------------------------
 344
 345 En la sección :ref:`con_pending` se mencionan varios aspectos de este trabajo
 346 que podrían verse beneficiados por trabajos futuros, sin embargo se trata en
 347 general de pequeñas optimizaciones o mejoras de alcance muy limitado.
 348
 349 A continuación se recopilan varios otros aspectos identificados durante el
 350 desarrollo del presente trabajo, pero que requieren un nivel de análisis
 351 y, potencialmente, de desarrollo mayor a los ya presentados en la sección
 352 mencionada.
 353
 354 * Mejoras en la organización de memoria del recolector.
 355
 356   Si bien se ha mencionado en un principio la organización actual como un
 357   aspecto positivo del recolector, varios resultados han demostrado
 358   deficiencias importantes. El nivel de espacio desperdiciado por la división
 359   de memoria en bloques puede ser muy significativa y la forma en la que se
 360   almacena la información de tipos para el marcado preciso puede incluso
 361   acentuarlo todavía más (como se demuestra en los resultados para ``bh``
 362   y ``dil``).
 363
 364   Este problema no solo afecta al consumo de memoria, además genera un efecto
 365   dominó por el incremento de la probabilidad de tener *falsos punteros*
 366   y perjudica al tiempo total de ejecución por empeorar la localidad de
 367   referencia del caché y por hacer que se prolongue la recolección de basura
 368   por tener que marcar y barrer más memoria.
 369
 370   Una posible alternativa es tener una lista de libres por **tipo**, cuyo
 371   tamaño de bloque sea exactamente igual al tamaño del tipo que almacena. La
 372   información de tipo se almacenaría entonces solo una vez y no habría
 373   desperdicio de memoria alguno dejando de lado un posible relleno para
 374   completar una página. Este esquema debería tener algún tipo de guarda para
 375   programas con una cantidad exuberante de tipos de datos.
 376
 377   También podría ser conveniente separar los bloques marcados como ``NO_SCAN``
 378   de los que sí deben ser marcados, de manera que no necesite almacenar
 379   directamente los bits de ``mark`` , ``scan`` y ``noscan``. También se podría
 380   proponer algún área de memoria especial para almacenar cadenas de texto
 381   (como un caso especial de lo anterior) por tener estas características muy
 382   particular (largos muy variables, cambian de tamaño de forma relativamente
 383   frecuente, etc.). Las posibilidades son enormes.
 384
 385 * Mejoras en la fase de barrido.
 386
 387   En este trabajo todas las mejoras propuestas se encargaron de la fase de
 388   marcado, pero mucho se pude mejorar en la fase de barrido también. Por un
 389   lado se podría agregar barrido perezoso para disminuir aún más el tiempo de
 390   pausa real. Se ha mostrado que en muchos casos los tiempos de pausa pueden
 391   ser considerablemente altos debido a que la fase de barrido no se realiza en
 392   paralelo como el marcado.
 393
 394   Otra forma de disminuir el tiempo de pausa real sería realizar un barrido
 395   concurrente también. Esto no puede realizarse en otro proceso porque el
 396   barrido es el encargado de ejecutar los *finalizadores*, pero sí se podría
 397   barrer en otro hilo y, por ejemplo, seguir utilizando *eager allocation*
 398   hasta que el barrido finalice.
 399
 400 * Mejoras en la precisión del marcado.
 401
 402   Como se mencionó anteriormente, el área de memoria estática se marca de
 403   forma conservativa dada la falta de información de tipos de ésta. Sin
 404   embargo es bastante razonable pensar en que el compilador genere información
 405   de tipos para el área de memoria estática o que al menos informe mejor al
 406   recolector que partes deben ser consideradas parte del *root set* y cuales
 407   no. Dado que la memoria estática crece de forma considerable con el
 408   incremento de la cantidad de tipos definidos por el usuario, ya solo esa
 409   división puede hacer una diferencia importante; en especial considerando
 410   como aumenta la memoria estática solamente por usar más tipos de datos en el
 411   recolector.
 412
 413   También podría explorarse el agregado de precisión al *stack* pero esto es
 414   realmente muy complicado dado que la única solución que pareciera viable es
 415   el uso de *shadow stack* [HEND02]_ que requiere un trabajo extra por cada
 416   llamado a función, cosa que va en contra de la filosofía de D_ de pagar solo
 417   por lo que se usa. Sin embargo podría explorarse agregar un esquema de ese
 418   tipo como una opción del compilador, de forma que el usuario pueda decidir
 419   si vale la pena para una aplicación particular o no.
 420
 421 * Mejoras en la concurrencia.
 422
 423   El *lock* global del recolector es otro aspecto que demostró ser
 424   problemático. Podrían analizarse formas de minimizar la necesidad de usar
 425   *locks* o de hacerlo de forma más granular, de manera que algunas
 426   operaciones del recolector puedan ser ejecutadas en paralelo. También se
 427   podría experimentar con el uso de estructura de datos libres de *locks*
 428   (*lock-free*).
 429
 430   Otra forma de minimizar la sincronización es utilizando *pools* por hilo, de
 431   manera de poder alocar memoria de forma concurrente y hasta explorar la
 432   posibilidad de efectuar recolecciones locales a un solo hilo; aunque esto
 433   último probablemente sea equivalente a implementar un recolector de basura
 434   con particiones (por ejemplo generacional).
 435
 436 * Recolección con movimiento.
 437
 438   La información de tipos provista por el trabajo hecho por Vincent Lang
 439   [DBZ3463]_ es suficientemente completa como para poder implementar un
 440   recolector con movimiento. La efectividad de un recolector de estas
 441   características en D_ está por comprobarse, dado que cualquier celda
 442   apuntada por alguna palabra que debió ser marcada de forma conservativa debe
 443   quedar inmóvil, por lo que gran parte del éxito de un recolector con
 444   movimiento en D_ está supeditado a la proporción de celdas que queden
 445   inmóviles. Sin embargo sea muy probablemente un área que valga la pena
 446   explorar.
 447
 448
 449 .. include:: links.rst
 450
 451 .. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :