9 ms·

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 :=

• 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; } }