[BDW-GC] Performance comparison for the two GCs

[Ludovic Courtès]

Hello!

I finally took the time to re-run the benchmarks used in Hansen's PhD
dissertation [0] and which are under `gc-benchmarks' in the repo.  The
methodology is still the same as before [1].  This correspond to commits
0e0d97c477b160f193b289b4aabfa73bbaf52e9b (boehm-demers-weiser-gc) and
ce3ed0125fcfb9ad09da815f133a2320102d164c (master).

`run-benchmarks' now produces bars on the right, which show whether (and
how much) BDW-GC is better/worse than Guile's current GC: `+' means
"better" and `-' means "worse".  "Better", here, means one of the
following scenarios:

  A. BDW-GC uses less heap and is faster.
  B. BDW-GC uses less heap and is slower but the outcome is positive
     (e.g., it is twice as slow and the heap is 4 times smaller).
  C. BDW-GC uses more heap and is faster but the outcome is positive
     (e.g., it uses twice as much heap and is 4 times faster).

For details on how the bar length is computed, see [2].

Note that heap size and execution time are the only criteria here.
Other criteria, such as pause time [3], may be of interest depending on
the application, but presumably memory and speed are those most people
care about.


1. Large-Heap Benchmarks
------------------------

benchmark: `./string.scm'
                       heap size (MiB)  execution time (s.)
Guile                   707.12 (1.00x)      7.247 (1.00x)
BDW-GC, FSD=3           258.84 (0.37x)      3.761 (0.52x) ++++++++++
BDW-GC, FSD=6           256.21 (0.36x)      3.101 (0.43x) ++++++++++
BDW-GC, FSD=9           311.58 (0.44x)      3.153 (0.44x) ++++++++
BDW-GC, FSD=3 incr.     468.72 (0.66x)      3.646 (0.50x) +++++
BDW-GC, FSD=3 gene.     488.08 (0.69x)      3.526 (0.49x) +++++

benchmark: `./larceny/dynamic.sch'
                       heap size (MiB)  execution time (s.)
Guile                    87.19 (1.00x)     16.578 (1.00x)
BDW-GC, FSD=3           100.35 (1.15x)     15.422 (0.93x) --
BDW-GC, FSD=6            82.96 (0.95x)     16.608 (1.00x) +
BDW-GC, FSD=9            74.90 (0.86x)     18.012 (1.09x) ++
BDW-GC, FSD=3 incr.     108.25 (1.24x)     16.590 (1.00x) ----
BDW-GC, FSD=3 gene.      97.34 (1.12x)     15.548 (0.94x) --

benchmark: `./larceny/perm.sch'
                       heap size (MiB)  execution time (s.)
Guile                    28.88 (1.00x)      0.934 (1.00x)
BDW-GC, FSD=3            27.75 (0.96x)      0.824 (0.88x) +
BDW-GC, FSD=6            30.74 (1.06x)      1.021 (1.09x) -
BDW-GC, FSD=9            34.77 (1.20x)      1.151 (1.23x) ---
BDW-GC, FSD=3 incr.      33.55 (1.16x)      0.891 (0.95x) --
BDW-GC, FSD=3 gene.      28.03 (0.97x)      0.949 (1.02x) 

benchmark: `./larceny/graphs.sch'
                       heap size (MiB)  execution time (s.)
Guile                    30.75 (1.00x)    425.026 (1.00x)
BDW-GC, FSD=3            60.08 (1.95x)    159.148 (0.37x) +++++++++
BDW-GC, FSD=6            48.46 (1.58x)    202.383 (0.48x) ++++++++
BDW-GC, FSD=9            42.31 (1.38x)    249.425 (0.59x) ++++++
BDW-GC, FSD=3 incr.     124.86 (4.06x)    165.998 (0.39x) ++++++++
BDW-GC, FSD=3 gene.      58.80 (1.91x)    156.682 (0.37x) +++++++++

benchmark: `./larceny/gcold.scm'
                       heap size (MiB)  execution time (s.)
Guile                   278.39 (1.00x)    103.479 (1.00x)
BDW-GC, FSD=3           108.50 (0.39x)    258.024 (2.49x) +
BDW-GC, FSD=6            89.84 (0.32x)    391.099 (3.78x) -----
BDW-GC, FSD=9            76.31 (0.27x)    531.270 (5.13x) ------------
BDW-GC, FSD=3 incr.      91.18 (0.33x)    211.965 (2.05x) +++
BDW-GC, FSD=3 gene.     107.51 (0.39x)    195.811 (1.89x) ++++

