Hacker News Reader

Several (about 10) years ago, I submitted essentially the same program. It was one of the fastest of all the implementations across all the languages.

However, Isaac rejected it, saying it violated the conditions.

Debian Maintainers doing Debian Things.

Of course. The problem description [1] specifically calls for the following:

When possible, use default GC; otherwise use per node allocation or use a library memory pool. As a practical matter, the myriad ways to tune GC will not be accepted. As a practical matter, the myriad ways to custom allocate memory will not be accepted. Please don't implement your own custom "arena" or "memory pool" or "free list" - they will not be accepted.

In the other words, this problem measures the memory allocation performance with the "natural" strategy, which is either a default GC, a memory pool or a per-node allocation in the order of availability. If the target implementation doesn't support GC by default the code would be necessarily more complex, which makes up the performance benefit. So you can't really compare submissions with different strategies, because they are just doing different things and there is no reasonable way to make them do the same thing [2].

[1] https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

[2] You may still argue that every submission should use a per-node allocation for the fair comparison, but a per-node allocation with GC and without GC is pretty different.

My submission did violate the conditions. I was just recollecting what happened; it is not a complaint.

I am at variance with those conditions, though. I refer to the benchmarks suite itself, broadly. When programs dip into GMP, PCRE, etc., we are no longer comparing the speeds of the different language implementations per se. Now, they are mixed with FFI speeds of those implementations, the choices of the foreign language libraries/algorithms, etc..

In the same vein, as you remark in your second footnote, for a fair comparison, the same algorithm should be used in all programs. That will shed light on the strengths and weaknesses of the different language implementations better. I don't intend to say that the current system is useless; I am saying that using the same set of algorithms is likely to be more illustrative.

The point of this benchmark (that you're deliberately ignoring) is actually to have at least one program that realistically shows how bad a language's GC is. Go performs terribly because its GC makes lousy tradeoffs, which is the only reason you're annoyed at its requirements. It's actually probably the best benchmark in the whole set on that site.

Can this benchmark be written using sync.Pool mentioned in the article? If so, then that should be accepted since sync.Pool comes in stdlib.

Now do the same in Java and it will be as fast, if not faster. The point is the benchmark is looking at GC performance. In large real world programs, it is not trivial to make such changes.

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".

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

Would you mind posting a complete example that compiles and runs? Your above changes to Go#8 break it. E.g. the function 'run' needs to be updated to use your new 'bottomUpTree' and 'inner'.

I'm not going to paste 170 lines of code into the thread. Add this line:

  var pool []Tree

to each of the stretch and long-lived closures in run(), pass &pool as the second argument to bottomUpTree(), pass pool as the second argument to itemCheck().

The call to inner() doesn't change.

It's trivial.

+1 Not bad, your simple pool improved performance from about 10.9 secs to 1.4 secs on my laptop here. However, it does break the stated rules for the benchmark.[1] The Java version doesn't use a pool and doesn't change Tree pointers into ints as your version does. The C/C++/Rust versions are required to use a "library memory pool." The rules state,

  Please don't implement your own custom "arena" or "memory pool"
  or "free list" - they will not be accepted."

Donald Knuth uses integers instead of proper pointers in the source code for TeX for maximum portability and performance so your technique is legit used by master programmers but in general replacing pointers with integer indices into arrays only works for monolithic programs of small to medium size. For example, could the Chromium maintainers rewrite the 20 million lines of C++ into Golang replacing most pointers with integer offsets into arrays for performance? No, impossible with current tools and practices, the technique won't scale to that, so this benchmark rule isn't totally stupid and unfair. This binary trees benchmark was originally devised decades ago by Hans Boehm, a notable GC researcher, as a way of testing GC performance that he as a GC implementer found informative.

[1] https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

You don't rewrite your whole program to use pooled allocations.

Just the parts of your program where allocation performance needs to be improved.

If part of your program is doing many allocations, and it's too slow, use a simple pool. Go makes pooled allocation easy and safe.

I have written huge Go programs (e.g., https://NN-512.com), and the garbage collector is not a problem. Quite the opposite, it's a major, major benefit.

Pooled allocations are rarely needed.