Corregir typo y usar referencia en vez de link

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

.. Acá va lo que decidí hacer en base al análisis anterior y sus razones.
   ESTADO: EMPEZADO


.. _solucion:

Solución adoptada
============================================================================

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:

* 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.

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:

Banco de pruebas
----------------------------------------------------------------------------

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.

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.

.. [#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.


.. _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.


``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
paliar el problema de forma razonablemente efectiva [PAN09]_.

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


``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
----------------------------------------------------------------------------

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()
      fflush(null) // evita que se duplique la salida de los FILE* abiertos
      child_pid = fork()
      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()
      fflush(null)
      child_pid = fork()
      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 :