benchmark: `./gcbench.scm'
                       heap size (MiB)  execution time (s.)
Guile                    52.27 (1.00x)     20.900 (1.00x)
BDW-GC, FSD=3            50.75 (0.97x)     14.956 (0.72x) +
BDW-GC, FSD=6            44.32 (0.85x)     14.742 (0.71x) +++
BDW-GC, FSD=9            45.05 (0.86x)     15.189 (0.73x) ++
BDW-GC, FSD=3 incr.      95.84 (1.83x)     18.585 (0.89x) -----------
BDW-GC, FSD=3 gene.      81.64 (1.56x)     17.074 (0.82x) -------


Scenario A (wins on both criteria) is uncommon (gcbench, perm, string).
Scenario C (faster) is the most common, with the exception of gcold.
BDW-GC is often worse in incremental and generational modes.


2. Small-Heap Benchmarks (< 10 MiB)
-----------------------------------

benchmark: `./larceny/lattice.sch'
                       heap size (MiB)  execution time (s.)
Guile                     3.51 (1.00x)    147.189 (1.00x)
BDW-GC, FSD=3             7.05 (2.01x)     88.755 (0.60x) ++++++
BDW-GC, FSD=6             5.14 (1.47x)    100.515 (0.68x) +++++
BDW-GC, FSD=9             4.64 (1.32x)    115.124 (0.78x) +++
BDW-GC, FSD=3 incr.       5.55 (1.58x)    103.257 (0.70x) ++++
BDW-GC, FSD=3 gene.       6.96 (1.99x)     96.383 (0.65x) +++++

benchmark: `./larceny/nucleic2.sch'
                       heap size (MiB)  execution time (s.)
Guile                     6.43 (1.00x)     33.663 (1.00x)
BDW-GC, FSD=3             9.04 (1.41x)     23.043 (0.68x) ++++
BDW-GC, FSD=6             7.52 (1.17x)     31.578 (0.94x) +
BDW-GC, FSD=9             7.09 (1.10x)     35.227 (1.05x) -
BDW-GC, FSD=3 incr.       8.81 (1.37x)     29.018 (0.86x) ++
BDW-GC, FSD=3 gene.      11.47 (1.78x)     25.480 (0.76x) +++

benchmark: `./larceny/sboyer.sch'
                       heap size (MiB)  execution time (s.)
Guile                     4.09 (1.00x)      3.390 (1.00x)
BDW-GC, FSD=3             7.05 (1.72x)      3.131 (0.92x) -------
BDW-GC, FSD=6             5.14 (1.26x)      3.233 (0.95x) --
BDW-GC, FSD=9             4.64 (1.13x)      3.109 (0.92x) -
BDW-GC, FSD=3 incr.       7.27 (1.78x)      3.250 (0.96x) -------
BDW-GC, FSD=3 gene.       8.98 (2.20x)      3.107 (0.92x) ------------

benchmark: `./larceny/nboyer.sch'
                       heap size (MiB)  execution time (s.)
Guile                     5.41 (1.00x)      2.929 (1.00x)
BDW-GC, FSD=3             9.04 (1.67x)      2.726 (0.93x) --------
BDW-GC, FSD=6             6.57 (1.21x)      2.705 (0.92x) --
BDW-GC, FSD=9             5.92 (1.09x)      2.937 (1.00x) -
BDW-GC, FSD=3 incr.      12.30 (2.27x)      3.050 (1.04x) ----------------
BDW-GC, FSD=3 gene.      14.81 (2.74x)      2.870 (0.98x) ----------------------

benchmark: `./larceny/earley.sch'
                       heap size (MiB)  execution time (s.)
Guile                     4.43 (1.00x)      0.793 (1.00x)
BDW-GC, FSD=3             7.05 (1.59x)      0.738 (0.93x) ---------
BDW-GC, FSD=6             5.80 (1.31x)      0.781 (0.98x) -----
BDW-GC, FSD=9             5.45 (1.23x)      0.812 (1.02x) ---
BDW-GC, FSD=3 incr.       8.82 (1.99x)      0.869 (1.10x) ---------------
BDW-GC, FSD=3 gene.      11.83 (2.67x)      0.808 (1.02x) 
-------------------------

On these small-heap programs, BDW-GC is often worse: it has a comparable
or slightly lower execution time but uses more heap than Guile's GC.
Presumably such cases would benefit from having libgc compiled with
`SMALL_CONFIG'.


I'll be working on merging the `boehm-demers-weiser-gc' branch in the
next few days and hopefully we won't look back!

Thanks,
Ludo'.

[0] http://www.ccs.neu.edu/home/will/GC/sourcecode.html
[1] http://lists.gnu.org/archive/html/guile-devel/2008-11/msg00001.html
[2] 
http://git.savannah.gnu.org/cgit/guile.git/commit/?id=b529eb5797ca0f62e0c57fcfde8e43c5fb00b3c0
[3] http://lists.gnu.org/archive/html/guile-devel/2007-06/msg00000.html

pgpHi8D_6go05.pgp
Description: PGP signature