Hacker News Reader

Comment by pron | Hacker News Reader

Go's work-stealing scheduler is crude in comparison to Doug Lea's, which is a work of artful mechanical sympathy: https://github.com/netroby/jdk9-dev/blob/master/jdk/src/java...

View on HN

Seems like a reasonable take on Java Fork-Join shortcomings [1]. One of them is exceeding complexity which of course is very popular in Java world and the comment shows how Go version is 'crude' so apparently not good enough.

"The F/J framework classes -

1) have many, many levels of inheritance,

2) nested classes on top of nested classes,

3) instance variables used directly by other classes (known internally as “representation-level coupling among classes”), code from the Hackers Delight without comments about what it does,

4) homegrown deques and queues instead of standard Java™ Classes, and so much more."

1. http://www.coopsoft.com/ar/CalamityArticle.html

One should bear in mind that the author of that article has a strong vested interest against the JVM's ForkJoin framework succeeding, because they are senior at a company whose sole product is a competing implementation of a similar idea [1].

1. http://www.coopsoft.com/Products.html

NO. The TymeacDSE product was released after JDK1.7. I took the proof-of-concept I gave Doug and made a professional product out of it. See the article "Is there a better way."

The remarkable thing about the implementation is the algorithm, not the programming style. Doug Lea's programming style has always been, and always will be, somewhat... idiosyncratic. Much of it is because he must take into account truly low-level details of compiler optimizations (and you can see that the implementation changes from one Java version to the other). He always warns people not to code like him. In any event, the beauty of the code (like in all of Doug Lea's code) is not in the programming style but in the algorithm and the attention to detail.

The remarkable thing about the implementation is the algorithm, not the programming style.

How so? Is there an article where the algorithm is covered?

EDIT: There seem to be some links in the comment referenced.

These are arguments against the implementation, not the actual utility of the framework. One can have ugly internal implementation (which sometimes is unavoidable because you're solving hard problems), but clean interfaces. Regardless, Doug Lea anticipated these complaints in the comments to his code:

     * Style notes
     * ===========
     *
     * Memory ordering relies mainly on VarHandles.  This can be
     * awkward and ugly, but also reflects the need to control
     * outcomes across the unusual cases that arise in very racy code
     * with very few invariants. All fields are read into locals
     * before use, and null-checked if they are references.  This is
     * usually done in a "C"-like style of listing declarations at the
     * heads of methods or blocks, and using inline assignments on
     * first encounter.  Nearly all explicit checks lead to
     * bypass/return, not exception throws, because they may
     * legitimately arise due to cancellation/revocation during
     * shutdown.
     *
     * There is a lot of representation-level coupling among classes
     * ForkJoinPool, ForkJoinWorkerThread, and ForkJoinTask.  The
     * fields of WorkQueue maintain data structures managed by
     * ForkJoinPool, so are directly accessed.  There is little point
     * trying to reduce this, since any associated future changes in
     * representations will need to be accompanied by algorithmic
     * changes anyway. Several methods intrinsically sprawl because
     * they must accumulate sets of consistent reads of fields held in
     * local variables.  There are also other coding oddities
     * (including several unnecessary-looking hoisted null checks)
     * that help some methods perform reasonably even when interpreted
     * (not compiled).

I find the "Calamity" article disingenuous. If you read more of the comments, Lea clearly explains the source of many of his data structures and gives an overview of how it all works.

The article was written in 2010 just before the release of JDK1.7. The above comments are for the JDK1.9 release in late 2017. Doug has had some time to improve his comments. Perhaps you should look into the calamity part 2 article to see how well this "framework" with it's internal structure problems performs in JDJ1.8 streams.

There are times where a simple solution can beat more complex solutions. That said, Doug's work is indeed beautiful.

Another quite beautiful model is the one by Occam Pi, which has a certain simplicity ring to it:

https://www.cs.kent.ac.uk/pubs/2012/3210/content.pdf

As someone who knows nothing about schedulers, care to explain?

More here: http://gee.cs.oswego.edu/dl/papers/fj.pdf

Neat

For the main tests, programs were run on a 30−CPU Sun Enterprise 10000 running the Solaris Production 1.2 JVM (an early version of the 1.2.2_05 release) on Solaris 7.

And slides: http://gee.cs.oswego.edu/dl/cpjslides/fj.pdf

Stuff that Quasar leverages (or will leverage), I gather? :)

Any more details to share about the differences? Something that Go could readily learn from? :)

Not just Quasar, but pretty much any high-level concurrency framework (Akka uses it, too). Doug's algorithm is lock-free (except in some marginal features, that are not supported and not relevant for the Go implementation anyway) and displays exceptional scalability even on machines with a large number of cores. AFAICT, Go could copy Doug's implementation completely.

Ofcourse. And Oracle would be so pleased with that like they always are with Google copying Oracle code. [1]

1. https://www.theverge.com/2012/4/19/2961128/google-chief-java...

I am not aware of any lawsuits involving Oracle over code used in accordance with its license. The Google lawsuit was over code that Google believed the license did not apply to, and they could therefore use not in accordance with the terms. In any event, the license of Doug Lea's code is creative commons.

It's not even Creative Commons, it's CC-zero, which is public domain or as close as it gets. Strangely, the file that you linked has a GPL overlay:

  /*
   * This file is available under and governed by the GNU General Public
   * License version 2 only, as published by the Free Software Foundation.
   * However, the following notice accompanied the original version of this
   * file:
   *
   * Written by Doug Lea with assistance from members of JCP JSR-166
   * Expert Group and released to the public domain, as explained at
   * http://creativecommons.org/publicdomain/zero/1.0/
   */

https://github.com/netroby/jdk9-dev/blob/master/jdk/src/java...

I wonder where the original CC-zero version is located.

http://g.oswego.edu/dl/concurrency-interest/

Reply on news.ycombinator.com