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.0 | C GNU gcc #7 | 15.04 | 6.30 | 151,220 | 850 | 42% 25% 84% 69% |
| 1.4 | C GNU gcc #2 | 31.91 | 8.64 | 115,504 | 1641 | 88% 95% 88% 99% |
| 1.4 | C++ GNU g++ #6 | 28.55 | 9.01 | 357,820 | 892 | 71% 62% 95% 82% |
| 2.3 | Java 6 steady state #2 | 17.75 | 14.74 | 1,016,984 | 675 | 48% 31% 17% 24% |
| 2.6 | Java 6 -server #2 | 20.53 | 16.18 | 566,032 | 603 | 13% 86% 16% 11% |
| 2.6 | ATS | 16.34 | 16.36 | 198,424 | 1060 | 0% 0% 100% 0% |
| 2.7 | Scala #4 | 20.53 | 16.95 | 555,044 | 536 | 14% 12% 83% 12% |
| 2.8 | Haskell GHC #2 | 56.52 | 17.76 | 439,872 | 544 | 77% 76% 78% 82% |
| 2.9 | C GNU gcc #5 | 68.14 | 18.58 | 503,380 | 963 | 94% 84% 97% 91% |
| 3.9 | Haskell GHC | 42.14 | 24.87 | 357,532 | 512 | 23% 23% 23% 100% |
| 4.0 | OCaml #2 | 89.57 | 25.32 | 157,664 | 784 | 82% 85% 95% 90% |
| 4.6 | Erlang HiPE #2 | 77.90 | 29.24 | 356,996 | 499 | 59% 58% 59% 88% |
| 5.4 | C GNU gcc | 33.72 | 33.73 | 131,820 | 706 | 1% 100% 1% 1% |
| 5.7 | C++ GNU g++ #2 | 35.61 | 35.62 | 197,836 | 553 | 0% 0% 100% 0% |
| 6.0 | Ada 2005 GNAT | 37.59 | 37.59 | 198,160 | 955 | 100% 0% 0% 0% |
| 6.1 | Lisp SBCL | 38.27 | 38.27 | 414,792 | 612 | 0% 0% 0% 100% |
| 6.8 | Erlang HiPE | 42.81 | 42.79 | 374,704 | 441 | 66% 34% 0% 0% |
| 7.1 | Clean #3 | 44.81 | 44.81 | 262,704 | 539 | 0% 0% 100% 0% |
| 7.4 | Fortran Intel | 46.54 | 46.55 | 131,540 | 826 | 0% 0% 0% 100% |
| 9.8 | C GNU gcc #4 | 61.52 | 61.53 | 289,980 | 672 | 0% 100% 0% 0% |
| 10 | Pascal Free Pascal | 62.77 | 62.77 | 131,292 | 769 | 0% 0% 100% 0% |
| 13 | Scheme PLT #2 | 80.63 | 80.62 | 452,364 | 503 | 0% 100% 0% 0% |
| 14 | C# Mono #2 | 88.42 | 88.42 | 454,284 | 650 | 0% 0% 0% 100% |
| 19 | JavaScript V8 | 117.79 | 117.79 | 386,944 | 467 | 2% 100% 0% 0% |
| 20 | Java 6 -Xint #2 | 136.24 | 128.46 | 526,792 | 603 | 4% 3% 95% 3% |
| 28 | F# Mono | 175.99 | 175.99 | 373,132 | 587 | 0% 100% 0% 0% |
| 40 | Go 6g 8g | 250.04 | 250.05 | 326,888 | 527 | 100% 0% 0% 0% |
| 40 | Smalltalk VisualWorks | 255.00 | 255.00 | 197,716 | 722 | 0% 100% 0% 0% |
| 42 | Ruby JRuby | 5 min | 264.08 | 2,053,612 | 412 | 20% 74% 23% 15% |
| 60 | Python CPython #6 | 22 min | 6 min | 1,373,400 | 626 | 96% 85% 85% 84% |
| 104 | Lua | 10 min | 10 min | 1,688,964 | 443 | 0% 1% 0% 100% |
| 108 | Lua #2 | 11 min | 11 min | 1,683,288 | 446 | 30% 16% 0% 54% |
| 199 | Ruby MRI | 20 min | 20 min | 781,228 | 412 | 0% 0% 100% 0% |
| 203 | Perl #2 | 21 min | 21 min | 1,091,276 | 541 | 0% 0% 100% 0% |
| 213 | PHP #2 | 22 min | 22 min | 2,311,980 | 493 | 0% 0% 100% 0% |
| 469 | Python CPython #2 | 49 min | 49 min | 445,700 | 365 | 79% 20% 1% 0% |
| JavaScript TraceMonkey | Failed | 467 | ||||
| PHP | Timed Out | 3h 00 min | 1089 | |||
| interesting alternative programs | ||||||
| 1.8 | Clean | 11.04 | 11.04 | 132,172 | 538 | |
| 2.6 | Haskell GHC #3 | 52.57 | 16.58 | 443,968 | 544 | |
| 4.0 | Go 6g 8g #2 | 25.27 | 25.27 | 227,472 | 719 | |
| 69 | Lua #3 | 435.97 | 435.96 | 997,008 | 470 | |
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
- define a tree node class and methods, a tree node record and procedures, or an algebraic data type and functions, or…
- allocate a binary tree to 'stretch' memory, check it exists, and deallocate it
- allocate a long-lived binary tree which will live-on while other trees are allocated and deallocated
- allocate, walk, and deallocate many bottom-up binary trees
- allocate a tree
- walk the tree nodes, checksum node items (and maybe deallocate the node)
- deallocate the tree
- check that the long-lived binary tree still exists
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.
