From: Leandro Lucarella <llucax@gmail.com>
Date: Sat, 20 Jun 2009 01:30:28 +0000 (-0300)
Subject: Agregar subsección Características destacadas en DGC
X-Git-Tag: entrega-2010-10-08~39
X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/commitdiff_plain/8467f5df997cd28332cbd57ad5917b6bfb287365

Agregar subsección Características destacadas en DGC
---

diff --git a/source/dgc.rst b/source/dgc.rst
index 44b31d0..a457444 100644
--- a/source/dgc.rst
+++ b/source/dgc.rst
@@ -1368,7 +1368,73 @@ asignación de memoria.
 
 
 
-.. _dgc_problems:
+.. _dgc_good:
+
+Características destacadas
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Si bien el recolector en términos generales no se aleja mucho de un
+:ref:`marcado y barrido clásico <gc_mark_sweep>`, tiene algunas mejoras por
+sobre el algoritmo más básicos que vale la pena destacar:
+
+
+Organización del *heap*
+^^^^^^^^^^^^^^^^^^^^^^^
+El *heap* está organizado de una forma que, si bien no emplea las técnicas más
+modernas que pueden observarse en el estado del arte (como :ref:`regiones
+<gc_free_list>`), es relativamente sofisticada. El esquema de *pools*
+y bloques permite disminuir considerablemente los problemas de *fragmentación*
+de memoria y evita búsquedas de *huecos* que pueden ser costosas (como
+*best-fit* [#dgcbestfit]_) o desperdiciar mucho especio (como *first-fit*
+[#dgcfirstfit]_), logrando un buen equilibrio entre velocidad y espacio
+desperdiciado.
+
+.. [#dgcbestfit] Las búsquedas de tipo *best-fit* son aquellas donde se busca
+   el *hueco* en el *heap* (es decir, una región contínua de memoria
+   libre) que mejor se ajuste al tamaño del objeto a asignar. Es decir, el
+   *hueco* más pequeño lo suficientemente grande como para almacenarlo.
+
+.. [#dgcfirstfit] Las búsquedas de tipo *first-fit* son aquellas donde se busca
+   el primer *hueco* en el *heap* (es decir, una región contínua de memoria
+   libre) que sea lo suficientemente grande como para almacenar el objeto
+   a asignar.
+
+
+Fase de marcado iterativa
+^^^^^^^^^^^^^^^^^^^^^^^^^
+A diferencia del algoritmo clásico recursivo, el algoritmo del recolector
+actual es iterativo. El algoritmo recursivo tiene un problema fundamental: se
+puede llegar a un desbordamiento de pila (o *stack overflow*). La cantidad de
+recursiones necesarias es, en el peor caso, :math:`O(|Live \thickspace set|)`
+(por ejemplo, si todas las celdas del *heap* formaran una lista simplemente
+enlazada). Hay muchas técnicas para lidiar con este problema, algunas que
+podrían aplicarse a D_ y otras que no (como *pointer reversal*) [JOLI96]_. El
+recolector actual, sin embargo, cambia complejidad en espacio por complejidad
+en tiempo, utilizando un algoritmo iterativo que es constante (:math:`O(1)`)
+en espacio, pero que requiere varias pasada sobre el *heap* en vez de una (la
+cantidad de pasadas es en el peor caso, al igual que la cantidad de
+recursiones del algoritmo recursivo, :math:`O(|Live \thickspace set|)`, pero
+cada pasada se realiza por sobre todo el *heap*).
+
+
+Conjuntos de bits para indicadores
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+El algoritmo cláscio propone almacenar en la propia celda la marca (para la
+fase de marcado) y otros indicadores. El algoritmo del recolector actual
+utiliza conjuntos de bits. Esto trae dos ventajas principales:
+
+* Permite minimizar el espacio requerido, ya que de otra forma en general se
+  desperdicia una palabra entera como cabecera de celda para guardar este tipo
+  de información.
+
+* Mejora la localidad de referencia, ya que los indicadores se escriben de
+  forma muy compacta y en una región de memoria contígua que generalmente
+  puede entrar en el cache o en pocas páginas de memoria acelerando
+  considerablemente la fase de marcado.
+
+
+
+.. _dgc_bad:
 
 Problemas y limitaciones
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
@@ -1617,18 +1683,20 @@ Listas de libres:
   sin embargo solo tienen sentido los bloques de tamaño ``B_16`` a ``B_2048``,
   por lo que 4 de esas listas no se utilizan.
 
-Conjuntos de bits:
+Conjuntos de bits para indicadores:
   los indicadores para la fase de marcado y otras propiedades de un bloque son
   almacenados en conjuntos de bits que almacenan los indicadores de todos los
-  bloques de un *pool*. Como un *pool* tiene páginas con distintos tamaños de
-  bloque, se reserva una cantidad de bits igual a la mayor cantidad posible de
-  bloques que puede haber en el *pool*; es decir, se reserva 1 bit por cada 16
-  bytes del *pool*. Para un *pool* de 1 MiB (tamaño mínimo), teniendo en
-  cuenta que se utilizan 5 conjuntos de bits (``mark``, ``scan``, ``finals``,
-  ``freebits`` y ``noscan``), se utilizan 40 KiB de memoria para conjuntos de
-  bits (un 4% de *desperdicio* si, por ejemplo, ese *pool* estuviera destinado
-  por completo a albergar un solo objeto grande; lo que equivaldría al 2560
-  objetos de 16 bytes desperdiciados en bits inutilizados).
+  bloques de un *pool*. Si bien se ha mencionado esto como una ventaja, hay
+  lugar todavía como para algunas mejoras. Como un *pool* tiene páginas con
+  distintos tamaños de bloque, se reserva una cantidad de bits igual a la
+  mayor cantidad posible de bloques que puede haber en el *pool*; es decir, se
+  reserva 1 bit por cada 16 bytes del *pool*. Para un *pool* de 1 MiB (tamaño
+  mínimo), teniendo en cuenta que se utilizan 5 conjuntos de bits (``mark``,
+  ``scan``, ``finals``, ``freebits`` y ``noscan``), se utilizan 40 KiB de
+  memoria para conjuntos de bits (un 4% de *desperdicio* si, por ejemplo, ese
+  *pool* estuviera destinado por completo a albergar un solo objeto grande; lo
+  que equivaldría al 2560 objetos de 16 bytes desperdiciados en bits
+  inutilizados).
 
 Repetición de código:
    Hay algunos fragmentos de código repetidos inecesariamente. Por ejemplo en
@@ -1644,6 +1712,12 @@ Uso de señales:
    señales en sus programas (o peor aún, si interactúan con bibliotecas
    de C que hacen uso de estas señales) [NGD5821]_.
 
+Marcado iterativo:
+   si bien esto se mencionó como algo bueno del recolector actual, es un
+   compromiso entre tiempo y espacio, y puede ser interesante analizar otros
+   métodos para evitar la recursión que no requieran tantas pasadas sobre el
+   *heap*.
+
 
 .. include:: links.rst