From: Leandro Lucarella 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?ds=inline 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 `, 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 +`), 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