From: Leandro Lucarella Date: Sat, 25 Sep 2010 01:53:28 +0000 (-0300) Subject: Completar sección de Banco de pruebas de Solución X-Git-Tag: entrega-2010-10-08~19 X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/commitdiff_plain/c410a685943a1d4df7556ad0e8912a0394d47b5b?ds=sidebyside;hp=d4b51bb3e136e607b99343536e4be8d942742ab2 Completar sección de Banco de pruebas de Solución --- diff --git a/source/referencias.rst b/source/referencias.rst index 3143437..b4346e0 100644 --- a/source/referencias.rst +++ b/source/referencias.rst @@ -62,6 +62,28 @@ __ http://cs.anu.edu.au/techreports/2007/TR-CS-07-04.pdf Applications. Noviembre 2003. __ http://www-plan.cs.colorado.edu/diwan/cbgc.pdf +.. [CAR95] A. Rogers and M. Carlisle and J. Reppy and L. Hendren. Supporting + Dynamic Data Structures on Distributed Memory Machines. Transactions on + Programming Languages and Systems, volúmen 17, número 2. Marzo 1995. + +.. [BH86] J. Barnes and P. Hut. A hierarchical o(N log N) force-calculation + algorithm. Nature Volumen 324, páginas 446-449. Diciembre 1986. + +.. [BN98] G. Bilardi and A. Nicolau. Adaptive Bitonic Sorting: An optimal + parallel algorithm for shared-memory machines. SIAM J. Comput. + Volumen 18, número 2, páginas 216-228. 1998. + +.. [CDG93] D. Culler, A. Dusseau, S. Goldstein, A. Krishnamurthy, S. Lumetta, + T. von Eicken and K. Yelick. Parallel Programming in Split-C. + Supercomputing 1993, páginas 262-273. 1993. + +.. [KAR77] R. Karp. Probabilistic analysis of partitioning algorithms for the + traveling-salesman problem in the plane. Mathematics of Operations + Research Volumen 2, número 3, páginas 209-224. Agosto 1977. + +.. [GS85] L. Guibas and J. Stolfi. General Subdivisions and Voronoi Diagrams. + ACM Trans. on Graphics Volumen 4, número 2, páginas 74-123. 1985. + .. Libros: diff --git a/source/solucion.rst b/source/solucion.rst index a1da636..b27ffbb 100644 --- a/source/solucion.rst +++ b/source/solucion.rst @@ -1,6 +1,6 @@ .. Acá va lo que decidí hacer en base al análisis anterior y sus razones. - ESTADO: SIN EMPEZAR + ESTADO: EMPEZADO .. _solucion: @@ -8,32 +8,546 @@ 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 spelllang=es :