5 ms·

The binary-trees benchmark on The Debian Language Shootout[1] involves allocating millions of short-lived trees and traversing them. It is informative about GC

The binary-trees benchmark on The Debian Language Shootout[1] involves allocating millions of short-lived trees and traversing them. It is informative about GC performance even with the caveat that there are 'lies, damned lies, and benchmarks', because many real-world graph analysis and brute force tree search algorithms similarly allocate zillions of short-lived nodes. For non-GC languages like C/C++/Rust it gives a decent idea of the performance difference between malloc'ing and freeing individual objects vs doing bulk arena allocations: language secs GC'd language? ======== ==== ============== C++ (g++) 0.94 Rust 1.09 C (gcc) 1.54 Free Pascal 1.99 Intel Fortran 2.38 Java 2.48 yes <==== Lisp (SBCL) 2.84 yes Ada (GNAT) 3.12 OCaml 4.68 yes Racket 4.81 yes C# .NET 4.81 yes Haskell (GHC) 5.02 yes Erlang 5.19 yes F# .NET 6.06 yes Node.js 7.20 yes Julia 7.43 yes Chapel 7.96 yes Dart 9.90 yes Go 12.23 yes <==== Swift 16.15 * "Automatic Reference Counting" Smalltalk (VW) 16.33 yes PHP 18.64 yes Ruby 23.80 yes Python 3 48.03 yes Lua 48.15 yes Perl 53.02 yes So Java has the fastest GC for this test, 2.48 secs vs 12.23 secs for Golang. The Java code is also notably perfectly idiomatic for multicore, it doesn't do heroic "avoid GC by writing C-like code manipulating a fixed global memory array" tricks. The Java code is also more concise. The 'plain C' code that uses Apache Portable Runtime memory pools instead of standard malloc/free and uses OpenMP #pragma's strikes me as more 'heroic' than 'idiomatic', whereas C++ and Rust use standard libraries/crates and idiomatic patterns. (Note that OpenMP is 'standard' for high-performance C and well supported across GCC/LLVM/Microsoft/Intel compilers. But still....) OCaml and Haskell made impressive showings for functional languages which are in practice the easiest for dealing with complicated tree algorithms, which is perhaps why the formally verified C compiler, CompCert, is implemented in OCaml, as is Frama-C for formally verifying ISO C programs, as is the Coq theorem prover, etc. [1] https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/binarytrees.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/... [Edited link]

geodel 5y ago
> So Java has the fastest GC for this test, 2.48 secs vs 12.23 secs for Golang. Further not mentioning memory used Java/Go programs makes it very fair comparison. Because GC perf does not depend on memory allocated.
- dandotway 5y ago
  Right now in the datacenter CPU usage is considerably more expensive than RAM usage. Ram consumes comparatively little power, whereas burning hot CPUs+GPUs are the reason datacenters are favored near cooling water and power stations. 2.48 vs 12.23 seconds for Java and Go is a big deal for how many solar panels or tons of coal are needed to run an app on Xeon or Epyc instances, whereas 1.7GB vs 0.4GB for Java and Go, a 4x difference in low-power memory usage, is not so big of deal. At any rate I did link to the full table so everyone can see the mem usage, source listings, etc.
  - _rlh 5y ago
    Just for fun set the Java heap to .4 Gigs or use GOGC to set the Go heap to 1.7 Gigs. If Go is faster then try some other sizes and draw a graph to see what the lines look like.
deleted 5y ago
[deleted]
tossaway32 5y ago
Look at the Go benchmark program: https://benchmarksgame-team.pages.debian.net/benchmarksgame/program/binarytrees-go-8.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/... Needs to be faster? Use a pool like the C benchmark programs, but super simple: just a slice, local to the goroutine. Trivially make the Go program 10x faster, 5 minutes of work, a few edits: type Tree struct { Left int Right int } func itemCheck(id int, pool []Tree) uint32 { tree := &pool[id] if tree.Left != -1 && tree.Right != -1 { return uint32(1) + itemCheck(tree.Right, pool) + itemCheck(tree.Left, pool) } return 1 } func bottomUpTree(depth uint32, pool *[]Tree) int { var tree Tree if depth > uint32(0) { tree.Left = bottomUpTree(depth-1, pool) tree.Right = bottomUpTree(depth-1, pool) } else { tree.Left = -1 tree.Right = -1 } id := len(*pool) *pool = append(*pool, tree) return id } func inner(depth, iterations uint32) string { var ( pool []Tree chk = uint32(0) ) for i := uint32(0); i < iterations; i++ { a := bottomUpTree(depth, &pool) chk += itemCheck(a, pool) pool = pool[:0] } return fmt.Sprintf("%d\t trees of depth %d\t check: %d", iterations, depth, chk) } If it matters, your Go program can be made as fast as a C program. Easily.

geodel 5y ago

> So Java has the fastest GC for this test, 2.48 secs vs 12.23 secs for Golang. Further not mentioning memory used Java/Go programs makes it very fair comparison. Because GC perf does not depend on memory allocated.

dandotway 5y ago
Right now in the datacenter CPU usage is considerably more expensive than RAM usage. Ram consumes comparatively little power, whereas burning hot CPUs+GPUs are the reason datacenters are favored near cooling water and power stations. 2.48 vs 12.23 seconds for Java and Go is a big deal for how many solar panels or tons of coal are needed to run an app on Xeon or Epyc instances, whereas 1.7GB vs 0.4GB for Java and Go, a 4x difference in low-power memory usage, is not so big of deal. At any rate I did link to the full table so everyone can see the mem usage, source listings, etc.
- _rlh 5y ago
  Just for fun set the Java heap to .4 Gigs or use GOGC to set the Go heap to 1.7 Gigs. If Go is faster then try some other sizes and draw a graph to see what the lines look like.

deleted 5y ago

[deleted]

tossaway32 5y ago

Look at the Go benchmark program: https://benchmarksgame-team.pages.debian.net/benchmarksgame/program/binarytrees-go-8.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/... Needs to be faster? Use a pool like the C benchmark programs, but super simple: just a slice, local to the goroutine. Trivially make the Go program 10x faster, 5 minutes of work, a few edits: type Tree struct { Left int Right int } func itemCheck(id int, pool []Tree) uint32 { tree := &pool[id] if tree.Left != -1 && tree.Right != -1 { return uint32(1) + itemCheck(tree.Right, pool) + itemCheck(tree.Left, pool) } return 1 } func bottomUpTree(depth uint32, pool *[]Tree) int { var tree Tree if depth > uint32(0) { tree.Left = bottomUpTree(depth-1, pool) tree.Right = bottomUpTree(depth-1, pool) } else { tree.Left = -1 tree.Right = -1 } id := len(*pool) *pool = append(*pool, tree) return id } func inner(depth, iterations uint32) string { var ( pool []Tree chk = uint32(0) ) for i := uint32(0); i < iterations; i++ { a := bottomUpTree(depth, &pool) chk += itemCheck(a, pool) pool = pool[:0] } return fmt.Sprintf("%d\t trees of depth %d\t check: %d", iterations, depth, chk) } If it matters, your Go program can be made as fast as a C program. Easily.