9 ms·
Go's work-stealing scheduler
- euyyn 9y agoInteresting!
- signa11 9y agothere is also this paper: http://supertech.csail.mit.edu/papers/steal.pdf http://supertech.csail.mit.edu/papers/steal.pdf which also describes something similar.
- scott_s 9y agoFor 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 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 http://supertech.csail.mit.edu/papers/cilk5.pdf
- anonymous7777 9y agoA Big Copy Cat from Microsoft Cilk!
- omginternets 9y ago>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?
- chrisseaton 9y agoI 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.
- loppers92 9y agoThe author of this article is part of the Golang team (https://github.com/rakyll https://github.com/rakyll). I guess the correctness of this article is ok.
- omginternets 9y ago>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 :)
- Matthias247 9y agoI 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.
- omginternets 9y agoSo 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...)
- echlebek 9y agoYes. 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
- Matthias247 9y agoHowever 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.
- echlebek 9y agoThat'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.
- Matthias247 9y ago> 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.
- dullgiulio 9y agoI think "they" above refers to Ms, I don't see the contradiction with what you say. Do I miss something?
- Matthias247 9y agoMakes sense then. For me "they" referred to Ps. But I'm not a native speaker. I would probably have expected "those" there.
- knome 9y agoIt isn't a matter of your not being a native speaker. The statement is ambiguous.
- samuell 9y agoI'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.
- stcredzero 9y agoFWIW: Go is creating extra OS threads for blocking system calls. One point for house Go!
- pron 9y agoGo'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.base/share/classes/java/util/concurrent/ForkJoinPool.java#L173 https://github.com/netroby/jdk9-dev/blob/master/jdk/src/java...
- samuell 9y agoStuff that Quasar leverages (or will leverage), I gather? :) Any more details to share about the differences? Something that Go could readily learn from? :)
- pron 9y agoNot 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.
- geodel 9y agoOfcourse. 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-architect-likely-i-copied-sun-code-in-android https://www.theverge.com/2012/4/19/2961128/google-chief-java...
- pron 9y agoI 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.
- 9y ago
- 43224gg252 9y agoI disagree. That's written in Java.
- deleted 9y ago[deleted]
- egeozcan 9y agoYou can hate Java all you want (a hate which I find confusing but it doesn't matter), but the beauty of the referenced code is very hard to match - given that you don't weirdly define beauty as the lack of braces.
- LunaSea 9y ago> the beauty of the referenced code is very hard to match - 50 line comments containing type annotations in a strictly typed language and HTML - 80 column limit - single character variable names - variable declarations inside loops yeah ... Edit: I like that people downvote without having counter arguments.
- egeozcan 9y agoI love it when the comments are rich as it helps the IDE, I love the great formatting achieved especially considering the column limit and I also love that the variable names are only single letter when they can be (a local context of a very clearly defined function). I don't love the variable declarations inside loops and hadn't noticed them, but even if I did, I don't have an opinion about them. Maybe they aren't good for performance? If so, well, then you have a point but I can't say. I'm not a Java expert, I'm not even using it very often. My first point in the comment you replied was "don't dismiss it just because it's a language you don't like, it actually looks beautiful" and you are arguing that (correct me if I'm wrong) it's not beautiful at all. I wouldn't down-vote you, but it's obvious that we differ on taste. Maybe I should have said that "the beauty of the referenced code is very hard to match if you ignore your bias against a language and appreciate the stylistic choices" as you would probably also agree that it is at least very, very coherent.
- twoodfin 9y agoOne 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?
- jlouis 9y agoAn 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.
- valarauca1 9y agoThe 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.
- snnn 9y agoTensorflow has the same thing from Eigen
- geodel 9y agoThe original design document for scheduler [1]. The author Dmitry Vyukov is famous for lockfree data structures implementation. 1. https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sLKhJYD0Y_kqxDv3I3XMw/edit https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sL...
- teacpde 9y ago> 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.
- Matthias247 9y agoThat'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.