Actualizar estado de PHP 5.3.0

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

diff --git a/source/conclusion.rst b/source/conclusion.rst
index 49cd15a871900ffc6aa34e3fe0ca85de8458338f..945513dbf58dad4bcb0bd93b23f92527b5a43486 100644 (file)
--- a/source/conclusion.rst
+++ b/source/conclusion.rst
@@ -2,7 +2,7 @@
 .. 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

 
 
 .. _conclusion:
 
 
 .. _conclusion:


@@ -10,16 +10,299 @@
 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:
+* Diamond [PAN09]_:

   http://thecybershadow.net/d/Memory_Management_in_the_D_Programming_Language.pdf
 
 
   http://thecybershadow.net/d/Memory_Management_in_the_D_Programming_Language.pdf
 
 


@@ -45,12 +328,12 @@ TODO
   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.
   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.

-* Medir mejor cuando lanzar una recolección cuando se usa early collection
-  (por ejemplo medir la tasa de alocación y el tiempo de recolección y así
-  hallar el momento ideal para lanzar la recolección).
-* Emprolijar todavía más el código (o reescribirlo).

 * Hacer preciso el static data por el tema de los TypeInfo's que ocupan mucha
   memoria que debe ser escaneada.
 * 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 :