X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/5f79318a52fc6ada10154cb148008bd9d44fa22e..869d3714190bbd53b65eee4e3e352f7035277a3e:/source/solucion.rst?ds=sidebyside

diff --git a/source/solucion.rst b/source/solucion.rst
index b4bbf4e..b27ffbb 100644
--- a/source/solucion.rst
+++ b/source/solucion.rst
@@ -1,39 +1,553 @@
 
 .. Acá va lo que decidí hacer en base al análisis anterior y sus razones.
-   ESTADO: SIN EMPEZAR
+   ESTADO: EMPEZADO
 
 
-.. _ref_solucion:
+.. _solucion:
 
 Solución adoptada
 ============================================================================
 
-TODO
+Como hemos visto en :ref:`dgc_bad`, la mejora del recolector de basura puede
+ser abordada desde múltiples flancos. Por lo tanto, para reducir la cantidad
+de posibilidades hay que tener en cuenta uno de los principales objetivos de
+este trabajo: encontrar una solución que tenga una buena probabilidad de ser
+adoptada por el lenguaje, o alguno de sus compiladores al menos. Para asegurar
+esto, la solución debe tener un alto grado de aceptación en la comunidad, lo
+que implica algunos puntos claves:
+
+* La eficiencia general de la solución no debe ser notablemente peor, en
+  ningún aspecto, que la implementación actual.
+* Los cambios no deben ser drásticos.
+* La solución debe atacar de forma efectiva al menos uno de los problemas
+  principales del recolector actual.
+
+Bajo estos requerimientos, se concluye que probablemente el área más fértil
+para explorar sea la falta de concurrencia por cumplir todos estos puntos:
 
+* 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.
 
-Recolector naive de referencia
+
+Banco de pruebas
 ----------------------------------------------------------------------------
 
-TODO
+Teniendo en cuenta que uno de los objetivos principales es no empeorar la
+eficiencia general de forma notable, la confección de un banco de pruebas es
+un aspecto fundamental, para poder comprobar con cada cambio que la eficiencia
+final no se vea notablemente afectada.
 
+La confección de un banco de pruebas no es una tarea trivial, mucho menos para
+un lenguaje con el nivel de fragmentación que tuvo D_ (que hace que a fines
+prácticos hayan 3 versiones del lenguaje compitiendo), y cuya masa crítica de
+usuarios es de aficionados que usualmente abandonan los proyectos, quedando
+obsoletos rápidamente.
 
+Con el objetivo de confeccionar este banco de pruebas, desde el comienzo del
+trabajo se han recolectado (usando como fuente principalmente el grupo de
+noticias de D_ [#benchmod]_) programas triviales sintetizados con el único
+propósito de mostrar problemas con el recolector de basura. Otros programas de
+este estilo fueron escritos explícitamente para este trabajo.
 
-Set de benchmarks y recolección de estadísticas
-----------------------------------------------------------------------------
+Además se han recolectado [#benchmod]_ algunos pequeños programas portados de
+otros lenguajes de programación, que si bien son pequeños y tienen como
+objetivo ejercitar el recolector de basura, son programas reales que resuelven
+un problema concreto, lo que otorga un juego de pruebas un poco más amplio que
+los programas triviales.
 
-TODO
+.. [#benchmod] Cabe destacar que en general todos los programas recolectados
+   han sido modificados levemente para ajustarlos mejor a las necesidades del
+   banco de prueba (entre las modificaciones más frecuentes se encuentran la
+   conversión de Phobos_ a Tango_ y la eliminación de mensajes por salida
+   estándar).
 
+Pero probablemente lo más importante para confeccionar un banco de pruebas
+verdaderamente útil es disponer de programas reales, que hayan sido diseñados
+con el único objetivo de hacer su trabajo, sin pensar en como impacta el
+recolector sobre ellos (ni ellos sobre el recolector). Estos programas proveen
+las pruebas más realistas y amplias. Desgraciadamente no hay muchos programas
+reales escritos en D_ disponibles públicamente, y no se encontró en la
+comunidad tampoco una muestra de voluntad por compartir programas privados
+para usar como banco de pruebas en este trabajo.
 
+Por lo tanto el banco de pruebas que se conformó como una mezcla de estas tres
+grandes categorías.
 
-Reescritura del GC actual
-----------------------------------------------------------------------------
 
-TODO
+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.
 
 
 
-Conversión a "cloning GC"
+Modificaciones propuestas
 ----------------------------------------------------------------------------
 
 TODO
@@ -47,5 +561,6 @@ TODO
 
 
 
+.. include:: links.rst
 
-.. vim: set ts=3 sts=3 sw=3 et tw=78 :
+.. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :