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 | 12.23 | 12.23 | 99,528 | 850 | 0% 0% 0% 100% |
| 1.1 | C++ GNU g++ #6 | 13.47 | 13.47 | 148,652 | 892 | 0% 0% 0% 100% |
| 1.2 | C GNU gcc #2 | 14.51 | 14.51 | 49,924 | 1641 | 0% 0% 0% 100% |
| 1.4 | ATS | 16.87 | 16.87 | 132,040 | 1060 | 0% 0% 0% 100% |
| 2.0 | Java 6 steady state #2 | 24.11 | 24.18 | 840,456 | 675 | 0% 0% 0% 100% |
| 2.1 | Lisp SBCL | 25.82 | 25.82 | 231,576 | 612 | 0% 0% 0% 100% |
| 2.3 | Java 6 -server #2 | 28.21 | 28.35 | 255,460 | 603 | 0% 0% 0% 99% |
| 2.5 | Scala #4 | 29.97 | 30.09 | 256,064 | 536 | 0% 0% 0% 100% |
| 2.5 | Clean #3 | 30.56 | 30.56 | 131,592 | 539 | 0% 0% 1% 100% |
| 2.5 | Pascal Free Pascal | 31.17 | 31.17 | 65,616 | 769 | 0% 0% 0% 100% |
| 2.7 | Haskell GHC | 33.14 | 33.15 | 169,016 | 512 | 0% 0% 0% 100% |
| 2.7 | Haskell GHC #2 | 33.24 | 33.24 | 193,604 | 544 | 0% 6% 0% 100% |
| 2.9 | C GNU gcc | 35.02 | 35.02 | 66,168 | 706 | 0% 0% 0% 100% |
| 3.3 | Erlang HiPE | 40.45 | 40.35 | 187,868 | 441 | 0% 100% 1% 1% |
| 3.3 | C++ GNU g++ #2 | 40.75 | 40.75 | 99,396 | 553 | 1% 6% 0% 100% |
| 3.6 | Ada 2005 GNAT | 44.21 | 44.21 | 99,580 | 955 | 0% 0% 0% 100% |
| 3.7 | OCaml #2 | 44.95 | 44.95 | 78,852 | 784 | 0% 0% 0% 100% |
| 3.9 | Fortran Intel | 47.90 | 47.90 | 65,940 | 826 | 0% 1% 0% 100% |
| 4.1 | Erlang HiPE #2 | 49.83 | 49.85 | 179,000 | 499 | 8% 0% 81% 11% |
| 5.4 | C GNU gcc #5 | 65.74 | 65.73 | 285,936 | 963 | 0% 0% 0% 100% |
| 5.4 | C GNU gcc #4 | 66.29 | 66.29 | 139,208 | 672 | 0% 0% 0% 100% |
| 5.9 | Scheme PLT #2 | 71.76 | 71.76 | 248,520 | 503 | 0% 0% 0% 100% |
| 6.4 | C# Mono #2 | 77.84 | 77.84 | 235,664 | 650 | 0% 0% 0% 100% |
| 7.8 | JavaScript V8 | 95.66 | 95.67 | 188,024 | 467 | 0% 0% 0% 100% |
| 11 | Java 6 -Xint #2 | 128.55 | 128.64 | 257,612 | 603 | 0% 0% 0% 100% |
| 12 | Smalltalk VisualWorks | 146.17 | 146.17 | 121,992 | 722 | 0% 0% 0% 100% |
| 12 | Lua LuaJIT #2 | 147.96 | 147.95 | 877,760 | 446 | 0% 0% 0% 100% |
| 13 | Lua LuaJIT | 153.21 | 153.21 | 953,404 | 443 | 0% 0% 0% 100% |
| 14 | F# Mono | 172.41 | 172.41 | 237,252 | 587 | 0% 0% 0% 100% |
| 14 | Mozart/Oz | 175.91 | 175.90 | 398,700 | 479 | 0% 1% 0% 100% |
| 16 | Go 6g 8g | 194.72 | 194.71 | 250,044 | 527 | 0% 0% 0% 100% |
| 22 | Ruby 1.9 | 265.07 | 265.06 | 299,960 | 412 | 0% 0% 0% 100% |
| 28 | Ruby JRuby | 5 min | 5 min | 1,184,816 | 412 | 0% 0% 0% 100% |
| 42 | Lua | 8 min | 8 min | 815,620 | 443 | 0% 0% 0% 100% |
| 43 | Lua #2 | 8 min | 8 min | 812,176 | 446 | 0% 0% 0% 100% |
| 58 | Python 3 #6 | 11 min | 11 min | 695,308 | 626 | 0% 0% 0% 100% |
| 67 | Python CPython #6 | 13 min | 13 min | 674,580 | 626 | 0% 0% 0% 100% |
| 87 | Ruby MRI | 17 min | 17 min | 457,796 | 412 | 0% 0% 0% 100% |
| 106 | Perl #2 | 21 min | 21 min | 643,488 | 541 | 0% 0% 0% 100% |
| 122 | PHP #2 | 24 min | 24 min | 1,220,416 | 493 | 0% 0% 0% 100% |
| 133 | PHP | 27 min | 27 min | 1,199,828 | 1089 | 0% 0% 0% 100% |
| 186 | Python CPython #2 | 37 min | 37 min | 221,588 | 365 | 1% 1% 1% 100% |
| JavaScript TraceMonkey | Failed | 467 | ||||
| interesting alternative programs | ||||||
| 0.9 | Clean | 10.65 | 10.65 | 66,572 | 538 | |
| Lisaac #2 | Failed | 691 | ||||
| 1.8 | Go 6g 8g #2 | 22.08 | 22.08 | 111,304 | 719 | |
| 2.7 | Haskell GHC #3 | 33.28 | 33.28 | 193,604 | 544 | |
| 14 | Lua LuaJIT #3 | 176.89 | 176.88 | 547,776 | 470 | |
| 31 | Lua #3 | 376.37 | 376.35 | 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.