Eliminar texto comentado que no se va a usar

[z.facultad/75.00/informe.git] / source / conclusion.rst

diff --git a/source/conclusion.rst b/source/conclusion.rst
index f25361c2c3b3b0777d84d83b186162dd7eb8bb3d..945513dbf58dad4bcb0bd93b23f92527b5a43486 100644 (file)
--- a/source/conclusion.rst
+++ b/source/conclusion.rst
@@ -2,23 +2,308 @@
 .. Se presentan las conclusiones del trabajo, comparando los resultados
    obtenidos con el punto de partida. Se mencionan puntos pendientes o
    nuevas líneas de investigación.
 .. Se presentan las conclusiones del trabajo, comparando los resultados
    obtenidos con el punto de partida. Se mencionan puntos pendientes o
    nuevas líneas de investigación.

-   ESTADO: SIN EMPEZAR
+   ESTADO: EMPEZADO

 
 
 
 

-.. _ref_conclusion:
+.. _conclusion:

 
 Conclusión
 ============================================================================
 
 
 Conclusión
 ============================================================================
 

-TODO
+Durante el desarrollo de este trabajo se introdujo al lenguaje de programación
+D_ y a los conceptos básicos de recolección de basura. Luego se analizó el
+recolector de basura actual y se señalaron sus principales falencias,
+proponiendo un conjunto de modificaciones con el objeto de subsanarlas.
+Para evaluar los resultados de las modificaciones se construyó un banco de
+pruebas variado para poder analizar tanto aspectos particulares como el
+funcionamiento de programas reales; y se establecieron métricas para
+cuantificar dichos resultados.
+
+El objetivo principal fue bajar la latencia del recolector, es decir el tiempo
+máximo de pausa real, y se pudo comprobar que, salvo en casos muy
+particulares, esto fue conseguido de manera contundente (con tiempos de pausa
+hasta 200 veces menores que el recolector original de D_). La inclusión del
+marcado concurrente demostró ser una aproximación correcta al problema.
+
+La aceptación de la solución por parte de la comunidad también ha sido un
+objetivo importante de este trabajo, y si bien en este sentido sigue siendo un
+trabajo en curso, la recepción ha sido ampliamente positiva por parte de la
+comunidad y se espera que el resultado de este trabajo sea incorporado en el
+corto plazo tanto a `D 1.0`_ a través de Tango_, como a `D 2.0`_.
+
+Además de los objetivos principales se cumplieron otros objetivos anexos, pero
+no por eso menos importantes. Para la aplicación real el tiempo total de
+ejecución se ha reducido hasta casi una tercera parte, y para otras
+aplicaciones pequeñas se ha reducido más de 17 veces. Estos resultados han
+sido particularmente sorprendentes, siendo que la reducción del tiempo total
+de ejecución no ha sido parte del objetivo principal y no se habían encontrado
+referencias en la bibliografía de casos similares (por el contrario, en
+general la baja de la latencia suele estar acompañada de una suba en el tiempo
+total de ejecución).
+
+Se ha podido experimentar además con el marcado preciso, otro de los problemas
+del recolector más presentes en la comunidad. Los resultados obtenidos son
+variados, encontrando casos donde se consigue una mejoría notoria y otros en
+donde la forma de almacenar la información de tipos produce resultados poco
+satisfactorios.
+
+La mayor flexibilidad del recolector al ser configurable también ha demostrado
+ser útil. Por un lado para este mismo trabajo, al permitir realizar mediciones
+sobre el mismo binario utilizando diferentes configuraciones. Por otro, la
+amplia gama de resultados dispares obtenidos son una buena muestra de que no
+existen *balas de plata*, y cada programa tiene necesidades particulares en
+cuanto a recolección de basura. Por lo tanto, distintos programas pueden verse
+beneficiados o perjudicados por diferentes configuraciones. Esto hace que la
+posibilidad de configurar el recolector en tiempo de inicialización sea
+particularmente ventajoso.
+
+Finalmente, algunas optimizaciones muy pequeñas demostraron ser también muy
+valiosas para algunos casos particulares, logrando reducciones en el tiempo
+total de ejecución de hasta 5 veces.
+
+
+
+Puntos pendientes, problemas y limitaciones
+----------------------------------------------------------------------------
+
+Si bien los objetivos de este trabajo han sido alcanzados con éxito, hay
+varias pequeñas mejoras que han quedado pendientes y algunos problemas
+y limitaciones conocidas. A continuación se describe cada una de ellos.
+
+* Emisión de mensajes informativos para depuración.
+
+  Entre las herramientas de depuración que provee el recolector, no se ha
+  mencionado la posibilidad de emitir opcionalmente mensajes informativos para
+  ayudar a depurar tanto problemas en el recolector como en el programa que lo
+  usa. El recolector actual tiene esa posibilidad pero es elegible en tiempo de
+  compilación. En este trabajo se agregaron las opciones en tiempo de
+  inicialización ``log_file`` y ``verbose`` con el propósito de poder elegir un
+  archivo en donde guardar los mensajes informativos y el nivel de detalle de
+  dichos mensajes respectivamente, pero finalmente nunca se implementaron.
+
+* Predicción para estimar cuando lanzar una recolección temprana.
+
+  Las recolecciones se lanzan de manera temprana según la opción ``min_free``.
+  Una mejor aproximación podría ser predecir cuando se va a agotar la memoria
+  libre de forma adaptativa, calculando la tasa de asignación de memoria
+  y el tiempo total que tomó la recolección. Esta estimación se podría mejorar
+  guardando un historial de que tan acertada fue para recolecciones pasadas. La
+  predicción ideal debería ser capaz de:
+
+  * Evitar tiempos de pausa (es decir, que la recolección temprana termine antes
+    de que se agote la memoria libre).
+  * No realizar recolecciones innecesarias (es decir, no lanzar recolecciones
+    tempranas si el programa no está pidiendo memoria a una tasa suficientemente
+    alta).
+
+* Explosión del uso de memoria con creación ansiosa de *pools*.
+
+  Se ha observado que en situaciones muy particulares, al usar creación
+  ansiosa de *pools* (o *eager allocation*), el uso de memoria crece
+  desmesuradamente. Si bien este efecto se ve principalmente en las pruebas
+  sintetizadas con tal fin, algunos programas reales lo sufren también, pero
+  en general se puede atenuar utilizando también *early collection*.
+  Recordemos además, que lo analizado es el consumo **máximo** de memoria, por
+  lo que una ráfaga de pedidos de memoria podría crear un pico, pero durante
+  la mayor parte del transcurso del programa el consumo de memoria podría ser
+  mucho menor. Queda pendiente analizar los casos puntuales con alguna métrica
+  más detallada sobre el progreso del uso de memoria.
+
+  También queda pendiente buscar alguna estimación de cuándo es conveniente
+  utilizar *eager allocation* de forma adaptativa, dado que en general se ve
+  que cuando explota el consumo de memoria, también explota el tiempo de
+  pausa, lo que quita gran parte del sentido de usar *eager allocation* en
+  primer lugar. Estimando de alguna manera cuanto va a crecer el tiempo de
+  pausa debido a esta opción, se podría desactivar temporalmente cuando no
+  haya ganancia en el tiempo de pausa para evitar esta explosión ante ráfagas
+  de pedidos de memoria.
+
+* Reestructuración y limpieza del código.
+
+  Si bien se han hecho muchas mejoras a nivel de estructura y limpieza de
+  código, ha quedado mucho pendiente. Todavía hay bastante repetición en el
+  código y se mantiene la arquitectura básica del recolector.
+
+* Experimentación con la llamada al sistema :manpage:`clone(2)`.
+
+  Linux_ implementa la llamada al sistema :manpage:`fork(2)` a través de otra de
+  más bajo nivel llamada :manpage:`clone(2)`. :manpage:`clone(2)` permite una
+  granularidad a la hora de indicar que partes del proceso deben ser copiadas al
+  hijo y cuales deben ser compartidas mucho mayor que :manpage:`fork(2)`. Por
+  ejemplo, se puede compartir toda la memoria del proceso, siendo este el
+  mecanismo por el cual Linux_ implementa los hilos. Para este trabajo podría
+  ser beneficioso usar :manpage:`clone(2)` para evitar copiar otro tipo de
+  estructuras dado que el proceso
+  hijo, al correr solo la fase de marcado, nunca va a interferir el *mutator*.
+  Se podría experimentar no copiando las siguientes estructuras, por ejemplo:
+
+  ``CLONE_FILES``
+     Tabla de descriptores de archivo.

 
 

