How big is the measured performance difference?
Each chart bar shows how many times more Time or how many times more Memory one unidentified ↓ binary-trees program used, compared to the program that used least Time or the program that used least Memory.
binary-trees benchmark N=20
This table shows 5 measurements - CPU Time, Elapsed Time, Memory, Code and ~ CPU Load.
Compare how much Memory the binary-trees programs used - sort Memory KB. Compare how much Code the programs used - sort Code B
Column × shows how many times more each program used compared to the program that used least.
| sort | sort | sort | sort | |||
|---|---|---|---|---|---|---|
| × | Program Source Code | CPU secs | Elapsed secs | Memory KB | Code B | ~ CPU Load |
| 1.0 | C GNU gcc #7 | 13.71 | 5.10 | 100,688 | 850 | 50% 34% 85% 81% |
| 1.2 | C++ GNU g++ #6 | 18.86 | 6.32 | 173,332 | 892 | 60% 74% 74% 71% |
| 3.0 | Java 6 steady state #2 | 28.76 | 15.40 | 855,996 | 675 | 52% 46% 41% 48% |
| 3.0 | OCaml #2 | 54.09 | 15.45 | 78,852 | 784 | 81% 100% 79% 90% |
| 3.3 | ATS | 16.84 | 16.84 | 132,040 | 1060 | 0% 0% 100% 0% |
| 3.8 | Java 6 -server #2 | 29.63 | 19.18 | 289,920 | 603 | 24% 75% 27% 28% |
| 3.8 | Erlang HiPE #2 | 55.33 | 19.28 | 179,688 | 499 | 68% 68% 61% 90% |
| 4.2 | Scala #4 | 34.11 | 21.21 | 292,472 | 536 | 64% 29% 43% 24% |
| 4.5 | C GNU gcc #5 | 83.67 | 23.01 | 258,892 | 963 | 88% 86% 98% 90% |
| 5.1 | Lisp SBCL | 25.83 | 25.83 | 231,576 | 612 | 2% 0% 0% 100% |
| 6.0 | Clean #3 | 30.73 | 30.73 | 131,592 | 539 | 0% 0% 0% 100% |
| 6.1 | Pascal Free Pascal | 31.29 | 31.28 | 65,620 | 769 | 0% 100% 0% 0% |
| 6.3 | C GNU gcc #2 | 123.14 | 32.17 | 58,048 | 1641 | 93% 91% 100% 98% |
| 6.5 | Haskell GHC | 49.53 | 33.05 | 194,792 | 512 | 17% 58% 57% 17% |
| 6.6 | Haskell GHC #2 | 64.26 | 33.48 | 221,464 | 544 | 48% 40% 55% 42% |
| 6.9 | C GNU gcc | 34.95 | 34.95 | 66,168 | 706 | 0% 0% 0% 100% |
| 7.9 | Erlang HiPE | 40.37 | 40.29 | 188,380 | 441 | 96% 4% 0% 0% |
| 8.0 | C++ GNU g++ #2 | 40.71 | 40.71 | 99,396 | 553 | 0% 0% 0% 100% |
| 8.6 | Ada 2005 GNAT | 44.09 | 44.08 | 99,580 | 955 | 0% 0% 100% 0% |
| 9.3 | C# Mono #2 | 83.43 | 47.30 | 235,596 | 650 | 26% 25% 100% 25% |
| 9.4 | Fortran Intel | 48.06 | 48.06 | 65,936 | 826 | 0% 0% 0% 100% |
| 13 | C GNU gcc #4 | 65.92 | 65.92 | 139,208 | 672 | 100% 0% 0% 0% |
| 14 | Scheme PLT #2 | 71.74 | 71.74 | 253,944 | 503 | 100% 0% 0% 0% |
| 19 | JavaScript V8 | 95.20 | 95.21 | 188,024 | 467 | 0% 0% 100% 0% |
| 23 | Java 6 -Xint #2 | 132.08 | 119.49 | 289,060 | 603 | 7% 91% 7% 6% |
| 27 | Smalltalk VisualWorks | 138.23 | 138.22 | 121,988 | 722 | 0% 1% 0% 100% |
| 29 | Lua LuaJIT #2 | 149.33 | 149.34 | 877,752 | 446 | 0% 100% 0% 0% |
| 30 | Lua LuaJIT | 153.21 | 153.21 | 953,400 | 443 | 0% 100% 0% 2% |
| 34 | F# Mono | 173.57 | 173.57 | 237,064 | 587 | 0% 0% 100% 0% |
| 35 | Mozart/Oz | 178.37 | 178.37 | 448,028 | 479 | 0% 0% 0% 100% |
| 38 | Go 6g 8g | 194.92 | 194.91 | 249,884 | 527 | 0% 100% 0% 0% |
| 38 | Python 3 #6 | 12 min | 195.42 | 695,172 | 626 | 92% 91% 92% 97% |
| 53 | Ruby 1.9 | 267.96 | 267.89 | 299,944 | 412 | 0% 0% 100% 0% |
| 54 | Ruby JRuby | 6 min | 273.45 | 1,406,184 | 412 | 26% 32% 17% 64% |
| 58 | Python CPython #6 | 17 min | 296.77 | 674,488 | 626 | 85% 85% 86% 97% |
| 98 | PHP | 27 min | 8 min | 1,199,756 | 1089 | 77% 78% 96% 76% |
| 103 | Lua | 8 min | 8 min | 815,616 | 443 | 47% 53% 0% 0% |
| 103 | Lua #2 | 8 min | 8 min | 812,172 | 446 | 1% 9% 92% 0% |
| 210 | Ruby MRI | 17 min | 17 min | 457,788 | 412 | 1% 100% 1% 1% |
| 253 | Perl #2 | 21 min | 21 min | 643,488 | 541 | 0% 0% 100% 0% |
| 290 | PHP #2 | 24 min | 24 min | 1,220,408 | 493 | 0% 0% 0% 100% |
| 445 | Python CPython #2 | 37 min | 37 min | 221,588 | 365 | 26% 75% 2% 1% |
| JavaScript TraceMonkey | Failed | 467 | ||||
| interesting alternative programs | ||||||
| 2.1 | Clean | 10.63 | 10.63 | 66,572 | 538 | |
| Lisaac #2 | Failed | 691 | ||||
| 4.4 | Go 6g 8g #2 | 22.20 | 22.20 | 111,304 | 719 | |
| 6.5 | Haskell GHC #3 | 62.70 | 32.99 | 223,512 | 544 | |
| 35 | Lua LuaJIT #3 | 177.52 | 177.51 | 547,768 | 470 | |
| 75 | Lua #3 | 382.57 | 382.56 | 551,244 | 470 | |
| missing programs | ||||||
| Lisaac | No program | |||||
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.