3 ms·
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 benchm
by 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;
}
}