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


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.


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 total, que puede involucrar a más de un hilo y por otro
el tiempo de *stop-the-world*, es decir, el tiempo en que los hilos son
efectivamente pausados por el recolector para tomar una *foto* de la pila
y registros para agregarlos al *root set*.

Se espera ``concpu`` sea capaz de explotar cualquier reducción en el tiempo de
*stop-the-world*, ya que los hilos solo son interrumpidos por este tipo de
pausa. Por otro lado, se espera que ``conalloc`` sea afectado por el tiempo
máximo de pausa, que podrían sufrir los hilos incluso cuando el *mundo* sigue
su marcha, debido al *lock* global del recolector y que los hilos usan
servicios de éste.

El código de ``concpu`` es el siguiente::

   import tango.core.Thread: Thread;
   import tango.core.Atomic: Atomic;
   import tango.io.device.File: File;
   import tango.util.digest.Sha512: Sha512;
   import tango.util.Convert: to;

   auto N = 100;
   auto NT = 2;
   ubyte[] BYTES;
   Atomic!(int) running;

   void main(char[][] args)
   {
      auto fname = args[0];
      if (args.length > 3)
         fname = args[3];
      if (args.length > 2)
         NT = to!(int)(args[2]);
      if (args.length > 1)
         N = to!(int)(args[1]);
      N /= NT;
      running.store(NT);
      BYTES = cast(ubyte[]) File.get(fname);
      auto threads = new Thread[NT];
      foreach(ref thread; threads) {
         thread = new Thread(&doSha);
         thread.start();
      }
      while (running.load()) {
         auto a = new void[](BYTES.length / 4);
         a[] = cast(void[]) BYTES[];
         Thread.yield();
      }
      foreach(thread; threads)
         thread.join();
   }

   void doSha()
   {
      auto sha = new Sha512;
      for (size_t i = 0; i < N; i++)
         sha.update(BYTES);
      running.decrement();
   }

El código de ``conalloc`` es igual excepto por la función ``doSha()``, que es
de la siguiente manera::

   void doSha()
   {
      for (size_t i = 0; i < N; i++) {
         auto sha = new Sha512;
         sha.update(BYTES);
      }
      running.decrement();
   }


``mcore``
^^^^^^^^^
Escrito por David Schima y también hallado__ en el grupo de noticias de D_,
este programa pretende mostrar como afecta el *lock* global del recolector
en ambientes *multi-core*, incluso cuando a simple vista parecen no utilizarse
servicios del recolector::

   import tango.core.Thread;

   void main()
   {
      enum { nThreads = 4 };
      auto threads = new Thread[nThreads];
      foreach (ref thread; threads) {
         thread = new Thread(&doAppending);
         thread.start();
      }
      foreach (thread; threads)
         thread.join();
   }

   void doAppending()
   {
      uint[] arr;
      for (size_t i = 0; i < 1_000_000; i++)
         arr ~= i;
   }

__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=103563

El secreto está en que la concatenación de arreglos utiliza por detrás
servicios del recolector, por lo tanto un programa multi-hilo en el cual los
hilos (aparentemente) no comparten ningún estado, se puede ver
considerablemente afectado por el recolector (siendo este efecto más visible
en ambientes *multi-core* por el nivel de sincronización extra que significa
a nivel de *hardware*). Cabe destacar que, sin embargo, en Linux_ no es tan
notorio.


``split``
^^^^^^^^^
Este programa trivial lee un archivo de texto y genera un arreglo de cadenas
de texto resultantes de partir el texto en palabras. Fue escrito por Leonardo
Maffi y también hallado__ en el grupo de noticias de D_. Su objetivo era
mostrar lo ineficiente que puede ser concatenar datos a un mismo arreglo
repetidas veces y ha desembocado en una pequeña `optimización`__ que sirvió
para apalear el problema de forma razonablemente efectiva.

