X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/d325ba11aa45fb60fab88b72b37e129115caf95a..6c0df59:/source/conclusion.rst?ds=sidebyside

diff --git a/source/conclusion.rst b/source/conclusion.rst
index 945513d..7df0af3 100644
--- 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.
-   ESTADO: EMPEZADO
+   ESTADO: TERMINADO
 
 
 .. _conclusion:
@@ -63,6 +63,8 @@ total de ejecución de hasta 5 veces.
 
 
 
+.. _con_pending:
+
 Puntos pendientes, problemas y limitaciones
 ----------------------------------------------------------------------------
 
@@ -298,40 +300,148 @@ y limitaciones conocidas. A continuación se describe cada una de ellos.
 Trabajos relacionados
 ----------------------------------------------------------------------------
 
-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.
+Dado que D_ no ha penetrado en ámbitos académicos, se ha encontrado un solo
+trabajo de investigación relacionado. Sin embargo se ha encontrado otro
+trabajo que si bien no es formal, ha sido de mucha importancia para el
+desarrollo de este trabajo.
+
+A continuación se describen ambos.
+
+* *Memory Management in the D Programming Language* [PAN09]_.
+
+  Tesis de licenciatura de Vladimir Panteleev cuya resumen traducido es el
+  siguiente:
+
+      Este reporte describe el estudio de las técnicas de manejo automático de
+      memoria, su implementación en el lenguaje de programación D_, y el
+      trabajo para mejorar el estado del manejo de memoria.
+
+  Si bien plantea pequeñas optimizaciones para el recolector de basura
+  (algunas utilizadas en este trabajo), se centra principalmente en el
+  desarrollo de Diamond, una utilidad para depuración de manejo de memoria en
+  D_.
+
+* Integración de marcado preciso del *heap* al recolector de basura
+  [DBZ3463]_.
+
+  Ya citado varias veces en este trabajo, fue comenzado por David Simcha
+  y publicado en el sistema de seguimiento de fallas de D_ que se limita a una
+  implementación a nivel biblioteca de usuario y sobre `D 2.0`_. Vincent Lang
+  (mejor conocido como *wm4* en la comunidad de D_) da continuidad a este
+  trabajo pero modificando el compilador DMD_ y trabajando con `D 1.0`_
+  y Tango_.
+
+  El soporte de marcado preciso presentado en este trabajo se basa en las
+  modificaciones hechas al compilador DMD_ por Vincent Lang (que aún no fueron
+  integradas de forma oficial).
 
-* Diamond [PAN09]_:
-  http://thecybershadow.net/d/Memory_Management_in_the_D_Programming_Language.pdf
 
 
 Trabajos futuros
 ----------------------------------------------------------------------------
 
-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.
+En la sección :ref:`con_pending` se mencionan varios aspectos de este trabajo
+que podrían verse beneficiados por trabajos futuros, sin embargo se trata en
+general de pequeñas optimizaciones o mejoras de alcance muy limitado.
+
+A continuación se recopilan varios otros aspectos identificados durante el
+desarrollo del presente trabajo, pero que requieren un nivel de análisis
+y, potencialmente, de desarrollo mayor a los ya presentados en la sección
+mencionada.
+
+* Mejoras en la organización de memoria del recolector.
+
+  Si bien se ha mencionado en un principio la organización actual como un
+  aspecto positivo del recolector, varios resultados han demostrado
+  deficiencias importantes. El nivel de espacio desperdiciado por la división
+  de memoria en bloques puede ser muy significativa y la forma en la que se
+  almacena la información de tipos para el marcado preciso puede incluso
+  acentuarlo todavía más (como se demuestra en los resultados para ``bh``
+  y ``dil``).
+
+  Este problema no solo afecta al consumo de memoria, además genera un efecto
+  dominó por el incremento de la probabilidad de tener *falsos punteros*
+  y perjudica al tiempo total de ejecución por empeorar la localidad de
+  referencia del caché y por hacer que se prolongue la recolección de basura
+  por tener que marcar y barrer más memoria.
+
+  Una posible alternativa es tener una lista de libres por **tipo**, cuyo
+  tamaño de bloque sea exactamente igual al tamaño del tipo que almacena. La
+  información de tipo se almacenaría entonces solo una vez y no habría
+  desperdicio de memoria alguno dejando de lado un posible relleno para
+  completar una página. Este esquema debería tener algún tipo de guarda para
+  programas con una cantidad exuberante de tipos de datos.
+
+  También podría ser conveniente separar los bloques marcados como ``NO_SCAN``
+  de los que sí deben ser marcados, de manera que no necesite almacenar
+  directamente los bits de ``mark`` , ``scan`` y ``noscan``. También se podría
+  proponer algún área de memoria especial para almacenar cadenas de texto
+  (como un caso especial de lo anterior) por tener estas características muy
+  particular (largos muy variables, cambian de tamaño de forma relativamente
+  frecuente, etc.). Las posibilidades son enormes.
+
+* Mejoras en la fase de barrido.
+
+  En este trabajo todas las mejoras propuestas se encargaron de la fase de
+  marcado, pero mucho se pude mejorar en la fase de barrido también. Por un
+  lado se podría agregar barrido perezoso para disminuir aún más el tiempo de
+  pausa real. Se ha mostrado que en muchos casos los tiempos de pausa pueden
+  ser considerablemente altos debido a que la fase de barrido no se realiza en
+  paralelo como el marcado.
+
+  Otra forma de disminuir el tiempo de pausa real sería realizar un barrido
+  concurrente también. Esto no puede realizarse en otro proceso porque el
+  barrido es el encargado de ejecutar los *finalizadores*, pero sí se podría
+  barrer en otro hilo y, por ejemplo, seguir utilizando *eager allocation*
+  hasta que el barrido finalice.
+
+* Mejoras en la precisión del marcado.
+
+  Como se mencionó anteriormente, el área de memoria estática se marca de
+  forma conservativa dada la falta de información de tipos de ésta. Sin
+  embargo es bastante razonable pensar en que el compilador genere información
+  de tipos para el área de memoria estática o que al menos informe mejor al
+  recolector que partes deben ser consideradas parte del *root set* y cuales
+  no. Dado que la memoria estática crece de forma considerable con el
+  incremento de la cantidad de tipos definidos por el usuario, ya solo esa
+  división puede hacer una diferencia importante; en especial considerando
+  como aumenta la memoria estática solamente por usar más tipos de datos en el
+  recolector.
+
+  También podría explorarse el agregado de precisión al *stack* pero esto es
+  realmente muy complicado dado que la única solución que pareciera viable es
+  el uso de *shadow stack* [HEND02]_ que requiere un trabajo extra por cada
+  llamado a función, cosa que va en contra de la filosofía de D_ de pagar solo
+  por lo que se usa. Sin embargo podría explorarse agregar un esquema de ese
+  tipo como una opción del compilador, de forma que el usuario pueda decidir
+  si vale la pena para una aplicación particular o no.
+
+* Mejoras en la concurrencia.
+
+  El *lock* global del recolector es otro aspecto que demostró ser
+  problemático. Podrían analizarse formas de minimizar la necesidad de usar
+  *locks* o de hacerlo de forma más granular, de manera que algunas
+  operaciones del recolector puedan ser ejecutadas en paralelo. También se
+  podría experimentar con el uso de estructura de datos libres de *locks*
+  (*lock-free*).
+
+  Otra forma de minimizar la sincronización es utilizando *pools* por hilo, de
+  manera de poder alocar memoria de forma concurrente y hasta explorar la
+  posibilidad de efectuar recolecciones locales a un solo hilo; aunque esto
+  último probablemente sea equivalente a implementar un recolector de basura
+  con particiones (por ejemplo generacional).
+
+* Recolección con movimiento.
+
+  La información de tipos provista por el trabajo hecho por Vincent Lang
+  [DBZ3463]_ es suficientemente completa como para poder implementar un
+  recolector con movimiento. La efectividad de un recolector de estas
+  características en D_ está por comprobarse, dado que cualquier celda
+  apuntada por alguna palabra que debió ser marcada de forma conservativa debe
+  quedar inmóvil, por lo que gran parte del éxito de un recolector con
+  movimiento en D_ está supeditado a la proporción de celdas que queden
+  inmóviles. Sin embargo sea muy probablemente un área que valga la pena
+  explorar.
 
 
 .. include:: links.rst