3 ms·
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
by tossaway32 5y ago
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".
- azth 5y agoFor 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-rust-a190bbca2b1f https://blog.discord.com/why-discord-is-switching-from-go-to... * https://news.ycombinator.com/item?id=21670110 https://news.ycombinator.com/item?id=21670110
- tossaway32 5y agoThanks for doing the test!
- azth 5y agoNo problem. I'll try to download a Valhalla JVM build and see how it fairs.
- tossaway32 5y agoHow 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 agoAfter 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; } }