3 ms·

Thanks for doing the test!

• azth 5y ago
  No problem. I'll try to download a Valhalla JVM build and see how it fairs.
  • tossaway32 5y ago
    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?
    • azth 5y ago
      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; } }