.. Acá va lo que decidí hacer en base al análisis anterior y sus razones.
- ESTADO: SIN EMPEZAR
+ ESTADO: EMPEZADO
.. _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
+.. include:: links.rst
.. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :
projects / z.facultad / 75.00 / informe.git / commitdiff