X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/15b868186b7ca1853b52a34ace0865f1cc24c677..af3cc91ddf531e9eb73f3dac73b15ab317a3cbb2:/source/solucion.rst

diff --git a/source/solucion.rst b/source/solucion.rst
index a1da636..32a94bd 100644
--- a/source/solucion.rst
+++ b/source/solucion.rst
@@ -1,6 +1,6 @@
 
 .. Acá va lo que decidí hacer en base al análisis anterior y sus razones.
-   ESTADO: SIN EMPEZAR
+   ESTADO: EMPEZADO
 
 
 .. _solucion:
@@ -8,44 +8,3337 @@
 Solución adoptada
 ============================================================================
 
-TODO
+Como hemos visto en :ref:`dgc_bad`, la mejora del recolector de basura puede
+ser abordada desde múltiples flancos. Por lo tanto, para reducir la cantidad
+de posibilidades hay que tener en cuenta uno de los principales objetivos de
+este trabajo: encontrar una solución que tenga una buena probabilidad de ser
+adoptada por el lenguaje, o alguno de sus compiladores al menos. Para asegurar
+esto, la solución debe tener un alto grado de aceptación en la comunidad, lo
+que implica algunos puntos claves:
 
+* La eficiencia general de la solución no debe ser notablemente peor, en
+  ningún aspecto, que la implementación actual.
+* Los cambios no deben ser drásticos.
+* La solución debe atacar de forma efectiva al menos uno de los problemas
+  principales del recolector actual.
 
+Bajo estos requerimientos, se concluye que probablemente el área más fértil
+para explorar sea la falta de concurrencia por cumplir todos estos puntos:
 
-Recolector naive de referencia
-----------------------------------------------------------------------------
+* Si bien hay evidencia en la literatura sobre el incremento del tiempo de
+  ejecución total de ejecución de un programa al usar algoritmos concurrentes,
+  éste no es, en general, muy grande comparativamente.
+* Existen algoritmos de recolección concurrente que no requieren ningún grado
+  de cooperación por parte del lenguaje o el compilador.
+* La falta de concurrencia y los largos tiempos de pausa es una de las
+  críticas más frecuentes al recolector actual por parte de la comunidad.
 
-TODO
+A pesar de ser la concurrencia la veta principal a explorar en este trabajo,
+se intenta abordar los demás problemas planteados siempre que sea posible
+hacerlo sin alejarse demasiado del objetivo principal.
 
 
+.. _sol_bench:
 
-Set de benchmarks y recolección de estadísticas
+Banco de pruebas
 ----------------------------------------------------------------------------
 
-TODO
+Teniendo en cuenta que uno de los objetivos principales es no empeorar la
+eficiencia general de forma notable, la confección de un banco de pruebas es
+un aspecto fundamental, para poder comprobar con cada cambio que la eficiencia
+final no se vea notablemente afectada.
 
+La confección de un banco de pruebas no es una tarea trivial, mucho menos para
+un lenguaje con el nivel de fragmentación que tuvo D_ (que hace que a fines
+prácticos hayan 3 versiones del lenguaje compitiendo), y cuya masa crítica de
+usuarios es de aficionados que usualmente abandonan los proyectos, quedando
+obsoletos rápidamente.
 
+Con el objetivo de confeccionar este banco de pruebas, desde el comienzo del
+trabajo se han recolectado (usando como fuente principalmente el grupo de
+noticias de D_ [#benchmod]_) programas triviales sintetizados con el único
+propósito de mostrar problemas con el recolector de basura. Otros programas de
+este estilo fueron escritos explícitamente para este trabajo.
 
-Reescritura del GC actual
-----------------------------------------------------------------------------
+Además se han recolectado [#benchmod]_ algunos pequeños programas portados de
+otros lenguajes de programación, que si bien son pequeños y tienen como
+objetivo ejercitar el recolector de basura, son programas reales que resuelven
+un problema concreto, lo que otorga un juego de pruebas un poco más amplio que
+los programas triviales.
 
-TODO
+.. [#benchmod] Cabe destacar que en general todos los programas recolectados
+   han sido modificados levemente para ajustarlos mejor a las necesidades del
+   banco de prueba (entre las modificaciones más frecuentes se encuentran la
+   conversión de Phobos_ a Tango_ y la eliminación de mensajes por salida
+   estándar).
 
+Pero probablemente lo más importante para confeccionar un banco de pruebas
+verdaderamente útil es disponer de programas reales, que hayan sido diseñados
+con el único objetivo de hacer su trabajo, sin pensar en como impacta el
+recolector sobre ellos (ni ellos sobre el recolector). Estos programas proveen
+las pruebas más realistas y amplias. Desgraciadamente no hay muchos programas
+reales escritos en D_ disponibles públicamente, y no se encontró en la
+comunidad tampoco una muestra de voluntad por compartir programas privados
+para usar como banco de pruebas en este trabajo.
 
+Por lo tanto el banco de pruebas que se conformó como una mezcla de estas tres
+grandes categorías.
 
-Conversión a "cloning GC"
-----------------------------------------------------------------------------
 
-TODO
+.. _sol_bench_synth:
 
+Pruebas sintetizadas
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
+Este es el juego de programas triviales, escritos con el único objetivo de
+ejercitar un área particular y acotada del recolector.
 
-Resultados
+
+``bigarr``
+^^^^^^^^^^
+Su objetivo es ejercitar la manipulación de arreglos de tamaño considerable
+que almacenan objetos de tamaño pequeño o mediano. Esta prueba fue hallada__
+en el grupo de noticias de D_ y escrita por Babele Dunnit y aunque
+originalmente fue concebido para mostrar un problema con la concatenación de
+arreglos (como se aprecia en la sentencia ``version(loseMemory)``), ejercita
+los aspectos más utilizados del del recolector: manipulación de arreglos
+y petición e memoria. Es una de las pruebas que más estresa al recolector ya
+que todo el trabajo que realiza el programa es utilizar servicios de éste.
+
+El código fuente del programa es el siguiente::
+
+   const IT = 300;
+   const N1 = 20_000;
+   const N2 = 40_000;
+
+   class Individual
+   {
+      Individual[20] children;
+   }
+
+   class Population
+   {
+      void grow()
+      {
+         foreach (inout individual; individuals)
+            individual = new Individual;
+      }
+      Individual[N1] individuals;
+   }
+
+   version = loseMemory;
+
+   int main(char[][] args)
+   {
+
+      Population testPop1 = new Population;
+      Population testPop2 = new Population;
+      Individual[N2] indi;
+      for (int i = 0; i < IT; i++) {
+         testPop1.grow();
+         testPop2.grow();
+         version (loseMemory) {
+            indi[] = testPop1.individuals ~ testPop2.individuals;
+         }
+         version (everythingOk) {
+            indi[0..N1] = testPop1.individuals;
+            indi[N1..N2] = testPop2.individuals;
+         }
+      }
+      return 0;
+   }
+
+__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=54084
+
+
+``concpu`` y ``conalloc``
+^^^^^^^^^^^^^^^^^^^^^^^^^
+Estos dos programas fueron escritos especialmente para este trabajo con el fin
+de ejercitar la interacción entre el recolector y un *mutator* con varios
+hilos. La única diferencia entre ellos es que ``concpu`` lanza hilos que hacen
+trabajar de forma intensiva el procesador pero que no utilizan servicios del
+recolector, salvo en el hilo principal, mientras que ``conalloc`` utiliza
+servicios del recolector en todos los hilos lanzados.
+
+El objetivo de estos programas es medir el impacto de las pausas del
+recolector. Se espera medir dos tipos de pausa principales, por un lado el
+tiempo máximo de pausa real, que puede involucrar a más de un hilo y por otro
+el tiempo de *stop-the-world*, es decir, el tiempo en que los hilos son
+efectivamente pausados por el recolector para tomar una *foto* de la pila
+y registros para agregarlos al *root set*.
+
+Se espera ``concpu`` sea capaz de explotar cualquier reducción en el tiempo de
+*stop-the-world*, ya que los hilos solo son interrumpidos por este tipo de
+pausa. Por otro lado, se espera que ``conalloc`` sea afectado por el tiempo
+máximo de pausa, que podrían sufrir los hilos incluso cuando el *mundo* sigue
+su marcha, debido al *lock* global del recolector y que los hilos usan
+servicios de éste.
+
+El código de ``concpu`` es el siguiente::
+
+   import tango.core.Thread: Thread;
+   import tango.core.Atomic: Atomic;
+   import tango.io.device.File: File;
+   import tango.util.digest.Sha512: Sha512;
+   import tango.util.Convert: to;
+
+   auto N = 100;
+   auto NT = 2;
+   ubyte[] BYTES;
+   Atomic!(int) running;
+
+   void main(char[][] args)
+   {
+      auto fname = args[0];
+      if (args.length > 3)
+         fname = args[3];
+      if (args.length > 2)
+         NT = to!(int)(args[2]);
+      if (args.length > 1)
+         N = to!(int)(args[1]);
+      N /= NT;
+      running.store(NT);
+      BYTES = cast(ubyte[]) File.get(fname);
+      auto threads = new Thread[NT];
+      foreach(ref thread; threads) {
+         thread = new Thread(&doSha);
+         thread.start();
+      }
+      while (running.load()) {
+         auto a = new void[](BYTES.length / 4);
+         a[] = cast(void[]) BYTES[];
+         Thread.yield();
+      }
+      foreach(thread; threads)
+         thread.join();
+   }
+
+   void doSha()
+   {
+      auto sha = new Sha512;
+      for (size_t i = 0; i < N; i++)
+         sha.update(BYTES);
+      running.decrement();
+   }
+
+El código de ``conalloc`` es igual excepto por la función ``doSha()``, que es
+de la siguiente manera::
+
+   void doSha()
+   {
+      for (size_t i = 0; i < N; i++) {
+         auto sha = new Sha512;
+         sha.update(BYTES);
+      }
+      running.decrement();
+   }
+
+
+``mcore``
+^^^^^^^^^
+Escrito por David Schima y también hallado__ en el grupo de noticias de D_,
+este programa pretende mostrar como afecta el *lock* global del recolector
+en ambientes *multi-core*, incluso cuando a simple vista parecen no utilizarse
+servicios del recolector::
+
+   import tango.core.Thread;
+
+   void main()
+   {
+      enum { nThreads = 4 };
+      auto threads = new Thread[nThreads];
+      foreach (ref thread; threads) {
+         thread = new Thread(&doAppending);
+         thread.start();
+      }
+      foreach (thread; threads)
+         thread.join();
+   }
+
+   void doAppending()
+   {
+      uint[] arr;
+      for (size_t i = 0; i < 1_000_000; i++)
+         arr ~= i;
+   }
+
+__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=103563
+
+El secreto está en que la concatenación de arreglos utiliza por detrás
+servicios del recolector, por lo tanto un programa multi-hilo en el cual los
+hilos (aparentemente) no comparten ningún estado, se puede ver
+considerablemente afectado por el recolector (siendo este efecto más visible
+en ambientes *multi-core* por el nivel de sincronización extra que significa
+a nivel de *hardware*). Cabe destacar que, sin embargo, en Linux_ no es tan
+notorio.
+
+
+``split``
+^^^^^^^^^
+Este programa trivial lee un archivo de texto y genera un arreglo de cadenas
+de texto resultantes de partir el texto en palabras. Fue escrito por Leonardo
+Maffi y también hallado__ en el grupo de noticias de D_. Su objetivo era
+mostrar lo ineficiente que puede ser concatenar datos a un mismo arreglo
+repetidas veces y ha desembocado en una pequeña `optimización`__ que sirvió
+para apalear el problema de forma razonablemente efectiva.
+
+El código es el siguiente::
+
+   import tango.io.device.File: File;
+   import tango.text.Util: delimit;
+   import tango.util.Convert: to;
+
+   int main(char[][] args) {
+      if (args.length < 2)
+         return 1;
+      auto txt = cast(byte[]) File.get(args[1]);
+      auto n = (args.length > 2) ? to!(uint)(args[2]) : 1;
+      if (n < 1)
+         n = 1;
+      while (--n)
+         txt ~= txt;
+      auto words = delimit!(byte)(txt, cast(byte[]) " \t\n\r");
+      return !words.length;
+   }
+
+__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=67673
+__ http://d.puremagic.com/issues/show_bug.cgi?id=1923
+
+
+``rnddata``
+^^^^^^^^^^^
+Este programa fue escrito por Oskar Linde y nuevamente hallado__ en el grupo
+de noticias. Fue construido para mostrar como el hecho de que el recolector
+sea conservativo puede hacer que al leer datos binarios hayan muchos *falsos
+punteros* que mantengan vivas celdas que en realidad ya no deberían ser
+accesibles desde el *root set* del grafo de conectividad.
+
+__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=46407
+
+El código del programa es el siguiente::
+
+   import tango.math.random.Random;
+
+   const IT = 125; // number of iterations, each creates an object
+   const BYTES = 1_000_000; // ~1MiB per object
+   const N = 50; // ~50MiB of initial objects
+
+   class C
+   {
+      C c; // makes the compiler not set NO_SCAN
+      long[BYTES/long.sizeof] data;
+   }
+
+   void main() {
+      auto rand = new Random();
+      C[] objs;
+            objs.length = N;
+      foreach (ref o; objs) {
+         o = new C;
+         foreach (ref x; o.data)
+            rand(x);
+      }
+      for (int i = 0; i < IT; ++i) {
+         C o = new C;
+         foreach (ref x; o.data)
+            rand(x);
+         // do something with the data...
+      }
+   }
+
+
+``sbtree``
+^^^^^^^^^^
+Este programa está basado en la prueba de nombre ``binary-trees`` de `The
+Computer Language Benchmarks Game`__, una colección de 12 programas escritos
+en alrededor de 30 lenguajes de programación para comparar su eficiencia
+(medida en tiempo de ejecución, uso de memoria y cantidad de líneas de
+código). De este juego de programas se utilizó solo ``binary-trees`` por ser
+el único destinado a ejercitar el manejo de memoria. El programa sólo manipula
+árboles binarios, creándolos y recorriéndolos inmediatamente (no realiza
+ningún trabajo útil). La traducción a D_ fue realizada por Andrey Khropov
+y fue hallada__ en el grupo de noticias.
+
+__ http://shootout.alioth.debian.org/
+__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=43991
+
+El código fuente es el siguiente::
+
+   import tango.util.Convert;
+   alias char[] string;
+
+   int main(string[] args)
+   {
+      int N = args.length > 1 ? to!(int)(args[1]) : 1;
+      int minDepth = 4;
+      int maxDepth = (minDepth + 2) > N ? minDepth + 2 : N;
+      int stretchDepth = maxDepth + 1;
+      int check = TreeNode.BottomUpTree(0, stretchDepth).ItemCheck;
+      TreeNode longLivedTree = TreeNode.BottomUpTree(0, maxDepth);
+      for (int depth = minDepth; depth <= maxDepth; depth += 2) {
+         int iterations = 1 << (maxDepth - depth + minDepth);
+         check = 0;
+         for (int i = 1; i <= iterations; i++) {
+            check += TreeNode.BottomUpTree(i, depth).ItemCheck;
+            check += TreeNode.BottomUpTree(-i, depth).ItemCheck;
+         }
+      }
+      return 0;
+   }
+
+   class TreeNode
+   {
+      TreeNode left, right;
+      int item;
+
+      this(int item, TreeNode left = null, TreeNode right = null)
+      {
+         this.item = item;
+         this.left = left;
+         this.right = right;
+      }
+
+      static TreeNode BottomUpTree(int item, int depth)
+      {
+         if (depth > 0)
+            return new TreeNode(item,
+                  BottomUpTree(2 * item - 1, depth - 1),
+                  BottomUpTree(2 * item, depth - 1));
+         return new TreeNode(item);
+      }
+
+      int ItemCheck()
+      {
+         if (left)
+            return item + left.ItemCheck() - right.ItemCheck();
+         return item;
+      }
+   }
+
+
+.. _sol_bench_small:
+
+Programas pequeños
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Todos los pequeños programas utilizados como parte del banco de prueba
+provienen del `Olden Benchmark`__ [CAR95]_. Estos programas fueron diseñados
+para probar el lenguaje de programación Olden__; un lenguaje diseñado para
+paralelizar programas automáticamente en arquitecturas con memoria
+distribuida. Son programas relativamente pequeños (entre 400 y 1000 líneas de
+código fuente cada uno) que realizan una tarea secuencial que asigna
+estructuras de datos dinámicamente. Las estructuras están usualmente
+organizadas como listas o árboles, y muy raramente como arreglos. Los
+programas pasan la mayor parte del tiempo alocando datos y el resto usando los
+datos alocados, por lo que en general están acotados en tiempo por el uso de
+memoria (y no de procesador).
+
+__ http://www.irisa.fr/caps/people/truong/M2COct99/Benchmarks/Olden/Welcome.html
+__ http://www.martincarlisle.com/olden.html
+
+La traducción a D_ fue realizada por Leonardo Maffi y están basadas a su vez
+en la traducción de este juego de pruebas a Java_, JOlden__ [CMK01]_. En Java_
+no se recomienda utilizar este conjunto de pruebas para medir la eficiencia
+del recolector de basura, dado que se han creado mejores pruebas para este
+propósito, como DaCapo__ [BLA06]_, sin embargo, dada la falta de programas
+disponibles en general, y de un conjunto de pruebas especialmente diseñado
+para evaluar el recolector de basura en D_, se decide utilizarlas en este
+trabajo de todos modos. Sin embargo sus resultados deben ser interpretados con
+una pizca de sal por lo mencionado anteriormente.
+
+__ http://www-ali.cs.umass.edu/DaCapo/benchmarks.html
+__ http://www.dacapobench.org/
+
+En general (salvo para el programa ``voronoï``) está disponible el código
+fuente portado a D_, Java_ y Python_, e incluso varias versiones con distintas
+optimizaciones para reducir el consumo de tiempo y memoria. Además provee
+comparaciones de tiempo entre todas ellas. Los programas utilizados en este
+banco de pruebas son la versión traducida más literalmente de Java_ a D_, ya
+que hace un uso más intensivo del recolector que las otras versiones.
+
+A continuación se da una pequeña descripción de cada uno de los 5 programas
+traducidos y los enlaces en donde encontrar el código fuente (y las
+comparaciones de tiempos estar disponibles).
+
+
+``bh``
+^^^^^^
+Este programa computa las interacciones gravitatorias entre un número
+:math:`N` de cuerpos en tiempo :math:`O(N log N)` y está basado en árboles
+heterogéneos de 8 ramas, según el algoritmo descripto por Barnes & Hut
+[BH86]_.
+
+Código fuente disponible en:
+http://www.fantascienza.net/leonardo/js/dolden_bh.zip
+
+
+``bisort``
+^^^^^^^^^^
+Este programa ordena :math:`N` números, donde :math:`N` es una potencia de 2,
+usando un ordenamiento *Bitonic* adaptativo, un algoritmo paralelo óptimo para
+computadoras con memoria compartida, según describen Bilardi & Nicolau
+[BN98]_. Utiliza árboles binarios como principal estructuras de datos.
+
+Código fuente disponible en:
+http://www.fantascienza.net/leonardo/js/dolden_bisort.zip
+
+
+``em3d``
+^^^^^^^^
+Este programa modela la propagación de ondas electromagnéticas a través de
+objetos en 3 dimensiones. Realiza un cálculo simple sobre un grafo irregular
+bipartito (implementado utilizando listas simplemente enlazadas) cuyos nodos
+representan valores de campo eléctrico y magnético. El algoritmo es el
+descripto por Culler, et al. [CDG93]_.
+
+Código fuente disponible en:
+http://www.fantascienza.net/leonardo/js/dolden_em3d.zip
+
+
+``tsp``
+^^^^^^^
+Este programa implementa una heurística para resolver el problema del viajante
+(*traveling salesman problem*) utilizando árboles binarios balanceados. El
+algoritmo utilizado es el descripto por Karp [KAR77]_.
+
+
+Código fuente disponible en:
+http://www.fantascienza.net/leonardo/js/dolden_tsp.zip
+
+
+``voronoï``
+^^^^^^^^^^^
+Este programa genera un conjunto aleatorio de puntos y computa su diagrama de
+Voronoï, una construcción geométrica que permite construir una partición del
+plano euclídeo, utilizando el algoritmo descripto por Guibas & Stolfi [GS85]_.
+
+Código fuente disponible en: http://codepad.org/xGDCS3KO
+
+
+.. _sol_bench_real:
+
+Programas *reales*
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Dil_ (escrito en su mayor parte por Aziz Köksal y publicado bajo licencia
+GPL_) es, lamentablemente, el único programa real hallado que, a pesar de
+estar incompleto, es lo suficientemente grande, mantenido y estable como para
+ser incluido en el banco de pruebas. Se trata de un compilador de D_ escrito
+en D_ y está incompleto porque no puede generar código (falta implementar el
+análisis semántico y la generación de código), por lo que es principalmente
+utilizado para generar documentación a partir del código.
+
+El programa está compuesto por:
+
+* 32.000 líneas de código fuente (aproximadamente).
+* 86 módulos (o archivos).
+* 322 diferentes tipos de datos definidos por el usuario, de los cuales 34 son
+  tipos *livianos* (``struct``) y 288 tipos polimórficos (``class``), de los
+  que 260 son subtipos (sub-clases).
+
+Puede observarse entonces que a pesar de ser incompleto, es una pieza de
+software bastante compleja y de dimensión considerable.
+
+Además, al interpretar código fuente se hace un uso intensivo de cadenas de
+texto que en general presentan problemas muy particulares por poder ser
+objetos extremadamente pequeños y de tamaños poco convencionales (no múltiplos
+de palabras, por ejemplo). A su vez, el texto interpretado es convertido a una
+representación interna en forma de árbol (o *árbol de sintaxis abstracta*)
+modelado por tipos *livianos* y polimórficos que están organizados en arreglos
+dinámicos contiguos y asociativos (que usan muchos servicios del recolector),
+y que finalmente son manipulados para obtener y generar la información
+necesaria, creando y dejando *morir* objetos constantemente (pero no como única
+forma de procesamiento, como otras pruebas sintetizadas).
+
+Por último, a diferencia de muchos otros programas escritos en D_, que dadas
+algunas de las ineficiencias del recolector invierten mucho trabajo en limitar
+su uso, este programa no está escrito pensando en dichas limitaciones, por lo
+que muestra un funcionamiento muy poco sesgado por estas infortunadas
+circunstancias.
+
+Por todas estas razones, Dil_ es el ejemplar que tal vez mejor sirve a la hora
+de medir de forma realista los resultados obtenidos o los avances realizados.
+Si bien, como se ha dicho anteriormente, las demás pruebas del banco pueden
+ser útiles para encontrar problemas muy particulares, está es la que da una
+lectura más cercana a la realidad del uso de un recolector.
+
+
+.. _sol_mod:
+
+Modificaciones propuestas
 ----------------------------------------------------------------------------
 
-TODO
+Se decide realizar todas las modificaciones al recolector actual de forma
+progresiva e incremental, partiendo como base del recolector de la versión
+0.99.9 de Tango_.  Las razones que motivan esta decisión son varias; por un
+lado es lo más apropiado dados los requerimientos claves mencionados al
+principio de este capítulo. Por ejemplo, al hacer cambios incrementales es más
+fácil comprobar que la eficiencia no se aleja mucho del actual con cada
+modificación y una modificación gradual impone menos resistencia a la
+aceptación del nuevo recolector.
+
+Además la construcción de un recolector de cero es una tarea difícil
+considerando que un error en el recolector es extremadamente complejo de
+rastrear, dado que en general el error se detecta en el *mutator* y en una
+instancia muy posterior al origen real del error. Esto ha sido comprobado de
+forma práctica, dado que, a modo de ejercicio para interiorizarse en el
+funcionamiento del *runtime* de D_, primero se ha construido desde cero una
+implementación de un recolector *naïve*, resultando muy difícil su depuración
+por las razones mencionadas. Por el contrario, comenzar con un recolector en
+funcionamiento como base hace más sencillo tanto probar cada pequeña
+modificación para asegurar que no introduce fallos, como encontrar y reparar
+los fallos cuando estos se producen, ya que el código incorrecto introducido
+está bien aislado e identificado.
+
+A continuación se hace un recorrido sobre cada una de las mejoras propuestas,
+y en los casos en los que la mejora propone un cambio algorítmico, se analiza
+la corrección del algoritmo resultante, partiendo de la base de que el
+algoritmo tomado como punto de partida es un marcado y barrido que utiliza la
+abstracción tricolor para hacer la fase de marcado de forma iterativa (ver
+:ref:`gc_mark_sweep` y :ref:`gc_intro_tricolor`), cuya corrección ya está
+probada en la literatura preexistente.
+
+
+.. _sol_config:
+
+Configurabilidad
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Una de las primeras mejoras propuestas es la posibilidad de configurar el
+recolector de forma más sencilla. El requerimiento mínimo es la posibilidad de
+configurar el recolector sin necesidad de recompilarlo. La complejidad de esto
+surge de que el recolector debe ser transparente para el programa del usuario.
+
+Configurar el recolector en tiempo de compilación del programa del usuario
+probablemente requeriría modificar el compilador, y además, si bien es una
+mejora sustancial a la configuración en tiempo de compilación del recolector,
+no termina de ser completamente conveniente para realizar pruebas reiteradas
+con un mismo programa para encontrar los mejores valores de configuración para
+ese programa en particular.
+
+Por otro lado, permitir configurar el recolector en tiempo de ejecución, una
+vez que su estructura interna ya fue definida y creada, puede ser no solo
+tedioso y complejo, además ineficiente, por lo tanto esta opción también se
+descarta.
+
+Finalmente, lo que parece ser más apropiado para un recolector, es permitir la
+configuración en tiempo de inicialización. Es decir, configurar el recolectar
+sin necesidad de recompilar ni el programa del usuario ni el recolector, pero
+antes de que el programa del usuario inicie, de manera que una vez iniciado el
+recolector con ciertos parámetros, éstos no cambien nunca más en durante la
+vida del programa.
+
+Este esquema provee la mejor relación entre configurabilidad, conveniencia,
+eficiencia y simplicidad. Una posibilidad para lograr esto es utilizar
+parámetros de línea de comandos, sin embargo no parece ni sencillo (proveer
+una forma de leer los parámetros de línea de comandos requiere cambios en el
+*runtime*) ni apropiado (el recolector debería ser lo más transparente posible
+para el programa del usuario).
+
+Otra posibilidad es utilizar variables de entorno, que parece ser la opción
+más sencilla y apropiada. Sencilla porque las variables de entorno pueden ser
+leídas directamente al inicializar el recolector sin necesidad de cooperación
+alguna del *runtime*, a través de :manpage:`getenv(3)`. Apropiada porque, si
+bien el problema de invasión del programa del usuario también existe, es una
+práctica más frecuente y aceptada la configuración de módulos internos
+o bibliotecas compartidas a través de variables de entorno.
+
+Por último, antes de comenzar a usar este esquema de configuración, se
+verifica que tomar ciertas decisiones en tiempo de ejecución no impacten en la
+eficiencia del recolector. Para esto se convierten algunas opciones que antes
+eran solo seleccionables en tiempo de compilación del recolector para que
+puedan ser seleccionables en tiempo de inicialización y se comprueba que no
+hay una penalización apreciable.
+
+
+.. _sol_config_spec:
+
+Especificación de opciones
+^^^^^^^^^^^^^^^^^^^^^^^^^^
+Para especificar opciones de configuración, hay que hacerlo a través de la
+variable de entorno de nombre :envvar:`D_GC_OPTS`. El valor de esa variable es
+interpretado de la siguiente manera (en formato similar a :term:`BNF`):
+
+.. productionlist::
+   D_GC_OPTS: `option` ( ':' `option` )* <lista de opciones>
+   option: `name` [ '=' `value` ]
+   name: `namec` `namec`*                <nombre de la opción>
+   value: `valuec`*                      <valor de la opción>
+   namec: `valuec` - '='
+   valuec: [0x01-0xFF] - ':'             <cualquier char salvo '\0' y ':'>
+
+Es decir, se compone de una lista de opciones separadas por **:**. Cada opción
+se especifica con un nombre, opcionalmente seguido por un valor (separados por
+**=**).
+
+El valor de una opción puede ser un texto arbitrario (exceptuando los
+caracteres ``'\0'`` y ``':'`` y de longitud máxima 255), pero cada opción lo
+interpreta de forma particular. Como caso general, hay opciones booleanas, que
+toman como valor verdadero un cualquier número distinto de 0 (o si el valor es
+vació, es decir, solo se indica el nombre de la opción), y como valor falso
+cualquier otro texto.
+
+A continuación se listan las opciones reconocidas por el recolector (indicando
+el formato del valor de la opción de tener uno especial):
+
+``mem_stomp``
+   Esta es una opción (booleana) disponible en el recolector original, pero
+   que se cambia para que sea configurable en tiempo de inicialización
+   (estando desactivada por omisión). Activa la opción ``MEMSTOMP`` descripta
+   en :ref:`dgc_debug`.
+
+``sentinel``
+   Esta opción es también booleana (desactivada por omisión), está disponible
+   en el recolector original, y se la cambia para sea configurable en tiempo
+   de inicialización. Activa la opción ``SENTINEL`` descripta en
+   :ref:`dgc_debug`.
+
+``pre_alloc``
+   Esta opción permite crear una cierta cantidad de *pools* de un tamaño
+   determinado previo a que inicie el programa. Si se especifica solo un
+   número, se crea un *pool* con ese tamaño en MiB.  Si, en cambio, se
+   especifica una cadena del tipo ``3x1``, el primer número indica la cantidad
+   de *pools* y el segundo el tamaño en MiB de cada uno (3 *pools* de 1MiB en
+   este caso). Ver :ref:`sol_pre_alloc` para más detalles sobre la utilidad de
+   esta opción.
+
+``min_free``
+   El valor de esta opción indica el porcentaje mínimo porcentaje del *heap*
+   que debe quedar libre luego de una recolección. Siendo un porcentaje, solo
+   se aceptan valores entre 0 y 100, siendo su valor por omisión 5. Ver
+   :ref:`sol_ocup` para más detalles sobre su propósito.
+
+``malloc_stats_file``
+   Esta opción sirve para especificar un archivo en el cual escribir un
+   reporte de todas la operaciones de pedido de memoria realizadas por el
+   programa (durante su tiempo de vida).  Ver :ref:`sol_stats` para más
+   detalles sobre la información provista y el formato del reporte.
+
+``collect_stats_file``
+   Esta opción sirve para especificar un archivo en el cual escribir un
+   reporte de todas las recolecciones hechas durante el tiempo de vida del
+   programa.  Ver :ref:`sol_stats` para más detalles sobre la información
+   provista y el formato del reporte.
+
+``conservative``
+   Esta opción booleana permite desactivar el escaneo preciso del *heap*,
+   forzando al recolector a ser completamente conservativo (excepto por los
+   bloques con el atributo ``NO_SCAN`` que siguen sin ser escaneados). Ver
+   :ref:`sol_precise` para más detalles sobre la existencia de esta opción.
+
+``fork``
+   Esta opción booleana (activada por omisión) permite seleccionar si el
+   recolector debe correr la fase de marcado en paralelo o no (es decir, si el
+   recolector corre de forma concurrente con el *mutator*).  Para más detalles
+   ver :ref:`sol_fork`.
+
+``eager_alloc``
+   Esta opción booleana (activada por omisión), sólo puede estar activa si
+   ``fork`` también está activa y sirve para indicar al recolector que reserve
+   un nuevo *pool* de memoria cuando una petición no puede ser satisfecha,
+   justo antes de lanzar la recolección concurrente. Ver
+   :ref:`sol_eager_alloc` para más detalles sobre el propósito de esta opción.
+
+``early_collect``
+   Esta opción booleana (desactivada por omisión), también sólo puede estar
+   activa si ``fork`` está activa y sirve para indicar al recolector que lance
+   una recolección (concurrente) antes de que la memoria libre se termine (la
+   recolección temprana será disparada cuando el porcentaje de memoria libre
+   sea menor a ``min_free``). Ver :ref:`sol_early_collect` para más detalles
+   sobre el propósito de esta opción.
+
+Cualquier opción o valor no reconocido es ignorado por el recolector. Se
+utilizan los valores por omisión de las opciones que no fueron especificadas,
+o cuyos valores no pudieron ser interpretados correctamente.
+
+Para cambiar la configuración del recolector se puede invocar el programa de
+la siguiente manera (usando un intérprete de comandos del tipo *bourne
+shell*):
+
+.. code-block:: none
+
+   D_GC_OPTS=conservative:eager_alloc=0:early_collect=1:pre_alloc=2x5 ./programa
+
+En este ejemplo, se activan las opciones ``conservative`` y ``early_collect``,
+se desactiva ``eager_alloc`` y se crean 2 *pools* de 5MiB cada uno al
+inicializar el recolector.
+
+
+Reestructuración y cambios menores
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Si bien se decide no comenzar una implementación desde cero, se ha mostrado
+(ver :ref:`dgc_bad_code`) que la implementación actual es lo suficientemente
+desprolija como para complicar su modificación. Es por esto que se hacen
+algunas reestructuraciones básicas del código, reescribiendo o saneando de
+forma incremental todas aquellas partes que complican su evolución.
+
+Además de las modificaciones puramente estéticas (aunque no por eso menos
+valuables, ya que la legibilidad y simplicidad del código son un factor
+fundamental a la hora de ser mantenido o extendido), se hacen otras pequeñas
+mejoras, que se detallan a continuación.
+
+Remoción de memoria *no-encomendada*
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Se elimina la distinción entre memoria *encomendada* y *no-encomendada* (ver
+:ref:`dgc_committed`), pasando a estar *encomendada* toda la memoria
+administrada por el recolector.
+
+Si bien a nivel de eficiencia este cambio no tuvo impacto alguno (cuando en un
+principio se especuló con que podría dar alguna ganancia en este sentido), se
+elimina el concepto de memoria *encomendada* para quitar complejidad al
+código.
+
+Esta mejora no afecta a la corrección del algoritmo, ya que a nivel lógico el
+recolector solo ve la memoria *encomendada*.
+
+.. _sol_minor_findsize:
+
+Caché de ``Pool.findSize()``
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Se crea un caché de tamaño de bloque para el método ``findSize()`` de un
+*pool*. Esto acelera considerablemente las operaciones que necesitan pedir el
+tamaño de un bloque reiteradamente, por ejemplo, al añadir nuevos elementos
+a un arreglo dinámico.
+
+Esta mejora tampoco afecta a la corrección del algoritmo, ya que nuevamente no
+afecta su comportamiento a nivel lógico, solo cambia detalles en la
+implementación de forma transparentes para el algoritmo de recolección.
+
+Optimizaciones sobre ``findPool()``
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Al analizar los principales cuellos de botella del recolector, es notoria la
+cantidad de tiempo que pasa ejecutando la función ``findPool()``, que dado un
+puntero devuelve el *pool* de memoria al cual pertenece. Es por esto que se
+minimiza el uso de esta función. Además, dado que los *pools* de memoria están
+ordenados por el puntero de comienzo del bloque de memoria manejado por el
+*pool*, se cambia la búsqueda (originalmente lineal) por una búsqueda binaria.
+Finalmente, dado que la lista de libre está construida almacenando el puntero
+al siguiente en las mismas celdas que componen la lista, se almacena también
+el puntero al *pool* al que dicha celda pertenece (dado que la celda más
+pequeña es de 16 bytes, podemos garantizar que caben dos punteros, incluso
+para arquitecturas de 64 bits). De esta manera no es necesario usar
+``findPool()`` al quitar una celda de la lista de libres.
+
+Una vez más, la mejora no afecta la corrección del código.
+
+.. _sol_pre_alloc:
+
+Pre-asignación de memoria
+^^^^^^^^^^^^^^^^^^^^^^^^^
+Esta opción permite crear una cierta cantidad de *pools* de un tamaño
+determinado previo a que inicie el programa. Normalmente el recolector no
+reserva memoria hasta que el programa lo pida. Esto puede llegar a evitar
+que un programa haga muchas recolecciones al comenzar, hasta que haya
+cargado su conjunto de datos de trabajo.
+
+Se han analizado varios valores por omisión pero ninguno es consistentemente
+mejor que comenzar sin memoria asignada, por lo tanto no se cambia el
+comportamiento original, pero se agrega una opción (ver ``pre_alloc`` en
+:ref:`sol_config_spec`) para que el usuario pueda experimentar con cada
+programa en particular si esta opción es beneficiosa.
+
+Esta opción tampoco cambia la corrección del algoritmo de recolección, solo
+sus condiciones iniciales.
+
+.. _sol_ocup:
+
+Mejora del factor de ocupación del *heap*
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+El factor de ocupación del *heap* debe ser apropiado por dos razones. Por un
+lado, si el *heap* está demasiado ocupado todo el tiempo, serán necesarias
+muchas recolecciones que, aunque pequeñas dado que la memoria utilizada es
+poca, puede llegar a ser extremadamente ineficiente en casos patológicos (ver
+:ref:`dgc_bad_ocup`). Por otro lado, si el tamaño del *heap* es extremadamente
+grande (en comparación con el tamaño real del grupo de trabajo del programa),
+se harán pocas recolecciones pero cada una es muy costosa, porque el algoritmo
+de marcado y barrido es :math:`O(\lvert Heap \rvert)` (ver
+:ref:`gc_mark_sweep`). Además la afinidad del caché va a ser extremadamente
+pobre.
+
+Para mantener el factor de ocupación dentro de límites razonables, se agrega
+la opción ``min_free`` (ver :ref:`sol_config_spec`). Esta opción indica el
+recolector cual debe ser el porcentaje mínimo del *heap* que debe quedar libre
+luego de una recolección. En caso de no cumplirse, se pide más memoria al
+sistema operativo para cumplir este requerimiento. Además, luego de cada
+recolección se verifica que el tamaño del *heap* no sea mayor a ``min_free``,
+para evitar que el *heap* crezca de forma descontrolada. Si es mayor
+a ``min_free`` se intenta minimizar el uso de memoria liberando *pools* que
+estén completamente desocupados, mientras que el factor de ocupación siga
+siendo mayor a ``min_free``. Si liberar un *pool* implica pasar ese límite, no
+se libera y se pasa a analizar el siguiente y así sucesivamente.
+
+Esta modificación no afecta a la corrección del algoritmo, ya que no lo afecta
+directamente.
+
+Modificaciones descartadas
+^^^^^^^^^^^^^^^^^^^^^^^^^^
+Se realizan varias otras modificaciones, con la esperanza de mejorar la
+eficiencia del recolector, pero que, al contrario de lo esperado, empeoran la
+eficiencia o la mejoran de forma muy marginal en comparación con la
+complejidad agregada.
+
+Probablemente el caso más significativo, y por tanto el único que vale la pena
+mencionar, es la conversión de marcado iterativo a marcado recursivo y luego
+a un esquema híbrido. Como se describe en :ref:`dgc_bad`, el marcado iterativo
+tiene sus ventajas, pero tiene desventajas también. Al convertirlo a puramente
+recursivo, se impracticable por resultar en errores de desbordamiento de pila.
+
+Por lo tanto se prueba con un esquema híbrido, poniendo un límite a la
+recursividad, volviendo al algoritmo iterativo cuando se alcanza este límite.
+
+La implementación del algoritmo híbrido consiste en los siguientes cambios
+sobre el algoritmo original (ver :ref:`dgc_algo_mark`)::
+
+   function mark_phase() is
+      global more_to_scan = false
+      global depth = 0                                // Agregado
+      stop_the_world()
+      clear_mark_scan_bits()
+      mark_free_lists()
+      mark_static_data()
+      push_registers_into_stack()
+      thread_self.stack.end = get_stack_top()
+      mark_stacks()
+      pop_registers_from_stack()
+      mark_user_roots()
+      mark_heap()
+      start_the_world()
+
+   function mark_range(begin, end) is
+      pointer = begin
+      global depth++                                  // Agregado
+      while pointer < end
+         [pool, page, block] = find_block(pointer)
+         if block is not null and block.mark is false
+            block.mark = true
+            if block.noscan is false
+               block.scan = true
+               if (global depth > MAX_DEPTH)          //
+                  more_to_scan = true                 //
+               else                                   // Agregado
+                  foreach ptr in block.words          //
+                     mark(ptr)                        //
+      global depth--                                  //
+
+Al analizar los resultados de de esta modificación, se observa una mejoría muy
+level, para valores de ``MAX_DEPTH`` mayores a cero (en algunos casos bastante
+mayores) y en general para ``MAX_DEPTH`` cero (es decir, usando el algoritmo
+de forma completamente iterativa) los resultados son peores, dado que se paga
+el trabajo extra sin ganancia alguna. En la figura :vref:`fig:sol-mark-rec` se
+puede ver, por ejemplo, el tiempo total de ejecución de Dil_ al generar la
+documentación completa del código de Tango_, según varía el valor de
+``MAX_DEPTH``.
+
+.. fig:: fig:sol-mark-rec
+
+   Análisis de tiempo total de ejecución en función del valor de
+   ``MAX_DEPTH``.
+
+   Tiempo total de ejecución de Dil_ al generar la documentación completa del
+   código de Tango_ en función del valor de ``MAX_DEPTH``. El rombo no
+   pertenece a ningún nivel de recursividad, representa el tiempo de ejecución
+   del algoritmo original (puramente iterativo).
+
+   .. image:: sol-mark-rec-dil.pdf
+
+
+Dado que aumentar el nivel máximo de recursividad significa un uso mayor del
+*stack*, y que esto puede impactar en el usuario (si el usuario tuviera un
+programa que esté al borde de consumir todo el *stack*, el recolector podría
+hacer fallar al programa de una forma inesperada para el usuario, problema que
+sería muy difícil de depurar para éste), y que los resultados obtenidos no son
+rotundamente superiores a los resultados sin esta modificación, se opta por no
+incluir este cambio. Tampoco vale la pena incluirlo como una opción con valor
+por omisión 0 porque, como se ha dicho, para este caso el resultado es incluso
+peor que sin la modificación.
+
+Esta modificación mantiene la corrección del recolector dado que tampoco
+modifica el algoritmo sino su implementación. Además ambos casos extremos son
+correctos (si ``MAX_DEPTH`` es 0, el algoritmo es puramente iterativo y si
+pudiera ser infinito resultaría en el algoritmo puramente recursivo).
+
+
+.. _sol_stats:
+
+Recolección de estadísticas
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Un requerimiento importante, tanto para evaluar los resultados de este trabajo
+como para analizar el comportamiento de los programas estudiados, es la
+recolección de estadísticas. Hay muchos aspectos que pueden ser analizados
+a la hora de evaluar un recolector, y es por esto que se busca que la
+recolección de datos sea lo más completa posible.
+
+Con este objetivo, se decide recolectar datos sobre lo que, probablemente,
+sean las operaciones más importantes del recolector: asignación de memoria
+y recolección.
+
+Todos los datos recolectados son almacenados en archivos que se especifican
+a través de opciones del recolector (ver :ref:`sol_config_spec`). Los archivos
+especificados debe poder ser escritos (y creados de ser necesario) por el
+recolector (de otra forma se ignora la opción). El conjunto de datos
+recolectados son almacenados en formato :term:`CSV` en el archivo, comenzando
+con una cabecera que indica el significado de cada columna.
+
+Los datos recolectados tienen en general 4 tipos de valores diferentes:
+
+Tiempo
+   Se guarda en segundos como número de punto flotante (por ejemplo ``0.12``).
+
+Puntero
+   Se guarda en forma hexadecimal (por ejemplo ``0xa1b2c3d4``).
+
+Tamaño
+   Se guarda como un número decimal, expresado en bytes (por ejemplo ``32``).
+
+Indicador
+   Se guarda como el número ``0`` si es falso o ``1`` si es verdadero.
+
+Esta modificación mantiene la corrección del recolector dado que no hay cambio
+algorítmico alguno.
+
+Asignación de memoria
+^^^^^^^^^^^^^^^^^^^^^
+La recolección de datos sobre asignación de memoria se activa asignando un
+nombre de archivo a la opción ``malloc_stats_file``. Por cada asignación de
+memoria pedida por el programa (es decir, por cada llamada a la función
+``gc_malloc()``) se guarda una fila con los siguientes datos:
+
+1. Cantidad de segundos que pasaron desde que empezó el programa (*timestamp*).
+2. Tiempo total que tomó la asignación de memoria.
+3. Valor del puntero devuelto por la asignación.
+4. Tamaño de la memoria pedida por el programa.
+5. Si esta petición de memoria disparó una recolección o no.
+6. Si debe ejecutarse un *finalizador* sobre el objeto (almacenado en la
+   memoria pedida) cuando ésta no sea más alcanzable (cuando sea barrido).
+7. Si objeto carece de punteros (es decir, no debe ser escaneada).
+8. Si objeto no debe ser movido por el recolector.
+9. Puntero a la información sobre la ubicación de los punteros del objeto.
+10. Tamaño del tipo del objeto.
+11. Primera palabra con los bits que indican que palabras del tipo deben ser
+    escaneados punteros y cuales no (en hexadecimal).
+12. Primera palabra con los bits que indican que palabras del tipo son
+    punteros garantizados (en hexadecimal).
+
+Como puede apreciarse, la mayor parte de esta información sirve más para
+analizar el programa que el recolector. Probablemente solo el punto 2 sea de
+interés para analizar como se comporta el recolector.
+
+El punto 8 es completamente inútil, ya que el compilador nunca provee esta
+información, pero se la deja por si en algún momento comienza a hacerlo. Los
+puntos 9 a 12 provee información sobre el tipo del objeto almacenado, útil
+para un marcado preciso (ver :ref:`sol_precise`).
+
+El punto 6 indica, indirectamente, cuales de los objetos asignados son
+*pesados*, ya que éstos son los únicos que pueden tener un *finalizador*.
+Además, a través de los puntos 4 y 10 es posible inferir si lo que va
+almacenarse es un objeto solo o un arreglo de objetos.
+
+Recolección de basura
+^^^^^^^^^^^^^^^^^^^^^
+Los datos sobre las recolecciones realizadas se guardan al asignar un nombre
+de archivo a la opción ``collect_stats_file``. Cada vez que se dispara una
+recolección [#solcollect]_ (es decir, cada vez que se llama a la función
+``fullcollect()``) se guarda una fila con los siguientes datos:
+
+1. Cantidad de segundos que pasaron desde que empezó el programa (*timestamp*).
+2. Tiempo total que tomó la asignación de memoria que disparó la recolección.
+3. Tiempo total que tomó la recolección.
+4. Tiempo total que deben pausarse todos los hilos (tiempo de
+   *stop-the-world*).
+5. Cantidad de memoria usada antes de la recolección.
+6. Cantidad de memoria libre antes de la recolección.
+7. Cantidad de memoria desperdiciada antes de la recolección.
+8. Cantidad de memoria utilizada por el mismo recolector antes de la
+   recolección (para sus estructuras internas).
+9. Cantidad de memoria usada después de la recolección.
+10. Cantidad de memoria libre después de la recolección.
+11. Cantidad de memoria desperdiciada [#solwaste]_ después de la recolección.
+12. Cantidad de memoria utilizada por el mismo recolector después de la
+    recolección.
+
+Si bien el punto 4 parece ser el más importante para un programa que necesita
+baja latencia, dado el *lock* global del recolector, el punto 2 es
+probablemente el valor más significativo en este aspecto, dado que, a menos
+que el programa en cuestión utilice muy poco el recolector en distintos hilos,
+los hilos se verán pausados de todas formas cuando necesiten utilizar el
+recolector.
+
+.. [#solcollect] Esto es en el sentido más amplio posible. Por ejemplo, cuando
+   se utiliza marcado concurrente (ver :ref:`sol_fork`), se guarda esta
+   información incluso si ya hay una recolección activa, pero el tiempo de
+   pausa de los hilos será -1 para indicar que en realidad nunca fueron
+   pausados.
+
+.. [#solwaste] Memoria *desperdiciada* se refiere a memoria que directamente
+   no puede utilizarse debido a la fragmentación. Si por ejemplo, se piden 65
+   bytes de memoria, dada la organización del *heap* en bloques (ver
+   :ref:`dgc_org`), el recolector asignará un bloque de 128 bytes, por lo
+   tanto 63 bytes quedarán desperdiciados.
+
+
+.. _sol_precise:
+
+Marcado preciso
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+En paralelo con este trabajo, David Simcha comienza a explorar la posibilidad
+de agregar precisión parcial al recolector, generando información sobre la
+ubicación de los punteros para cada tipo [DBZ3463]_. Su trabajo se limita
+a una implementación a nivel biblioteca de usuario y sobre `D 2.0`_.
+Desafortunadamente su trabajo pasa desapercibido por un buen tiempo.
+
+Luego Vincent Lang (mejor conocido como *wm4* en la comunidad de D_), retoma
+este trabajo, pero modificando el compilador DMD_ y trabajando con `D 1.0`_
+y Tango_, al igual que este trabajo. Dado el objetivo y entorno común, se abre
+la posibilidad de adaptar los cambios de Vincent Lang a este trabajo,
+utilizando una versión modificada de DMD_ (dado que los cambios aún no son
+integrados al compilador oficial).
+
+Información de tipos provista por el compilador
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Con éstas modificaciones, el compilador en cada asignación le pasa al
+recolector información sobre los punteros del tipo para el cual se pide la
+memoria. Esta información se pasa como un puntero a un arreglo de palabras con
+la estructura mostrada en la figura :vref:`fig:sol-ptrmap` y que se describe
+a continuación.
+
+.. fig:: fig:sol-ptrmap
+
+   Estructura de la información de tipos provista por el compilador.
+
+   .. aafig::
+      :scale: 110
+
+      /----- ptrmap
+      |
+      V
+      +-------------+----------------------------+----------------------------+
+      | "Tamaño en" |    "Bits indicando si la"  |      "Bits indicando si"   |
+      | "cantidad"  |  "palabra en una posición" |      "la palabra en una"   |
+      |    "de"     |    "debe escanearse como"  |          "posición es"     |
+      | "palabras"  |     "si fuera un puntero"  |          "un puntero"      |
+      +-------------+----------------------------+----------------------------+
+
+      |             |                            |                            |
+      +----- 1 -----+------- ceil(N/BPW) --------+------- ceil(N/BPW) --------+
+      |             |                            |                            |
+
+* La primera palabra indica el tamaño, en **cantidad de palabras**, del tipo
+  para el cual se pide la memoria (:math:`N`).
+* Las siguientes :math:`ceil(\frac{N}{BPW})` palabras indican,
+  como un conjunto de bits, qué palabras deben ser escaneadas por el
+  recolector como si fueran punteros (donde :math:`BPW` indica la cantidad de
+  bits por palabra, por ejemplo 32 para x86).
+* Las siguientes :math:`ceil(\frac{N}{BPW})` palabras son otro conjunto de
+  bits indicando qué palabras son realmente punteros.
+
+Los conjuntos de bits guardan la información sobre la primera palabra en el
+bit menos significativo. Dada la complejidad de la representación, se ilustra
+con un ejemplo. Dada la estructura::
+
+   union U {
+      ubyte ub;
+      void* ptr;
+   }
+
+   struct S
+   {
+      void* begin1;                        // 1 word
+      byte[size_t.sizeof * 14 + 1] bytes;  // 15 words
+      // el compilador agrega bytes de "padding" para alinear
+      void* middle;                        // 1 word
+      size_t[14] ints;                     // 14 words
+      void* end1;                          // 1 words
+      // hasta acá se almacenan los bits en la primera palabra
+      void* begin2;                        // 1 words
+      int i;                               // 1 word
+      U u;                                 // 1 word
+      S* s;                                // 1 word
+   }
+
+El compilador genera la estructura que se muestra en la figura
+:vref:`fig:sol-ptrmap-example` (asumiendo una arquitectura de 32 bits). Como
+puede apreciarse, el miembro ``u``, al ser una unión entre un puntero y un
+dato común, el compilador no puede asegurar que lo que se guarda en esa
+palabra sea realmente un puntero, pero indica que debe ser escaneado. El
+recolector debe debe ser conservativo en este caso, y escanear esa palabra
+como si fuera un puntero.
+
+.. fig:: fig:sol-ptrmap-example
+
+   Ejemplo de estructura de información de tipos generada para el tipo ``S``.
+
+   .. aafig::
+      :textual:
+      :aspect: 55
+      :scale: 110
+
+        /---- "bit de 'end1'"                                 -\
+        |                                                      | "Significado"
+        |              /---- "bit de 'middle'"                 | "de bits"
+        |              |                                       | "en la"
+        |    "bits de" |    "bits de"  /---- "bit de 'begin1'" | "primera"
+        |     "'ints'" |    "'bytes'"  |                       | "palabra"
+        |/------------\|/-------------\|                      -/
+        V|            |V|             |V
+      +----------------------------------+
+      | 00000000000000000000000000100100 | "Tamaño en cantidad de palabras (36)"
+      +==================================+ --\
+      | 10000000000000010000000000000001 |   | "Bits que indican si hay que"
+      +----------------------------------+   | "escanear una palabra según"
+      | 00000000000000000000000000001101 |   | "su posición"
+      +==================================+ --+
+      | 10000000000000010000000000000001 |   | "Bits que indican si hay un"
+      +----------------------------------+   | "puntero en la palabra según"
+      | 00000000000000000000000000001001 |   | "su posición"
+      +----------------------------------+ --/
+        |                          |AAAA
+        \--------------------------/||||                      -\
+              "bits de relleno"     ||||                       |
+                                    ||||                       | "Significado"
+                 "bit de 's'"       ||||                       | "de bits"
+                    |               ||||                       | "en la"
+                    \---------------/||\---- "bit de 'begin2'" | "segunda"
+                                     ||                        | "palabra"
+                     /---------------/\---- "bit de 'i'"       |
+                     |                                         |
+                  "bit de 'u'"                                -/
+
+Si una implementación quisiera mover memoria (ver :ref:`gc_moving`), debería
+mantener inmóvil a cualquier objeto que sea apuntado por una palabra de estas
+características, ya que no es seguro actualizar la palabra con la nueva
+posición el objeto movido. Es por esta razón que se provee desglosada la
+información sobre lo que hay que escanear, y lo que es realmente un puntero
+(que puede ser actualizado de forma segura por el recolector de ser
+necesario).
+
+Implementación en el recolector
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+La implementación está basada en la idea original de David Simcha, pero
+partiendo de la implementación de Vincent Lang (que está basada en Tango_)
+y consiste en almacenar el puntero a la estructura con la descripción del tipo
+generada por el compilador al final del bloque de datos. Este puntero solo se
+almacena si el bloque solicitado no tiene el atributo ``NO_SCAN``, dado que en
+ese caso no hace falta directamente escanear ninguna palabra del bloque.
+
+En la figura :vref:`fig:sol-ptrmap-blk` se puede ver, como continuación del
+ejemplo anterior, como se almacenaría en memoria un objeto del tipo ``S``.
+
+.. fig:: fig:sol-ptrmap-blk
+
+   Ejemplo de bloque que almacena un objeto de tipo ``S`` con información de
+   tipo.
+
+   .. aafig::
+      :scale: 110
+
+      |                                                                |
+      +------------------------ 256 bytes -----------------------------+
+      |                                                                |
+
+      +----------------------------------+-----------------------+-----+
+      |                                  |                       |     |
+      | Objeto                           | Desperdicio           | Ptr |
+      |                                  |                       |     |
+      +----------------------------------+-----------------------+-----+
+
+      |                                  |                       |     |
+      +------------ 144 bytes -----------+------ 108 bytes ------+- 4 -+
+      |                                  |                       |     |
+
+Un problema evidente de este esquema es que si el tamaño de un objeto se
+aproxima mucho al tamaño de bloque (difiere en menos de una palabra), el
+objeto ocupará el doble de memoria.
+
+El algoritmo de marcado se cambia de la siguiente forma::
+
+   // Agregado
+   global conservative_scan = [1, 1, 0]
+
+   // Agregado
+   function must_scan_word(pos, bits) is
+      return bits[pos / BITS_PER_WORD] & (1 << (pos % BITS_PER_WORD))
+
+   function mark_range(begin, end, ptrmap) is             // Modificado
+      number_of_words_in_type = ptrmap[0]                 // Agregado
+      size_t* scan_bits = ptrmap + 1                      // Agregado
+      pointer = begin
+      while pointer < end
+         foreach word_pos in 0..number_of_words_in_type   //
+            if not must_scan_word(n, scan_bits)           // Agregado
+               continue                                   //
+            [pool, page, block] = find_block(pointer)
+            if block is not null and block.mark is false
+               block.mark = true
+               if block.noscan is false
+                  block.scan = true
+                  global more_to_scan = true
+         pointer += number_of_words_in_type               // Modificado
+
+   function mark_heap() is
+      while global more_to_scan
+         global more_to_scan = false
+         foreach pool in heap
+            foreach page in pool
+               if page.block_size <= PAGE // saltea FREE y CONTINUATION
+                  foreach block in page
+                     if block.scan is true
+                        block.scan = false
+                        if page.block_size is PAGE // obj grande //
+                           begin = cast(byte*) page              //
+                           end = find_big_object_end(pool, page) //
+                        else // objeto pequeño                   //
+                           begin = block.begin                   //
+                           end = block.end                       // Modificado
+                        ptrmap = global conservative_scan        //
+                        if NO_SCAN not in block.attrs            //
+                           end -= size_t.sizeof                  //
+                           ptrmap = cast(size_t*) *end           //
+                        mark_range(begin, end, ptrmap)           //
+
+   function mark_static_data() is
+      mark_range(static_data.begin, static_data.end,
+            global conservative_scan)                // Agregado
+
+   function mark_stacks() is
+      foreach thread in threads
+         mark_range(thread.stack.begin, thread.stack.end,
+               global conservative_scan)                  // Agregado
+
+   function mark_user_roots() is
+      foreach root_range in user_roots
+         mark_range(root_range.begin, root_range.end,
+               global conservative_scan)              // Agregado
+
+Las funciones de asignación de memoria se modifican de forma similar, para
+guardar el puntero a la información de tipos. Esta implementación utiliza solo
+la información sobre que palabras hay que tratar como punteros (deben ser
+escaneadas); la información sobre qué palabras son efectivamente punteros no
+se utiliza ya que no se mueven celdas.
+
+El algoritmo sigue siendo correcto, puesto que solamente se dejan de escanear
+palabras que el compilador sabe que no pueden ser punteros. Si bien el
+lenguaje permite almacenar punteros en una variable que no lo sea, esto es
+comportamiento indefinido por lo tanto un programa que lo hace no es
+considerado correcto, por lo cual el recolector tampoco debe ser correcto en
+esas circunstancias.
+
+Cabe destacar que la información de tipos solo se provee para objetos
+almacenados en el *heap*, el área de memoria estática, registros del
+procesador y la pila de todos los hilos siguen siendo escaneados de forma
+completamente conservativa. Se puede forzar el escaneo puramente conservativo
+utilizando la opción ``conservative`` (ver :ref:`sol_config_spec`).
+
+
+.. _sol_fork:
+
+Marcado concurrente
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Finalmente se procede al objetivo primario de este trabajo, hacer que la fase
+más costosa del recolector (el marcado) pueda correr de manera concurrente con
+el *mutator*, con el objeto principal de disminuir el tiempo de pausa.
+
+Cabe aclarar, una vez más, que si bien los recolectores concurrentes buscan
+disminuir solo el tiempo de *stop-the-world*, en este caso es también
+fundamental disminuir el tiempo máximo que está tomado el *lock* global, dado
+que ese tiempo puede convertirse en una pausa para todos los threads que
+requieran servicios del recolector.
+
+Se decide basar la implementación en el *paper* "Non-intrusive Cloning Garbage
+Collector with Stock Operating System Support" [RODR97]_ por las siguientes
+razones principales:
+
+* Su implementación encaja de forma bastante natural con el diseño del
+  recolector actual, por lo que requiere pocos cambios, lo que hace más
+  factible su aceptación.
+* Está basado en la llamada al sistema :manpage:`fork(2)`, que no solo está
+  muy bien soportada (y de manera muy eficiente) en Linux_, debe estar
+  soportada en cualquier sistema operativo :term:`POSIX`.
+* No necesita instrumentar el código incluyendo barreras de memoria para
+  informar al recolector cuando cambia el grafo de conectividad. Este es un
+  aspecto fundamental, dada la filosofía de D_ de no pagar el precio de cosas
+  que no se usan. La penalización en la eficiencia solo se paga cuando corre
+  el recolector. Este aspecto también es crítico a la hora de evaluar la
+  aceptación de la solución por parte de la comunidad.
+* Dada su sencillez general, no es difícil ofrecer el algoritmo concurrente
+  como una opción, de manera que el usuario pueda optar por usarlo o no.
+
+Llamada al sistema *fork*
+^^^^^^^^^^^^^^^^^^^^^^^^^
+El término *fork* proviene del inglés y significa *tenedor* de manera textual,
+pero se lo utiliza como analogía de una bifurcación. La operación crea una
+copia (llamada *hijo*) del proceso que la ejecuta (llamado *padre*).
+
+El punto más importante es que se crea un espacio de direcciones de memoria
+separado para el proceso hijo y una copia exacta de todos los segmentos de
+memoria del proceso padre. Es por esto que cualquier modificación que se haga
+en el proceso padre, no se refleja en el proceso hijo (y viceversa), a menos
+que la memoria sea compartida entre los procesos de forma explícita.
+
+Esto, sin embargo, no significa que la memoria física sea realmente duplicada;
+en general todos los sistemas operativos modernos (como Linux_) utilizan una
+técnica llamada *copy-on-write* (*copiar-al-escribir* en castellano) que
+retrasa la copia de memoria hasta que alguno de los dos procesos escribe en un
+segmento. Recién en ese momento el sistema operativo realiza la copia de **ese
+segmento solamente**. Es por esto que la operación puede ser muy eficiente,
+y la copia de memoria es proporcional a la cantidad de cambios que hayan.
+
+:manpage:`fork(2)` tiene otra propiedad importante de mencionar: detiene todos
+los hilos de ejecución en el proceso hijo. Es decir, el proceso hijo se crear
+con un solo hilo (el hilo que ejecutó la operación de :manpage:`fork(2)`).
+
+Algoritmo
+^^^^^^^^^
+Lo que propone el algoritmo es muy sencillo, utilizar la llamada al sistema
+:manpage:`fork(2)` para crear una *fotografía* de la memoria del proceso en un
+nuevo proceso. En el proceso padre sigue corriendo el *mutator* y en el
+proceso hijo se corre la fase de marcado. El *mutator* puede modificar el
+grafo de conectividad pero los cambios quedan aislados el hijo (el marcado),
+que tiene una visión consistente e inmutable de la memoria. El sistema
+operativo duplica las páginas que modifica el padre bajo demanda, por lo tanto
+la cantidad de memoria física realmente copiada es proporcional a la cantidad
+y dispersión de los cambios que haga el *mutator*.
+
+La corrección del algoritmo se mantiene gracias a que la siguiente invariante
+se preserva:
+
+   Cuando una celda se convierte en basura, permanece como basura hasta ser
+   reciclada por el recolector.
+
+Es decir, el *mutator* no puede *resucitar* una celda *muerta* y esta
+invariante se mantiene al correr la fase de marcado sobre una vista inmutable
+de la memoria. El único efecto introducido es que el algoritmo toma una
+aproximación más conservativa. Es decir, lo que sí puede pasar es que una
+celda que pasó a estar *muerta* una vez que la fase de marcado se inició, pero
+antes de que ésta termine, la celda no se reciclará hasta la próxima
+recolección, dado que este algoritmo no incluye una comunicación entre
+*mutator* y recolector para notificar cambios en el grafo de conectividad.
+Pero esto no afecta la corrección del algoritmo, ya que un recolector es
+correcto cuando nunca recicla celdas *vivas*.
+
+La única comunicación necesaria entre el *mutator* y el recolector son los
+bits de marcado (ver :ref:`dgc_impl`), dado que la fase de barrido debe correr
+en el proceso padre. No es necesaria ningún tipo de sincronización entre
+*mutator* y recolector más allá de que uno espera a que el otro finalice.
+
+Además de almacenar el conjunto de bits ``mark`` en memoria compartida entre
+el proceso padre e hijo (necesario para la fase de barrido), las
+modificaciones necesarias para hacer la fase de marcado concurrente son las
+siguientes [#solforkerr]_::
+
+   function collect() is
+      stop_the_world()
+      child_pid = fork()
+      fflush(null) // evita que se duplique la salida de los FILE* abiertos
+      if child_pid is 0 // proceso hijo
+         mark_phase()
+         exit(0) // termina el proceso hijo
+      // proceso padre
+      start_the_world()
+      wait(child_pid)
+      sweep()
+
+   function mark_phase() is
+      global more_to_scan = false
+      // Borrado: stop_the_world()
+      clear_mark_scan_bits()
+      mark_free_lists()
+      mark_static_data()
+      push_registers_into_stack()
+      thread_self.stack.end = get_stack_top()
+      mark_stacks()
+      pop_registers_from_stack()
+      mark_user_roots()
+      mark_heap()
+      // Borrado: start_the_world()
+
+Como se puede observar, el cambio es extremadamente sencillo. Sigue siendo
+necesario un tiempo mínimo de pausa (básicamente el tiempo que tarda la
+llamada al sistema operativo :manpage:`fork(2)`) para guardar una vista
+consistente de los registros del CPU y *stacks* de los hilos. Si bien el
+conjunto de bits ``mark`` es compartido por el proceso padre e hijo dado que
+es necesario para *comunicar* las fases de marcado y barrido, cabe notar que
+nunca son utilizados de forma concurrente (la fase de barrido espera que la
+fase de marcado termine antes de usar dichos bits), por lo tanto no necesitan
+ningún tipo de sincronización y nunca habrá más de una recolección en proceso
+debido al *lock* global del recolector.
+
+A pesar de que con estos cambios el recolector técnicamente corre de forma
+concurrente, se puede apreciar que para un programa con un solo hilo el
+tiempo máximo de pausa seguirá siendo muy grande, incluso más grande que antes
+dado el trabajo extra que impone crear un nuevo proceso y duplicar las páginas
+de memoria modificadas. Lo mismo le pasará a cualquier hilo que necesite hacer
+uso del recolector mientras hay una recolección en proceso, debido al *lock*
+global.
+
+Para bajar este tiempo de pausa se experimenta con dos nuevas mejoras, que se
+describen a continuación, cuyo objetivo es correr la fase de marcado de forma
+concurrente a **todos** los hilos, incluyendo el hilo que la disparó.
+
+.. [#solforkerr] Se omite el manejo de errores y la activación/desactivación
+   del marcado concurrente a través de opciones del recolector para facilitar
+   la comprensión del algoritmo y los cambios realizados. Si devuelve con
+   error la llamada a ``fork()`` o ``waitpid()``, se vuelve al esquema
+   *stop-the-world* como si se hubiera desactivado el marcado concurrente
+   utilizando la opción del recolector ``fork=0``.
+
+
+.. _sol_eager_alloc:
+
+Creación ansiosa de *pools* (*eager allocation*)
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Esta mejora, que puede ser controlada a través de la opción ``eager_alloc``
+(ver :ref:`sol_config_spec`), consiste en crear un nuevo *pool* cuando un
+pedido de memoria no puede ser satisfecho, justo después de lanzar la
+recolección. Esto permite al recolector satisfacer la petición de memoria
+inmediatamente, corriendo la fase de marcado de forma realmente concurrente,
+incluso para programas con un solo hilo o programas cuyos hilos usan
+frecuentemente servicios del recolector. El precio a pagar es un mayor uso de
+memoria de forma temporal (y el trabajo extra de crear y eliminar *pools* más
+frecuentemente), pero es esperable que el tiempo máximo de pausa **real** se
+vea drásticamente disminuido.
+
+A simple vista las modificaciones necesarias para su implementación parecieran
+ser las siguientes::
+
+   // Agregado
+   global mark_pid = 0
+
+   // Agregado
+   function mark_is_running() is
+      return global mark_pid != 0
+
+   function collect() is
+      if mark_is_running()                      //
+         finished = try_wait(global mark_pid)   //
+         if finished                            // Agregado
+            mark_pid = 0                        //
+            sweep()                             //
+         return                                 //
+      stop_the_world()
+      child_pid = fork()
+      fflush(null)
+      if child_pid is 0 // proceso hijo
+         mark_phase()
+         exit(0)
+      // proceso padre
+      start_the_world()
+      // Borrado: wait(child_pid)
+      global mark_pid = child_pid
+
+Sin embargo con sólo estas modificaciones el algoritmo deja de ser correcto,
+ya que tres cosas problemáticas pueden suceder:
+
+1. Puede llamarse a la función ``minimize()`` mientras hay una fase de marcado
+   corriendo en paralelo. Esto puede provocar que se libere un *pool* mientras
+   se lo está usando en la fase de marcado, lo que no sería un problema
+   (porque el proceso de marcado tiene una copia) si no fuera porque los bits
+   de marcado, que son compartidos por los procesos, se liberan con el *pool*.
+2. Si un bloque libre es asignado después de que la fase de marcado comienza,
+   pero antes de que termine, ese bloque será barrido dado la función
+   ``rebuild_free_lists()`` puede reciclar páginas si todos sus bloques tienen
+   el bit ``freebits`` activo (ver :ref:`dgc_algo_sweep`).
+3. El *pool* creado ansiosamente, tendrá sus bits de marcado sin activar, por
+   lo que en la fase de barrido será interpretado como memoria libre, incluso
+   cuando puedan estar siendo utilizados por el *mutator*.
+
+El punto 1 sencillamente hace que el programa finalice con una violación de
+segmento (en el mejor caso) y 2 y 3 pueden desembocar en la liberación de una
+celda alcanzable por el *mutator*.
+
+El punto 1 se resuelve a través de la siguiente modificación::
+
+   function minimize() is
+      if mark_is_running()                            // Agregado
+         return                                       //
+      for pool in heap
+         all_free = true
+         for page in pool
+            if page.block_size is not FREE
+               all_free = false
+               break
+         if all_free is true
+            free(pool.pages)
+            free(pool)
+            heap.remove(pool)
+
+La resolución del punto 2 es un poco más laboriosa, ya que hay que mantener
+actualizado los ``freebits``, de forma que las celdas asignadas después de
+empezar la fase de marcado no sean barridas por tener ese bit activo::
+
+   function new_big(size) is
+      number_of_pages = ceil(size / PAGE_SIZE)
+      pages = find_pages(number_of_pages)
+      if pages is null
+         collect()
+         pages = find_pages(number_of_pages)
+         if pages is null
+            minimize()
+            pool = new_pool(number_of_pages)
+            if pool is null
+               return null
+            pages = assign_pages(pool, number_of_pages)
+      pages[0].block.free = true                         // Agregado
+      pages[0].block_size = PAGE
+      foreach page in pages[1..end]
+         page.block_size = CONTINUATION
+      return pages[0]
+
+   function assign_page(block_size) is
+      foreach pool in heap
+         foreach page in pool
+            if page.block_size is FREE
+               page.block_size = block_size
+               foreach block in page
+                  block.free = true                         // Agregado
+                  free_lists[page.block_size].link(block)
+
+   function mark_phase() is
+      global more_to_scan = false
+      // Borrado: clear_mark_scan_bits()
+      // Borrado: mark_free_lists()
+      clear_scan_bits()                         // Agregado
+      mark_free()                               //
+      mark_static_data()
+      push_registers_into_stack()
+      thread_self.stack.end = get_stack_top()
+      mark_stacks()
+      pop_registers_from_stack()
+      mark_user_roots()
+      mark_heap()
+
+   // Agregado
+   function clear_scan_bits() is
+      // La implementación real limpia los bits en bloques de forma eficiente
+      foreach pool in heap
+         foreach page in pool
+            foreach block in page
+               block.scan = false
+
+   // Agregado
+   function mark_free() is
+      // La implementación real copia los bits en bloques de forma eficiente
+      foreach pool in heap
+         foreach page in pool
+            foreach block in page
+               block.mark = block.free
+
+   function free_big_object(pool, page) is
+      pool_end = cast(byte*) pool.pages + (PAGE_SIZE * pool.number_of_pages)
+      do
+         page.block_size = FREE
+         page.block.free = true                 // Agregado
+         page = cast(byte*) page + PAGE_SIZE
+      while page < pool_end and page.block_size is CONTINUATION
+
+   function new(size, attrs) is
+      block_size = find_block_size(size)
+      if block_size < PAGE
+         block = new_small(block_size)
+      else
+         block = new_big(size)
+      if block is null
+         throw out_of_memory
+      if final in attrs
+         block.final = true
+      if noscan in attrs
+         block.noscan = true
+      block.free = false         // Agregado
+      return cast(void*) block
+
+   funciones new_pool(number_of_pages = 1) is
+      pool = alloc(pool.sizeof)
+      if pool is null
+         return null
+      pool.number_of_pages = number_of_pages
+      pool.pages = alloc(number_of_pages * PAGE_SIZE)
+      if pool.pages is null
+         free(pool)
+         return null
+      heap.add(pool)
+      foreach page in pool
+         page.block_size = FREE
+         foreach block in page      //
+            block.free = true       // Agregado
+            block.mark = true       //
+      return pool
+
+Finalmente, el punto número tres puede ser solucionado con el siguiente
+pequeño cambio::
+
+   funciones new_pool(number_of_pages = 1) is
+      pool = alloc(pool.sizeof)
+      if pool is null
+         return null
+      pool.number_of_pages = number_of_pages
+      pool.pages = alloc(number_of_pages * PAGE_SIZE)
+      if pool.pages is null
+         free(pool)
+         return null
+      heap.add(pool)
+      foreach page in pool
+         page.block_size = FREE
+         foreach block in page      // Agregado
+            block.mark = true       //
+      return pool
+
+La solución es conservativa porque, por un lado evita la liberación de *pools*
+mientras haya una recolección en curso (lo que puede hacer que el consumo de
+memoria sea un poco mayor al requerido) y por otro asegura que, como se
+mencionó anteriormente, los cambios hechos al grafo de conectividad luego de
+iniciar la fase de marcado y antes de que ésta termine, no serán detectados
+por el recolector hasta la próxima recolección (marcar todos los bloques de
+un nuevo *pool* como el bit ``mark`` asegura que que la memoria no sea
+recolectada por la fase de barrido cuando termine el marcado).
+
+Estas modificaciones son las que hacen que el algoritmo siga siendo correcto,
+asegurando que no se van a liberar celdas *vivas* (a expensas de diferir la
+liberación de algunas celdas *muertas* por algún tiempo).
+
+
+.. _sol_early_collect:
+
+Recolección temprana (*early collection*)
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Esta mejora, que puede ser controlada a través de la opción ``early_collect``
+(ver :ref:`sol_config_spec`), consiste en lanzar una recolección preventiva,
+antes de que una petición de memoria falle. El momento en que se lanza la
+recolección es controlado por la opción ``min_free`` (ver :ref:`sol_ocup`).
+
+De esta forma también puede correr de forma realmente concurrente el *mutator*
+y el recolector, al menos hasta que se acabe la memoria, en cuyo caso, a menos
+que la opción ``eager_alloc`` (ver :ref:`sol_eager_alloc`) también esté
+activada, se deberá esperar a que la fase de marcado termine para recuperar
+memoria en la fase de barrido.
+
+Para facilitar la comprensión de esta mejora se muestran sólo los cambios
+necesarios si no se utiliza la opción ``eager_alloc``::
+
+   function collect(early = false) is  // Modificado
+      if mark_is_running()
+         finished = try_wait(global mark_pid)
+         if finished
+            mark_pid = 0
+            sweep()
+            return                     //
+         else if early                 // Agregado
+            return                     //
+      stop_the_world()
+      child_pid = fork()
+      fflush(null)
+      if child_pid is 0 // proceso hijo
+         mark_phase()
+         exit(0)
+      // proceso padre
+      start_the_world()
+      if early                         //
+         global mark_pid = child_pid   //
+      else                             // Agregado
+         wait(child_pid)               //
+         sweep()                       //
+
+   // Agregado
+   function early_collect() is
+      if not collect_in_progress() and (percent_free < min_free)
+         collect(true)
+
+   function new(size, attrs) is
+      block_size = find_block_size(size)
+      if block_size < PAGE
+         block = new_small(block_size)
+      else
+         block = new_big(size)
+      if block is null
+         throw out_of_memory
+      if final in attrs
+         block.final = true
+      if noscan in attrs
+         block.noscan = true
+      early_collect()               // Agregado
+      return cast(void*) block
+
+Es de esperarse que cuando no está activa la opción ``eager_alloc`` por un
+lado el tiempo de pausa máximo no sea tan chico como cuando sí lo está (dado
+que si la recolección no se lanza de forma suficientemente temprana se va
+a tener que esperar que la fase de marcado termine), y por otro que se hagan
+más recolecciones de lo necesario (cuando pasa lo contrario, se recolecta más
+temprano de lo que se debería). Sin embargo, también es de esperarse que el
+consumo de memoria sea un poco menor que al usar la opción ``eager_alloc``.
+
+En cuanto a la corrección del algoritmo, éste solamente presenta los problemas
+número 1 y 2 mencionados en :ref:`sol_eager_alloc`, dado que jamás se crean
+nuevos *pools* y la solución es la ya presentada, por lo tanto el algoritmo
+sigue siendo correcto con los cuidados pertinentes.
+
+
+
+Resultados
+----------------------------------------------------------------------------
+
+Los resultados de las modificación propuestas en la sección anterior (ver
+:ref:`sol_mod`) se evalúan utilizando el conjunto de pruebas mencionado en la
+sección :ref:`sol_bench`).
+
+En esta sección se describe la forma en la que el conjunto de pruebas es
+utilizado, la forma en la que se ejecutan los programas para recolectar dichos
+resultados y las métricas principales utilizadas para analizarlos.
+
+A fines prácticos, y haciendo alusión al nombre utilizado por Tango_, en esta
+sección se utiliza el nombre **TBGC** (acrónimo para el nombre en inglés
+*Tango Basic Garbage Collector*) para hacer referencia al recolector original
+provisto por Tango_ 0.99.9 (que, recordamos, es el punto de partida de este
+trabajo). Por otro lado, y destacando la principal modificación propuesta por
+este trabajo, haremos referencia al recolector resultante de éste utilizando
+el nombre **CDGC** (acrónimo para el nombre en inglés *Concurrent D Garbage
+Collector*).
+
+
+Ejecución del conjunto de pruebas
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Dado el indeterminismo inherente a los sistemas operativos de tiempo
+compartido modernos, se hace un particular esfuerzo por obtener resultados lo
+más estable posible.
+
+Hardware y software utilizado
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Para realizar las pruebas se utiliza el siguiente hardware:
+
+* Procesador Intel(R) Core(TM)2 Quad CPU Q8400 @ 2.66GHz.
+* 2GiB de memoria RAM.
+
+El entorno de software es el siguiente:
+
+* Sistema operativo Debian_ Sid (para arquitectura *amd64*).
+* Linux_ 2.6.35.7.
+* DMD_ 1.063 modificado para proveer información de tipos al recolector (ver
+  :ref:`sol_precise`).
+* *Runtime* Tango_ 0.99.9 modificado para utilizar la información de tipos
+  provista por el compilador modificado.
+* GCC_ 4.4.5.
+* Embedded GNU_ C Library 2.11.2.
+
+Si bien el sistema operativo utiliza arquitectura *amd64*, dado que DMD_
+todavía no soporta 64 bits, se compila y corren los programas de D_ en 32
+bits.
+
+Opciones del compilador
+^^^^^^^^^^^^^^^^^^^^^^^
+Los programas del conjunto de pruebas se compilan utilizando las siguientes
+opciones del compilador DMD_:
+
+``-O``
+   Aplica optimizaciones generales.
+
+``-inline``
+   Aplica la optimización de expansión de funciones. Consiste en sustituir la
+   llamada a función por el cuerpo de la función (en general solo para
+   funciones pequeñas).
+
+``-release``
+   No genera el código para verificar pre y post-condiciones, invariantes de
+   representación, operaciones fuera de los límites de un arreglo y
+   *assert*\ 's en general (ver :ref:`d_dbc`).
+
+Parámetros de los programas
+^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Los programas de prueba se ejecutan siempre con los mismos parámetros (a menos
+que se especifique lo contrario), que se detallan a continuación.
+
+.. highlight:: none
+
+``conalloc``
+   ``40 4 bible.txt``
+
+   Procesa 40 veces un archivo de texto plano (de 4MiB de tamaño) [#solbible]_
+   utilizando 4 hilos (más el principal).
+
+``concpu``
+   ``40 4 bible.txt``
+
+   Procesa 40 veces un archivo de texto plano (de 4MiB de tamaño) [#solbible]_
+   utilizando 4 hilos (más el principal).
+
+``split``
+   ``bible.txt 2``
+
+   Procesa dos veces un archivo de texto plano (de 4MiB de tamaño)
+   [#solbible]_.
+
+``sbtree``
+   ``16``
+
+   Construyen árboles con profundidad máxima 16.
+
+``bh``
+   ``-b 4000``
+
+   Computa las interacciones gravitatorias entre 4.000 cuerpos.
+
+``bisort``
+   ``-s 2097151``
+
+   Ordena alrededor de 2 millones de números (exactamente :math:`2^21
+   = 2097151`).
+
+``em3d``
+   ``-n 4000 -d 300 -i 74``
+
+   Realiza 74 iteraciones para modelar 4.000 nodos con grado 300.
+
+``tsp``
+   ``-c 1000000``
+
+   Resuelve el problema del viajante a través de una heurística para un
+   millón de ciudades.
+
+``voronoi``
+   ``-n 30000``
+
+   Se construye un diagrama con 30.000 nodos.
+
+``dil``
+   ``ddoc $dst_dir -hl --kandil -version=Tango -version=TangoDoc
+   -version=Posix -version=linux $tango_files``
+
+   Genera la documentación de todo el código fuente de Tango_ 0.99.9, donde
+   ``$dst_dir`` es el directorio donde almacenar los archivos generados
+   y ``$tango_files`` es la lista de archivos fuente de Tango_.
+
+.. highlight:: d
+
+El resto de los programas se ejecutan sin parámetros (ver :ref:`sol_bench`
+para una descripción detallada sobre cada uno).
+
+.. [#solbible] El archivo contiene la Biblia completa, la versión traducida al
+   inglés autorizada por el Rey Jaime o Jacobo (*Authorized King James
+   Version* en inglés). Obtenida de: http://download.o-bible.com:8080/kjv.gz
+
+Recolectores y configuraciones utilizadas
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+En general se presentan resultados para TBGC y varias configuraciones de CDGC,
+de manera de poder tener una mejor noción de que mejoras y problemas puede
+introducir cada una de las modificaciones más importantes.
+
+CDGC se utiliza con siguientes configuraciones:
+
+.. highlight:: none
+
+cons
+   En modo conservativo. Específicamente, utilizando el juego de opciones::
+
+      conservative=1:fork=0:early_collect=0:eager_alloc=0
+
+prec
+   En modo preciso (ver :ref:`sol_precise`). Específicamente, utilizando el
+   juego de opciones::
+
+      conservative=0:fork=0:early_collect=0:eager_alloc=0
+
+fork
+   En modo preciso activando el marcado concurrente (ver :ref:`sol_fork`).
+   Específicamente, utilizando el juego de opciones::
+
+      conservative=0:fork=1:early_collect=0:eager_alloc=0
+
+ecol
+   En modo preciso activando el marcado concurrente con recolección temprana
+   (ver :ref:`sol_early_collect`).  Específicamente, utilizando el juego de
+   opciones::
+
+      conservative=0:fork=1:early_collect=1:eager_alloc=0
+
+eall
+   En modo preciso activando el marcado concurrente con creación ansiosa de
+   *pools* (ver :ref:`sol_eager_alloc`).  Específicamente, utilizando el juego
+   de opciones::
+
+      conservative=0:fork=1:early_collect=0:eager_alloc=1
+
+todo
+   En modo preciso activando el marcado concurrente con recolección temprana
+   y creación ansiosa de *pools*.  Específicamente, utilizando el juego de
+   opciones::
+
+      conservative=0:fork=1:early_collect=1:eager_alloc=1
+
+.. highlight:: d
+
+Métricas utilizadas
+^^^^^^^^^^^^^^^^^^^
+Para analizar los resultados se utilizan varias métricas. Las más importantes
+son:
+
+* Tiempo total de ejecución.
+* Tiempo máximo de *stop-the-world*.
+* Tiempo máximo de pausa real.
+* Cantidad máxima de memoria utilizada.
+* Cantidad total de recolecciones realizadas.
+
+El tiempo total de ejecución es una buena medida del **rendimiento** general
+del recolector, mientras que la cantidad total de recolecciones realizadas
+suele ser una buena medida de su **eficacia** [#soleficacia]_.
+
+Los tiempos máximos de pausa, *stop-the-world* y real, son una buena medida de
+la **latencia** del recolector; el segundo siendo una medida más realista dado
+que es raro que los demás hilos no utilicen servicios del recolector mientras
+hay una recolección en curso. Esta medida es particularmente importante para
+programas que necesiten algún nivel de ejecución en *tiempo-real*.
+
+En general el consumo de tiempo y espacio es un compromiso, cuando se consume
+menos tiempo se necesita más espacio y viceversa. La cantidad máxima de
+memoria utilizada nos da un parámetro de esta relación.
+
+.. [#soleficacia] Esto no es necesariamente cierto para recolectores con
+   particiones (ver :ref:`gc_part`) o incrementales (ver :ref:`gc_inc`), dado
+   que en ese caso podría realizar muchas recolecciones pero cada una muy
+   velozmente.
+
+Métodología de medición
+^^^^^^^^^^^^^^^^^^^^^^^
+Para medir el tiempo total de ejecución se utiliza el comando
+:manpage:`time(1)` con la especificación de formato ``%e``, siendo la medición
+más realista porque incluye el tiempo de carga del ejecutable, inicialización
+del *runtime* de D_ y del recolector.
+
+Todas las demás métricas se obtienen utilizando la salida generada por la
+opción ``collect_stats_file`` (ver :ref:`sol_stats`), por lo que no pueden ser
+medidos para TBGC. Sin embargo se espera que para esos casos los resultados no
+sean muy distintos a CDGC utilizando la configuración **cons** (ver sección
+anterior).
+
+Cabe destacar que las corridas para medir el tiempo total de ejecución no son
+las mismas que al utilizar la opción ``collect_stats_file``; cuando se mide el
+tiempo de ejecución no se utiliza esa opción porque impone un trabajo extra
+importante y perturbaría demasiado la medición del tiempo. Sin embargo, los
+tiempos medidos internamente al utilizar la opción ``collect_stats_file`` son
+muy precisos, dado que se hace un particular esfuerzo para que no se haga un
+trabajo extra mientras se está midiendo el tiempo.
+
+Al obtener el tiempo de *stop-the-world* se ignoran los apariciones del valor
+``-1``, que indica que se solicitó una recolección pero que ya había otra en
+curso, por lo que no se pausan los hilos realmente. Como tiempo de pausa real
+(ver :ref:`sol_fork` para más detalles sobre la diferencia con el tiempo de
+*stop-the-world*) se toma el valor del tiempo que llevó la asignación de
+memoria que disparó la recolección.
+
+Para medir la cantidad de memoria máxima se calcula el valor máximo de la
+sumatoria de: memoria usada, memoria libre, memoria desperdiciada y memoria
+usada por el mismo recolector (es decir, el total de memoria pedida por el
+programa al sistema operativo, aunque no toda este siendo utilizada por el
+*mutator* realmente).
+
+Por último, la cantidad total de recolecciones realizadas se calcula contando
+la cantidad de entradas del archivo generado por ``collect_stats_file``,
+ignorando la cabecera y las filas cuyo valor de tiempo de *stop-the-world* es
+``-1``, debido a que en ese caso no se disparó realmente una recolección dado
+que ya había una en curso.
+
+Además, ciertas pruebas se corren variando la cantidad de procesadores
+utilizados, para medir el impacto de la concurrencia en ambientes con un
+procesador solo y con múltiples procesadores. Para esto se utiliza el comando
+:manpage:`taskset`, que establece la *afinidad* de un proceso, *atándolo*
+a correr en un cierto conjunto de procesadores. Si bien las pruebas se
+realizan utilizando 1, 2, 3 y 4 procesadores, los resultados presentados en
+general se limitan a 1 y 4 procesadores, ya que no se observan diferencias
+sustanciales al utilizar 2 o 3 procesadores con respecto a usar 4 (solamente
+se ven de forma más atenuadas las diferencias entre la utilización de
+1 o 4 procesadores). Dado que de por sí ya son muchos los datos a procesar
+y analizar, agregar más resultados que no aportan información valiosa termina
+resultando contraproducente.
+
+En los casos donde se utilizan otro tipo de métricas para evaluar aspectos
+particulares sobre alguna modificación se describe como se realiza la medición
+donde se utiliza la métrica especial.
+
+Variabilidad de los resultados entre ejecuciones
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Es de esperarse que haya una cierta variación en los resultados entre
+corridas, dada la indeterminación inherente a los sistemas operativos de
+tiempo compartido, que compiten por los recursos de la computadora.
+
+Para minimizar esta variación se utilizan varias herramientas. En primer
+lugar, se corren las pruebas estableciendo máxima prioridad (-19 en Linux_) al
+proceso utilizando el comando :manpage:`nice(1)`. La variación en la
+frecuencia del reloj los procesadores (para ahorrar energía) puede ser otra
+fuente de variación, por lo que se usa el comando :manpage:`cpufreq-set(1)`
+para establecer la máxima frecuencia disponible de manera fija.
+
+Sin embargo, a pesar de tomar estas precauciones, se sigue observando una
+amplia variabilidad entre corridas. Además se observa una variación más
+importante de la esperada no solo en el tiempo, también en el consumo de
+memoria, lo que es más extraño. Esta variación se debe principalmente a que
+Linux_ asigna el espacio de direcciones a los procesos con una componente
+azarosa (por razones de seguridad). Además, por omisión, la llamada al sistema
+:manpage:`mmap(2)` asigna direcciones de memoria altas primero, entregando
+direcciones más bajas en llamadas subsiguientes [LWN90311]_.
+
+El comando :manpage:`setarch(8)` sirve para controlar éste y otros aspectos de
+Linux_. La opción ``-L`` hace que se utilice un esquema de asignación de
+direcciones antiguo, que no tiene una componente aleatoria y asigna primero
+direcciones bajas. La opción ``-R`` solamente desactiva la componente azarosa
+al momento de asignar direcciones.
+
+.. ftable:: t:sol-setarch
+
+   Variación entre corridas para TBGC.
+
+   Variación entre corridas para TBGC. La medición está efectuada utilizando
+   los valores máximo, mínimo y media estadística de 20 corridas, utilizando
+   la siguiente métrica: :math:`\frac{max - min}{\mu}`. La medida podría
+   realizarse utilizando el desvío estándar en vez de la amplitud máxima, pero
+   en este cuadro se quiere ilustrar la variación máxima, no la típica.
+
+   .. subtable::
+
+      Del tiempo total de ejecución.
+
+      ======== ======== ======== ========
+      Programa Normal   ``-R``   ``-L``
+      ======== ======== ======== ========
+      bh       0.185    0.004    0.020
+      bigarr   0.012    0.002    0.016
+      bisort   0.006    0.003    0.006
+      conalloc 0.004    0.004    0.004
+      concpu   0.272    0.291    0.256
+      dil      0.198    0.128    0.199
+      em3d     0.006    0.033    0.029
+      mcore    0.009    0.009    0.014
+      rnddata  0.015    0.002    0.011
+      sbtree   0.012    0.002    0.012
+      split    0.025    0.000    0.004
+      tsp      0.071    0.068    0.703
+      voronoi  0.886    0.003    0.006
+      ======== ======== ======== ========
+
+   .. subtable::
+
+      Del consumo máximo de memoria.
+
+      ======== ======== ======== ========
+      Programa Normal   ``-R``   ``-L``
+      ======== ======== ======== ========
+      bh       0.001    0.000    0.001
+      bigarr   0.001    0.000    0.001
+      bisort   0.000    0.000    0.000
+      conalloc 0.753    0.000    0.001
+      concpu   0.002    0.000    0.001
+      dil      0.055    0.028    0.013
+      em3d     0.000    0.001    0.001
+      mcore    0.447    0.482    0.460
+      rnddata  0.000    0.000    0.000
+      sbtree   0.000    0.000    0.000
+      split    0.000    0.000    0.000
+      tsp      0.000    0.001    0.000
+      voronoi  0.001    0.000    0.000
+      ======== ======== ======== ========
+
+Ambas opciones, reducen notablemente la variación en los resultados (ver
+cuadro :vref:`t:sol-setarch`). Esto probablemente se debe a la naturaleza
+conservativa del recolector, dado que la probabilidad de tener *falsos
+punteros* depende directamente de los valores de las direcciones de memoria,
+aunque las pruebas en la que hay concurrencia involucrada, se siguen viendo
+grandes variaciones, que probablemente estén vinculadas a problemas de
+sincronización que se ven expuestos gracias al indeterminismo inherente a los
+programas multi-hilo.
+
+Si bien se obtienen resultados más estables utilizando un esquema diferente al
+utilizado por omisión, se decide no hacerlo dado que las mediciones serían
+menos realistas. Los usuarios en general no usan esta opción y se presentaría
+una visión más acotada sobre el comportamiento de los programas. Sin embargo,
+para evaluar el este efecto en los resultados, siempre que sea posible se
+analizan los resultados de un gran número de corridas observando
+principalmente su mínima, media, máxima y desvío estándar.
+
+.. Tamaño del ejecutable (XXX: SEGUN LAS PRUEBAS NO FUCKING CAMBIA!!!)
+   El tamaño del ejecutable es un factor importante. Cuanto más grande es el
+   ejecutable, más parecieran variar los resultados. Por ejemplo se observa un
+   incremento de la estabilidad de los resultados al eliminar toda información
+   de depuración (*debug*) del ejecutable, utilizando el comando
+   :manpage:`strip(1)` (*stripped*). En el cuadro :vref:`t:sol-exesize-tbgc`
+   se puede ver la reducción del tamaño del ejecutable para TBGC cuando se
+   elimina la información de depuración (4.25 veces más chico en promedio),
+   mientas que en el cuadro :vref:`t:sol-exesize-cdgc` se puede ver CDGC (4.6
+   veces más chico en promedio).
+   .. ftable:: t:sol-exesize-tbgc
+      Reducción del tamaño del ejecutable para TBGC.
+      ======== ======== ======== ==============
+      Nombre   Debug    Stripped Debug/Stripped
+      ======== ======== ======== ==============
+      bh       586517   138060   4.248
+      bigarr   547687   192004   2.852
+      bisort   485857   115164   4.219
+      conalloc 616613   149848   4.115
+      concpu   616575   149848   4.115
+      dil      7293277  1859208  3.923
+      em3d     505019   116324   4.341
+      mcore    461767   105748   4.367
+      rnddata  2832935  1492588  1.898
+      sbtree   526402   129860   4.054
+      split    589353   144308   4.084
+      tree     462009   105844   4.365
+      tsp      544901   128412   4.243
+      voronoi  601259   141112   4.261
+      ======== ======== ======== ==============
+   .. ftable:: t:sol-exesize-cdgc
+      Reducción del tamaño del ejecutable para CDGC.
+      ========  ======== ======== ===============
+      Nombre    Debug    Stripped Debug/Stripped
+      ========  ======== ======== ===============
+      bh        736115   159884   4.604
+      bigarr    697406   213832   3.261
+      bisort    635537   136988   4.639
+      conalloc  766328   171676   4.464
+      concpu    766294   171676   4.464
+      dil       7442657  1881028  3.957
+      em3d      658827   142248   4.632
+      mcore     611486   127576   4.793
+      rnddata   2986736  1518512  1.967
+      sbtree    680217   155784   4.366
+      split     739072   166136   4.449
+      tree      611728   127672   4.791
+      tsp       694581   150236   4.623
+      voronoi   750847   162936   4.608
+      ========  ======== ======== ===============
+   TODO: Mostrar tiempos de corridas.
+
+
+.. Resultados generales
+   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+.. Primero se presenta una visión global de los resultados, utilizando las
+   métricas más importantes. Para generar los gráficos se utilizan los valores
+   máximos (en blanco), mínimos (en negro), media y desvío estándar (en gris)
+   calculados en base a, como mínimo, 20 corridas (para algunos casos se hacen
+   hasta 50 corridas).
+
+
+Resultados para pruebas sintizadas
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+A continuación se presentan los resultados obtenidos para las pruebas
+sintetizadas (ver :ref:`sol_bench_synth`). Se recuerda que este conjunto de
+resultados es útil para analizar ciertos aspectos puntuales de las
+modificaciones propuestas, pero en general distan mucho de como se comporta un
+programa real, por lo que los resultados deben ser analizados teniendo esto
+presente.
+
+``bigarr``
+^^^^^^^^^^
+.. fig:: fig:sol-bigarr-1cpu
+
+   Resultados para ``bigarr`` (utilizando 1 procesador).
+
+   Resultados para ``bigarr`` (utilizando 1 procesador). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-bigarr-1cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-bigarr-1cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-bigarr-1cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-bigarr-1cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-bigarr-1cpu.pdf
+
+.. fig:: fig:sol-bigarr-4cpu
+
+   Resultados para ``bigarr`` (utilizando 4 procesadores).
+
+   Resultados para ``bigarr`` (utilizando 4 procesadores). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-bigarr-4cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-bigarr-4cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-bigarr-4cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-bigarr-4cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-bigarr-4cpu.pdf
+
+En la figura :vref:`fig:sol-bigarr-1cpu` se pueden observar los resultados
+para ``bigarr`` al utilizar un solo procesador. En ella se puede notar que el
+tiempo total de ejecución en general aumenta al utilizar CDGC, esto es
+esperable, dado esta prueba se limitan a usar servicios del recolector. Dado
+que esta ejecución utiliza solo un procesador y por lo tanto no se puede sacar
+provecho a la concurrencia, es de esperarse que el trabajo extra realizado por
+las modificaciones se vea reflejado en los resultados. En la
+:vref:`fig:sol-bigarr-4cpu` (resultados al utilizar 4 procesadores) se puede
+observar como al usar solamente *eager allocation* se recupera un poco el
+tiempo de ejecución, probablemente debido al incremento en la concurrencia
+(aunque no se observa el mismo efecto al usar *early collection*).
+
+Observando el tiempo total de ejecución, no se esperaba un incremento tan
+notorio al pasar de TBGC a una configuración equivalente de CDGC **cons**,
+haciendo un breve análisis de las posibles causas, lo más probable parece ser
+el incremento en la complejidad de la fase de marcado dada capacidad para
+marcar de forma precisa (aunque no se use la opción, se paga el precio de la
+complejidad extra y sin obtener los beneficios).  Además se puede observar
+como el agregado de precisión al marcado mejora un poco las cosas (donde sí se
+obtiene rédito de la complejidad extra en el marcado).
+
+En general se observa que al usar *eager allocation* el consumo de memoria
+y los tiempos de pausa se disparan mientras que la cantidad de recolecciones
+disminuye drásticamente. Lo que se observa es que el programa es
+más veloz pidiendo memoria que recolectándola, por lo que crece mucho el
+consumo de memoria. Como consecuencia la fase de barrido (que no corre en
+paralelo al *mutator* como la fase de marcado) empieza a ser predominante en
+el tiempo de pausa por ser tan grande la cantidad de memoria a barrer. Este
+efecto se ve tanto al usar 1 como 4 procesadores, aunque el efecto es mucho
+más nocivo al usar 1 debido a la alta variabilidad que impone la competencia
+entre el *mutator* y recolector al correr de forma concurrente.
+
+Sin embargo, el tiempo de *stop-the-world* es siempre considerablemente más
+pequeño al utilizar marcado concurrente en CDGC, incluso cuando se utiliza
+*eager allocation*, aunque en este caso aumenta un poco, también debido al
+incremento en el consumo de memoria, ya que el sistema operativo tiene que
+copiar tablas de memoria más grandes al efectuar el *fork* (ver
+:ref:`sol_fork`).
+
+``concpu``
+^^^^^^^^^^
+.. fig:: fig:sol-concpu-1cpu
+
+   Resultados para ``concpu`` (utilizando 1 procesador).
+
+   Resultados para ``concpu`` (utilizando 1 procesador). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-concpu-1cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-concpu-1cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-concpu-1cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-concpu-1cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-concpu-1cpu.pdf
+
+.. fig:: fig:sol-concpu-4cpu
+
+   Resultados para ``concpu`` (utilizando 4 procesadores).
+
+   Resultados para ``concpu`` (utilizando 4 procesadores). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-concpu-4cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-concpu-4cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-concpu-4cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-concpu-4cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-concpu-4cpu.pdf
+
+En la figura :vref:`fig:sol-concpu-1cpu` se pueden observar los resultados
+para ``concpu`` al utilizar un solo procesador. En ella se aprecia que el
+tiempo total de ejecución disminuye levemente al usar marcado concurrente
+mientras no se utilice *eager allocation* pero aumenta al utilizarlo.
+
+Con respecto a la cantidad de recolecciones, uso máximo de memoria y tiempo de
+*stop-the-world* se ve un efecto similar al descripto para ``bigarr`` (aunque
+magnificado), pero sorprendentemente el tiempo total de pausa se dispara,
+además con una variabilidad sorprendente, cuando se usa marcado concurrente
+(pero no *eager allocation*). Una posible explicación podría ser que al
+realizarse el *fork*, el sistema operativo muy probablemente entregue el
+control del único procesador disponible al resto de los hilos que compiten por
+él, por lo que queda mucho tiempo pausado en esa operación aunque realmente no
+esté haciendo trabajo alguno (simplemente no tiene tiempo de procesador para
+correr). Este efecto se cancela al usar *eager allocation* dado que el
+*mutator* nunca se bloquea esperando que el proceso de marcado finalice.
+
+Además se observa una caída importante en la cantidad de recolecciones al
+utilizar marcado concurrente. Esto probablemente se deba a que solo un hilo
+pide memoria (y por lo tanto dispara recolecciones), mientras los demás hilos
+también estén corriendo. Al pausarse todos los hilos por menos tiempo, el
+trabajo se hace más rápido (lo que explica la disminución del tiempo total de
+ejecución) y son necesarias menos recolecciones, por terminar más rápido
+también el hilo que las dispara.
+
+En la :vref:`fig:sol-concpu-4cpu` se pueden ver los resultados al utilizar
+4 procesadores, donde el panorama cambia sustancialmente. El efecto mencionado
+en el párrafo anterior no se observa más (pues el sistema operativo tiene más
+procesadores para asignar a los hilos) pero todos los resultados se vuelven
+más variables. Los tiempos de *stop-the-world* y pausa real (salvo por lo
+recién mencionado) crecen notablemente, al igual que su variación. No se
+encuentra una razón evidente para esto; podría ser un error en la medición
+dado que al utilizar todos los procesadores disponibles del *hardware*,
+cualquier otro proceso que compita por tiempo de procesador puede afectarla
+más fácilmente.
+
+El tiempo total de ejecución crece considerablemente, como se espera, dado que
+el programa aprovecha los múltiples hilos que pueden correr en paralelo en
+procesadores diferentes.
+
+Sin embargo, no se encuentra una razón clara para explicar el crecimiento
+dramático en la cantidad de recolecciones solo al no usar marcado concurrente
+para 4 procesadores.
+
+``conalloc``
+^^^^^^^^^^^^
+.. fig:: fig:sol-conalloc-1cpu
+
+   Resultados para ``conalloc`` (utilizando 1 procesador).
+
+   Resultados para ``conalloc`` (utilizando 1 procesador). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-conalloc-1cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-conalloc-1cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-conalloc-1cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-conalloc-1cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-conalloc-1cpu.pdf
+
+.. fig:: fig:sol-conalloc-4cpu
+
+   Resultados para ``conalloc`` (utilizando 4 procesadores).
+
+   Resultados para ``conalloc`` (utilizando 4 procesadores). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-conalloc-4cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-conalloc-4cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-conalloc-4cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-conalloc-4cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-conalloc-4cpu.pdf
+
+En la figura :vref:`fig:sol-conalloc-1cpu` se pueden observar los resultados
+para ``conalloc`` al utilizar un solo procesador. Los cambios con respecto
+a lo observado para ``concpu`` son mínimos. El efecto de la mejoría al usar
+marcado concurrente pero no *eager allocation* no se observa más, dado que
+``conalloc`` pide memoria en todos los hilos, se crea un cuello de botella. Se
+ve claramente como tampoco baja la cantidad de recolecciones hecha debido
+a esto y se invierte la variabilidad entre los tiempos pico de pausa real
+y *stop-the-world* (sin una razón obvia, pero probablemente relacionado que
+todos los hilos piden memoria).
+
+Al utilizar 4 procesadores (figura :vref:`fig:sol-conalloc-4cpu`), más allá de
+las diferencias mencionadas para 1 procesador, no se observan grandes cambios
+con respecto a lo observado para ``concpu``, excepto que los tiempos de pausa
+(real y *stop-the-world*) son notablemente más pequeños, lo que pareciera
+confirmar un error en la medición de ``concpu``.
+
+``split``
+^^^^^^^^^
+.. fig:: fig:sol-split-1cpu
+
+   Resultados para ``split`` (utilizando 1 procesador).
+
+   Resultados para ``split`` (utilizando 1 procesador). Se presenta el mínimos
+   (en negro), la media centrada entre dos desvíos estándar (en gris), y el
+   máximo (en blanco) calculados sobre 50 corridas (para tiempo de ejecución)
+   o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-split-1cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-split-1cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-split-1cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-split-1cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-split-1cpu.pdf
+
+Este es el primer caso donde se aprecia la sustancial mejora proporcionada por
+una pequeña optimización, el caché de ``findSize()`` (ver
+:ref:`sol_minor_findsize`). En la figura :vref:`fig:sol-split-1cpu` se puede
+observar con claridad como, para cualquier configuración de CDGC, hay una
+caída notable en el tiempo total de ejecución. Sin embargo, a excepción de
+cuando se utiliza *eager allocation*, la cantidad de recolecciones y memoria
+usada permanece igual.
+
+La utilización de *eager allocation* mejora (aunque de forma apenas
+apreciable) el tiempo de ejecución, la cantidad de recolecciones baja a un
+tercio y el tiempo de pausa real cae dramáticamente. Al usar marcado
+concurrente ya se observa una caída determinante en el tiempo de
+*stop-the-world*. Todo esto sin verse afectado el uso máximo de memoria,
+incluso al usar *eager allocation*.
+
+Se omiten los resultados para más de un procesador por ser prácticamente
+idénticos para este análisis.
+
+``mcore``
+^^^^^^^^^
+.. fig:: fig:sol-mcore-1cpu
+
+   Resultados para ``mcore`` (utilizando 1 procesador).
+
+   Resultados para ``mcore`` (utilizando 1 procesador). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-mcore-1cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-mcore-1cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-mcore-1cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-mcore-1cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-mcore-1cpu.pdf
+
+.. fig:: fig:sol-mcore-4cpu
+
+   Resultados para ``mcore`` (utilizando 4 procesadores).
+
+   Resultados para ``mcore`` (utilizando 4 procesadores). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-mcore-4cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-mcore-4cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-mcore-4cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-mcore-4cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-mcore-4cpu.pdf
+
+El caso de ``mcore`` es interesante por ser, funcionalmente, una combinación
+entre ``concpu`` y ``split``, con un agregado extra: el incremento notable de
+la competencia por utilizar el recolector entre los múltiples hilos.
+
+Los efectos observados (en la figura :vref:`fig:sol-mcore-1cpu` para
+1 procesador y en la figura :vref:`fig:sol-mcore-4cpu` para 4) confirman esto,
+al ser una suma de los efectos observados para ``concpu`` y ``split``, con el
+agregado de una particularidad extra por la mencionada competencia entre
+hilos. A diferencia de ``concpu`` donde el incremento de procesadores resulta
+en un decremento en el tiempo total de ejecución, en este caso resulta en una
+disminución, dado que se necesita mucha sincronización entre hilos, por
+utilizar todos de forma intensiva los servicios del recolector (y por lo tanto
+competir por su *lock* global).
+
+Otro efecto común observado es que cuando el tiempo de pausa es muy pequeño
+(del orden de los milisegundos), el marcado concurrente suele incrementarlo en
+vez de disminuirlo.
+
+``rnddata``
+^^^^^^^^^^^
+.. fig:: fig:sol-rnddata-1cpu
+
+   Resultados para ``rnddata`` (utilizando 1 procesador).
+
+   Resultados para ``rnddata`` (utilizando 1 procesador). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-rnddata-1cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-rnddata-1cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-rnddata-1cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-rnddata-1cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-rnddata-1cpu.pdf
+
+En la figura :vref:`fig:sol-rnddata-1cpu` se presentan los resultados para
+``rnddata`` utilizando 1 procesador. Una vez más estamos ante un caso en el
+cual se observa claramente la mejoría gracias a una modificación en particular
+principalmente. En esta caso es el marcado preciso. Se puede ver claramente
+como mejora el tiempo de total de ejecución a algo más que la mitad (en
+promedio, aunque se observa una anomalía donde el tiempo baja hasta más de
+3 veces). Sin embargo, a menos que se utilice *eager allocation* o *early
+collection* (que en este caso prueba ser muy efectivo), la cantidad de
+recolecciones aumenta considerablemente.
+
+La explicación puede ser hallada en el consumo de memoria, que baja unas
+3 veces en promedio usando marcado preciso que además hace disminuir
+drásticamente (unas 10 veces) el tiempo de pausa (real y *stop-the-world*). El
+tiempo de *stop-the-world* disminuye unas 10 veces más al usar marcado
+concurrente y el tiempo de pausa real al usar *eager allocation*, pero en este
+caso el consumo de memoria aumenta también bastante (aunque no tanto como
+disminuye el tiempo de pausa, por lo que puede ser un precio que valga la pena
+pagar si se necesitan tiempos de pausa muy pequeños).
+
+El aumento en el variación de los tiempos de ejecución al usar marcado preciso
+probablemente se debe a lo siguiente: con marcado conservativo, debe estar
+sobreviviendo a las recolecciones el total de memoria pedida por el programa,
+debido a falsos punteros (por eso no se observa prácticamente variación en el
+tiempo de ejecución y memoria máxima consumida); al marcar con precisión
+parcial, se logra disminuir mucho la cantidad de falsos punteros, pero el
+*stack* y la memoria estática, se sigue marcado de forma conservativa, por lo
+tanto dependiendo de los valores (aleatorios) generados por la prueba, aumenta
+o disminuye la cantidad de falsos punteros, variando así la cantidad de
+memoria consumida y el tiempo de ejecución.
+
+No se muestran los resultados para más de un procesador por ser demasiado
+similares a los obtenidos utilizando solo uno.
+
+``sbtree``
+^^^^^^^^^^
+Los resultados para ``sbtree`` son tan similares a los obtenidos con
+``bigarr`` que directamente se omiten por completo, dado que no aportan ningún
+tipo de información nueva. Por un lado es esperable, dado que ambas pruebas se
+limitan prácticamente a pedir memoria, la única diferencia es que una pide
+objetos grandes y otra objetos pequeños, pero esta diferencia parece no
+afectar la forma en la que se comportan los cambios introducidos en este
+trabajo.
+
+
+Resultados para pruebas pequeñas
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+A continuación se presentan los resultados obtenidos para las pruebas pequeñas
+(ver :ref:`sol_bench_small`). Se recuerda que si bien este conjunto de pruebas
+se compone de programas reales, que efectúan una tarea útil, están diseñados
+para ejercitar la asignación de memoria y que no son recomendados para evaluar
+el desempeño de recolectores de basura. Sin embargo se las utiliza igual por
+falta de programas más realistas, por lo que hay que tomarlas como un grado de
+suspicacia.
+
+``bh``
+^^^^^^
+.. fig:: fig:sol-bh-1cpu
+
+   Resultados para ``bh`` (utilizando 1 procesador).
+
+   Resultados para ``bh`` (utilizando 1 procesador). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-bh-1cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-bh-1cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-bh-1cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-bh-1cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-bh-1cpu.pdf
+
+En la figura :vref:`fig:sol-bh-1cpu` se pueden observar los resultados
+para ``bh`` al utilizar un solo procesador. Ya en una prueba un poco más
+realista se puede observar el efecto positivo del marcado preciso, en especial
+en la cantidad de recolecciones efectuadas (aunque no se traduzca en un menor
+consumo de memoria).
+
+Sin embargo se observa también un efecto nocivo del marcado preciso en el
+consumo de memoria que intuitivamente debería disminuir, pero crece, y de
+forma considerable (unas 3 veces en promedio). La razón de esta particularidad
+es el incremento en el espacio necesario para almacenar objetos debido a que
+el puntero a la información del tipo se guarda al final del bloque (ver
+:ref:`sol_precise`). En el cuadro :vref:`t:sol-prec-mem-bh` se puede observar
+la cantidad de memoria pedida por el programa, la cantidad de memoria
+realmente asignada por el recolector (y la memoria desperdiciada) cuando se
+usa marcado conservativo y preciso. Estos valores fueron tomados usando la
+opción ``malloc_stats_file`` (ver :ref:`sol_stats`).
+
+.. ftable:: t:sol-prec-mem-bh
+
+   Memoria pedida y asignada para ``bh`` según modo de marcado.
+
+   Memoria pedida y asignada para ``bh`` según modo de marcado conservativo
+   o preciso (acumulativo durante toda la vida del programa).
+
+   ============== ============== ============== =================
+   Memoria        Pedida (MiB)   Asignada (MiB) Desperdicio (MiB)
+   ============== ============== ============== =================
+   Conservativo   302.54         354.56         52.02 (15%)
+   Preciso        302.54         472.26         169.72 (36%)
+   ============== ============== ============== =================
+
+Más allá de esto, los resultados son muy similares a los obtenidos para
+pruebas sintetizadas que se limitan a ejercitar el recolector (como ``bigarr``
+y ``sbtree``), lo que habla de lo mucho que también lo hace este pequeño
+programa.
+
+No se muestran los resultados para más de un procesador por ser extremadamente
+similares a los obtenidos utilizando solo uno.
+
+``bisort``
+^^^^^^^^^^
+.. fig:: fig:sol-bisort-1cpu
+
+   Resultados para ``bisort`` (utilizando 1 procesador).
+
+   Resultados para ``bisort`` (utilizando 1 procesador). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-bisort-1cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-bisort-1cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-bisort-1cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-bisort-1cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-bisort-1cpu.pdf
+
+La figura :vref:`fig:sol-bisort-1cpu` muestra los resultados para ``bisort``
+al utilizar 1 procesador. En este caso el parecido es con los resultados para
+la prueba sintetizada ``split``, con la diferencia que el tiempo de ejecución
+total prácticamente no varía entre TBGC y CDGC, ni entre las diferentes
+configuraciones del último (evidentemente en este caso no se aprovecha el
+caché de ``findSize()``).
+
+Otra diferencia notable es la considerable reducción del tiempo de pausa real
+al utilizar *early collection* (más de 3 veces menor en promedio comparado
+a cuando se marca conservativamente, y más de 2 veces menor que cuando se hace
+de forma precisa), lo que indica que la predicción de cuando se va a necesitar
+una recolección es más efectiva que para ``split``.
+
+No se muestran los resultados para más de un procesador por ser extremadamente
+similares a los obtenidos utilizando solo uno.
+
+``em3d``
+^^^^^^^^
+.. fig:: fig:sol-em3d-1cpu
+
+   Resultados para ``em3d`` (utilizando 1 procesador).
+
+   Resultados para ``em3d`` (utilizando 1 procesador). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-em3d-1cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-em3d-1cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-em3d-1cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-em3d-1cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-em3d-1cpu.pdf
+
+Los resultados para ``em3d`` (figura :vref:`fig:sol-em3d-1cpu`) son
+sorprendentemente similares a los de ``bisort``. La única diferencia es que en
+este caso el marcado preciso y el uso de *early collection** no parecen
+ayudar; por el contrario, aumentan levemente el tiempo de pausa real.
+
+Una vez más no se muestran los resultados para más de un procesador por ser
+extremadamente similares a los obtenidos utilizando solo uno.
+
+``tsp``
+^^^^^^^^
+.. fig:: fig:sol-tsp-1cpu
+
+   Resultados para ``tsp`` (utilizando 1 procesador).
+
+   Resultados para ``tsp`` (utilizando 1 procesador). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-tsp-1cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-tsp-1cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-tsp-1cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-tsp-1cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-tsp-1cpu.pdf
+
+Los resultados para ``tsp`` (figura :vref:`fig:sol-tsp-1cpu`) son
+prácticamente idénticos a los de ``bisort``. La única diferencia es que la
+reducción del tiempo de pausa real es un poco menor.
+
+Esto confirma en cierta medida la poca utilidad de este juego de pruebas para
+medir el rendimiento de un recolector, dado que evidentemente, si bien todas
+resuelven problemas diferentes, realizan todas el mismo tipo de trabajo.
+
+Una vez más no se muestran los resultados para más de un procesador por ser
+extremadamente similares a los obtenidos utilizando solo uno.
+
+``voronoi``
+^^^^^^^^^^^
+.. fig:: fig:sol-voronoi-1cpu
+
+   Resultados para ``voronoi`` (utilizando 1 procesador).
+
+   Resultados para ``voronoi`` (utilizando 1 procesador). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-voronoi-1cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-voronoi-1cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-voronoi-1cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-voronoi-1cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-voronoi-1cpu.pdf
+
+.. fig:: fig:sol-voronoi-4cpu
+
+   Resultados para ``voronoi`` (utilizando 4 procesadores).
+
+   Resultados para ``voronoi`` (utilizando 4 procesadores). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-voronoi-4cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-voronoi-4cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-voronoi-4cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-voronoi-4cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-voronoi-4cpu.pdf
+
+En la figura :vref:`fig:sol-voronoi-1cpu` se presentan los resultados para
+``voronoi``, probablemente la prueba más interesante de este conjunto de
+pruebas pequeñas.
+
+Por un lado se puede observar una vez más como baja dramáticamente el tiempo
+total de ejecución cuando se empieza a utilizar CDGC. Ya se ha visto que esto
+es común en programas que se benefician del caché de ``findSize()``, pero en
+este caso no parece provenir toda la ganancia solo de ese cambio, dado que
+para TBGC se ve una variación entre los resultados muy grande que desaparece
+al cambiar a CDGC, esto no puede ser explicado por esa optimización. En
+general la disminución de la variación de los resultados hemos visto que está
+asociada al incremento en la precisión en el marcado, dado que los falsos
+punteros ponen una cuota de aleatoriedad importante. Pero este tampoco parece
+ser el caso, ya que no se observan cambios apreciables al pasar a usar marcado
+preciso.
+
+Lo que se observa en esta oportunidad es un caso patológico de un mal factor
+de ocupación del *heap* (ver :ref:`sol_ocup`). Lo que muy probablemente está
+sucediendo con TBGC es que luego de ejecutar una recolección, se libera muy
+poco espacio, entonces luego de un par de asignaciones, es necesaria una nueva
+recolección. En este caso es donde dificulta la tarea de analizar los
+resultados la falta de métricas para TBGC, dado que no se pueden observar la
+cantidad de recolecciones ni de consumo máximo de memoria. Sin embargo es
+fácil corroborar esta teoría experimentalmente, gracias a la opción
+``min_free``. Utilizando la ``min_free=0`` para emular el comportamiento de
+TBGC (se recuerda que el valor por omisión es ``min_free=5``), se obtiene una
+media de 4 segundos, mucho más parecida a lo obtenido para TBGC.
+
+Otra particularidad de esta prueba es que al utilizar *early collection* el
+tiempo de pausa real aumenta notablemente al usar un procesador, mientras que
+al usar 4 (ver figura :vref:`fig:sol-voronoi-4cpu` disminuye levemente (además
+de otros cambios en el nivel de variación, pero en general las medias no
+cambian).
+
+
+Resultados para pruebas reales
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+A continuación se presentan los resultados obtenidos para las pruebas reales
+(ver :ref:`sol_bench_real`). Recordamos que solo se pudo halla un programa que
+pueda ser utilizado a este fin, Dil_, y que el objetivo principal de este
+trabajo se centra alrededor de obtener resultados positivos para este
+programa, por lo que a pesar de ser una única prueba, se le presta particular
+atención.
+
+``dil``
+^^^^^^^
+.. fig:: fig:sol-dil-1cpu
+
+   Resultados para ``dil`` (utilizando 1 procesador).
+
+   Resultados para ``dil`` (utilizando 1 procesador). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-dil-1cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-dil-1cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-dil-1cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-dil-1cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-dil-1cpu.pdf
+
+.. fig:: fig:sol-dil-4cpu
+
+   Resultados para ``dil`` (utilizando 4 procesadores).
+
+   Resultados para ``dil`` (utilizando 4 procesadores). Se presenta el
+   mínimos (en negro), la media centrada entre dos desvíos estándar (en gris),
+   y el máximo (en blanco) calculados sobre 50 corridas (para tiempo de
+   ejecución) o 20 corridas (para el resto).
+
+   .. subfig::
+
+      Tiempo de ejecución (seg)
+
+      .. image:: plots/time-dil-4cpu.pdf
+
+   .. subfig::
+
+      Cantidad de recolecciones
+
+      .. image:: plots/ncol-dil-4cpu.pdf
+
+   .. subfig::
+
+      Uso máximo de memoria (MiB)
+
+      .. image:: plots/mem-dil-4cpu.pdf
+
+   .. subfig::
+
+      *Stop-the-world* máximo (seg)
+
+      .. image:: plots/stw-dil-4cpu.pdf
+
+   .. subfig::
+
+      Pausa real máxima (seg)
+
+      .. image:: plots/pause-dil-4cpu.pdf
+
+En la figura :vref:`fig:sol-dil-1cpu` se presentan los resultados para
+``dil`` al utilizar un procesador. Una vez más vemos una mejoría inmediata del
+tiempo total de ejecución al pasar de TBGC a CDGC, y una vez más se debe
+principalmente al mal factor de ocupación del *heap* de TBGC, dado que
+utilizando CDGC con la opción ``min_free=0`` se obtiene una media del orden de
+los 80 segundos, bastante más alta que el tiempo obtenido para TBGC.
+
+Sin embargo se observa un pequeño incremento del tiempo de ejecución al
+introducir marcado preciso, y un incremento bastante más importante (de
+alrededor del 30%) en el consumo máximo de memoria. Nuevamente, como pasa con
+la prueba ``bh``, el efecto es probablemente producto del incremento en el
+espacio necesario para almacenar objetos debido a que el puntero a la
+información del tipo se guarda al final del bloque (ver :ref:`sol_precise`).
+En el cuadro :vref:`t:sol-prec-mem-dil` se puede observar la diferencia de
+memoria desperdiciada entre el modo conservativo y preciso.
+
+El pequeño incremento en el tiempo total de ejecución podría estar dado por la
+mayor probabilidad de tener *falsos punteros* debido al incremento del tamaño
+del *heap*; se recuerda que el *stack* y memoria estática se siguen marcado de
+forma conservativa, incluso en modo preciso.
+
+.. ftable:: t:sol-prec-mem-dil
+
+   Memoria pedida y asignada para ``dil`` según modo de marcado.
+
+   Memoria pedida y asignada para ``dil`` según modo de marcado conservativo
+   o preciso (acumulativo durante toda la vida del programa).
+
+   ============== ============== ============== =================
+   Memoria        Pedida (MiB)   Asignada (MiB) Desperdicio (MiB)
+   ============== ============== ============== =================
+   Conservativo   307.48         399.94         92.46 (23%)
+   Preciso        307.48         460.24         152.76 (33%)
+   ============== ============== ============== =================
+
+También se puede observar una gran disminución del tiempo total de ejecución
+(cerca de un 60%, y más de un 200% comparado con TBGC) alrededor de la mitad)
+al empezar a usar *eager allocation*, acompañado como es usual de una baja en
+la cantidad de recolecciones realizadas (esta vez mayor, de más de 3 veces)
+y de una caída drástica del tiempo de pausa real (alrededor de 40 veces más
+pequeño); todo esto con un incremento marginal en el consumo total de memoria
+(aproximadamente un 5%). En este caso el uso de *early collection* apenas
+ayuda a bajar el tiempo de pausa real en un 20% en promedio aproximadamente.
+El tiempo de *stop-the-world* cae dramáticamente al empezar a realizar la fase
+de marcado de manera concurrente; es 200 veces más pequeño.
+
+Al utilizar 4 procesadores (ver figura :vref:`fig:sol-dil-4cpu`), hay algunos
+pequeños cambios. El tiempo total de ejecución es reducido todavía más (un 20%
+que cuando se usa 1 procesador) cuando se utiliza *eager allocation*. Además
+al utilizar *early collection*, hay otra pequeña ganancia de alrededor del
+10%, tanto para el tiempo total de ejecución como para el tiempo de pausa
+real.
+
+
+.. _sol_accept:
+
+Aceptación
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Los avances de este trabajo fueron comunicados regularmente a la comunidad de
+D_ a través de un blog [LMTDGC]_ y del grupo de noticias de D_. Los
+comentarios hechos sobre el primero son en general positivos y denotan una
+buena recepción por parte de la comunidad a las modificaciones propuestas.
+
+Una vez agregado el marcado concurrente se hace un anuncio en el grupo de
+noticias que también muestra buenos comentarios y aceptación, en particular
+por parte de Sean Kelly, encargado de mantener el *runtime* de `D 2.0`_, que
+comienza a trabajar en adaptar el recolector con idea de tal vez incluirlo en
+el futuro [NGA19235]_. Poco después Sean Kelly publica una versión preliminar
+de la adaptación en la lista de correos que coordina el desarrollo del
+*runtime* de `D 2.0`_ [DRT117]_.
 
+También se ha mostrado interés de incluirlo en Tango_, aunque no se han ha
+comenzado aún con la adaptación, pero debería ser trivial dado que este
+trabajo se desarrolla usando Tango_ (y el recolector está basado en el de
+Tango_) [TT1997]_.
 
 
+.. include:: links.rst
 
 .. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :