Go's work-stealing scheduler | Hacker News Reader

Go's work-stealing scheduler

rakyll.org

200 pointssigna1169 comments

The original design document for scheduler [1]. The author Dmitry Vyukov is famous for lockfree data structures implementation.

1. https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sL...

One missing piece for me: How does the Go scheduler ensure it won't end up fighting the underlying OS scheduler? Are thread-affinity APIs enough?

Does the scheduler have any awareness of NUMA or NUMA-like topologies (I'm thinking here of hyperthreading) that could influence scheduling decisions?

An interesting tidbit from the Erlang world: We have CPU affinity controls (erl(1) options +sbt {db,tnnps}) which will spread schedulers (Erlang's name for a P) over a NUMA-like topology and keep track of the relative price of handoff/stealing between CPUs. Another option defines if you want load compaction and load balancing (+scl, +sub). Some workloads are more efficient if you can keep the work mostly on a few cores rather than spread the work over all available cores in the system because communication will be faster that way. If one core can process all work and get back to an idling state quickly, it usually beats spreading the load out due to caching.

For some workloads and hardware configurations, the gain from doing this is quite high because you can avoid schedulers jumping between cores and in the process destroying cache layers and TLBs.

OTOH, when running in a typical cloud environment, you are at the mercy of the underlying hypervisor and thus your load profile is different. In that case, affinity has little to no effect.

The answer is no.

Go-Lang heavily trashes your cache, and quickly moves things between cores.

---

There are underlying API's on the OS level that work well. But to my understanding Go doesn't leverage them. Also NUMA aware allocations are lacking.

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

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/

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

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

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.

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

> Each M should be assigned to a P. Ps may have no Ms if they are blocked or in a system call. At any time, there are at most GOMAXPROCS number of P. At any time, only one M can run per P. More Ms can be created by the scheduler if required.

So if every new Goroutine I spawn does an I/O operation that takes long time to finish, the scheduler will essentially spawn the same number of OS threads because every other one is blocked and no 'spinning' thread is available? If so, creating new OS threads seems like a lot overhead comparing to run a single thread in an event loop.

That's only happening for IO operations which get really blocked on syscall level, which means no async version is available. For the most important IO operations (sockets) the asynchronous variants are used internally. Which means if a read/write can not be performed immediately, the goroutine will register at the netpoller component (which is a wrapper around epoll/kqueue/iocp for IO status updates) for IO status updates, and then the goroutine will yield and wait until IO becomes possible again. The current thread can execute another goroutine until then. This means for goroutines blocked on network no extra OS threads are required. For other blocking OS operations (maybe file IO) extra OS threads are required.

Tensorflow has the same thing from Eigen

there is also this paper: http://supertech.csail.mit.edu/papers/steal.pdf which also describes something similar.

For interested readers, there's a bunch of papers on the Cilk runtime's work-stealing scheduler. The paper signa11 pointed to is one of many. They are classics in the runtime literature. Other two great papers are "Cilk: An Efficient Multithreaded Runtime System" by Blumofe et al., PPoPP 1995, http://supertech.csail.mit.edu/papers/PPoPP95.pdf and "The Implementation of the Cilk-5 Multithreaded Language", Frigo et al., PLDI 1998, http://supertech.csail.mit.edu/papers/cilk5.pdf

>if not found, poll network.

Does this mean network IO is only performed when there are no idling goroutines? That can't be right... what am I not understanding, here?

I don't know if the article is accurate or not, but I think you do have it backwards from what the article says.

I think it says that network IO is only performed where there are no runnable (not idling) goroutines.

The author of this article is part of the Golang team (https://github.com/rakyll). I guess the correctness of this article is ok.

>I think it says that network IO is only performed where there are no runnable (not idling) goroutines.

Yes, that's what I meant. Got mixed up :)

I understand that network polling is only performed then. For network IO in general things look different: E.g. if you do a write() the runtime will first try to perform it synchronously in a nonblocking fashion. Only when that fails (E_WOULDBLOCK) then the executing goroutine is parked until the network poller executes and gets the information that IO is possible again.

So if I had GOMAXPROCS set to 1 and had two goroutines, one doing file IO and one doing

    var i int
    for { i++ }

the former goroutine would never actually perform the IO?

(I can't fight the feeling that I'm misunderstanding this on some level...)

Yes. The goroutine that increments i in a loop never has a chance to yield to the scheduler.

    package main
    
    import (
    	"fmt"
    	"time"
    )
    
    func main() {
    	go func() {
    		time.Sleep(100 * time.Millisecond)
    		fmt.Println("hi")
    	}()
    	var i int
    	for {
    		i++
    	}
    }

  $ GOMAXPROCS=1 go run test.go  # never prints anything

However that should happen only in a loop without function calls inside it. Afaik the newer Go versions will also yield in the function call preambles to the scheduler from time to time to give another goroutine in ready state the chance to run.

That's right. The newer releases of Go include more points where goroutines will yield to the scheduler.

I'm unsure about how that plays with inlining, though.

> Ps may have no Ms if they are blocked or in a system call.

Is it really this way or the other way around? I would have guessed threads which are blocked in a system call are represented by an M which is not currently scheduled by the scheduler, which means that M isn't assigned to a P.

I think "they" above refers to Ms, I don't see the contradiction with what you say. Do I miss something?

Makes sense then. For me "they" referred to Ps. But I'm not a native speaker. I would probably have expected "those" there.

It isn't a matter of your not being a native speaker. The statement is ambiguous.

I'm not super sure what was meant here, but I could add one point of info, FWIW: Go is creating extra OS threads for blocking system calls. In fact, sometimes more than one thread per such (for taking care of stdin and stdout, I think).

I have been able to create at least 4999 go-routines with blocking system calls though (Two OS threads were created per go-routine / syscall), so not a problem you will run into quickly.

FWIW: Go is creating extra OS threads for blocking system calls.

One point for house Go!

Interesting!

Reply on news.ycombinator.com