28 ms·

The Go 1.1 scheduler

139 points by thepumpkin1979 13y ago

thepumpkin1979 13y ago
I really wish D could have an scheduler and goroutines like Go does. I think D has the perfect foundation for gorutines by supporting actors [0] and fibers[1], they just need to be put together by someone clever on the topic. [0] http://dlang.org/phobos/std_concurrency.html http://dlang.org/phobos/std_concurrency.html [1] http://dlang.org/phobos/core_thread.html#.Fiber http://dlang.org/phobos/core_thread.html#.Fiber
hosay123 13y ago
"Don't read the design doc, it's too complicated. Instead read this cutpaste!" The single "lock free" idlep looks like it's just moved the futex contention elsewhere. This will almost certainly bounce like crazy on a many-cored system. Would be interested to see benchmarks of the new design before considering it somehow better.
- pron 13y ago
  > The single "lock free" idlep looks like it's just moved the futex contention elsewhere. Possibly. The Go 1.1 scheduler is inspired by Java's fork/join scheduler, which suffered from the same problem in Java 7. In Java 8 it's been improved to no longer have a single wait-list, and external submissions of tasks (i.e. tasks that are not submitted by tasks running in the thread pool, but elsewhere) are multiplexed randomly (IIRC) among the individual thread queues.
- Arnor 13y ago
  I concur. While the article made sense and the decisions seemed logical, I'm shy of the level of knowledge necessary to come up with healthy criticism. A nice quantitative benchmark would clear things up an awful lot.
davidw 13y ago
Interesting, looks like they've made progress on this: https://code.google.com/p/go/issues/detail?id=543 https://code.google.com/p/go/issues/detail?id=543 Also, from the article: > Go garbage collector requires that all threads are stopped when running a collection and that memory must be in a consistent state. People often ask about how Go differs from Erlang. That one's a fairly large difference under the hood. Erlang does GC on a per process (Erlang process, not OS process) basis.
- Roboprog 13y ago
  So, does that mean it's safe to say that Erlang must copy the memory of values sent as messages between processes? Or, is there some kind of locking of such (aliased) message data???
  - voidlogic 13y ago
    I would think so unless it stores all message bodies in shared memory and protects them with an enforced COW policy to begin with, or better yet does this with virtual memory with some clever COW mmapping.
  - JulianMorrison 13y ago
    Messages are deep-copied in Erlang. There are other techniques possible such as uniqueness types, which allow "transfer of ownership", Rust uses those but Erlang does not.
    - lpgauth 13y ago
      That's not exactly true... in Erlang, any binary with size > 64 bytes will not be copied. Instead a pointer to a shared memory area will be passed.
      - cpeterso 13y ago
        If pointers are sent between Erlang processes, how does the per-process GC work without stopping the world?
        JulianMorrison 13y ago
        Big binaries (which yeah, I forgot about) live off to the side and are not GC'd. They're ref counted.
  - masklinn 13y ago
    > So, does that mean it's safe to say that Erlang must copy the memory of values sent as messages between processes? Theoretically not since Erlang data structures are immutable, but outside of binaries which seat in a shared global heap the benefits was never considered to outweight the complexity costs (aliasing analysis and others), so messages are copied indeed.
Arnor 13y ago
Thanks for this. After reading the article I was able to go to the design document and keep my head above water. Go has a lot going for it, but one underrated aspect is excellent propagation of information about the language. The talks by the likes of Rob Pike and the writing here and elsewhere drives the language in popularity and productivity. We learn the language, true, but we also learn very strong computer science. No wonder people become more productive when they switch to Go! By using it and reading about it, they get better at programming! (I'll grant that this is true of learning new languages in general, but maintain it's especially true with Go...)
bfrog 13y ago
I've said this before. Go's biggest problem will forever be a blocking GC due to the global heap they've decided to go with versus a hybrid global/goroutine local heap style like the beam erlang vm has. The problem will show up when people try to fire up millions of goroutines and then wonder "why is my latency suddenly spiking in to the seconds! WTF!"
- GhotiFish 13y ago
  That definitely surprised me to learn that go's garbage collection required all threads stop. That can't possibly manifest as anything other than a visible and uncontrollable "THUNK" in your application. I'd love to see a pros/cons comparison between Go's all at once strategy vs Erlang's per process strategy.
  - pcwalton 13y ago
    The pros and cons are pretty simple. Go's advantage is that you can share data cheaply while retaining memory safety [1]. The disadvantage is that you have stop-the-world GC and potential for data races, so you must rely on the race detector. Erlang's advantage is that you have no data races and no stop-the-world GC (and Erlang's GC is easier to implement). The disadvantage is that all messages must be copied and parallel algorithms that require data sharing are more difficult to write. There are hybrid approaches like Singularity, JS with transferable data structures, and Rust (disclaimer: I work on Rust). These systems use some form of static or dynamic access control scheme (for example, uniqueness or immutability) to control data races and perform memory management for shared data structures, while retaining Erlang's thread-local GC. [1] With one exception, the memory unsafe data race in maps and slices. See: http://research.swtch.com/gorace http://research.swtch.com/gorace
    - pron 13y ago
      Go has gone the Java route (I find both runtimes to be somewhat similar -- well other than the whole JIT thing -- with Java some years ahead in terms of GC and scheduling), and I suppose that Go, too, will get a concurrent GC sooner or later, but even the concurrent GC on the JVM has a few stop-the-world phases.
parennoob 13y ago
I don't understand much about processes and threads, but I do know a bit about queues. What is the meaning of this? "Once a context has run a goroutine until a scheduling point, it pops a goroutine off its runqueue, sets stack and instruction pointer and begins running the goroutine." Do they mean: "begins running the next goroutine"?

139 points by thepumpkin1979 13y ago

thepumpkin1979 13y ago

I really wish D could have an scheduler and goroutines like Go does. I think D has the perfect foundation for gorutines by supporting actors [0] and fibers[1], they just need to be put together by someone clever on the topic. [0] http://dlang.org/phobos/std_concurrency.html http://dlang.org/phobos/std_concurrency.html [1] http://dlang.org/phobos/core_thread.html#.Fiber http://dlang.org/phobos/core_thread.html#.Fiber

hosay123 13y ago

"Don't read the design doc, it's too complicated. Instead read this cutpaste!" The single "lock free" idlep looks like it's just moved the futex contention elsewhere. This will almost certainly bounce like crazy on a many-cored system. Would be interested to see benchmarks of the new design before considering it somehow better.

pron 13y ago
> The single "lock free" idlep looks like it's just moved the futex contention elsewhere. Possibly. The Go 1.1 scheduler is inspired by Java's fork/join scheduler, which suffered from the same problem in Java 7. In Java 8 it's been improved to no longer have a single wait-list, and external submissions of tasks (i.e. tasks that are not submitted by tasks running in the thread pool, but elsewhere) are multiplexed randomly (IIRC) among the individual thread queues.
Arnor 13y ago
I concur. While the article made sense and the decisions seemed logical, I'm shy of the level of knowledge necessary to come up with healthy criticism. A nice quantitative benchmark would clear things up an awful lot.

davidw 13y ago

Interesting, looks like they've made progress on this: https://code.google.com/p/go/issues/detail?id=543 https://code.google.com/p/go/issues/detail?id=543 Also, from the article: > Go garbage collector requires that all threads are stopped when running a collection and that memory must be in a consistent state. People often ask about how Go differs from Erlang. That one's a fairly large difference under the hood. Erlang does GC on a per process (Erlang process, not OS process) basis.

Roboprog 13y ago
So, does that mean it's safe to say that Erlang must copy the memory of values sent as messages between processes? Or, is there some kind of locking of such (aliased) message data???
- voidlogic 13y ago
  I would think so unless it stores all message bodies in shared memory and protects them with an enforced COW policy to begin with, or better yet does this with virtual memory with some clever COW mmapping.
- JulianMorrison 13y ago
  Messages are deep-copied in Erlang. There are other techniques possible such as uniqueness types, which allow "transfer of ownership", Rust uses those but Erlang does not.
  - lpgauth 13y ago
    That's not exactly true... in Erlang, any binary with size > 64 bytes will not be copied. Instead a pointer to a shared memory area will be passed.
    - cpeterso 13y ago
      If pointers are sent between Erlang processes, how does the per-process GC work without stopping the world?
      - JulianMorrison 13y ago
        Big binaries (which yeah, I forgot about) live off to the side and are not GC'd. They're ref counted.
- masklinn 13y ago
  > So, does that mean it's safe to say that Erlang must copy the memory of values sent as messages between processes? Theoretically not since Erlang data structures are immutable, but outside of binaries which seat in a shared global heap the benefits was never considered to outweight the complexity costs (aliasing analysis and others), so messages are copied indeed.

Arnor 13y ago

Thanks for this. After reading the article I was able to go to the design document and keep my head above water. Go has a lot going for it, but one underrated aspect is excellent propagation of information about the language. The talks by the likes of Rob Pike and the writing here and elsewhere drives the language in popularity and productivity. We learn the language, true, but we also learn very strong computer science. No wonder people become more productive when they switch to Go! By using it and reading about it, they get better at programming! (I'll grant that this is true of learning new languages in general, but maintain it's especially true with Go...)

bfrog 13y ago

I've said this before. Go's biggest problem will forever be a blocking GC due to the global heap they've decided to go with versus a hybrid global/goroutine local heap style like the beam erlang vm has. The problem will show up when people try to fire up millions of goroutines and then wonder "why is my latency suddenly spiking in to the seconds! WTF!"

GhotiFish 13y ago
That definitely surprised me to learn that go's garbage collection required all threads stop. That can't possibly manifest as anything other than a visible and uncontrollable "THUNK" in your application. I'd love to see a pros/cons comparison between Go's all at once strategy vs Erlang's per process strategy.
- pcwalton 13y ago
  The pros and cons are pretty simple. Go's advantage is that you can share data cheaply while retaining memory safety [1]. The disadvantage is that you have stop-the-world GC and potential for data races, so you must rely on the race detector. Erlang's advantage is that you have no data races and no stop-the-world GC (and Erlang's GC is easier to implement). The disadvantage is that all messages must be copied and parallel algorithms that require data sharing are more difficult to write. There are hybrid approaches like Singularity, JS with transferable data structures, and Rust (disclaimer: I work on Rust). These systems use some form of static or dynamic access control scheme (for example, uniqueness or immutability) to control data races and perform memory management for shared data structures, while retaining Erlang's thread-local GC. [1] With one exception, the memory unsafe data race in maps and slices. See: http://research.swtch.com/gorace http://research.swtch.com/gorace
  - pron 13y ago
    Go has gone the Java route (I find both runtimes to be somewhat similar -- well other than the whole JIT thing -- with Java some years ahead in terms of GC and scheduling), and I suppose that Go, too, will get a concurrent GC sooner or later, but even the concurrent GC on the JVM has a few stop-the-world phases.

parennoob 13y ago

I don't understand much about processes and threads, but I do know a bit about queues. What is the meaning of this? "Once a context has run a goroutine until a scheduling point, it pops a goroutine off its runqueue, sets stack and instruction pointer and begins running the goroutine." Do they mean: "begins running the next goroutine"?