GHC's GC default heap growth strategy is not as good as other runtimes

This is a GC performance ticket. The benchmark is the binary-trees benchmark, and the issue is whether or not GHC's ability to grow the heap without a heap check is comparably worse than other similar language runtimes.

Looking at the binary-trees benchmark, we see that GHC does very well on a parallel system, when we give a GC hint to the size.

E.g. the attached binary-trees program is very very competitive:

Compile with:

    ghc -O2 -fasm --make -threaded A.hs 

Run with:

    $ /A 20  +RTS -N4 -H340M

And we get:

    $ time ./A +RTS -N4 -H340M -RTS 20          
stretch tree of depth 21	 check: -1
2097152	 trees of depth 4	 check: -2097152
524288	 trees of depth 6	 check: -524288
131072	 trees of depth 8	 check: -131072
32768	 trees of depth 10	 check: -32768
8192	 trees of depth 12	 check: -8192
2048	 trees of depth 14	 check: -2048
512	 trees of depth 16	 check: -512
128	 trees of depth 18	 check: -128
32	 trees of depth 20	 check: -32
long lived tree of depth 20	 check: -1
./A +RTS -N4 -H340M -RTS 20  17.08s user 0.30s system 315% cpu 5.511 total

However, without that GC hint performance deteriorates dramatically,

$ time ./A +RTS -N4  -RTS 20      
stretch tree of depth 21	 check: -1
2097152	 trees of depth 4	 check: -2097152
524288	 trees of depth 6	 check: -524288
131072	 trees of depth 8	 check: -131072
32768	 trees of depth 10	 check: -32768
8192	 trees of depth 12	 check: -8192
2048	 trees of depth 14	 check: -2048
512	 trees of depth 16	 check: -512
128	 trees of depth 18	 check: -128
32	 trees of depth 20	 check: -32
long lived tree of depth 20	 check: -1
./A +RTS -N4 -RTS 20  33.83s user 0.42s system 136% cpu 25.033 total

So 5x slow down.

Could the GC heap growth algorithm be tuned? Other language runtimes, that are slower than Haskell's on this benchmark when our GC hint is in play, don't seem to suffer as badly without the hint:

http://shootout.alioth.debian.org/u64q/benchmark.php?test=binarytrees&lang=all

See e.g. Erlang. So: is there a better growth algorithm?

Trac metadata

Trac field	Value
Version	6.10.1
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Runtime System
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture