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.83 | 13.84 | 149,588 | 850 | 1% 2% 1% 100% |
| 1.2 | Java 6 steady state #2 | 16.13 | 16.15 | 913,088 | 675 | 0% 0% 0% 100% |
| 1.2 | ATS | 16.43 | 16.43 | 198,432 | 1060 | 0% 0% 0% 100% |
| 1.2 | C++ GNU g++ #6 | 16.52 | 16.51 | 296,208 | 892 | 0% 1% 0% 100% |
| 1.3 | C GNU gcc #2 | 17.45 | 17.45 | 99,284 | 1641 | 0% 0% 0% 100% |
| 1.3 | Scala #4 | 17.75 | 17.77 | 577,388 | 536 | 4% 0% 0% 100% |
| 1.3 | Java 6 -server #2 | 18.51 | 18.55 | 565,112 | 603 | 0% 0% 0% 100% |
| 1.4 | Haskell GHC #2 | 19.65 | 19.65 | 329,080 | 544 | 0% 0% 0% 100% |
| 1.4 | Haskell GHC | 19.77 | 19.77 | 360,816 | 512 | 0% 0% 0% 100% |
| 2.4 | C GNU gcc | 33.18 | 33.18 | 131,816 | 706 | 0% 0% 0% 100% |
| 2.6 | C++ GNU g++ #2 | 35.50 | 35.49 | 197,836 | 553 | 0% 0% 0% 100% |
| 2.7 | Ada 2005 GNAT | 37.61 | 37.61 | 198,160 | 955 | 0% 0% 0% 100% |
| 2.7 | Lisp SBCL | 38.04 | 38.04 | 407,052 | 612 | 0% 0% 0% 100% |
| 3.2 | Erlang HiPE | 43.73 | 43.63 | 373,264 | 441 | 1% 100% 0% 0% |
| 3.2 | Clean #3 | 44.71 | 44.72 | 262,708 | 539 | 0% 0% 0% 100% |
| 3.4 | Fortran Intel | 46.62 | 46.62 | 131,536 | 826 | 0% 0% 0% 100% |
| 3.7 | OCaml #2 | 51.65 | 51.65 | 157,668 | 784 | 0% 0% 0% 100% |
| 4.4 | C GNU gcc #4 | 61.48 | 61.48 | 289,980 | 672 | 0% 0% 0% 100% |
| 4.5 | Erlang HiPE #2 | 62.47 | 62.48 | 355,520 | 499 | 0% 100% 0% 0% |
| 4.7 | Pascal Free Pascal | 65.32 | 65.31 | 131,292 | 769 | 0% 0% 0% 100% |
| 4.7 | C GNU gcc #5 | 65.50 | 65.50 | 514,260 | 963 | 0% 0% 0% 100% |
| 5.8 | Scheme PLT #2 | 80.57 | 80.56 | 452,372 | 503 | 0% 0% 0% 100% |
| 7.8 | C# Mono #2 | 107.84 | 107.84 | 454,504 | 650 | 0% 0% 3% 100% |
| 8.5 | JavaScript V8 | 117.66 | 117.66 | 386,944 | 467 | 0% 0% 0% 100% |
| 9.5 | Java 6 -Xint #2 | 131.42 | 131.49 | 547,096 | 603 | 0% 0% 0% 100% |
| 13 | F# Mono | 184.43 | 184.45 | 390,136 | 587 | 0% 0% 0% 100% |
| 16 | Go 6g 8g | 225.48 | 225.47 | 296,052 | 527 | 0% 0% 0% 100% |
| 18 | Smalltalk VisualWorks | 255.48 | 255.46 | 197,720 | 722 | 0% 0% 0% 100% |
| 22 | Ruby JRuby | 299.45 | 299.70 | 1,981,416 | 412 | 0% 0% 0% 100% |
| 48 | Lua | 10 min | 10 min | 1,688,960 | 443 | 0% 0% 1% 100% |
| 48 | Lua #2 | 11 min | 11 min | 1,683,288 | 446 | 0% 1% 0% 100% |
| 65 | Python CPython #6 | 15 min | 15 min | 1,349,936 | 626 | 0% 0% 0% 100% |
| 91 | Ruby MRI | 20 min | 20 min | 781,212 | 412 | 0% 0% 0% 100% |
| 96 | PHP #2 | 22 min | 22 min | 2,311,976 | 493 | 1% 0% 0% 100% |
| 108 | Perl #2 | 24 min | 24 min | 1,091,276 | 541 | 0% 0% 0% 100% |
| 140 | PHP | 26 min | 32 min | 2,266,136 | 1089 | 25% 25% 26% 100% |
| 214 | Python CPython #2 | 49 min | 49 min | 445,616 | 365 | 0% 0% 0% 100% |
| JavaScript TraceMonkey | Failed | 467 | ||||
| interesting alternative programs | ||||||
| 0.8 | Clean | 11.03 | 11.03 | 132,168 | 538 | |
| 1.4 | Haskell GHC #3 | 19.66 | 19.67 | 329,080 | 544 | |
| 1.7 | Go 6g 8g #2 | 23.10 | 23.10 | 222,396 | 719 | |
| 32 | Lua #3 | 436.36 | 436.33 | 997,004 | 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.