El código es el siguiente::

   import tango.io.device.File: File;
   import tango.text.Util: delimit;
   import tango.util.Convert: to;

   int main(char[][] args) {
      if (args.length < 2)
         return 1;
      auto txt = cast(byte[]) File.get(args[1]);
      auto n = (args.length > 2) ? to!(uint)(args[2]) : 1;
      if (n < 1)
         n = 1;
      while (--n)
         txt ~= txt;
      auto words = delimit!(byte)(txt, cast(byte[]) " \t\n\r");
      return !words.length;
   }

__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=67673
__ http://d.puremagic.com/issues/show_bug.cgi?id=1923


``rnddata``
^^^^^^^^^^^
Este programa fue escrito por Oskar Linde y nuevamente hallado__ en el grupo
de noticias. Fue construido para mostrar como el hecho de que el recolector
sea conservativo puede hacer que al leer datos binarios hayan muchos *falsos
punteros* que mantengan vivas celdas que en realidad ya no deberían ser
accesibles desde el *root set* del grafo de conectividad.

__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=46407

El código del programa es el siguiente::

   import tango.math.random.Random;

   const IT = 125; // number of iterations, each creates an object
   const BYTES = 1_000_000; // ~1MiB per object
   const N = 50; // ~50MiB of initial objects

   class C
   {
      C c; // makes the compiler not set NO_SCAN
      long[BYTES/long.sizeof] data;
   }

   void main() {
      auto rand = new Random();
      C[] objs;
            objs.length = N;
      foreach (ref o; objs) {
         o = new C;
         foreach (ref x; o.data)
            rand(x);
      }
      for (int i = 0; i < IT; ++i) {
         C o = new C;
         foreach (ref x; o.data)
            rand(x);
         // do something with the data...
      }
   }


``sbtree``
^^^^^^^^^^
Este programa está basado en la prueba de nombre ``binary-trees`` de `The
Computer Language Benchmarks Game`__, una colección de 12 programas escritos
en alrededor de 30 lenguajes de programación para comparar su eficiencia
(medida en tiempo de ejecución, uso de memoria y cantidad de líneas de
código). De este juego de programas se utilizó solo ``binary-trees`` por ser
el único destinado a ejercitar el manejo de memoria. El programa sólo manipula
árboles binarios, creándolos y recorriéndolos inmediatamente (no realiza
ningún trabajo útil). La traducción a D_ fue realizada por Andrey Khropov
y fue hallada__ en el grupo de noticias.

__ http://shootout.alioth.debian.org/
__ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=43991

El código fuente es el siguiente::

   import tango.util.Convert;
   alias char[] string;

   int main(string[] args)
   {
      int N = args.length > 1 ? to!(int)(args[1]) : 1;
      int minDepth = 4;
      int maxDepth = (minDepth + 2) > N ? minDepth + 2 : N;
      int stretchDepth = maxDepth + 1;
      int check = TreeNode.BottomUpTree(0, stretchDepth).ItemCheck;
      TreeNode longLivedTree = TreeNode.BottomUpTree(0, maxDepth);
      for (int depth = minDepth; depth <= maxDepth; depth += 2) {
         int iterations = 1 << (maxDepth - depth + minDepth);
         check = 0;
         for (int i = 1; i <= iterations; i++) {
            check += TreeNode.BottomUpTree(i, depth).ItemCheck;
            check += TreeNode.BottomUpTree(-i, depth).ItemCheck;
         }
      }
      return 0;
   }

   class TreeNode
   {
      TreeNode left, right;
      int item;

      this(int item, TreeNode left = null, TreeNode right = null)
      {
         this.item = item;
         this.left = left;
         this.right = right;
      }

      static TreeNode BottomUpTree(int item, int depth)
      {
         if (depth > 0)
            return new TreeNode(item,
                  BottomUpTree(2 * item - 1, depth - 1),
                  BottomUpTree(2 * item, depth - 1));
         return new TreeNode(item);
      }

      int ItemCheck()
      {
         if (left)
            return item + left.ItemCheck() - right.ItemCheck();
         return item;
      }
   }


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

__ http://www-ali.cs.umass.edu/DaCapo/benchmarks.html

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


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.



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] - ':'             <cualquiera 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 encomendada
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
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*.

