tossaway32

How does Java do without using an array of ints, or Valhalla? In other words, what's the cost of Java's forced indirection?

What happens if you use

  pool := make([]Tree, 0, 256)

instead of

  var pool []Tree

in the Go so it doesn't waste time growing tiny slices?

Thanks for doing the test!

Do it. Show me that Java can avoid allocating/collecting the Tree objects. Go has no indirection for the Tree objects, in this example. The Trees are contiguous in memory.

Measure the performance.

I have no garbage collection performance problems in the various large Go projects I have worked on. But I am also a competent programmer, so "your mileage may vary".

You don't rewrite your whole program to use pooled allocations.

Just the parts of your program where allocation performance needs to be improved.

If part of your program is doing many allocations, and it's too slow, use a simple pool. Go makes pooled allocation easy and safe.

I have written huge Go programs (e.g., https://NN-512.com), and the garbage collector is not a problem. Quite the opposite, it's a major, major benefit.

Pooled allocations are rarely needed.

I'm not going to paste 170 lines of code into the thread. Add this line:

  var pool []Tree

to each of the stretch and long-lived closures in run(), pass &pool as the second argument to bottomUpTree(), pass pool as the second argument to itemCheck().

The call to inner() doesn't change.

It's trivial.

Look at the Go benchmark program:

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.