Difference between revisions of "MotionsToContinue"

From JVMLangSummit
Jump to navigationJump to search
Line 34: Line 34:
  
 
A simpler problem that illustrates a more typical use case is generating/iterating over the nodes of a binary tree.  Using threads or true coroutines, this can be done in linear time.  A common failing of coroutine implementations is that they require between O(n log n) and O(n^2) time for this use case.  That appears to be a limitation of the JVM prototype for continuations too.  While that doesn't totally undermine their utility, it does make them impractical for many applications.
 
A simpler problem that illustrates a more typical use case is generating/iterating over the nodes of a binary tree.  Using threads or true coroutines, this can be done in linear time.  A common failing of coroutine implementations is that they require between O(n log n) and O(n^2) time for this use case.  That appears to be a limitation of the JVM prototype for continuations too.  While that doesn't totally undermine their utility, it does make them impractical for many applications.
 +
 +
Asynchronous programming is another large class of use cases, also rooted in the desire to minimize the number of threads (again, because threads are expensive).  Assuming one can't simply make threads cheap enough, it is possible to build a library framework on top of coroutines that enable writing asynchronous code in the synchronous style (i.e., the system performs the inversion of control for you, under the covers).  Such frameworks have been built for C# and other languages using the language's iterator methods as corotuines.

Revision as of 14:23, 24 September 2009

We had a lively ad hoc workshop after Lukas Stadler's talk ended in a vigorous Q&A session.

Key design points for continuations:

  • full or scoped
  • restartability: one-shot or repeated restart
  • reflectability: opaque, read-only, serializable (forgeable!)
  • mobility: thread-bound, JVM-bound, mobile

These design choices are all more or less independent.

The Hottest Use Case
Generators and coroutines may be viewed as scoped, one-shot, opaque, and thread-bound.

Rose said: We're crazy (e.g, 2nd Life style continuations) but we're also willing to take short-term gains.

The Room said: We want coroutines & generators ASAP. That's your short-term goal, please.

Coroutines can be thread-bound, and swapped like Green Threads. But, in order to give them (and parallel generators!?) more room to grow into our multicore future, they must not be CPU-bound. This involves either (a) a non-thread-bound view of coroutines, or (b) a way to split threads into "fibers" (cf. Ruby).

Discussion
How much "fiber" do we need to be healthy here? Would it be best to layer fibers (at the Java level) onto thread pools? Or is there a JVM or hardware abstraction that's better? Must specify interactions with thread locals, thread locks, backtraces, (implicitly) thread critical sections, etc. Fibers seem to want "miniature" versions of all these. Basic problem is that threads have grown to do too much; we need a strength-reduced thread.
Hard Problem
How does existing code (bytecodes!) interact with continuations? Throw-out is OK, but restart is seemingly intractable. The result is that continuation restarting only works for code within a "silo" (e.g, code compiled by my Scheme bytecode compiler). Good model: Scheme's DYNAMIC-WIND. Key idea is bracketing; for every finalization there is a paired initialization; re-entry of a continuation runs the initialization. Problem: It's impossible to extract these retroactively from Java (source or bytecode).

Some (Bloch, Gafter?) claimed that the compatibility problem makes restartable continuations an impractical goal in our ecosystem, since no solution interoperates with existing JDK code. John: Distinguish between three kinds of code: 1. older stack frames outside a continuation, 2. stack frames crossed (especially resumed) by continuations, 3. younger stack frames which enter and exit without touching continuatiosn. 1 and 3 have no compatibility problem, 2 are a minority in the JDK, since they correspond to higher-order functions of some sort.

[Gafter: If you consider things like service provider frameworks to be higher-order functions, sure. I'm afraid this might include more than we expect.]

Code in category 2 is of course the problem. Glimmer of partial solution: If a Java method has no exception handlers, it is almost certainly bracket-free (or else originally buggy!). Stadler's solution is to accept siloing and annotate the category 2 methods; a continuation which fails to "see" an annotation will refuse to restart an unknown method, throwing an error instead.

[Gafter: It isn't clear to me that the scheme described can be checked at compile-time. A scheme that causes a runtime failure because something somewhere on the call stack doesn't have an annotation sounds disastrous from a software engineering perspective.]

Design Problem
What is the status of JVM locals w.r.t. continuations? John: They are a stable property of the continuation. Neal: Unless the continuation respects the mutable nature of JVM locals (and allows changes to them to persist into restarts) the continuation mechanism is useless. John: Useless = overstatement. Compiler writers will do what they always have, statically evacuate mutable variables to the heap, so as not to be caught up directly in the continuation. Neal, Josh: That's siloing, so it's wrong. ...Back to the previous Hard Problem.
Why coroutines
[Gafter] Setting aside continuations for a moment, the main reason that coroutines are needed is that threads are just too expensive. If threads were cheap enough, one could just create a thread to do the work, and use the normal synchronization mechanisms (again, presumably very cheap) to effect transfer of control. That is the Erlang philosophy. See http://gafter.blogspot.com/2007/07/internal-versus-external-iterators.html for an example of a problem easily solved using threads, but at a high cost (threads are very heavyweight). Reimplementing threads using a green model would help considerably. Implementing the (VM) stack in a segmented manner would help too. A solution that causes siloing, as C# and many other languages have done, cannot solve this example problem but does address many use cases in practice.

A simpler problem that illustrates a more typical use case is generating/iterating over the nodes of a binary tree. Using threads or true coroutines, this can be done in linear time. A common failing of coroutine implementations is that they require between O(n log n) and O(n^2) time for this use case. That appears to be a limitation of the JVM prototype for continuations too. While that doesn't totally undermine their utility, it does make them impractical for many applications.

Asynchronous programming is another large class of use cases, also rooted in the desire to minimize the number of threads (again, because threads are expensive). Assuming one can't simply make threads cheap enough, it is possible to build a library framework on top of coroutines that enable writing asynchronous code in the synchronous style (i.e., the system performs the inversion of control for you, under the covers). Such frameworks have been built for C# and other languages using the language's iterator methods as corotuines.