Micro-optimizaciones
^^^^^^^^^^^^^^^^^^^^
Si bien se realizan varias micro-optimizaciones, probablemente la más
relevante es la inclusión de 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'"
        |
        |              /---- "bit de 'middle'"
        |              |
        |    "bits de" |    "bits de"  /---- "bit de 'begin1'"
        |     "'ints'" |    "'bytes'"  |
        |/------------\|/-------------\|
        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"     ||||
                                    ||||
                 "bit de 's'"       ||||
                    |               ||||
                    \---------------/||\---- "bit de 'begin2'"
                                     ||
                     /---------------/\---- "bit de 'i'"
                     |
                  "bit de 'u'"

Si una implementación quisiera mover memoria (ver :ref:`gc_moving`), debería
mantener inmóvil a cualquier objeto que sea apuntado por una palabra de estas
características, ya que no es seguro actualizar la palabra con la nueva
posición el objeto movido. Es por esta razón que se provee desglosada la
información sobre lo que hay que escanear, y lo que es realmente un puntero
(que puede ser actualizado de forma segura por el recolector de ser
necesario).

Implementación en el recolector
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
La implementación está basada en la idea original de David Simcha, pero
partiendo de la implementación de Vincent Lang (que está basada en Tango_)
y consiste en almacenar el puntero a la estructura con la descripción del tipo
generada por el compilador al final del bloque de datos. Este puntero solo se
almacena si el bloque solicitado no tiene el atributo ``NO_SCAN``, dado que en
ese caso no hace falta directamente escanear ninguna palabra del bloque.

En la figura :vref:`fig:sol-ptrmap-blk` se puede ver, como continuación del
ejemplo anterior, como se almacenaría en memoria un objeto del tipo ``S``.

.. fig:: fig:sol-ptrmap-blk

   Ejemplo de bloque que almacena un objeto de tipo ``S`` con información de
   tipo.

   .. aafig::
      :scale: 110

      |                                                                |
      +------------------------ 256 bytes -----------------------------+
      |                                                                |

      +----------------------------------+-----------------------+-----+
      |                                  |                       |     |
      | Objeto                           | Desperdicio           | Ptr |
      |                                  |                       |     |
      +----------------------------------+-----------------------+-----+

      |                                  |                       |     |
      +------------ 144 bytes -----------+------ 108 bytes ------+- 4 -+
      |                                  |                       |     |

Un problema evidente de este esquema es que si el tamaño de un objeto se
aproxima mucho al tamaño de bloque (difiere en menos de una palabra), el
objeto ocupará el doble de memoria.

El algoritmo de marcado se cambia de la siguiente forma::

   // Agregado
   global conservative_scan = [1, 1, 0]

   // Agregado
   function must_scan_word(pos, bits) is
      return bits[pos / BITS_PER_WORD] & (1 << (pos % BITS_PER_WORD))

   function mark_range(begin, end, ptrmap) is             // Modificado
      number_of_words_in_type = ptrmap[0]                 // Agregado
      size_t* scan_bits = ptrmap + 1                      // Agregado
      pointer = begin
      while pointer < end
         foreach word_pos in 0..number_of_words_in_type   //
            if not must_scan_word(n, scan_bits)           // Agregado
               continue                                   //
            [pool, page, block] = find_block(pointer)
            if block is not null and block.mark is false
               block.mark = true
               if block.noscan is false
                  block.scan = true
                  global more_to_scan = true
         pointer += number_of_words_in_type               // Modificado

   function mark_heap() is
      while global more_to_scan
         global more_to_scan = false
         foreach pool in heap
            foreach page in pool
               if page.block_size <= PAGE // saltea FREE y CONTINUATION
                  foreach block in page
                     if block.scan is true
                        block.scan = false
                        if page.block_size is PAGE // obj grande //
                           begin = cast(byte*) page              //
                           end = find_big_object_end(pool, page) //
                        else // objeto pequeño                   //
                           begin = block.begin                   //
                           end = block.end                       // Modificado
                        ptrmap = global conservative_scan        //
                        if NO_SCAN not in block.attrs            //
                           end -= size_t.sizeof                  //
                           ptrmap = cast(size_t*) *end           //
                        mark_range(begin, end, ptrmap)           //

   function mark_static_data() is
      mark_range(static_data.begin, static_data.end,
            global conservative_scan)                // Agregado

   function mark_stacks() is
      foreach thread in threads
         mark_range(thread.stack.begin, thread.stack.end,
               global conservative_scan)                  // Agregado

   function mark_user_roots() is
      foreach root_range in user_roots
         mark_range(root_range.begin, root_range.end,
               global conservative_scan)              // Agregado

