source/solucion.rst

   1
   2 .. Acá va lo que decidí hacer en base al análisis anterior y sus razones.
   3    ESTADO: EMPEZADO
   4
   5
   6 .. _solucion:
   7
   8 Solución adoptada
   9 ============================================================================
  10
  11 Como hemos visto en :ref:`dgc_bad`, la mejora del recolector de basura puede
  12 ser abordada desde múltiples flancos. Por lo tanto, para reducir la cantidad
  13 de posibilidades hay que tener en cuenta uno de los principales objetivos de
  14 este trabajo: encontrar una solución que tenga una buena probabilidad de ser
  15 adoptada por el lenguaje, o alguno de sus compiladores al menos. Para asegurar
  16 esto, la solución debe tener un alto grado de aceptación en la comunidad, lo
  17 que implica algunos puntos claves:
  18
  19 * La eficiencia general de la solución no debe ser notablemente peor, en
  20   ningún aspecto, que la implementación actual.
  21 * Los cambios no deben ser drásticos.
  22 * La solución debe atacar de forma efectiva al menos uno de los problemas
  23   principales del recolector actual.
  24
  25 Bajo estos requerimientos, se concluye que probablemente el área más fértil
  26 para explorar sea la falta de concurrencia por cumplir todos estos puntos:
  27
  28 * Si bien hay evidencia en la literatura sobre el incremento del tiempo de
  29   ejecución total de ejecución de un programa al usar algoritmos concurrentes,
  30   éste no es, en general, muy grande comparativamente.
  31 * Existen algoritmos de recolección concurrente que no requieren ningún grado
  32   de cooperación por parte del lenguaje o el compilador.
  33 * La falta de concurrencia y los largos tiempos de pausa es una de las
  34   críticas más frecuentes al recolector actual por parte de la comunidad.
  35
  36 A pesar de ser la concurrencia la veta principal a explorar en este trabajo,
  37 se intenta abordar los demás problemas planteados siempre que sea posible
  38 hacerlo sin alejarse demasiado del objetivo principal.
  39
  40
  41 Banco de pruebas
  42 ----------------------------------------------------------------------------
  43
  44 Teniendo en cuenta que uno de los objetivos principales es no empeorar la
  45 eficiencia general de forma notable, la confección de un banco de pruebas es
  46 un aspecto fundamental, para poder comprobar con cada cambio que la eficiencia
  47 final no se vea notablemente afectada.
  48
  49 La confección de un banco de pruebas no es una tarea trivial, mucho menos para
  50 un lenguaje con el nivel de fragmentación que tuvo D_ (que hace que a fines
  51 prácticos hayan 3 versiones del lenguaje compitiendo), y cuya masa crítica de
  52 usuarios es de aficionados que usualmente abandonan los proyectos, quedando
  53 obsoletos rápidamente.
  54
  55 Con el objetivo de confeccionar este banco de pruebas, desde el comienzo del
  56 trabajo se han recolectado (usando como fuente principalmente el grupo de
  57 noticias de D_ [#benchmod]_) programas triviales sintetizados con el único
  58 propósito de mostrar problemas con el recolector de basura. Otros programas de
  59 este estilo fueron escritos explícitamente para este trabajo.
  60
  61 Además se han recolectado [#benchmod]_ algunos pequeños programas portados de
  62 otros lenguajes de programación, que si bien son pequeños y tienen como
  63 objetivo ejercitar el recolector de basura, son programas reales que resuelven
  64 un problema concreto, lo que otorga un juego de pruebas un poco más amplio que
  65 los programas triviales.
  66
  67 .. [#benchmod] Cabe destacar que en general todos los programas recolectados
  68    han sido modificados levemente para ajustarlos mejor a las necesidades del
  69    banco de prueba (entre las modificaciones más frecuentes se encuentran la
  70    conversión de Phobos_ a Tango_ y la eliminación de mensajes por salida
  71    estándar).
  72
  73 Pero probablemente lo más importante para confeccionar un banco de pruebas
  74 verdaderamente útil es disponer de programas reales, que hayan sido diseñados
  75 con el único objetivo de hacer su trabajo, sin pensar en como impacta el
  76 recolector sobre ellos (ni ellos sobre el recolector). Estos programas proveen
  77 las pruebas más realistas y amplias. Desgraciadamente no hay muchos programas
  78 reales escritos en D_ disponibles públicamente, y no se encontró en la
  79 comunidad tampoco una muestra de voluntad por compartir programas privados
  80 para usar como banco de pruebas en este trabajo.
  81
  82 Por lo tanto el banco de pruebas que se conformó como una mezcla de estas tres
  83 grandes categorías.
  84
  85
  86 Pruebas sintetizadas
  87 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  88
  89 Este es el juego de programas triviales, escritos con el único objetivo de
  90 ejercitar un área particular y acotada del recolector.
  91
  92
  93 ``bigarr``
  94 ^^^^^^^^^^
  95 Su objetivo es ejercitar la manipulación de arreglos de tamaño considerable
  96 que almacenan objetos de tamaño pequeño o mediano. Esta prueba fue hallada__
  97 en el grupo de noticias de D_ y escrita por Babele Dunnit y aunque
  98 originalmente fue concebido para mostrar un problema con la concatenación de
  99 arreglos (como se aprecia en la sentencia ``version(loseMemory)``), ejercita
 100 los aspectos más utilizados del del recolector: manipulación de arreglos
 101 y petición e memoria. Es una de las pruebas que más estresa al recolector ya
 102 que todo el trabajo que realiza el programa es utilizar servicios de éste.
 103
 104 El código fuente del programa es el siguiente::
 105
 106    const IT = 300;
 107    const N1 = 20_000;
 108    const N2 = 40_000;
 109
 110    class Individual
 111    {
 112       Individual[20] children;
 113    }
 114
 115    class Population
 116    {
 117       void grow()
 118       {
 119          foreach (inout individual; individuals)
 120             individual = new Individual;
 121       }
 122       Individual[N1] individuals;
 123    }
 124
 125    version = loseMemory;
 126
 127    int main(char[][] args)
 128    {
 129
 130       Population testPop1 = new Population;
 131       Population testPop2 = new Population;
 132       Individual[N2] indi;
 133       for (int i = 0; i < IT; i++) {
 134          testPop1.grow();
 135          testPop2.grow();
 136          version (loseMemory) {
 137             indi[] = testPop1.individuals ~ testPop2.individuals;
 138          }
 139          version (everythingOk) {
 140             indi[0..N1] = testPop1.individuals;
 141             indi[N1..N2] = testPop2.individuals;
 142          }
 143       }
 144       return 0;
 145    }
 146
 147 __ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=54084
 148
 149
 150 ``concpu`` y ``conalloc``
 151 ^^^^^^^^^^^^^^^^^^^^^^^^^
 152 Estos dos programas fueron escritos especialmente para este trabajo con el fin
 153 de ejercitar la interacción entre el recolector y un *mutator* con varios
 154 hilos. La única diferencia entre ellos es que ``concpu`` lanza hilos que hacen
 155 trabajar de forma intensiva el procesador pero que no utilizan servicios del
 156 recolector, salvo en el hilo principal, mientras que ``conalloc`` utiliza
 157 servicios del recolector en todos los hilos lanzados.
 158
 159 El objetivo de estos programas es medir el impacto de las pausas del
 160 recolector. Se espera medir dos tipos de pausa principales, por un lado el
 161 tiempo máximo de pausa total, que puede involucrar a más de un hilo y por otro
 162 el tiempo de *stop-the-world*, es decir, el tiempo en que los hilos son
 163 efectivamente pausados por el recolector para tomar una *foto* de la pila
 164 y registros para agregarlos al *root set*.
 165
 166 Se espera ``concpu`` sea capaz de explotar cualquier reducción en el tiempo de
 167 *stop-the-world*, ya que los hilos solo son interrumpidos por este tipo de
 168 pausa. Por otro lado, se espera que ``conalloc`` sea afectado por el tiempo
 169 máximo de pausa, que podrían sufrir los hilos incluso cuando el *mundo* sigue
 170 su marcha, debido al *lock* global del recolector y que los hilos usan
 171 servicios de éste.
 172
 173 El código de ``concpu`` es el siguiente::
 174
 175    import tango.core.Thread: Thread;
 176    import tango.core.Atomic: Atomic;
 177    import tango.io.device.File: File;
 178    import tango.util.digest.Sha512: Sha512;
 179    import tango.util.Convert: to;
 180
 181    auto N = 100;
 182    auto NT = 2;
 183    ubyte[] BYTES;
 184    Atomic!(int) running;
 185
 186    void main(char[][] args)
 187    {
 188       auto fname = args[0];
 189       if (args.length > 3)
 190          fname = args[3];
 191       if (args.length > 2)
 192          NT = to!(int)(args[2]);
 193       if (args.length > 1)
 194          N = to!(int)(args[1]);
 195       N /= NT;
 196       running.store(NT);
 197       BYTES = cast(ubyte[]) File.get(fname);
 198       auto threads = new Thread[NT];
 199       foreach(ref thread; threads) {
 200          thread = new Thread(&doSha);
 201          thread.start();
 202       }
 203       while (running.load()) {
 204          auto a = new void[](BYTES.length / 4);
 205          a[] = cast(void[]) BYTES[];
 206          Thread.yield();
 207       }
 208       foreach(thread; threads)
 209          thread.join();
 210    }
 211
 212    void doSha()
 213    {
 214       auto sha = new Sha512;
 215       for (size_t i = 0; i < N; i++)
 216          sha.update(BYTES);
 217       running.decrement();
 218    }
 219
 220 El código de ``conalloc`` es igual excepto por la función ``doSha()``, que es
 221 de la siguiente manera::
 222
 223    void doSha()
 224    {
 225       for (size_t i = 0; i < N; i++) {
 226          auto sha = new Sha512;
 227          sha.update(BYTES);
 228       }
 229       running.decrement();
 230    }
 231
 232
 233 ``mcore``
 234 ^^^^^^^^^
 235 Escrito por David Schima y también hallado__ en el grupo de noticias de D_,
 236 este programa pretende mostrar como afecta el *lock* global del recolector
 237 en ambientes *multi-core*, incluso cuando a simple vista parecen no utilizarse
 238 servicios del recolector::
 239
 240    import tango.core.Thread;
 241
 242    void main()
 243    {
 244       enum { nThreads = 4 };
 245       auto threads = new Thread[nThreads];
 246       foreach (ref thread; threads) {
 247          thread = new Thread(&doAppending);
 248          thread.start();
 249       }
 250       foreach (thread; threads)
 251          thread.join();
 252    }
 253
 254    void doAppending()
 255    {
 256       uint[] arr;
 257       for (size_t i = 0; i < 1_000_000; i++)
 258          arr ~= i;
 259    }
 260
 261 __ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=103563
 262
 263 El secreto está en que la concatenación de arreglos utiliza por detrás
 264 servicios del recolector, por lo tanto un programa multi-hilo en el cual los
 265 hilos (aparentemente) no comparten ningún estado, se puede ver
 266 considerablemente afectado por el recolector (siendo este efecto más visible
 267 en ambientes *multi-core* por el nivel de sincronización extra que significa
 268 a nivel de *hardware*). Cabe destacar que, sin embargo, en Linux_ no es tan
 269 notorio.
 270
 271
 272 ``split``
 273 ^^^^^^^^^
 274 Este programa trivial lee un archivo de texto y genera un arreglo de cadenas
 275 de texto resultantes de partir el texto en palabras. Fue escrito por Leonardo
 276 Maffi y también hallado__ en el grupo de noticias de D_. Su objetivo era
 277 mostrar lo ineficiente que puede ser concatenar datos a un mismo arreglo
 278 repetidas veces y ha desembocado en una pequeña `optimización`__ que sirvió
 279 para apalear el problema de forma razonablemente efectiva.
 280
 281 El código es el siguiente::
 282
 283    import tango.io.device.File: File;
 284    import tango.text.Util: delimit;
 285    import tango.util.Convert: to;
 286
 287    int main(char[][] args) {
 288       if (args.length < 2)
 289          return 1;
 290       auto txt = cast(byte[]) File.get(args[1]);
 291       auto n = (args.length > 2) ? to!(uint)(args[2]) : 1;
 292       if (n < 1)
 293          n = 1;
 294       while (--n)
 295          txt ~= txt;
 296       auto words = delimit!(byte)(txt, cast(byte[]) " \t\n\r");
 297       return !words.length;
 298    }
 299
 300 __ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=67673
 301 __ http://d.puremagic.com/issues/show_bug.cgi?id=1923
 302
 303
 304 ``rnddata``
 305 ^^^^^^^^^^^
 306 Este programa fue escrito por Oskar Linde y nuevamente hallado__ en el grupo
 307 de noticias. Fue construido para mostrar como el hecho de que el recolector
 308 sea conservativo puede hacer que al leer datos binarios hayan muchos *falsos
 309 punteros* que mantengan vivas celdas que en realidad ya no deberían ser
 310 accesibles desde el *root set* del grafo de conectividad.
 311
 312 __ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=46407
 313
 314 El código del programa es el siguiente::
 315
 316    import tango.math.random.Random;
 317
 318    const IT = 125; // number of iterations, each creates an object
 319    const BYTES = 1_000_000; // ~1MiB per object
 320    const N = 50; // ~50MiB of initial objects
 321
 322    class C
 323    {
 324       C c; // makes the compiler not set NO_SCAN
 325       long[BYTES/long.sizeof] data;
 326    }
 327
 328    void main() {
 329       auto rand = new Random();
 330       C[] objs;
 331             objs.length = N;
 332       foreach (ref o; objs) {
 333          o = new C;
 334          foreach (ref x; o.data)
 335             rand(x);
 336       }
 337       for (int i = 0; i < IT; ++i) {
 338          C o = new C;
 339          foreach (ref x; o.data)
 340             rand(x);
 341          // do something with the data...
 342       }
 343    }
 344
 345
 346 ``sbtree``
 347 ^^^^^^^^^^
 348 Este programa está basado en la prueba de nombre ``binary-trees`` de `The
 349 Computer Language Benchmarks Game`__, una colección de 12 programas escritos
 350 en alrededor de 30 lenguajes de programación para comparar su eficiencia
 351 (medida en tiempo de ejecución, uso de memoria y cantidad de líneas de
 352 código). De este juego de programas se utilizó solo ``binary-trees`` por ser
 353 el único destinado a ejercitar el manejo de memoria. El programa sólo manipula
 354 árboles binarios, creándolos y recorriéndolos inmediatamente (no realiza
 355 ningún trabajo útil). La traducción a D_ fue realizada por Andrey Khropov
 356 y fue hallada__ en el grupo de noticias.
 357
 358 __ http://shootout.alioth.debian.org/
 359 __ http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=43991
 360
 361 El código fuente es el siguiente::
 362
 363    import tango.util.Convert;
 364    alias char[] string;
 365
 366    int main(string[] args)
 367    {
 368       int N = args.length > 1 ? to!(int)(args[1]) : 1;
 369       int minDepth = 4;
 370       int maxDepth = (minDepth + 2) > N ? minDepth + 2 : N;
 371       int stretchDepth = maxDepth + 1;
 372       int check = TreeNode.BottomUpTree(0, stretchDepth).ItemCheck;
 373       TreeNode longLivedTree = TreeNode.BottomUpTree(0, maxDepth);
 374       for (int depth = minDepth; depth <= maxDepth; depth += 2) {
 375          int iterations = 1 << (maxDepth - depth + minDepth);
 376          check = 0;
 377          for (int i = 1; i <= iterations; i++) {
 378             check += TreeNode.BottomUpTree(i, depth).ItemCheck;
 379             check += TreeNode.BottomUpTree(-i, depth).ItemCheck;
 380          }
 381       }
 382       return 0;
 383    }
 384
 385    class TreeNode
 386    {
 387       TreeNode left, right;
 388       int item;
 389
 390       this(int item, TreeNode left = null, TreeNode right = null)
 391       {
 392          this.item = item;
 393          this.left = left;
 394          this.right = right;
 395       }
 396
 397       static TreeNode BottomUpTree(int item, int depth)
 398       {
 399          if (depth > 0)
 400             return new TreeNode(item,
 401                   BottomUpTree(2 * item - 1, depth - 1),
 402                   BottomUpTree(2 * item, depth - 1));
 403          return new TreeNode(item);
 404       }
 405
 406       int ItemCheck()
 407       {
 408          if (left)
 409             return item + left.ItemCheck() - right.ItemCheck();
 410          return item;
 411       }
 412    }
 413
 414
 415 Programas pequeños
 416 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 417
 418 Todos los pequeños programas utilizados como parte del banco de prueba
 419 provienen del `Olden Benchmark`__ [CAR95]_. Estos programas fueron diseñados
 420 para probar el lenguaje de programación Olden__; un lenguaje diseñado para
 421 paralelizar programas automáticamente en arquitecturas con memoria
 422 distribuida. Son programas relativamente pequeños (entre 400 y 1000 líneas de
 423 código fuente cada uno) que realizan una tarea secuencial que aloca
 424 estructuras de datos dinámicamente. Las estructuras están usualmente
 425 organizadas como listas o árboles, y muy raramente como arreglos. Los
 426 programas pasan la mayor parte del tiempo alocando datos y el resto usando los
 427 datos alocados, por lo que en general están acotados en tiempo por el uso de
 428 memoria (y no de procesador).
 429
 430 __ http://www.irisa.fr/caps/people/truong/M2COct99/Benchmarks/Olden/Welcome.html
 431 __ http://www.martincarlisle.com/olden.html
 432
 433 La traducción a D_ fue realizada por Leonardo Maffi y están basadas a su vez
 434 en la traducción de este juego de pruebas a Java_, JOlden__ [CMK01]_. En
 435 general (salvo para el programa ``voronoï``) está disponible el código fuente
 436 portado a D_, Java_ y Python_, e incluso varias versiones con distintas
 437 optimizaciones para reducir el consumo de tiempo y memoria. Además provee
 438 comparaciones de tiempo entre todas ellas. Los programas utilizados en este
 439 banco de pruebas son la versión traducida más literalmente de Java_ a D_, ya
 440 que hace un uso más intensivo del recolector que las otras versiones.
 441
 442 __ http://www-ali.cs.umass.edu/DaCapo/benchmarks.html
 443
 444 A continuación se da una pequeña descripción de cada uno de los 5 programas
 445 traducidos y los enlaces en donde encontrar el código fuente (y las
 446 comparaciones de tiempos estar disponibles).
 447
 448
 449 ``bh``
 450 ^^^^^^
 451 Este programa computa las interacciones gravitatorias entre un número
 452 :math:`N` de cuerpos en tiempo :math:`O(N log N)` y está basado en árboles
 453 heterogéneos de 8 ramas, según el algoritmo descripto por Barnes & Hut
 454 [BH86]_.
 455
 456 Código fuente disponible en:
 457 http://www.fantascienza.net/leonardo/js/dolden_bh.zip
 458
 459
 460 ``bisort``
 461 ^^^^^^^^^^
 462 Este programa ordena :math:`N` números, donde :math:`N` es una potencia de 2,
 463 usando un ordenamiento *Bitonic* adaptativo, un algoritmo paralelo óptimo para
 464 computadoras con memoria compartida, según describen Bilardi & Nicolau
 465 [BN98]_. Utiliza árboles binarios como principal estructuras de datos.
 466
 467 Código fuente disponible en:
 468 http://www.fantascienza.net/leonardo/js/dolden_bisort.zip
 469
 470
 471 ``em3d``
 472 ^^^^^^^^
 473 Este programa modela la propagación de ondas electromagnéticas a través de
 474 objetos en 3 dimensiones. Realiza un cálculo simple sobre un grafo irregular
 475 bipartito (implementado utilizando listas simplemente enlazadas) cuyos nodos
 476 representan valores de campo eléctrico y magnético. El algoritmo es el
 477 descripto por Culler, et al. [CDG93]_.
 478
 479 Código fuente disponible en:
 480 http://www.fantascienza.net/leonardo/js/dolden_em3d.zip
 481
 482
 483 ``tsp``
 484 ^^^^^^^
 485 Este programa implementa una heurística para resolver el problema del viajante
 486 (*traveling salesman problem*) utilizando árboles binarios balanceados. El
 487 algoritmo utilizado es el descripto por Karp [KAR77]_.
 488
 489
 490 Código fuente disponible en:
 491 http://www.fantascienza.net/leonardo/js/dolden_tsp.zip
 492
 493
 494 ``voronoï``
 495 ^^^^^^^^^^^
 496 Este programa genera un conjunto aleatorio de puntos y computa su diagrama de
 497 Voronoï, una construcción geométrica que permite construir una partición del
 498 plano euclídeo, utilizando el algoritmo descripto por Guibas & Stolfi [GS85]_.
 499
 500 Código fuente disponible en: http://codepad.org/xGDCS3KO
 501
 502
 503 Programas *reales*
 504 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 505
 506 Dil_ (escrito en su mayor parte por Aziz Köksal y publicado bajo licencia
 507 GPL_) es, lamentablemente, el único programa real hallado que, a pesar de
 508 estar incompleto, es lo suficientemente grande, mantenido y estable como para
 509 ser incluido en el banco de pruebas. Se trata de un compilador de D_ escrito
 510 en D_ y está incompleto porque no puede generar código (falta implementar el
 511 análisis semántico y la generación de código), por lo que es principalmente
 512 utilizado para generar documentación a partir del código.
 513
 514 El programa está compuesto por:
 515
 516 * 32.000 líneas de código fuente (aproximadamente).
 517 * 86 módulos (o archivos).
 518 * 322 diferentes tipos de datos definidos por el usuario, de los cuales 34 son
 519   tipos *livianos* (``struct``) y 288 tipos polimórficos (``class``), de los
 520   que 260 son subtipos (sub-clases).
 521
 522 Puede observarse entonces que a pesar de ser incompleto, es una pieza de
 523 software bastante compleja y de dimensión considerable.
 524
 525 Además, al interpretar código fuente se hace un uso intensivo de cadenas de
 526 texto que en general presentan problemas muy particulares por poder ser
 527 objetos extremadamente pequeños y de tamaños poco convencionales (no múltiplos
 528 de palabras, por ejemplo). A su vez, el texto interpretado es convertido a una
 529 representación interna en forma de árbol (o *árbol de sintaxis abstracta*)
 530 modelado por tipos *livianos* y polimórficos que están organizados en arreglos
 531 dinámicos contiguos y asociativos (que usan muchos servicios del recolector),
 532 y que finalmente son manipulados para obtener y generar la información
 533 necesaria, creando y dejando *morir* objetos constantemente (pero no como única
 534 forma de procesamiento, como otras pruebas sintetizadas).
 535
 536 Por último, a diferencia de muchos otros programas escritos en D_, que dadas
 537 algunas de las ineficiencias del recolector invierten mucho trabajo en limitar
 538 su uso, este programa no está escrito pensando en dichas limitaciones, por lo
 539 que muestra un funcionamiento muy poco sesgado por estas infortunadas
 540 circunstancias.
 541
 542 Por todas estas razones, Dil_ es el ejemplar que tal vez mejor sirve a la hora
 543 de medir de forma realista los resultados obtenidos o los avances realizados.
 544 Si bien, como se ha dicho anteriormente, las demás pruebas del banco pueden
 545 ser útiles para encontrar problemas muy particulares, está es la que da una
 546 lectura más cercana a la realidad del uso de un recolector.
 547
 548
 549
 550 Modificaciones propuestas
 551 ----------------------------------------------------------------------------
 552
 553 TODO
 554
 555
 556
 557 Resultados
 558 ----------------------------------------------------------------------------
 559
 560 TODO
 561
 562
 563
 564 .. include:: links.rst
 565
 566 .. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :