7 ms·

> all relevant standard library methods have been patched to yield to the scheduler whenever they encounter a situation where they will block the current fiber

by rdw 6y ago

> all relevant standard library methods have been patched to yield to the scheduler whenever they encounter a situation where they will block the current fiber This is huge. They solved the function-coloring problem by deciding that all functions are now potentially async. It makes it more likely that the ecosystem as a whole actually becomes async-compatible. I wish Python had taken this approach, though I understand why they didn't.

cogman10 6y ago
This is essentially the approach Java is taking with the upcoming loom project.
Rapzid 6y ago
I don't see how this solves the "coloring" problem. "Colored" functions have a different return type; a future of some sort. If you want to return a future to a caller, or have a method that blocks until the work is done, you still need a way to differentiate that. Golang does essentially the same thing and uses channels instead of "futures". However, some APIs will have functions that return a channel that you receive a message on later.. Which is a lot like a future. And if you provide a more simple non-channel API along side(instead of making the consumer wrap your calls in a Go routine or always use a channel), you now have "colored" functions. I believe this is just a solution to a scheduling problem(pre-emptive vs cooperative).
- chrisseaton 6y ago
  > "Colored" functions have a different return type; a future of some sort. This is an aside and possibly pedantic, but everyone seems to have forgotten that the whole idea of futures was originally that they weren't some different type. They were the same type, but blocked transparently on demand and had no `get` operation. The construct that came before futures, called eventual-values, had the different-type thing. The only difference of futures, the big idea, was they said 'maybe we can get rid of that part'. > These “futures” greatly resemble the “eventual values” of Hibbard’s Algol 68 [39]. The principal difference is that eventual values are declared as a separate data type, distinct from the type of the value they take on, whereas futures cannot be distinguished from the type of the value they take on. (Halstead, 1985) But now people write types like `Future[T]`... which completely misses the point! If you start to write `Future[...` then think to yourself... this isn't a future. And that's how you get this colouring problem you describe... it was already fixed and people have forgotten all about it.
  - dfee 6y ago
    I don’t understand your final point. Are you saying that generics on futures are bad? I don’t see the alternative.
    - chrisseaton 6y ago
      > Are you saying that generics on futures are bad? Yes - because it means existing code that expects a T cannot accept a Future<T>, which is the colouring problem being discussed. You end up with half your code accepting futures and the other legacy half not accepting them and there's a divide. If you want to use the legacy code you have to force the future potentially before you really needed it. > I don’t see the alternative. The alternative is wherever a function accepts a concrete value T t, also let it accept a future value T t. When t is actually used, then block as if get was called.
      - tinco 6y ago
        Does this mean that Rust's Future trait is incorrectly named? Or at least not named according to the academic use of the word? Of course because Rust's runtime or lack thereof aims to be zero overhead a Future could never be without the poll function.. right? You need a runtime to make regular functions accept these magic opaque future values.
        chrisseaton 6y ago
        Yes not named according to the original paper. Yes it requires some kind of special compiler or runtime support.
      - wbl 6y ago
        Isn't Future a functor?
        chrisseaton 6y ago
        That's not the intention of the original authors, no.
- rdw 6y ago
  It solves the coloring problem by not having a coloring problem in the first place. Maybe I should have said "avoids the function-coloring problem".
  - Rapzid 6y ago
    I believe the example in the article "avoids the function-coloring problem" by completely avoiding its problem space of continuing the execution of an imperative block of code after starting an asynchronous task to produce some value, and then synchronizing at the production of that value. In the example each code block run in a fiber blocks at Net::HTTP.get and only continues after it returns a value. Looking at the API for Fiber.. It looks like "resume" returns the yield(generator) or fiber return value? So Fibers can be treated as a sort of Promise? As soon as you start returning fibers from methods you have the coloring problem..
orf 6y ago
> They solved the function-coloring problem Not really, they've just made it super implicit. Any FFI calls are now implicitly coloured, same with anything CPU-heavy. Like their approach to type annotations, I think this will be a mistake in hindsight.
- rdw 6y ago
  This is gonna sound pedantic but I think it's not a coloring problem. Coloring is when syntactically a function has to change its own signature just because it started calling an inner function with the new color. That said, you're right in that one may have to make some changes to code to get around some new problems. The problem with FFI/CPU-heavy functions is that they prevent _other_ fibers from being scheduled while they run. If it becomes possible to implement work-stealing, then that would mitigate the problem. It would also be solvable by sprinkling "yield to scheduler" calls throughout such functions. Annoying and not always possible, but, since in these cases the signature would not change, technically not coloring.
  - gpderetta 6y ago
    It is not pedantic at all, you are completely right; if this implementation were to be classified as coloroing, then everything would be, including classic threads.
  - ioquatix 6y ago
    Ruby FFI has been experimenting with provided support for kicking external functions to background threads with a single keyword argument.
- lalaithion 6y ago
  In a high level dynamic language with exceptions, there's already so many implicit "colors" to a function that I think this is still the right choice.
- svieira 6y ago
  This "implicit coloring" is what's talked about in _Unyielding_ [1], which is the "explicit color is good" counterpoint to _What Color is Your Function?_ (though Unyielding predates WCIYF by about a year). [1]: https://glyph.twistedmatrix.com/2014/02/unyielding.html https://glyph.twistedmatrix.com/2014/02/unyielding.html
WJW 6y ago
(Author here) I kinda agree but yielding only on I/O is not enough IMO. Sooner or later we'll want to do CPU intensive work in fibers as well, which in the current implementation will block all other fibers on the same thread. Like I mentioned in the article, I'd like to see work stealing between different threads as that would allow fibers to migrate away from threads stuck in CPU intensive work. An alternative way could be to adopt a model similar to Haskells lightweight threads, where the runtime forces a `yield` after N milliseconds (configurable). That would make sure that CPU intensive work would not block other fibers "too" much.
- nesarkvechnep 6y ago
  This is not only the way Haskell's scheduler work but also Erlang VM's. Not completely the same because the BEAM scheduler uses reductions instead of time but both scheduling schemes can be classified as preemptive. Since fibers are cooperatively scheduled I don't believe the core developers of Ruby would just agree to switch the scheduling scheme.
- anonacct38 6y ago
  Go's journey here has been interesting. Early on it was possible (though rarely seen in practice) to end up with a cpu bound thread not yielding because it didn't hit yield point like I/O. Then they added a guarantee that if your loop called a function, the scheduler would be able to make the goroutine yield. https://golang.org/doc/go1.2#preemption https://golang.org/doc/go1.2#preemption This mostly worked although you could still have a CPU-bound thread not making any function calls. I also personally ran into a pathological issue where the scheduler was being invoked, but a heuristic kept the current goroutine running so others were still starved. Finally they added true pre-emption (not yielding) in 1.14 https://golang.org/doc/go1.14#runtime https://golang.org/doc/go1.14#runtime it looks like it just sends signals and saves state. Once nice thing is that if I understand the go runtime correctly, work stealing by scheduling goroutines on different threads has been a thing for a long time.
- matheusmoreira 6y ago
  > Sooner or later we'll want to do CPU intensive work in fibers as well, which in the current implementation will block all other fibers on the same thread. This limitation is present in every modern asynchronous programming system I've ever seen. They simply can't deal with long function calls. There's a loop under the hood which constantly executes queued functions. Any long-running function will stall the execution pipeline and increase latency. It's just like cooperative multitasking...
ghostwriter 6y ago
Python has gevent.

by rdw 6y ago

cogman10 6y ago

This is essentially the approach Java is taking with the upcoming loom project.

Rapzid 6y ago

I don't see how this solves the "coloring" problem. "Colored" functions have a different return type; a future of some sort. If you want to return a future to a caller, or have a method that blocks until the work is done, you still need a way to differentiate that. Golang does essentially the same thing and uses channels instead of "futures". However, some APIs will have functions that return a channel that you receive a message on later.. Which is a lot like a future. And if you provide a more simple non-channel API along side(instead of making the consumer wrap your calls in a Go routine or always use a channel), you now have "colored" functions. I believe this is just a solution to a scheduling problem(pre-emptive vs cooperative).

chrisseaton 6y ago
> "Colored" functions have a different return type; a future of some sort. This is an aside and possibly pedantic, but everyone seems to have forgotten that the whole idea of futures was originally that they weren't some different type. They were the same type, but blocked transparently on demand and had no `get` operation. The construct that came before futures, called eventual-values, had the different-type thing. The only difference of futures, the big idea, was they said 'maybe we can get rid of that part'. > These “futures” greatly resemble the “eventual values” of Hibbard’s Algol 68 [39]. The principal difference is that eventual values are declared as a separate data type, distinct from the type of the value they take on, whereas futures cannot be distinguished from the type of the value they take on. (Halstead, 1985) But now people write types like `Future[T]`... which completely misses the point! If you start to write `Future[...` then think to yourself... this isn't a future. And that's how you get this colouring problem you describe... it was already fixed and people have forgotten all about it.
- dfee 6y ago
  I don’t understand your final point. Are you saying that generics on futures are bad? I don’t see the alternative.
  - chrisseaton 6y ago
    > Are you saying that generics on futures are bad? Yes - because it means existing code that expects a T cannot accept a Future<T>, which is the colouring problem being discussed. You end up with half your code accepting futures and the other legacy half not accepting them and there's a divide. If you want to use the legacy code you have to force the future potentially before you really needed it. > I don’t see the alternative. The alternative is wherever a function accepts a concrete value T t, also let it accept a future value T t. When t is actually used, then block as if get was called.
    - tinco 6y ago
      Does this mean that Rust's Future trait is incorrectly named? Or at least not named according to the academic use of the word? Of course because Rust's runtime or lack thereof aims to be zero overhead a Future could never be without the poll function.. right? You need a runtime to make regular functions accept these magic opaque future values.
      - chrisseaton 6y ago
        Yes not named according to the original paper. Yes it requires some kind of special compiler or runtime support.
    - wbl 6y ago
      Isn't Future a functor?
      - chrisseaton 6y ago
        That's not the intention of the original authors, no.
rdw 6y ago
It solves the coloring problem by not having a coloring problem in the first place. Maybe I should have said "avoids the function-coloring problem".
- Rapzid 6y ago
  I believe the example in the article "avoids the function-coloring problem" by completely avoiding its problem space of continuing the execution of an imperative block of code after starting an asynchronous task to produce some value, and then synchronizing at the production of that value. In the example each code block run in a fiber blocks at Net::HTTP.get and only continues after it returns a value. Looking at the API for Fiber.. It looks like "resume" returns the yield(generator) or fiber return value? So Fibers can be treated as a sort of Promise? As soon as you start returning fibers from methods you have the coloring problem..

orf 6y ago

> They solved the function-coloring problem Not really, they've just made it super implicit. Any FFI calls are now implicitly coloured, same with anything CPU-heavy. Like their approach to type annotations, I think this will be a mistake in hindsight.

rdw 6y ago
This is gonna sound pedantic but I think it's not a coloring problem. Coloring is when syntactically a function has to change its own signature just because it started calling an inner function with the new color. That said, you're right in that one may have to make some changes to code to get around some new problems. The problem with FFI/CPU-heavy functions is that they prevent _other_ fibers from being scheduled while they run. If it becomes possible to implement work-stealing, then that would mitigate the problem. It would also be solvable by sprinkling "yield to scheduler" calls throughout such functions. Annoying and not always possible, but, since in these cases the signature would not change, technically not coloring.
- gpderetta 6y ago
  It is not pedantic at all, you are completely right; if this implementation were to be classified as coloroing, then everything would be, including classic threads.
- ioquatix 6y ago
  Ruby FFI has been experimenting with provided support for kicking external functions to background threads with a single keyword argument.
lalaithion 6y ago
In a high level dynamic language with exceptions, there's already so many implicit "colors" to a function that I think this is still the right choice.
svieira 6y ago
This "implicit coloring" is what's talked about in _Unyielding_ [1], which is the "explicit color is good" counterpoint to _What Color is Your Function?_ (though Unyielding predates WCIYF by about a year). [1]: https://glyph.twistedmatrix.com/2014/02/unyielding.html https://glyph.twistedmatrix.com/2014/02/unyielding.html

WJW 6y ago

(Author here) I kinda agree but yielding only on I/O is not enough IMO. Sooner or later we'll want to do CPU intensive work in fibers as well, which in the current implementation will block all other fibers on the same thread. Like I mentioned in the article, I'd like to see work stealing between different threads as that would allow fibers to migrate away from threads stuck in CPU intensive work. An alternative way could be to adopt a model similar to Haskells lightweight threads, where the runtime forces a `yield` after N milliseconds (configurable). That would make sure that CPU intensive work would not block other fibers "too" much.

nesarkvechnep 6y ago
This is not only the way Haskell's scheduler work but also Erlang VM's. Not completely the same because the BEAM scheduler uses reductions instead of time but both scheduling schemes can be classified as preemptive. Since fibers are cooperatively scheduled I don't believe the core developers of Ruby would just agree to switch the scheduling scheme.
anonacct38 6y ago
Go's journey here has been interesting. Early on it was possible (though rarely seen in practice) to end up with a cpu bound thread not yielding because it didn't hit yield point like I/O. Then they added a guarantee that if your loop called a function, the scheduler would be able to make the goroutine yield. https://golang.org/doc/go1.2#preemption https://golang.org/doc/go1.2#preemption This mostly worked although you could still have a CPU-bound thread not making any function calls. I also personally ran into a pathological issue where the scheduler was being invoked, but a heuristic kept the current goroutine running so others were still starved. Finally they added true pre-emption (not yielding) in 1.14 https://golang.org/doc/go1.14#runtime https://golang.org/doc/go1.14#runtime it looks like it just sends signals and saves state. Once nice thing is that if I understand the go runtime correctly, work stealing by scheduling goroutines on different threads has been a thing for a long time.
matheusmoreira 6y ago
> Sooner or later we'll want to do CPU intensive work in fibers as well, which in the current implementation will block all other fibers on the same thread. This limitation is present in every modern asynchronous programming system I've ever seen. They simply can't deal with long function calls. There's a loop under the hood which constantly executes queued functions. Any long-running function will stall the execution pipeline and increase latency. It's just like cooperative multitasking...

ghostwriter 6y ago

Python has gevent.