Las funciones de asignación de memoria se modifican de forma similar, para
guardar el puntero a la información de tipos. Esta implementación utiliza solo
la información sobre que palabras hay que tratar como punteros (deben ser
escaneadas); la información sobre qué palabras son efectivamente punteros no
se utiliza ya que no se mueven celdas.

El algoritmo sigue siendo correcto, puesto que solamente se dejan de escanear
palabras que el compilador sabe que no pueden ser punteros. Si bien el
lenguaje permite almacenar punteros en una variable que no lo sea, esto es
comportamiento indefinido por lo tanto un programa que lo hace no es
considerado correcto, por lo cual el recolector tampoco debe ser correcto en
esas circunstancias.

Cabe destacar que la información de tipos solo se provee para objetos
almacenados en el *heap*, el área de memoria estática, registros del
procesador y la pila de todos los hilos siguen siendo escaneados de forma
completamente conservativa. Se puede forzar el escaneo puramente conservativo
utilizando la opción ``conservative`` (ver :ref:`sol_config_spec`).


.. _sol_fork:

Marcado concurrente
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Finalmente se procede al objetivo primario de este trabajo, hacer que la fase
más costosa del recolector (el marcado) pueda correr de manera concurrente con
el *mutator*, con el objeto principal de disminuir el tiempo de pausa.

Cabe aclarar, una vez más, que si bien los recolectores concurrentes buscan
disminuir solo el tiempo de *stop-the-world*, en este caso es también
fundamental disminuir el tiempo máximo que está tomado el *lock* global, dado
que ese tiempo puede convertirse en una pausa para todos los threads que
requieran servicios del recolector.

Se decide basar la implementación en el *paper* "Non-intrusive Cloning Garbage
Collector with Stock Operating System Support" [RODR97]_ por las siguientes
razones principales:

* Su implementación encaja de forma bastante natural con el diseño del
  recolector actual, por lo que requiere pocos cambios, lo que hace más
  factible su aceptación.
* Está basado en la llamada al sistema :manpage:`fork(2)`, que no solo está
  muy bien soportada (y de manera muy eficiente) en Linux_, debe estar
  soportada en cualquier sistema operativo :term:`POSIX`.
* No necesita instrumentar el código incluyendo barreras de memoria para
  informar al recolector cuando cambia el grafo de conectividad. Este es un
  aspecto fundamental, dada la filosofía de D_ de no pagar el precio de cosas
  que no se usan. La penalización en la eficiencia solo se paga cuando corre
  el recolector. Este aspecto también es crítico a la hora de evaluar la
  aceptación de la solución por parte de la comunidad.
* Dada su sencillez general, no es difícil ofrecer el algoritmo concurrente
  como una opción, de manera que el usuario pueda optar por usarlo o no.

Llamada al sistema *fork*
^^^^^^^^^^^^^^^^^^^^^^^^^
El término *fork* proviene del inglés y significa *tenedor* de manera textual,
pero se lo utiliza como analogía de una bifurcación. La operación crea una
copia (llamada *hijo*) del proceso que la ejecuta (llamado *padre*).

El punto más importante es que se crea un espacio de direcciones de memoria
separado para el proceso hijo y una copia exacta de todos los segmentos de
memoria del proceso padre. Es por esto que cualquier modificación que se haga
en el proceso padre, no se refleja en el proceso hijo (y viceversa), a menos
que la memoria sea compartida entre los procesos de forma explícita.

