Hacker News Reader

Comment by jpolitz | Hacker News Reader

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

[1] https://github.com/plasma-umass/doppio

[2] https://cs.brown.edu/~sk/Publications/Papers/Published/yk-wh...

[3] https://github.com/gopherjs/gopherjs#goroutines

View on HN

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

Thanks for the good vibes!

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.

Because generators may be implemented with delineated continuations but they are not themselves the same thing.

Are you sure it's not because those frameworks/libraries were written before generators became available in the latest browsers?

that's Delimited continuation

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?

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

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.

Ah! You're right. Now I get what you mean. Thanks.

No problem. Thanks for asking bluntly about generators. It made me write some more experiments using them.

Right now, the main thing that I think stands in the way of them being a good solution for Pyret is that they have limited stack depth – about 7000 frames on Chrome Canary, for instance. One thing we get out of our strategy, which reifies stack frames onto the heap when pausing, is that we can simulate a much deeper stack.

See http://imgur.com/a/GaBg2 (I don't need to be able to do sum of ten million, but 10,000 would be nice! This is just so a non-tail-recursive map works over reasonable-sized lists; we'd rather not have the concept of tail recursion as a curricular dependency for working with that size of data.)

Pyret looks like a good endeavor.

Another dumb question: doesn't every recursive function have an iterative version? and in the case where you're transpiling to JS couldn't 'map' (whatever the syntax in Pyret) and other functional primitives be converted to imperative code? Generator functions are no different than regular functions when it comes to stack depth. I think that depends on the amount of memory you have, so different from machine to machine. I'm learning by asking dumb questions... :)

> doesn't every recursive function have an iterative version

True in the abstract, yes. But it's a sophisticated compiler indeed that turns something like a recursive binary tree traversal into a loop (it would need to synthesize the stack worklist).

In practice, it's easy to do this for tail recursion (and mutual tail recursion, with a little more sophistication). You can get slightly fancier with "tail recursion modulo cons," which is a little more clever and handles map. Beyond that, it's pretty gnarly to do a good transformation, because recursive code is implicitly using the stack in interesting ways.

> couldn't... functional primitives be converted to imperative code

Indeed, and we do write those in pure JS with carefully-crafted while loops to make those primitives more efficient. But if students are learning to write their own map, or another functional combinator on lists, those need to work, too, and will be implemented recursively by them.

> Generator functions are no different than regular functions when it comes to stack depth.

Yeah, stack depth in general is annoyingly low on modern browsers, IMO, so this isn't just a problem with generators. It's also unpredictable (http://stackoverflow.com/a/28730491/2718315). So we're working around the normal stack limit already. I was sort of hoping that when a generator's continuation was captured, it would stay heap-allocated and not "count" towards stack space when restarted, but that's not the case.

Self-reply for posterity. Here's a sketched-out comparison of generators vs. the manual strategy we use in Pyret (this isn't _exactly_ what Pyret generated code looks like, but it's close):

https://www.measurethat.net/Benchmarks/Show/675/0/stack-stra...

As of October 2016, generators are much slower on all browsers I tested.

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?

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

Reply on news.ycombinator.com