For the time being, until Valhalla is finalized, Java can emulate this approach simply by using an int array.

After making the modifications, on my local machine, Java ran as low as ~820ms, compared to golang's ~932ms.

golang's GC is no silver bullet as we see here:

* https://blog.discord.com/why-discord-is-switching-from-go-to...

* https://news.ycombinator.com/item?id=21670110

Thanks for doing the test!

No problem. I'll try to download a Valhalla JVM build and see how it fairs.

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?

After making the change in the golang version, I saw it go as low as 867.61ms.

The JVM is very good at inlining. It's not perfect obviously, but in this benchmark just using an `int[]` wrapped in a class (similar to an ArrayList) produced quicker results than golang. I'm not surprised, since the golang compiler doesn't generate the greatest code.

I tried with Valhalla, with the following array wrapper, and I saw it run as quick as 667ms.

    stretch tree of depth 22  check: 8388607
    2097152  trees of depth 4  check: 65011712
    524288  trees of depth 6  check: 66584576
    131072  trees of depth 8  check: 66977792
    32768  trees of depth 10  check: 67076096
    8192  trees of depth 12  check: 67100672
    2048  trees of depth 14  check: 67106816
    512  trees of depth 16  check: 67108352
    128  trees of depth 18  check: 67108736
    32  trees of depth 20  check: 67108832
    long lived tree of depth 21  check: 4194303
    0.667455718

This is the Java Tree and array wrapper code I used

    inline class Tree {
     public int left; 
     public int right;

     public Tree(int left, int right) {
      this.left = left;
      this.right = right;
     }
    }
    
    ///////////////////////////////////////////////////////////////////////////////
    // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
    //
    // This library is free software; you can redistribute it and/or
    // modify it under the terms of the GNU Lesser General Public
    // License as published by the Free Software Foundation; either
    // version 2.1 of the License, or (at your option) any later version.
    //
    // This library is distributed in the hope that it will be useful,
    // but WITHOUT ANY WARRANTY; without even the implied warranty of
    // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    // GNU General Public License for more details.
    //
    // You should have received a copy of the GNU Lesser General Public
    // License along with this program; if not, write to the Free Software
    // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
    ///////////////////////////////////////////////////////////////////////////////
    
    final class TIntArrayList {
     protected Tree[] _data;
     protected int _pos;
     public TIntArrayList() {
      _data = new Tree[0];
      _pos = 0;
     }
    
     public void ensureCapacity(int capacity) {
      if (capacity > _data.length) {
       int newCap = Math.max(_data.length << 1, capacity);
       Tree[] tmp = new Tree[newCap];
       System.arraycopy(_data, 0, tmp, 0, _data.length);
       _data = tmp;
      }
     }
     public int size() {
      return _pos;
     }
    
     public void add(Tree val) {
      ensureCapacity(_pos + 1);
      _data[_pos++] = val;
     }
    
     public Tree get(int offset) {
      return _data[offset];
     }
    
     public void resetQuick() {
      _pos = 0;
     }
    }