Esto, sin embargo, no significa que la memoria física sea realmente duplicada;
en general todos los sistemas operativos modernos (como Linux_) utilizan una
técnica llamada *copy-on-write* (*copiar-al-escribir* en castellano) que
retrasa la copia de memoria hasta que alguno de los dos procesos escribe en un
segmento. Recién en ese momento el sistema operativo realiza la copia de **ese
segmento solamente**. Es por esto que la operación puede ser muy eficiente,
y la copia de memoria es proporcional a la cantidad de cambios que hayan.

:manpage:`fork(2)` tiene otra propiedad importante de mencionar: detiene todos
los hilos de ejecución en el proceso hijo. Es decir, el proceso hijo se crear
con un solo hilo (el hilo que ejecutó la operación de :manpage:`fork(2)`).

Algoritmo
^^^^^^^^^
Lo que propone el algoritmo es muy sencillo, utilizar la llamada al sistema
:manpage:`fork(2)` para crear una *fotografía* de la memoria del proceso en un
nuevo proceso. En el proceso padre sigue corriendo el *mutator* y en el
proceso hijo se corre la fase de marcado. El *mutator* puede modificar el
grafo de conectividad pero los cambios quedan aislados el hijo (el marcado),
que tiene una visión consistente e inmutable de la memoria. El sistema
operativo duplica las páginas que modifica el padre bajo demanda, por lo tanto
la cantidad de memoria física realmente copiada es proporcional a la cantidad
y dispersión de los cambios que haga el *mutator*.

La corrección del algoritmo se mantiene gracias a que la siguiente invariante
se preserva:

   Cuando una celda se convierte en basura, permanece como basura hasta ser
   reciclada por el recolector.

Es decir, el *mutator* no puede *resucitar* una celda *muerta* y esta
invariante se mantiene al correr la fase de marcado sobre una vista inmutable
de la memoria. El único efecto introducido es que el algoritmo toma una
aproximación más conservativa. Es decir, lo que sí puede pasar es que una
celda que pasó a estar *muerta* una vez que la fase de marcado se inició, pero
antes de que ésta termine, la celda no se reciclará hasta la próxima
recolección, dado que este algoritmo no incluye una comunicación entre
*mutator* y recolector para notificar cambios en el grafo de conectividad.
Pero esto no afecta la corrección del algoritmo, ya que un recolector es
correcto cuando nunca recicla celdas *vivas*.

La única comunicación necesaria entre el *mutator* y el recolector son los
bits de marcado (ver :ref:`dgc_impl`), dado que la fase de barrido debe correr
en el proceso padre. No es necesaria ningún tipo de sincronización entre
*mutator* y recolector más allá de que uno espera a que el otro finalice.

Además de almacenar el conjunto de bits ``mark`` en memoria compartida entre
el proceso padre e hijo (necesario para la fase de barrido), las
modificaciones necesarias para hacer la fase de marcado concurrente son las
siguientes [#solforkerr]_::

   function collect() is
      stop_the_world()
      child_pid = fork()
      fflush(null) // evita que se duplique la salida de los FILE* abiertos
      if child_pid is 0 // proceso hijo
         mark_phase()
         exit(0) // termina el proceso hijo
      // proceso padre
      start_the_world()
      wait(child_pid)
      sweep()

   function mark_phase() is
      global more_to_scan = false
      // Borrado: stop_the_world()
      clear_mark_scan_bits()
      mark_free_lists()
      mark_static_data()
      push_registers_into_stack()
      thread_self.stack.end = get_stack_top()
      mark_stacks()
      pop_registers_from_stack()
      mark_user_roots()
      mark_heap()
      // Borrado: start_the_world()

Como se puede observar, el cambio es extremadamente sencillo. Sigue siendo
necesario un tiempo mínimo de pausa (básicamente el tiempo que tarda la
llamada al sistema operativo :manpage:`fork(2)`) para guardar una vista
consistente de los registros del CPU y *stacks* de los hilos. Si bien el
conjunto de bits ``mark`` es compartido por el proceso padre e hijo dado que
es necesario para *comunicar* las fases de marcado y barrido, cabe notar que
nunca son utilizados de forma concurrente (la fase de barrido espera que la
fase de marcado termine antes de usar dichos bits), por lo tanto no necesitan
ningún tipo de sincronización y nunca habrá más de una recolección en proceso
debido al *lock* global del recolector.

A pesar de que con estos cambios el recolector técnicamente corre de forma
concurrente, se puede apreciar que para un programa con un solo hilo el
tiempo máximo de pausa seguirá siendo muy grande, incluso más grande que antes
dado el trabajo extra que impone crear un nuevo proceso y duplicar las páginas
de memoria modificadas. Lo mismo le pasará a cualquier hilo que necesite hacer
uso del recolector mientras hay una recolección en proceso, debido al *lock*
global.

Para bajar este tiempo de pausa se experimenta con dos nuevas mejoras, que se
describen a continuación, cuyo objetivo es correr la fase de marcado de forma
concurrente a **todos** los hilos, incluyendo el hilo que la disparó.

.. [#solforkerr] Se omite el manejo de errores y la activación/desactivación
   del marcado concurrente a través de opciones del recolector para facilitar
   la comprensión del algoritmo y los cambios realizados. Si devuelve con
   error la llamada a ``fork()`` o ``waitpid()``, se vuelve al esquema
   *stop-the-world* como si se hubiera desactivado el marcado concurrente
   utilizando la opción del recolector ``fork=0``.


.. _sol_eager_alloc:

Creación ansiosa de *pools*
^^^^^^^^^^^^^^^^^^^^^^^^^^^
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
^^^^^^^^^^^^^^^^^^^^
Esta mejora, que puede ser controlada a través de la opción ``early_collect``
(ver :ref:`sol_config_spec`), consiste en lanzar una recolección preventiva,
antes de que una petición de memoria falle. El momento en que se lanza la
recolección es controlado por la opción ``min_free`` (ver :ref:`sol_ocup`).

De esta forma también puede correr de forma realmente concurrente el *mutator*
y el recolector, al menos hasta que se acabe la memoria, en cuyo caso, a menos
que la opción ``eager_alloc`` (ver :ref:`sol_eager_alloc`) también esté
activada, se deberá esperar a que la fase de marcado termine para recuperar
memoria en la fase de barrido.

Para facilitar la comprensión de esta mejora se muestran sólo los cambios
necesarios si no se utiliza la opción ``eager_alloc``::

   function collect(early = false) is  // Modificado
      if mark_is_running()
         finished = try_wait(global mark_pid)
         if finished
            mark_pid = 0
            sweep()
            return                     //
         else if early                 // Agregado
            return                     //
      stop_the_world()
      child_pid = fork()
      fflush(null)
      if child_pid is 0 // proceso hijo
         mark_phase()
         exit(0)
      // proceso padre
      start_the_world()
      if early                         //
         global mark_pid = child_pid   //
      else                             // Agregado
         wait(child_pid)               //
         sweep()                       //

   // Agregado
   function early_collect() is
      if not collect_in_progress() and (percent_free < min_free)
         collect(true)

   function new(size, attrs) is
      block_size = find_block_size(size)
      if block_size < PAGE
         block = new_small(block_size)
      else
         block = new_big(size)
      if block is null
         throw out_of_memory
      if final in attrs
         block.final = true
      if noscan in attrs
         block.noscan = true
      early_collect()               // Agregado
      return cast(void*) block

Es de esperarse que cuando no está activa la opción ``eager_alloc`` por un
lado el tiempo de pausa máximo no sea tan chico como cuando sí lo está (dado
que si la recolección no se lanza de forma suficientemente temprana se va
a tener que esperar que la fase de marcado termine), y por otro que se hagan
más recolecciones de lo necesario (cuando pasa lo contrario, se recolecta más
temprano de lo que se debería). Sin embargo, también es de esperarse que el
consumo de memoria sea un poco menor que al usar la opción ``eager_alloc``.

En cuanto a la corrección del algoritmo, éste solamente presenta los problemas
número 1 y 2 mencionados en :ref:`sol_eager_alloc`, dado que jamás se crean
nuevos *pools* y la solución es la ya presentada, por lo tanto el algoritmo
sigue siendo correcto con los cuidados pertinentes.



Resultados
----------------------------------------------------------------------------

TODO



.. include:: links.rst

.. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :