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: EMPEZADO
   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 Puntos pendientes, problemas y limitaciones
  67 ----------------------------------------------------------------------------
  68
  69 Si bien los objetivos de este trabajo han sido alcanzados con éxito, hay
  70 varias pequeñas mejoras que han quedado pendientes y algunos problemas
  71 y limitaciones conocidas. A continuación se describe cada una de ellos.
  72
  73 * Emisión de mensajes informativos para depuración.
  74
  75   Entre las herramientas de depuración que provee el recolector, no se ha
  76   mencionado la posibilidad de emitir opcionalmente mensajes informativos para
  77   ayudar a depurar tanto problemas en el recolector como en el programa que lo
  78   usa. El recolector actual tiene esa posibilidad pero es elegible en tiempo de
  79   compilación. En este trabajo se agregaron las opciones en tiempo de
  80   inicialización ``log_file`` y ``verbose`` con el propósito de poder elegir un
  81   archivo en donde guardar los mensajes informativos y el nivel de detalle de
  82   dichos mensajes respectivamente, pero finalmente nunca se implementaron.
  83
  84 * Predicción para estimar cuando lanzar una recolección temprana.
  85
  86   Las recolecciones se lanzan de manera temprana según la opción ``min_free``.
  87   Una mejor aproximación podría ser predecir cuando se va a agotar la memoria
  88   libre de forma adaptativa, calculando la tasa de asignación de memoria
  89   y el tiempo total que tomó la recolección. Esta estimación se podría mejorar
  90   guardando un historial de que tan acertada fue para recolecciones pasadas. La
  91   predicción ideal debería ser capaz de:
  92
  93   * Evitar tiempos de pausa (es decir, que la recolección temprana termine antes
  94     de que se agote la memoria libre).
  95   * No realizar recolecciones innecesarias (es decir, no lanzar recolecciones
  96     tempranas si el programa no está pidiendo memoria a una tasa suficientemente
  97     alta).
  98
  99 * Explosión del uso de memoria con creación ansiosa de *pools*.
 100
 101   Se ha observado que en situaciones muy particulares, al usar creación
 102   ansiosa de *pools* (o *eager allocation*), el uso de memoria crece
 103   desmesuradamente. Si bien este efecto se ve principalmente en las pruebas
 104   sintetizadas con tal fin, algunos programas reales lo sufren también, pero
 105   en general se puede atenuar utilizando también *early collection*.
 106   Recordemos además, que lo analizado es el consumo **máximo** de memoria, por
 107   lo que una ráfaga de pedidos de memoria podría crear un pico, pero durante
 108   la mayor parte del transcurso del programa el consumo de memoria podría ser
 109   mucho menor. Queda pendiente analizar los casos puntuales con alguna métrica
 110   más detallada sobre el progreso del uso de memoria.
 111
 112   También queda pendiente buscar alguna estimación de cuándo es conveniente
 113   utilizar *eager allocation* de forma adaptativa, dado que en general se ve
 114   que cuando explota el consumo de memoria, también explota el tiempo de
 115   pausa, lo que quita gran parte del sentido de usar *eager allocation* en
 116   primer lugar. Estimando de alguna manera cuanto va a crecer el tiempo de
 117   pausa debido a esta opción, se podría desactivar temporalmente cuando no
 118   haya ganancia en el tiempo de pausa para evitar esta explosión ante ráfagas
 119   de pedidos de memoria.
 120
 121 * Reestructuración y limpieza del código.
 122
 123   Si bien se han hecho muchas mejoras a nivel de estructura y limpieza de
 124   código, ha quedado mucho pendiente. Todavía hay bastante repetición en el
 125   código y se mantiene la arquitectura básica del recolector.
 126
 127 * Experimentación con la llamada al sistema :manpage:`clone(2)`.
 128
 129   Linux_ implementa la llamada al sistema :manpage:`fork(2)` a través de otra de
 130   más bajo nivel llamada :manpage:`clone(2)`. :manpage:`clone(2)` permite una
 131   granularidad a la hora de indicar que partes del proceso deben ser copiadas al
 132   hijo y cuales deben ser compartidas mucho mayor que :manpage:`fork(2)`. Por
 133   ejemplo, se puede compartir toda la memoria del proceso, siendo este el
 134   mecanismo por el cual Linux_ implementa los hilos. Para este trabajo podría
 135   ser beneficioso usar :manpage:`clone(2)` para evitar copiar otro tipo de
 136   estructuras dado que el proceso
 137   hijo, al correr solo la fase de marcado, nunca va a interferir el *mutator*.
 138   Se podría experimentar no copiando las siguientes estructuras, por ejemplo:
 139
 140   ``CLONE_FILES``
 141      Tabla de descriptores de archivo.
 142
 143   ``CLONE_FS``
 144      Tabla de sistemas de archivo montados.
 145
 146   ``CLONE_IO``
 147      Contextos de entrada/salida.
 148
 149   ``CLONE_SIGHAND``
 150      Tabla de manejadores de señales.
 151
 152 * Uso de memoria compartida.
 153
 154   Al realizar marcado concurrente, si el *mutator* usa memoria compartida entre
 155   procesos que almacene punteros al *heap* podría haber problemas, dado que la
 156   fase de barrido no estaría trabajando con una *fotografía* de la memoria. El
 157   grafo de conectividad podría efectivamente cambiar mientras se corre la fase
 158   de barrido y por lo tanto el algoritmo deja de ser correcto, existiendo la
 159   posibilidad de que se reciclen celdas *vivas*.
 160
 161   Dado que el usuario debe registrar cualquier puntero que no sea parte de la
 162   memoria estática, *stack* o *heap* del recolector como parte del *root set*,
 163   se podría agregar un parámetro extra a la función de registro que indique si
 164   los punteros agregados residen en memoria compartida. De este modo, al momento
 165   de hacer el :manpage:`fork(2)`, el recolector debería realizar una copia de
 166   esos punteros mientras todos los hilos están pausados para obtener
 167   efectivamente una *fotografía* estable del *root set*.
 168
 169 * Condición de carrera al utilizar :manpage:`fork(2)`.
 170
 171   Existe una condición de carrera si se lanzan hilos usando directamente las
 172   llamadas al sistema operativo, es decir si no se lanzan a través del soporte
 173   de hilos de D_, si el hilo lanzado utiliza archivos con *buffer* de
 174   C (``FILE*``). Esto se debe a la siguiente porción de código (introducida por
 175   el marcado concurrente)::
 176
 177      function collect() is
 178         stop_the_world()
 179         fflush(null) //    <-------------------------
 180         child_pid = fork()
 181         if child_pid is 0
 182            mark_phase()
 183            exit(0)
 184         // proceso padre
 185         start_the_world()
 186         wait(child_pid)
 187         sweep()
 188
 189   La llamada a :manpage:`fflush(3)` es necesaria para evitar que los archivos
 190   con *buffer* escriban su contenido dos veces al dispositivo, ya que la llamada
 191   a :manpage:`fork(2)` duplica el *buffer*, y si bien el archivo no se usa en el
 192   proceso con la fase de marcado, la biblioteca estándar de C escribe todos los
 193   *buffers* pendientes al terminar el proceso. Esto funciona para los hilos
 194   registrados por D_ gracias a que :manpage:`fflush(3)` se llama cuando todos
 195   los hilos están pausados, si no un hilo podría escribir al *buffer* justo
 196   después de llamar a :manpage:`fflush(3)` pero antes de llamar
 197   a :manpage:`fflush(2)`. Es por esto que si hay hilos no registrados por D_ que
 198   utilicen manejo de archivos con *buffer* de C, esta condición sí se puede dar
 199   y se pueden observar contenidos duplicados en dichos archivos.
 200
 201   Esta condición de carrera no tiene una solución simple, pero es de esperarse
 202   que no sea un problema real dado que no es un escenario común. Sin embargo
 203   eventualmente debería analizarse alguna solución más robusta.
 204
 205 * Soporte de referencias débiles.
 206
 207   Tango_ 0.99.9 incluye soporte de referencias débiles. Si bien se incorporó
 208   el código para manejar las referencias débiles, se espera que no funcione
 209   correctamente con CDGC (no se ha podido comprobar por la falta de programas
 210   de prueba que lo utilicen). La razón es que el soporte de referencias
 211   débiles de Tango_ 0.99.9 se basa en la premisa de que la fase de marcado
 212   corre con todos los hilos pausados, sin embargo al utilizar marcado
 213   concurrente, esto no es más cierto. Parecen haber soluciones viables a este
 214   problema pero no se han analizado en profundidad aún.
 215
 216 * Pérdida de rendimiento con respecto al recolector original.
 217
 218   Se ha observado también que, al no utilizar algunas optimizaciones de CDGC
 219   (como la mejora del factor de ocupación del *heap*), éste puede tener un
 220   rendimiento bastante menor a TBGC. Si bien no se ha investigado en
 221   profundidad las causas de esta pérdida de rendimiento, se han identificado
 222   algunos factores que podrían ser determinantes.
 223
 224   Por un lado, se ha observado que la mayor parte del tiempo extra que utiliza
 225   CDGC proviene de la fase de marcado, en particular de los cambios
 226   introducidos por el marcado preciso. Si bien se puede desactivar el marcado
 227   preciso, la lógico en tiempo de ejecución no cambia, por lo que se paga el
 228   precio sin obtener los beneficios. Queda pendiente analizar en más detalle
 229   las causas de esto y posibles optimizaciones para subsanarlo.
 230
 231   .. ftable:: t:con-staticsize
 232
 233      Aumento del tamaño de la memoria estática (bytes).
 234
 235      ======== ======== ======== =========== ===========
 236      Programa TBGC     CDGC     CDGC-TBGC   CDGC/TBGC
 237      ======== ======== ======== =========== ===========
 238      bh       22208    27604    5396        1.243
 239      bigarr   18820    24212    5392        1.287
 240      bisort   19836    25232    5396        1.272
 241      conalloc 25816    31208    5392        1.209
 242      concpu   25816    31208    5392        1.209
 243      dil      416900   422300   5400        1.013
 244      em3d     20988    26380    5392        1.257
 245      mcore    18564    23988    5424        1.292
 246      rnddata  188940   194332   5392        1.029
 247      sbtree   22196    27588    5392        1.243
 248      split    24312    29736    5424        1.223
 249      tree     18660    24084    5424        1.291
 250      tsp      20772    26168    5396        1.260
 251      voronoi  21184    26580    5396        1.255
 252      ======== ======== ======== =========== ===========
 253
 254   Además se ha observado un crecimiento importante en el tamaño del área de
 255   memoria estática del programa. En el cuadro :vref:`t:con-staticsize` se
 256   puede observar dicho crecimiento para cada uno de los programas del banco de
 257   pruebas. Esto se debe a que el recolector original está escrito de una forma
 258   muy primitiva, usando muy pocos tipos de datos definidos por el usuario,
 259   mientras que CDGC utiliza varias más, incluyendo algunos parametrizados. D_
 260   guarda la información de tipos en el área de memoria estática y se genera
 261   mucha información por cada tipo. Además no separa el área de memoria
 262   estática que debe ser utilizada como parte del *root set* de la que no (no
 263   hay necesidad de que la información de tipos sea parte del *root set*). Esto
 264   causa que por cada recolección, se tenga que visitar bastante más memoria y,
 265   lo que es probablemente peor, que aumente la probabilidad de encontrar
 266   *falsos punteros*, dado que este área de memoria se marca siempre de forma
 267   conservativa.
 268
 269   Finalmente, en el cuadro :vref:`t:con-binsize` también se puede observar un
 270   incremento en el tamaño del binario, lo que puede ser otra causa de la
 271   pérdida de rendimiento, dado que puede afectar a la localidad de referencia
 272   del caché, por ejemplo.
 273
 274   .. ftable:: t:con-binsize
 275
 276      Aumento del tamaño del binario (bytes).
 277
 278      ======== ======== ======== =========== ===========
 279      Programa TBGC     CDGC     CDGC-TBGC   CDGC/TBGC
 280      ======== ======== ======== =========== ===========
 281      bh       138060   159884   21824       1.158
 282      bigarr   192004   213832   21828       1.114
 283      bisort   115164   136988   21824       1.190
 284      conalloc 149848   171676   21828       1.146
 285      concpu   149848   171676   21828       1.146
 286      dil      1859208  1881028  21820       1.012
 287      em3d     116324   142248   25924       1.223
 288      mcore    105748   127576   21828       1.206
 289      rnddata  1492588  1518512  25924       1.017
 290      sbtree   129860   155784   25924       1.200
 291      split    144308   166136   21828       1.151
 292      tree     105844   127672   21828       1.206
 293      tsp      128412   150236   21824       1.170
 294      voronoi  141112   162936   21824       1.155
 295      ======== ======== ======== =========== ===========
 296
 297
 298 Trabajos relacionados
 299 ----------------------------------------------------------------------------
 300
 301 Dado que D_ no está muy difundido en ámbitos académicos, la cantidad de
 302 trabajos relacionados es muy pequeña, sin embargo los hay, y a continuación se
 303 describen.
 304
 305 * Diamond [PAN09]_:
 306   http://thecybershadow.net/d/Memory_Management_in_the_D_Programming_Language.pdf
 307
 308
 309 Trabajos futuros
 310 ----------------------------------------------------------------------------
 311
 312 TODO
 313
 314 * Cambiar el layout de memoria (mostrar lo encontrado en el post). Se podría
 315   usar un tamaño de bloque por cada tipo de dato (y por lo tanto una lista de
 316   libres por cada tipo de dato). Esto podría ahorrar muchos bits (mark,
 317   freebits, scan, etc.), el puntero al pointer mask se guardaría una sola vez,
 318   no hay ningún desperdicio de espacio salvo algún padding, pero podrían haber
 319   esquemas donde ni siquiera (si siempre se alocan tantas páginas como sean
 320   necesarias para evitar el padding para un tamaño de bloque). Un tipo de dato
 321   NO_SCAN no alocaría directamente bits de noscan, mark y scan. Se podría
 322   tratar de forma especial a strings.
 323 * Lazy sweeping.
 324 * Concurrent sweeping (lanzar fase de sweep en un thread que no pertenezca al
 325   mutator).
 326 * Continuous collection (lanzar un thread que esté haciendo fullcollect() en
 327   un loop). Lo bueno es que el sweep podría correr en ese thread, bajando aún
 328   más el tiempo máximo de pausa (aunque esto se puede hacer más allá de hacer
 329   continuous collection, ver "concurrent sweeping"), lo malo es que tal vez se
 330   estaría recolectando demasiado sin ninguna ganancia substancial.
 331 * Hacer preciso el static data por el tema de los TypeInfo's que ocupan mucha
 332   memoria que debe ser escaneada.
 333 * Tratar de remover el *lock* global.
 334 * Implementar un recolector con movimiento.
 335
 336
 337 .. include:: links.rst
 338
 339 .. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :