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 benchmark 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 benchmark programs used - sort Code B
Column × shows how many times more each program used compared to the benchmark 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.88 | 7.06 | 151,180 | 850 | 53% 83% 2% 50% |
| 1.3 | C GNU gcc #2 | 30.44 | 9.28 | 115,492 | 1641 | 53% 99% 96% 81% |
| 1.4 | C++ GNU g++ #6 | 28.56 | 10.20 | 382,904 | 892 | 89% 68% 65% 58% |
| 2.1 | Java 6 steady state #2 | 17.04 | 14.90 | 949,204 | 675 | 93% 8% 7% 6% |
| 2.2 | ATS | 15.34 | 15.34 | 198,236 | 926 | 0% 0% 100% 0% |
| 2.4 | Java 6 -server #2 | 19.37 | 17.20 | 565,628 | 603 | 7% 11% 81% 13% |
| 2.5 | Scala #4 | 19.30 | 17.57 | 580,216 | 536 | 6% 11% 80% 12% |
| 2.8 | C GNU gcc #5 | 68.55 | 19.41 | 424,544 | 963 | 74% 91% 94% 96% |
| 3.6 | OCaml #2 | 85.48 | 25.54 | 157,648 | 784 | 75% 93% 70% 95% |
| 4.4 | Haskell GHC | 43.24 | 30.90 | 357,576 | 512 | 5% 89% 42% 3% |
| 4.7 | C GNU gcc | 33.27 | 33.27 | 131,644 | 706 | 0% 0% 0% 100% |
| 4.9 | C++ GNU g++ #2 | 34.61 | 34.61 | 197,836 | 553 | 0% 0% 0% 100% |
| 5.3 | Ada 2005 GNAT | 37.11 | 37.12 | 198,136 | 955 | 0% 0% 0% 100% |
| 6.4 | Pascal Free Pascal | 44.86 | 44.87 | 131,420 | 769 | 0% 0% 0% 100% |
| 8.5 | C# Mono #2 | 91.92 | 59.70 | 462,924 | 650 | 44% 32% 43% 32% |
| 11 | Scheme PLT #2 | 77.48 | 77.48 | 304,156 | 503 | 0% 100% 0% 0% |
| 17 | F# Mono | 187.32 | 118.42 | 271,820 | 587 | 35% 48% 41% 32% |
| 18 | Java 6 -Xint #2 | 130.11 | 126.31 | 545,732 | 603 | 3% 2% 95% 5% |
| 35 | Go 6g 8g | 245.46 | 245.46 | 301,264 | 516 | 0% 0% 100% 0% |
| Haskell GHC #2 | Make Error | 544 | ||||
| "interesting alternative" programs | ||||||
| Haskell GHC #3 | Make Error | 544 | ||||
| 3.3 | Go 6g 8g #2 | 22.98 | 22.97 | 222,404 | 695 | |
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.