+  ``CLONE_FS``
+     Tabla de sistemas de archivo montados.
+
+  ``CLONE_IO``
+     Contextos de entrada/salida.
+
+  ``CLONE_SIGHAND``
+     Tabla de manejadores de señales.
+
+* Uso de memoria compartida.
+
+  Al realizar marcado concurrente, si el *mutator* usa memoria compartida entre
+  procesos que almacene punteros al *heap* podría haber problemas, dado que la
+  fase de barrido no estaría trabajando con una *fotografía* de la memoria. El
+  grafo de conectividad podría efectivamente cambiar mientras se corre la fase
+  de barrido y por lo tanto el algoritmo deja de ser correcto, existiendo la
+  posibilidad de que se reciclen celdas *vivas*.
+
+  Dado que el usuario debe registrar cualquier puntero que no sea parte de la
+  memoria estática, *stack* o *heap* del recolector como parte del *root set*,
+  se podría agregar un parámetro extra a la función de registro que indique si
+  los punteros agregados residen en memoria compartida. De este modo, al momento
+  de hacer el :manpage:`fork(2)`, el recolector debería realizar una copia de
+  esos punteros mientras todos los hilos están pausados para obtener
+  efectivamente una *fotografía* estable del *root set*.
+
+* Condición de carrera al utilizar :manpage:`fork(2)`.
+
+  Existe una condición de carrera si se lanzan hilos usando directamente las
+  llamadas al sistema operativo, es decir si no se lanzan a través del soporte
+  de hilos de D_, si el hilo lanzado utiliza archivos con *buffer* de
+  C (``FILE*``). Esto se debe a la siguiente porción de código (introducida por
+  el marcado concurrente)::
+
+     function collect() is
+        stop_the_world()
+        fflush(null) //    <-------------------------
+        child_pid = fork()
+        if child_pid is 0
+           mark_phase()
+           exit(0)
+        // proceso padre
+        start_the_world()
+        wait(child_pid)
+        sweep()
+
+  La llamada a :manpage:`fflush(3)` es necesaria para evitar que los archivos
+  con *buffer* escriban su contenido dos veces al dispositivo, ya que la llamada
+  a :manpage:`fork(2)` duplica el *buffer*, y si bien el archivo no se usa en el
+  proceso con la fase de marcado, la biblioteca estándar de C escribe todos los
+  *buffers* pendientes al terminar el proceso. Esto funciona para los hilos
+  registrados por D_ gracias a que :manpage:`fflush(3)` se llama cuando todos
+  los hilos están pausados, si no un hilo podría escribir al *buffer* justo
+  después de llamar a :manpage:`fflush(3)` pero antes de llamar
+  a :manpage:`fflush(2)`. Es por esto que si hay hilos no registrados por D_ que
+  utilicen manejo de archivos con *buffer* de C, esta condición sí se puede dar
+  y se pueden observar contenidos duplicados en dichos archivos.
+
+  Esta condición de carrera no tiene una solución simple, pero es de esperarse
+  que no sea un problema real dado que no es un escenario común. Sin embargo
+  eventualmente debería analizarse alguna solución más robusta.
+
+* Soporte de referencias débiles.
+
+  Tango_ 0.99.9 incluye soporte de referencias débiles. Si bien se incorporó
+  el código para manejar las referencias débiles, se espera que no funcione
+  correctamente con CDGC (no se ha podido comprobar por la falta de programas
+  de prueba que lo utilicen). La razón es que el soporte de referencias
+  débiles de Tango_ 0.99.9 se basa en la premisa de que la fase de marcado
+  corre con todos los hilos pausados, sin embargo al utilizar marcado
+  concurrente, esto no es más cierto. Parecen haber soluciones viables a este
+  problema pero no se han analizado en profundidad aún.
+
+* Pérdida de rendimiento con respecto al recolector original.
+
+  Se ha observado también que, al no utilizar algunas optimizaciones de CDGC
+  (como la mejora del factor de ocupación del *heap*), éste puede tener un
+  rendimiento bastante menor a TBGC. Si bien no se ha investigado en
+  profundidad las causas de esta pérdida de rendimiento, se han identificado
+  algunos factores que podrían ser determinantes.
+
+  Por un lado, se ha observado que la mayor parte del tiempo extra que utiliza
+  CDGC proviene de la fase de marcado, en particular de los cambios
+  introducidos por el marcado preciso. Si bien se puede desactivar el marcado
+  preciso, la lógico en tiempo de ejecución no cambia, por lo que se paga el
+  precio sin obtener los beneficios. Queda pendiente analizar en más detalle
+  las causas de esto y posibles optimizaciones para subsanarlo.
+
+  .. ftable:: t:con-staticsize
+
+     Aumento del tamaño de la memoria estática (bytes).
+
+     ======== ======== ======== =========== ===========
+     Programa TBGC     CDGC     CDGC-TBGC   CDGC/TBGC
+     ======== ======== ======== =========== ===========
+     bh       22208    27604    5396        1.243
+     bigarr   18820    24212    5392        1.287
+     bisort   19836    25232    5396        1.272
+     conalloc 25816    31208    5392        1.209
+     concpu   25816    31208    5392        1.209
+     dil      416900   422300   5400        1.013
+     em3d     20988    26380    5392        1.257
+     mcore    18564    23988    5424        1.292
+     rnddata  188940   194332   5392        1.029
+     sbtree   22196    27588    5392        1.243
+     split    24312    29736    5424        1.223
+     tree     18660    24084    5424        1.291
+     tsp      20772    26168    5396        1.260
+     voronoi  21184    26580    5396        1.255
+     ======== ======== ======== =========== ===========
+
+  Además se ha observado un crecimiento importante en el tamaño del área de
+  memoria estática del programa. En el cuadro :vref:`t:con-staticsize` se
+  puede observar dicho crecimiento para cada uno de los programas del banco de
+  pruebas. Esto se debe a que el recolector original está escrito de una forma
+  muy primitiva, usando muy pocos tipos de datos definidos por el usuario,
+  mientras que CDGC utiliza varias más, incluyendo algunos parametrizados. D_
+  guarda la información de tipos en el área de memoria estática y se genera
+  mucha información por cada tipo. Además no separa el área de memoria
+  estática que debe ser utilizada como parte del *root set* de la que no (no
+  hay necesidad de que la información de tipos sea parte del *root set*). Esto
+  causa que por cada recolección, se tenga que visitar bastante más memoria y,
+  lo que es probablemente peor, que aumente la probabilidad de encontrar
+  *falsos punteros*, dado que este área de memoria se marca siempre de forma
+  conservativa.
+
+  Finalmente, en el cuadro :vref:`t:con-binsize` también se puede observar un
+  incremento en el tamaño del binario, lo que puede ser otra causa de la
+  pérdida de rendimiento, dado que puede afectar a la localidad de referencia
+  del caché, por ejemplo.
+
+  .. ftable:: t:con-binsize
+
+     Aumento del tamaño del binario (bytes).
+
+     ======== ======== ======== =========== ===========
+     Programa TBGC     CDGC     CDGC-TBGC   CDGC/TBGC
+     ======== ======== ======== =========== ===========
+     bh       138060   159884   21824       1.158
+     bigarr   192004   213832   21828       1.114
+     bisort   115164   136988   21824       1.190
+     conalloc 149848   171676   21828       1.146
+     concpu   149848   171676   21828       1.146
+     dil      1859208  1881028  21820       1.012
+     em3d     116324   142248   25924       1.223
+     mcore    105748   127576   21828       1.206
+     rnddata  1492588  1518512  25924       1.017
+     sbtree   129860   155784   25924       1.200
+     split    144308   166136   21828       1.151
+     tree     105844   127672   21828       1.206
+     tsp      128412   150236   21824       1.170
+     voronoi  141112   162936   21824       1.155
+     ======== ======== ======== =========== ===========

 
 
 Trabajos relacionados
 ----------------------------------------------------------------------------
 
 
 
 Trabajos relacionados
 ----------------------------------------------------------------------------
 

