binary-trees benchmark hypotheses non fingo

↓ Allocate and deallocate many many binary trees, N=20.

Which programs used least Code? Which programs use highly optimised assembly code libraries? Which programs make use of all the processor cores?

    sort sort sort sort
  ×   Program & Logs CPU secs Elapsed secs Memory KB Code B ~ CPU Load
1.0GNU gcc #7 15.046.30151,220850  42% 25% 84% 69%
1.4GNU gcc #2 31.918.64115,5041641  88% 95% 88% 99%
1.4C++ GNU g++ #6 28.559.01357,820892  71% 62% 95% 82%
2.3Java 6 steady state #2 17.7514.741,016,984675  48% 31% 17% 24%
2.6Java 6 -server #2 20.5316.18566,032603  13% 86% 16% 11%
2.6ATS 16.3416.36198,4241060  0% 0% 100% 0%
2.7Scala #4 20.5316.95555,044536  14% 12% 83% 12%
2.8Haskell GHC #2 56.5217.76439,872544  77% 76% 78% 82%
2.9GNU gcc #5 68.1418.58503,380963  94% 84% 97% 91%
3.9Haskell GHC 42.1424.87357,532512  23% 23% 23% 100%
4.0OCaml #2 89.5725.32157,664784  82% 85% 95% 90%
4.6Erlang HiPE #2 77.9029.24356,996499  59% 58% 59% 88%
5.4GNU gcc 33.7233.73131,820706  1% 100% 1% 1%
5.7C++ GNU g++ #2 35.6135.62197,836553  0% 0% 100% 0%
6.0Ada 2005 GNAT 37.5937.59198,160955  100% 0% 0% 0%
6.1Lisp SBCL 38.2738.27414,792612  0% 0% 0% 100%
6.8Erlang HiPE 42.8142.79374,704441  66% 34% 0% 0%
7.1Clean #3 44.8144.81262,704539  0% 0% 100% 0%
7.4Fortran Intel 46.5446.55131,540826  0% 0% 0% 100%
9.8GNU gcc #4 61.5261.53289,980672  0% 100% 0% 0%
10Pascal Free Pascal 62.7762.77131,292769  0% 0% 100% 0%
13Scheme PLT #2 80.6380.62452,364503  0% 100% 0% 0%
14C# Mono #2 88.4288.42454,284650  0% 0% 0% 100%
19JavaScript V8 117.79117.79386,944467  2% 100% 0% 0%
20Java 6 -Xint #2 136.24128.46526,792603  4% 3% 95% 3%
28F# Mono 175.99175.99373,132587  0% 100% 0% 0%
40Go 6g 8g 250.04250.05326,888527  100% 0% 0% 0%
40Smalltalk VisualWorks 255.00255.00197,716722  0% 100% 0% 0%
42Ruby JRuby 5 min264.082,053,612412  20% 74% 23% 15%
60Python CPython #6 22 min6 min1,373,400626  96% 85% 85% 84%
104Lua 10 min10 min1,688,964443  0% 1% 0% 100%
108Lua #2 11 min11 min1,683,288446  30% 16% 0% 54%
199Ruby MRI 20 min20 min781,228412  0% 0% 100% 0%
203Perl #2 21 min21 min1,091,276541  0% 0% 100% 0%
213PHP #2 22 min22 min2,311,980493  0% 0% 100% 0%
469Python CPython #2 49 min49 min445,700365  79% 20% 1% 0%
JavaScript TraceMonkey Failed467
PHP Timed Out3h 00 min1089
interesting alternative programs
1.8Clean 11.0411.04132,172538
2.6Haskell GHC #3 52.5716.58443,968544
4.0Go 6g 8g #2 25.2725.27227,472719
69Lua #3 435.97435.96997,008470

 binary-trees benchmark : Allocate and deallocate many many binary trees

diff program output N = 10 with this 1KB output file to check your program is correct before contributing.

Each program should

Note: this is an adaptation of a benchmark for testing GC so we are interested in the whole tree being allocated before any nodes are GC'd - which probably excludes lazy evaluation.

Note: the left subtrees are heads of the right subtrees, keeping a depth counter in the accessors to avoid duplication is cheating!

Note: the tree should have tree-nodes all the way down, replacing the bottom nodes by some other value is not acceptable; and the bottom nodes should be at depth 0.

Note: these programs are being measured with the default initial heap size - the measurements may be very different with a larger initial heap size or GC tuning.

Please don't implement your own custom memory pool or free list.


The binary-trees benchmark is a simplistic adaptation of Hans Boehm's GCBench, which in turn was adapted from a benchmark by John Ellis and Pete Kovac.

Thanks to Christophe Troestler and Einar Karttunen for help with this benchmark.

Revised BSD license