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