-TODO
+Dado que D_ no está muy difundido en ámbitos académicos, la cantidad de
+trabajos relacionados es muy pequeña, sin embargo los hay, y a continuación se
+describen.

 
 

+* Diamond [PAN09]_:
+  http://thecybershadow.net/d/Memory_Management_in_the_D_Programming_Language.pdf

 
 
 Trabajos futuros
 
 
 Trabajos futuros


@@ -26,6 +311,29 @@ Trabajos futuros
 
 TODO
 
 
 TODO
 

+* Cambiar el layout de memoria (mostrar lo encontrado en el post). Se podría
+  usar un tamaño de bloque por cada tipo de dato (y por lo tanto una lista de
+  libres por cada tipo de dato). Esto podría ahorrar muchos bits (mark,
+  freebits, scan, etc.), el puntero al pointer mask se guardaría una sola vez,
+  no hay ningún desperdicio de espacio salvo algún padding, pero podrían haber
+  esquemas donde ni siquiera (si siempre se alocan tantas páginas como sean
+  necesarias para evitar el padding para un tamaño de bloque). Un tipo de dato
+  NO_SCAN no alocaría directamente bits de noscan, mark y scan. Se podría
+  tratar de forma especial a strings.
+* Lazy sweeping.
+* Concurrent sweeping (lanzar fase de sweep en un thread que no pertenezca al
+  mutator).
+* Continuous collection (lanzar un thread que esté haciendo fullcollect() en
+  un loop). Lo bueno es que el sweep podría correr en ese thread, bajando aún
+  más el tiempo máximo de pausa (aunque esto se puede hacer más allá de hacer
+  continuous collection, ver "concurrent sweeping"), lo malo es que tal vez se
+  estaría recolectando demasiado sin ninguna ganancia substancial.
+* Hacer preciso el static data por el tema de los TypeInfo's que ocupan mucha
+  memoria que debe ser escaneada.
+* Tratar de remover el *lock* global.
+* Implementar un recolector con movimiento.
+

 
 

+.. include:: links.rst

 
 

-.. vim: set ts=3 sts=3 sw=3 et tw=78 :
+.. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :