4 ms·

Part of these notes, Fiber [0], reminds me of a half-joking "corollary" to Greenspun's Tenth Rule (credit @shriramkmurthi): Any sufficiently complicated Java

by jpolitz 10y ago

Part of these notes, Fiber [0], reminds me of a half-joking "corollary" to Greenspun's Tenth Rule (credit @shriramkmurthi): Any sufficiently complicated JavaScript program contains an ad hoc, informally-specified, bug-ridden, slow implementation of delimited continuations. Control over continuations and the stack is our main compiler and runtime engineering hurdle in Pyret. Projects like Doppio [1], WeScheme [2] and GopherJS [3] go through staggering amounts of overhead and effort to get pausable, resumable, and stoppable computation in the browser environment. I'm excited to see how this develops in React with fiber. It's much more application-specific, but it's the same underlying problem. [0] https://facebook.github.io/react/contributing/codebase-overview.html#fiber-reconciler https://facebook.github.io/react/contributing/codebase-overv... [1] https://github.com/plasma-umass/doppio https://github.com/plasma-umass/doppio [2] https://cs.brown.edu/~sk/Publications/Papers/Published/yk-whalesong-racket-browser/paper.pdf https://cs.brown.edu/~sk/Publications/Papers/Published/yk-wh... [3] https://github.com/gopherjs/gopherjs#goroutines https://github.com/gopherjs/gopherjs#goroutines

ilostmykeys 10y ago
What about generators? I've built coroutines based on generators. CSP has been implemented in JS using generators. Not sure why those projects went thru "staggering amount of overhead" to get what we get for free with generators. Please educate.
- 1propionyl 10y ago
  Because generators may be implemented with delineated continuations but they are not themselves the same thing.
  - ilostmykeys 10y ago
    Are you sure it's not because those frameworks/libraries were written before generators became available in the latest browsers? :)
  - morenoh149 10y ago
    that's Delimited continuation
- jpolitz 10y ago
  The main difference is that all of the use cases I mentioned necessarily don't distinguish between calls/functions that may pause, and calls that don't (it's just the semantics of those languages that arbitrary calls might need to pause). So to use generators as a compilation target, every function has to be a generator, and every call a generator instantiation followed by yield*. I actually don't know if that qualifies as "staggering". Your sibling comment has some truth; I can only speak generally about Gopherjs and Doppio, because I know them less intimately, but I know that Pyret and Whalesong were definitely started before generators had widespread adoption. Compiling to generators, rather than to the handwritten stack unwinding we have, is on my list of things to try and measure. Maybe "significant" overhead would be more obviously true than "staggering," since I don't have clear numbers to back it up. Does that make sense?
  - ilostmykeys 10y ago
    <<So to use generators as a compilation target, every function has to be a generator>> Sure, but in those cases the functions are transpiled to JS so it doesn't really matter, not like they're coded by hand, right...? I think I understand what you mean.
    - jpolitz 10y ago
      I don't know what you mean by "it doesn't really matter." Surely there's a cost to using generators instead of regular function calls and returns, right? That's where the overhead would come from, because generators aren't free. Right now, Pyret and GopherJS (the last time I checked in GopherJS's case) basically manually encode the `IteratorResult` type, and check for "stack unwind" vs "regular result" when each function call returns, if it might pause. The first question for generators is if they are less overhead than this manual process. There's a bunch of other details, too, but this is the main one. And generators are certainly going to cause _some_ overhead over regular calls and returns, just like the manual checking of return values has overhead. My original comment was about the lack of something like delimited continuations in JS, which would allow saving portions of the stack while intentionally minimizing the overhead of regular function calls. That's a well-fitting language-level solution to this issue.
eyan 10y ago
Offtopic but... I'm cheering for pyret! And for the group behind it of course. :)
- jpolitz 10y ago
  Thanks for the good vibes!
amelius 10y ago
Interesting. Do you also address scheduling? I.e., giving some computations priority over others? And do you address the implicit transfer of those priorities based on a dependency graph?
- jpolitz 10y ago
  My conjecture: Scheduling with priority is pretty easy across these systems. The dependency graph transfer would be outside the scope of what they already tackle, and require new engineering. In Pyret, I prototyped virtual threads at one point, and each thread had the same amount of "fuel" before yielding (at the top of every compiled function in Pyret, there's a decrement to a "fuel" counter, and when it reaches zero, the stack is unwound). That could easily be configured on each start/restart of a thread to provide different amounts of fuel, or to re-order the restarts based on typical thread-scheduling policies. Whalesong does the same thing with fuel, so I imagine it could be extended similarly. I don't know how Doppio and GopherJS do scheduling in detail, but here's where I'd start looking: 1. GopherJS looks like it's a simple queue based on the code around https://github.com/gopherjs/gopherjs/blob/master/compiler/prelude/goroutines.go#L160 https://github.com/gopherjs/gopherjs/blob/master/compiler/pr... (goroutines push themselves onto a list when they pause, then the next one starts up again) 2. Doppio implements a thread pool abstraction, so you can simulate JVM threads in the browser: https://github.com/plasma-umass/doppio/blob/master/src/threadpool.ts#L1 https://github.com/plasma-umass/doppio/blob/master/src/threa...

by jpolitz 10y ago

ilostmykeys 10y ago

What about generators? I've built coroutines based on generators. CSP has been implemented in JS using generators. Not sure why those projects went thru "staggering amount of overhead" to get what we get for free with generators. Please educate.

1propionyl 10y ago
Because generators may be implemented with delineated continuations but they are not themselves the same thing.
- ilostmykeys 10y ago
  Are you sure it's not because those frameworks/libraries were written before generators became available in the latest browsers? :)
- morenoh149 10y ago
  that's Delimited continuation
jpolitz 10y ago
The main difference is that all of the use cases I mentioned necessarily don't distinguish between calls/functions that may pause, and calls that don't (it's just the semantics of those languages that arbitrary calls might need to pause). So to use generators as a compilation target, every function has to be a generator, and every call a generator instantiation followed by yield*. I actually don't know if that qualifies as "staggering". Your sibling comment has some truth; I can only speak generally about Gopherjs and Doppio, because I know them less intimately, but I know that Pyret and Whalesong were definitely started before generators had widespread adoption. Compiling to generators, rather than to the handwritten stack unwinding we have, is on my list of things to try and measure. Maybe "significant" overhead would be more obviously true than "staggering," since I don't have clear numbers to back it up. Does that make sense?
- ilostmykeys 10y ago
  <<So to use generators as a compilation target, every function has to be a generator>> Sure, but in those cases the functions are transpiled to JS so it doesn't really matter, not like they're coded by hand, right...? I think I understand what you mean.
  - jpolitz 10y ago
    I don't know what you mean by "it doesn't really matter." Surely there's a cost to using generators instead of regular function calls and returns, right? That's where the overhead would come from, because generators aren't free. Right now, Pyret and GopherJS (the last time I checked in GopherJS's case) basically manually encode the `IteratorResult` type, and check for "stack unwind" vs "regular result" when each function call returns, if it might pause. The first question for generators is if they are less overhead than this manual process. There's a bunch of other details, too, but this is the main one. And generators are certainly going to cause _some_ overhead over regular calls and returns, just like the manual checking of return values has overhead. My original comment was about the lack of something like delimited continuations in JS, which would allow saving portions of the stack while intentionally minimizing the overhead of regular function calls. That's a well-fitting language-level solution to this issue.

eyan 10y ago

Offtopic but... I'm cheering for pyret! And for the group behind it of course. :)

jpolitz 10y ago
Thanks for the good vibes!

amelius 10y ago

Interesting. Do you also address scheduling? I.e., giving some computations priority over others? And do you address the implicit transfer of those priorities based on a dependency graph?

jpolitz 10y ago
My conjecture: Scheduling with priority is pretty easy across these systems. The dependency graph transfer would be outside the scope of what they already tackle, and require new engineering. In Pyret, I prototyped virtual threads at one point, and each thread had the same amount of "fuel" before yielding (at the top of every compiled function in Pyret, there's a decrement to a "fuel" counter, and when it reaches zero, the stack is unwound). That could easily be configured on each start/restart of a thread to provide different amounts of fuel, or to re-order the restarts based on typical thread-scheduling policies. Whalesong does the same thing with fuel, so I imagine it could be extended similarly. I don't know how Doppio and GopherJS do scheduling in detail, but here's where I'd start looking: 1. GopherJS looks like it's a simple queue based on the code around https://github.com/gopherjs/gopherjs/blob/master/compiler/prelude/goroutines.go#L160 https://github.com/gopherjs/gopherjs/blob/master/compiler/pr... (goroutines push themselves onto a list when they pause, then the next one starts up again) 2. Doppio implements a thread pool abstraction, so you can simulate JVM threads in the browser: https://github.com/plasma-umass/doppio/blob/master/src/threadpool.ts#L1 https://github.com/plasma-umass/doppio/blob/master/src/threa...