Quantcast

Continuations / Fibers

classic Classic list List threaded Threaded
25 messages Options
12
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Continuations / Fibers

Andrew Trumper
Hi All,

I've been meaning to ask for some time. Is there anyone working on
adding continuations to the jvm with the idea of using them to allow the
writing of single-threaded threaded Actors more naturally? ie: instead
of callbacks just blocking? like:

Typical modern style:
someAsyncTask()
   .mapAsync(result -> someOtherAsyncTask(result))
   .mapAsync(otherResult -> yetAnotherAsyncTask(otherResult))
   .onSuccess(yetAnotherResult -> System.out.println( "" +
yetAnotherResult))
   .setInvoker(thisThread);

converts to:

// doesn't block the current (actor? EDT?) thread
Object result = yetAnotherAsyncTask(someOtherAsyncTask(someAsyncTask()));
System.out.println( "" + result );

- Andrew

--

This email or any attachments may contain confidential or legally
privileged information intended for the sole use of the addressees. Any
use, redistribution, disclosure, or reproduction of this information,
except as intended, is prohibited. If you received this email in error,
please notify the sender and remove all copies of the message, including
any attachments.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Markus KARG
I don't understand the question. Why not just using CompletableFuture to build Fibers?

-----Original Message-----
From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Andrew Trumper
Sent: Freitag, 7. Oktober 2016 19:48
To: [hidden email]
Subject: [concurrency-interest] Continuations / Fibers

Hi All,

I've been meaning to ask for some time. Is there anyone working on adding continuations to the jvm with the idea of using them to allow the writing of single-threaded threaded Actors more naturally? ie: instead of callbacks just blocking? like:

Typical modern style:
someAsyncTask()
   .mapAsync(result -> someOtherAsyncTask(result))
   .mapAsync(otherResult -> yetAnotherAsyncTask(otherResult))
   .onSuccess(yetAnotherResult -> System.out.println( "" +
yetAnotherResult))
   .setInvoker(thisThread);

converts to:

// doesn't block the current (actor? EDT?) thread Object result = yetAnotherAsyncTask(someOtherAsyncTask(someAsyncTask()));
System.out.println( "" + result );

- Andrew

--

This email or any attachments may contain confidential or legally privileged information intended for the sole use of the addressees. Any use, redistribution, disclosure, or reproduction of this information, except as intended, is prohibited. If you received this email in error, please notify the sender and remove all copies of the message, including any attachments.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Viktor Klang
From a syntax PoV, there's things like Scala Async (which is syntactically similar to C# async/await): https://github.com/scala/async

On Fri, Oct 7, 2016 at 7:55 PM, Markus KARG <[hidden email]> wrote:
I don't understand the question. Why not just using CompletableFuture to build Fibers?

-----Original Message-----
From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Andrew Trumper
Sent: Freitag, 7. Oktober 2016 19:48
To: [hidden email]
Subject: [concurrency-interest] Continuations / Fibers

Hi All,

I've been meaning to ask for some time. Is there anyone working on adding continuations to the jvm with the idea of using them to allow the writing of single-threaded threaded Actors more naturally? ie: instead of callbacks just blocking? like:

Typical modern style:
someAsyncTask()
   .mapAsync(result -> someOtherAsyncTask(result))
   .mapAsync(otherResult -> yetAnotherAsyncTask(otherResult))
   .onSuccess(yetAnotherResult -> System.out.println( "" +
yetAnotherResult))
   .setInvoker(thisThread);

converts to:

// doesn't block the current (actor? EDT?) thread Object result = yetAnotherAsyncTask(someOtherAsyncTask(someAsyncTask()));
System.out.println( "" + result );

- Andrew

--

This email or any attachments may contain confidential or legally privileged information intended for the sole use of the addressees. Any use, redistribution, disclosure, or reproduction of this information, except as intended, is prohibited. If you received this email in error, please notify the sender and remove all copies of the message, including any attachments.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



--
Cheers,

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Andrew Trumper
I guess I'm wondering if anyone is working on bringing async/await like
functionality to java. Either by continuation support in the JVM or
whatever magic Scala uses.

Given that java has a great concurrency community around it, I'm
surprised I never seem to hear anything about it.

- Andrew

On 10/07/2016 02:09 PM, Viktor Klang wrote:

> From a syntax PoV, there's things like Scala Async (which is
> syntactically similar to C# async/await): https://github.com/scala/async
>
> On Fri, Oct 7, 2016 at 7:55 PM, Markus KARG <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     I don't understand the question. Why not just using
>     CompletableFuture to build Fibers?
>
>     -----Original Message-----
>     From: Concurrency-interest
>     [mailto:[hidden email]
>     <mailto:[hidden email]>] On Behalf Of
>     Andrew Trumper
>     Sent: Freitag, 7. Oktober 2016 19:48
>     To: [hidden email]
>     <mailto:[hidden email]>
>     Subject: [concurrency-interest] Continuations / Fibers
>
>     Hi All,
>
>     I've been meaning to ask for some time. Is there anyone working on
>     adding continuations to the jvm with the idea of using them to allow
>     the writing of single-threaded threaded Actors more naturally? ie:
>     instead of callbacks just blocking? like:
>
>     Typical modern style:
>     someAsyncTask()
>        .mapAsync(result -> someOtherAsyncTask(result))
>        .mapAsync(otherResult -> yetAnotherAsyncTask(otherResult))
>        .onSuccess(yetAnotherResult -> System.out.println( "" +
>     yetAnotherResult))
>        .setInvoker(thisThread);
>
>     converts to:
>
>     // doesn't block the current (actor? EDT?) thread Object result =
>     yetAnotherAsyncTask(someOtherAsyncTask(someAsyncTask()));
>     System.out.println( "" + result );
>
>     - Andrew
>
>     --
>
>     This email or any attachments may contain confidential or legally
>     privileged information intended for the sole use of the addressees.
>     Any use, redistribution, disclosure, or reproduction of this
>     information, except as intended, is prohibited. If you received this
>     email in error, please notify the sender and remove all copies of
>     the message, including any attachments.
>
>     _______________________________________________
>     Concurrency-interest mailing list
>     [hidden email]
>     <mailto:[hidden email]>
>     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>     <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
>
>     _______________________________________________
>     Concurrency-interest mailing list
>     [hidden email]
>     <mailto:[hidden email]>
>     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>     <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
>
>
>
>
> --
> Cheers,
> √

--

This email or any attachments may contain confidential or legally
privileged information intended for the sole use of the addressees. Any
use, redistribution, disclosure, or reproduction of this information,
except as intended, is prohibited. If you received this email in error,
please notify the sender and remove all copies of the message, including
any attachments.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Viktor Klang
By no means exhaustive:

Scala uses no magic, only macros. So no need for language support.

Quasar does bytecode rewriting to implement fibers: https://github.com/puniverse/quasar








On Fri, Oct 7, 2016 at 10:40 PM, Andrew Trumper <[hidden email]> wrote:
I guess I'm wondering if anyone is working on bringing async/await like functionality to java. Either by continuation support in the JVM or whatever magic Scala uses.

Given that java has a great concurrency community around it, I'm surprised I never seem to hear anything about it.

- Andrew

On 10/07/2016 02:09 PM, Viktor Klang wrote:
From a syntax PoV, there's things like Scala Async (which is
syntactically similar to C# async/await): https://github.com/scala/async

On Fri, Oct 7, 2016 at 7:55 PM, Markus KARG <[hidden email]
<mailto:[hidden email]>> wrote:

    I don't understand the question. Why not just using
    CompletableFuture to build Fibers?

    -----Original Message-----
    From: Concurrency-interest
    [mailto:[hidden email]
    <mailto:[hidden email]>] On Behalf Of
    Andrew Trumper
    Sent: Freitag, 7. Oktober 2016 19:48
    To: [hidden email]
    <mailto:[hidden email]>
    Subject: [concurrency-interest] Continuations / Fibers

    Hi All,

    I've been meaning to ask for some time. Is there anyone working on
    adding continuations to the jvm with the idea of using them to allow
    the writing of single-threaded threaded Actors more naturally? ie:
    instead of callbacks just blocking? like:

    Typical modern style:
    someAsyncTask()
       .mapAsync(result -> someOtherAsyncTask(result))
       .mapAsync(otherResult -> yetAnotherAsyncTask(otherResult))
       .onSuccess(yetAnotherResult -> System.out.println( "" +
    yetAnotherResult))
       .setInvoker(thisThread);

    converts to:

    // doesn't block the current (actor? EDT?) thread Object result =
    yetAnotherAsyncTask(someOtherAsyncTask(someAsyncTask()));
    System.out.println( "" + result );

    - Andrew

    --

    This email or any attachments may contain confidential or legally
    privileged information intended for the sole use of the addressees.
    Any use, redistribution, disclosure, or reproduction of this
    information, except as intended, is prohibited. If you received this
    email in error, please notify the sender and remove all copies of
    the message, including any attachments.

    _______________________________________________
    Concurrency-interest mailing list
    [hidden email]
    <mailto:[hidden email]>
    http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>

    _______________________________________________
    Concurrency-interest mailing list
    [hidden email]
    <mailto:[hidden email]>
    http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>




--
Cheers,


--

This email or any attachments may contain confidential or legally privileged information intended for the sole use of the addressees. Any use, redistribution, disclosure, or reproduction of this information, except as intended, is prohibited. If you received this email in error, please notify the sender and remove all copies of the message, including any attachments.




--
Cheers,

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Charles Oliver Nutter-4
On Fri, Oct 7, 2016 at 3:46 PM, Viktor Klang <[hidden email]> wrote:
Scala uses no magic, only macros. So no need for language support.

Quasar does bytecode rewriting to implement fibers: https://github.com/puniverse/quasar


Coroutine options built atop threads suffer from inter-thread signaling delays, thread count limits, and high memory use.

Options that use trampolines and bytecode rewriting impact performance and can't suspend/resume across call boundaries that haven't been likewise rewritten (so you have to rewrite everything).

True coroutines on the JVM would provide a lightweight way to cooperatively share a thread of execution across multiple call stacks. Go has 'em, Ruby has 'em, Python has 'em...the JVM needs 'em.

- Charlie

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Viktor Klang


On Fri, Oct 7, 2016 at 11:07 PM, Charles Oliver Nutter <[hidden email]> wrote:
On Fri, Oct 7, 2016 at 3:46 PM, Viktor Klang <[hidden email]> wrote:
Scala uses no magic, only macros. So no need for language support.

Quasar does bytecode rewriting to implement fibers: https://github.com/puniverse/quasar


Coroutine options built atop threads suffer from inter-thread signaling delays, thread count limits, and high memory use.

There will need to be inter-thread signalling anyway, though?
 

Options that use trampolines and bytecode rewriting impact performance and can't suspend/resume across call boundaries that haven't been likewise rewritten (so you have to rewrite everything).

Not only that, you'd have to rewrite all usage of monitorenter/monitorexit.
 

True coroutines on the JVM would provide a lightweight way to cooperatively share a thread of execution across multiple call stacks. Go has 'em, Ruby has 'em, Python has 'em...the JVM needs 'em.

You still have problems with native code calls…
 

- Charlie



--
Cheers,

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Viktor Klang
Sorry if I sound negative, JVM-native coroutines would be interesting.

On Fri, Oct 7, 2016 at 11:18 PM, Viktor Klang <[hidden email]> wrote:


On Fri, Oct 7, 2016 at 11:07 PM, Charles Oliver Nutter <[hidden email]> wrote:
On Fri, Oct 7, 2016 at 3:46 PM, Viktor Klang <[hidden email]> wrote:
Scala uses no magic, only macros. So no need for language support.

Quasar does bytecode rewriting to implement fibers: https://github.com/puniverse/quasar


Coroutine options built atop threads suffer from inter-thread signaling delays, thread count limits, and high memory use.

There will need to be inter-thread signalling anyway, though?
 

Options that use trampolines and bytecode rewriting impact performance and can't suspend/resume across call boundaries that haven't been likewise rewritten (so you have to rewrite everything).

Not only that, you'd have to rewrite all usage of monitorenter/monitorexit.
 

True coroutines on the JVM would provide a lightweight way to cooperatively share a thread of execution across multiple call stacks. Go has 'em, Ruby has 'em, Python has 'em...the JVM needs 'em.

You still have problems with native code calls…
 

- Charlie



--
Cheers,



--
Cheers,

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Continuations / Fibers

Vitaly Davidovich
In reply to this post by Charles Oliver Nutter-4


On Friday, October 7, 2016, Charles Oliver Nutter <<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;headius@headius.com&#39;);" target="_blank">headius@...> wrote:
On Fri, Oct 7, 2016 at 3:46 PM, Viktor Klang <[hidden email]> wrote:
Scala uses no magic, only macros. So no need for language support.

Quasar does bytecode rewriting to implement fibers: https://github.com/puniverse/quasar


Coroutine options built atop threads suffer from inter-thread signaling delays, thread count limits, and high memory use.

Options that use trampolines and bytecode rewriting impact performance and can't suspend/resume across call boundaries that haven't been likewise rewritten (so you have to rewrite everything).

True coroutines on the JVM would provide a lightweight way to cooperatively share a thread of execution across multiple call stacks. Go has 'em, Ruby has 'em, Python has 'em...the JVM needs 'em.
Looks like C++ will also be getting them.

I think John Rose may have some JVM thoughts on this - this might be a good post to the mlvm list rather than concurrency-interest (although I understand why this list was picked). 

- Charlie


--
Sent from my phone

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Charles Oliver Nutter-4
In reply to this post by Viktor Klang
On Fri, Oct 7, 2016 at 4:18 PM, Viktor Klang <[hidden email]> wrote:
There will need to be inter-thread signalling anyway, though?

No. A thread can switch from one fiber to another without involving the thread scheduler.
 
 Not only that, you'd have to rewrite all usage of monitorenter/monitorexit.

Locking is a challenge but it's no better with thread-based coroutines. In fact, it might be easier, since we wouldn't have to pass ownership of a lock around to different threads.

 You still have problems with native code calls…

Not necessarily. If the JVM can see the size of the native frames on the stack, it would be able to reify and swap them out too. JNI-wise, if suspend/resume only happen from managed code, I think safepoint entry/exit should be balanced on the stack too.

This definitely gets into some deeper magic than I know, but there has already been a prototype of coroutines for OpenJDK, and it worked pretty well: https://wiki.openjdk.java.net/display/mlvm/Coroutines

As with tail calling, someone needs to champion this work at a JVMS/JLS/JCP level. It might be possible to do something short term through JEPs.

> Sorry if I sound negative, JVM-native coroutines would be interesting.

Not at all :-) These are fair points. Coroutines solve many problems of thread-based "microthreading" and introduce some others of their own. At least we'd have a very interesting and unusual hammer to add to our bag of hammers!

- Charlie

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Nathan & Ila Reynolds
In reply to this post by Charles Oliver Nutter-4

Here’s a 10,000-foot view of a possible implementation of fibers in the JVM.

 

At the lowest level, a thread is simply a CPU state (i.e. registers), stack space and wakeup condition.  At a higher level, there are Java objects tied to the thread (i.e. Thread and ThreadLocals).  On x86, these objects are accessed through a CPU register so the CPU state handles this.

 

To implement fibers, it seems that when a fiber is going to block, then the registers have to be saved (e.g. x86 pusha instruction), the instruction pointer changed in the saved stated and the wakeup condition has to be created.  (The registers have a pointer to the stack.)  Once this is completed, the thread can go find another runnable fiber.  The thread then loads the registers for that fiber (e.g. x86 popa instruction) and starts executing.

 

From the above 10,000-foot view, it seems like we could implement fibers in Java with no visible side-effects from Java.  The visible side-effects would be visible through JNI.  Am I missing something?

However, it doesn’t seem like we have saved that much.  We still have stack space allocated to each fiber.  We still have context switching but it is implemented in user space and not kernel space.  I don’t think this is going to make much difference since context switching is no longer costly.  Hence, I am not sure what this implementation of fibers really buys us that plain old threads don’t already accomplish.  Is there a better way to implement fibers which mitigates the cost of threads?

 

-Nathan

 

From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Charles Oliver Nutter
Sent: Friday, October 07, 2016 3:07 PM
To: Viktor Klang <[hidden email]>
Cc: concurrency-interest <[hidden email]>
Subject: Re: [concurrency-interest] Continuations / Fibers

 

On Fri, Oct 7, 2016 at 3:46 PM, Viktor Klang <[hidden email]> wrote:

Scala uses no magic, only macros. So no need for language support.

 

Quasar does bytecode rewriting to implement fibers: https://github.com/puniverse/quasar

 

 

Coroutine options built atop threads suffer from inter-thread signaling delays, thread count limits, and high memory use.

 

Options that use trampolines and bytecode rewriting impact performance and can't suspend/resume across call boundaries that haven't been likewise rewritten (so you have to rewrite everything).

 

True coroutines on the JVM would provide a lightweight way to cooperatively share a thread of execution across multiple call stacks. Go has 'em, Ruby has 'em, Python has 'em...the JVM needs 'em.

 

- Charlie


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Viktor Klang
In reply to this post by Charles Oliver Nutter-4


On Fri, Oct 7, 2016 at 11:29 PM, Charles Oliver Nutter <[hidden email]> wrote:
On Fri, Oct 7, 2016 at 4:18 PM, Viktor Klang <[hidden email]> wrote:
There will need to be inter-thread signalling anyway, though?

No. A thread can switch from one fiber to another without involving the thread scheduler.

Sure, but if you want to be able to leverage multithreading then you're going to need a jvm-level fiber scheduler anyway.
(compare to Erlang for instance).
 
 
 Not only that, you'd have to rewrite all usage of monitorenter/monitorexit.

Locking is a challenge but it's no better with thread-based coroutines. In fact, it might be easier, since we wouldn't have to pass ownership of a lock around to different threads.

That will definitely affect runtime behavior tho.
(Same tradeoffs which the OS-level scheduler has when it comes to thread-to-core migration/retention)
 

 You still have problems with native code calls…

Not necessarily. If the JVM can see the size of the native frames on the stack, it would be able to reify and swap them out too. JNI-wise, if suspend/resume only happen from managed code, I think safepoint entry/exit should be balanced on the stack too.

Sure, but the vm wouldn't know if the native call ever hands back control or not.
 

This definitely gets into some deeper magic than I know, but there has already been a prototype of coroutines for OpenJDK, and it worked pretty well: https://wiki.openjdk.java.net/display/mlvm/Coroutines


Thanks for the link!
 
As with tail calling, someone needs to champion this work at a JVMS/JLS/JCP level. It might be possible to do something short term through JEPs.

Sadly I'd expect a 5 year battle… :S
 

> Sorry if I sound negative, JVM-native coroutines would be interesting.

Not at all :-) These are fair points. Coroutines solve many problems of thread-based "microthreading" and introduce some others of their own. At least we'd have a very interesting and unusual hammer to add to our bag of hammers!

Worth having a look at the thoughts behind Scheduler Activations as well.
 

- Charlie



--
Cheers,

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Charles Oliver Nutter-4

On Fri, Oct 7, 2016 at 4:41 PM, Viktor Klang <[hidden email]> wrote:
On Fri, Oct 7, 2016 at 11:29 PM, Charles Oliver Nutter <[hidden email]> wrote:
No. A thread can switch from one fiber to another without involving the thread scheduler.

Sure, but if you want to be able to leverage multithreading then you're going to need a jvm-level fiber scheduler anyway.
(compare to Erlang for instance).

Fibers, at least in the Ruby (and I believe win32) sense, do not cross thread boundaries. Coroutines could or could not (but it would be more useful if they could).

But that's largely beside the point. Yes, if you want to hand a coroutine off from one thread to another, or have a group of N threads driving those coroutines, they'll have to coordinate. But you could also have any number of coroutines running on the *same* thread, without any handoff. You're timeslicing one thread into many threadlets without any hand-off (other than the overhead of suspend/resume).
 
 Locking is a challenge but it's no better with thread-based coroutines. In fact, it might be easier, since we wouldn't have to pass ownership of a lock around to different threads.

That will definitely affect runtime behavior tho.
(Same tradeoffs which the OS-level scheduler has when it comes to thread-to-core migration/retention)

I think just about everything relating to true coroutines will affect runtime behavior in some way :-)

It's a fundamentally new concurrency mechanism from anything we have on JVM right now (other than the bytecode-rewriting options, which are a close approximation).
 
  
Not necessarily. If the JVM can see the size of the native frames on the stack, it would be able to reify and swap them out too. JNI-wise, if suspend/resume only happen from managed code, I think safepoint entry/exit should be balanced on the stack too.

Sure, but the vm wouldn't know if the native call ever hands back control or not.

If the native call never hands control back, it would never be able to resume. My point above was that suspend/resume would only be problematic when JNI code upcalls back into the JVM, but in that case it will have exited its safepoint anyway. It should be possible to save off those native frames without causing headaches for the GC.

At least, that's my impression of how it would work. Devil's in the details!
As with tail calling, someone needs to champion this work at a JVMS/JLS/JCP level. It might be possible to do something short term through JEPs.

Sadly I'd expect a 5 year battle… :S

Yes...I wish someone with a pressing need would have started ten years ago. I would have, if I weren't already working on a rather language implementation :-D
 
Not at all :-) These are fair points. Coroutines solve many problems of thread-based "microthreading" and introduce some others of their own. At least we'd have a very interesting and unusual hammer to add to our bag of hammers!

Worth having a look at the thoughts behind Scheduler Activations as well.

I'll have a look, thanks!

- Charlie

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Viktor Klang


On Fri, Oct 7, 2016 at 11:52 PM, Charles Oliver Nutter <[hidden email]> wrote:

On Fri, Oct 7, 2016 at 4:41 PM, Viktor Klang <[hidden email]> wrote:
On Fri, Oct 7, 2016 at 11:29 PM, Charles Oliver Nutter <[hidden email]> wrote:
No. A thread can switch from one fiber to another without involving the thread scheduler.

Sure, but if you want to be able to leverage multithreading then you're going to need a jvm-level fiber scheduler anyway.
(compare to Erlang for instance).

Fibers, at least in the Ruby (and I believe win32) sense, do not cross thread boundaries. Coroutines could or could not (but it would be more useful if they could).

But that's largely beside the point. Yes, if you want to hand a coroutine off from one thread to another, or have a group of N threads driving those coroutines, they'll have to coordinate. But you could also have any number of coroutines running on the *same* thread, without any handoff. You're timeslicing one thread into many threadlets without any hand-off (other than the overhead of suspend/resume).

Well of course—I've spent the past 7-8 years implementing Actors on the JVM ;)
 
 
 Locking is a challenge but it's no better with thread-based coroutines. In fact, it might be easier, since we wouldn't have to pass ownership of a lock around to different threads.

That will definitely affect runtime behavior tho.
(Same tradeoffs which the OS-level scheduler has when it comes to thread-to-core migration/retention)

I think just about everything relating to true coroutines will affect runtime behavior in some way :-)

Perhaps we need to define "true coroutines" so we're talking about the same semantics :-)
 

It's a fundamentally new concurrency mechanism from anything we have on JVM right now (other than the bytecode-rewriting options, which are a close approximation).

It's not really that new, I'd say, but I'm getting old ;)
 
 
  
Not necessarily. If the JVM can see the size of the native frames on the stack, it would be able to reify and swap them out too. JNI-wise, if suspend/resume only happen from managed code, I think safepoint entry/exit should be balanced on the stack too.

Sure, but the vm wouldn't know if the native call ever hands back control or not.

If the native call never hands control back, it would never be able to resume.

Yes, but now all coroutines that are parked behind it will be starved forver—unless—you migrate fibers across threads. :)
 
My point above was that suspend/resume would only be problematic when JNI code upcalls back into the JVM, but in that case it will have exited its safepoint anyway. It should be possible to save off those native frames without causing headaches for the GC.

GC interaction is above my paygrade ^^
 

At least, that's my impression of how it would work. Devil's in the details!
As with tail calling, someone needs to champion this work at a JVMS/JLS/JCP level. It might be possible to do something short term through JEPs.

Sadly I'd expect a 5 year battle… :S

Yes...I wish someone with a pressing need would have started ten years ago. I would have, if I weren't already working on a rather language implementation :-D

Haha :)
 
 
Not at all :-) These are fair points. Coroutines solve many problems of thread-based "microthreading" and introduce some others of their own. At least we'd have a very interesting and unusual hammer to add to our bag of hammers!

Worth having a look at the thoughts behind Scheduler Activations as well.

I'll have a look, thanks!

- Charlie



--
Cheers,

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Charles Oliver Nutter-4
In reply to this post by Nathan & Ila Reynolds
On Fri, Oct 7, 2016 at 4:40 PM, Nathan & Ila Reynolds <[hidden email]> wrote:

Here’s a 10,000-foot view of a possible implementation of fibers in the JVM.

 

At the lowest level, a thread is simply a CPU state (i.e. registers), stack space and wakeup condition.  At a higher level, there are Java objects tied to the thread (i.e. Thread and ThreadLocals).  On x86, these objects are accessed through a CPU register so the CPU state handles this.

 

To implement fibers, it seems that when a fiber is going to block, then the registers have to be saved (e.g. x86 pusha instruction), the instruction pointer changed in the saved stated and the wakeup condition has to be created.  (The registers have a pointer to the stack.)  Once this is completed, the thread can go find another runnable fiber.  The thread then loads the registers for that fiber (e.g. x86 popa instruction) and starts executing.


Yeah, that's about the size of it.
 

 From the above 10,000-foot view, it seems like we could implement fibers in Java with no visible side-effects from Java.  The visible side-effects would be visible through JNI.  Am I missing something?


From Java with no assistance from the JVM? I don't think so. Bytecode-rewriting options fundamentally change how methods execute and can't interact with non-rewritten code, so I don't consider them a complete (or particularly useful) solution. At some level, someone's going to have to get into the dirty native bits and actually save those registers off and deal with saving any frames that happen to be shared (most coroutines are not root threads; they are multiple tentacles dangling off of the same root thread, so you need to manage partial stacks).

Have a look at the MLVM link I posted...there's a paper that describes Lukas's approach (lazy stack reification, etc). He helped us implement JRuby Fibers atop Coroutines at one point, and the single-thread speed of Fiber switching improved something like 8x.
 

However, it doesn’t seem like we have saved that much.  We still have stack space allocated to each fiber.  We still have context switching but it is implemented in user space and not kernel space.  I don’t think this is going to make much difference since context switching is no longer costly.  Hence, I am not sure what this implementation of fibers really buys us that plain old threads don’t already accomplish.  Is there a better way to implement fibers which mitigates the cost of threads?


Stack space for fibers can be smaller than for threads, since you have a smaller downstream set of calls to make. In C Ruby, the default Fiber stack size is something 1/10 the default Thread stack size. But yes, both options have to have stack space *somewhere*.

Context switching in user space can *definitely* be cheaper than switching threads at the kernel level, because the kernel doesn't have to be involved, you don't fight the thread-scheduler to get your coroutine to start running again, you don't have to do nasty tricks to keep threads hot, etc. If you reduce the cost of switching enough, coroutine A's last blocking instruction might be followed only very quickly by coroutine B's first non-blocking instruction. Experimentally, the prototype coroutine support made a huge different for single-thread coroutine scheduling in JRuby. I've never managed to get thread-to-thread context switching to even come close.

- Charlie 

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Alex Otenko
In reply to this post by Nathan & Ila Reynolds
Anything can be written in assembly :-)

It offers a different way to separate concerns.

A glaring example, although far from what people usually see async is useful for:

try to write an Iterator for a binary Tree. You’ll need to spend a lot of mental effort to maintain the state - are you in the left leaf? where’s the parent node? oh, you need a pointer to the parent now? have you visited its right subtree? This is because you have to take into account the concern of the consumer of the data - they will need sequential access to the Tree nodes.


Now, with co-routines it becomes trivial to express and easy to understand - because the concern of how exactly the values are consumed, are separated from the concern of how the values are produced.

function* depthfirst(t){
  if (t === undefined) return;
  yield t.value;
  yield* depthfirst(t.left);
  yield* depthfirst(t.right);
}

Alex

On 7 Oct 2016, at 22:40, Nathan & Ila Reynolds <[hidden email]> wrote:

Here’s a 10,000-foot view of a possible implementation of fibers in the JVM.
 
At the lowest level, a thread is simply a CPU state (i.e. registers), stack space and wakeup condition.  At a higher level, there are Java objects tied to the thread (i.e. Thread and ThreadLocals).  On x86, these objects are accessed through a CPU register so the CPU state handles this.
 
To implement fibers, it seems that when a fiber is going to block, then the registers have to be saved (e.g. x86 pusha instruction), the instruction pointer changed in the saved stated and the wakeup condition has to be created.  (The registers have a pointer to the stack.)  Once this is completed, the thread can go find another runnable fiber.  The thread then loads the registers for that fiber (e.g. x86 popa instruction) and starts executing.
 
From the above 10,000-foot view, it seems like we could implement fibers in Java with no visible side-effects from Java.  The visible side-effects would be visible through JNI.  Am I missing something?
However, it doesn’t seem like we have saved that much.  We still have stack space allocated to each fiber.  We still have context switching but it is implemented in user space and not kernel space.  I don’t think this is going to make much difference since context switching is no longer costly.  Hence, I am not sure what this implementation of fibers really buys us that plain old threads don’t already accomplish.  Is there a better way to implement fibers which mitigates the cost of threads?
 
-Nathan
 
From: Concurrency-interest [[hidden email]] On Behalf Of Charles Oliver Nutter
Sent: Friday, October 07, 2016 3:07 PM
To: Viktor Klang <[hidden email]>
Cc: concurrency-interest <[hidden email]>
Subject: Re: [concurrency-interest] Continuations / Fibers
 
On Fri, Oct 7, 2016 at 3:46 PM, Viktor Klang <[hidden email]> wrote:
Scala uses no magic, only macros. So no need for language support.
 
Quasar does bytecode rewriting to implement fibers: https://github.com/puniverse/quasar
 
 
Coroutine options built atop threads suffer from inter-thread signaling delays, thread count limits, and high memory use.
 
Options that use trampolines and bytecode rewriting impact performance and can't suspend/resume across call boundaries that haven't been likewise rewritten (so you have to rewrite everything).
 
True coroutines on the JVM would provide a lightweight way to cooperatively share a thread of execution across multiple call stacks. Go has 'em, Ruby has 'em, Python has 'em...the JVM needs 'em.
 
- Charlie
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Charles Oliver Nutter-4
In reply to this post by Viktor Klang
On Fri, Oct 7, 2016 at 4:58 PM, Viktor Klang <[hidden email]> wrote:
Perhaps we need to define "true coroutines" so we're talking about the same semantics :-)

"True" coroutines, to me, are swappable stacks of execution that can hand off control on the same thread (or possibly on a different thread), do not involve the thread-scheduler to do so, but DO have real native execution stacks with calls deepening that stack. It is not possible to implement them in Java on today's JVMs.

It's a fundamentally new concurrency mechanism from anything we have on JVM right now (other than the bytecode-rewriting options, which are a close approximation).

It's not really that new, I'd say, but I'm getting old ;)

From a VM perspective...it's very peculiar. I usually have a VM perspective :-)

At a user level, coroutines simulated with threads or bytecode rewriting at least *look* the same as true coroutines. The interesting differences are not at that level.

If the native call never hands control back, it would never be able to resume.

Yes, but now all coroutines that are parked behind it will be starved forver—unless—you migrate fibers across threads. :)

If you make a blocking call to *anything* that doesn't suspend, you're blocking a thread. This is no different in calls from Java to Java; a coroutine that calls a method that loops forever or a thread that calls an actor that loops forever both get stuck. This is not unique to coroutines; badly-behaved code is still badly-behaved code.

Perhaps this isn't clear: coroutines are *cooperatively* scheduled, not *preemptively* scheduled like a thread. And just like in any cooperatively-scheduled system, you have to cooperate :-)
 
- Charlie

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Viktor Klang


On Sat, Oct 8, 2016 at 12:14 AM, Charles Oliver Nutter <[hidden email]> wrote:
On Fri, Oct 7, 2016 at 4:58 PM, Viktor Klang <[hidden email]> wrote:
Perhaps we need to define "true coroutines" so we're talking about the same semantics :-)

"True" coroutines, to me, are swappable stacks of execution that can hand off control on the same thread (or possibly on a different thread), do not involve the thread-scheduler to do so, but DO have real native execution stacks with calls deepening that stack. It is not possible to implement them in Java on today's JVMs.

It's a fundamentally new concurrency mechanism from anything we have on JVM right now (other than the bytecode-rewriting options, which are a close approximation).

It's not really that new, I'd say, but I'm getting old ;)

From a VM perspective...it's very peculiar. I usually have a VM perspective :-)

At a user level, coroutines simulated with threads or bytecode rewriting at least *look* the same as true coroutines. The interesting differences are not at that level.

If the native call never hands control back, it would never be able to resume.

Yes, but now all coroutines that are parked behind it will be starved forver—unless—you migrate fibers across threads. :)

If you make a blocking call to *anything* that doesn't suspend, you're blocking a thread. This is no different in calls from Java to Java; a coroutine that calls a method that loops forever or a thread that calls an actor that loops forever both get stuck. This is not unique to coroutines; badly-behaved code is still badly-behaved code.

Perhaps this isn't clear: coroutines are *cooperatively* scheduled, not *preemptively* scheduled like a thread. And just like in any cooperatively-scheduled system, you have to cooperate :-)

You can still instrument the instructions and do reduction counting á la Erlang to address fairness and "timeslicing" so you get opportunity for preemption.
 
 
- Charlie



--
Cheers,

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Charles Oliver Nutter-4
In reply to this post by Alex Otenko
On Fri, Oct 7, 2016 at 5:12 PM, Alex Otenko <[hidden email]> wrote:
try to write an Iterator for a binary Tree. You’ll need to spend a lot of mental effort to maintain the state - are you in the left leaf? where’s the parent node? oh, you need a pointer to the parent now? have you visited its right subtree? This is because you have to take into account the concern of the consumer of the data - they will need sequential access to the Tree nodes.


Now, with co-routines it becomes trivial to express and easy to understand - because the concern of how exactly the values are consumed, are separated from the concern of how the values are produced.

I think it's helpful to think of coroutines as allowing you to reify stack state as just another piece of your application. By suspending, you yank off an execution context and swap in another on the same thread. When the coroutine is later resumed, you have the same stack state as before ready for execution. It's continuation-passing style, which of course can be converted to a hand-written state machine that tracks all that execution-contextual state. With coroutines, you don't have to write that state machine :-)

- Charlie

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Continuations / Fibers

Charles Oliver Nutter-4
In reply to this post by Viktor Klang


On Fri, Oct 7, 2016 at 5:17 PM, Viktor Klang <[hidden email]> wrote:
You can still instrument the instructions and do reduction counting á la Erlang to address fairness and "timeslicing" so you get opportunity for preemption.

EOUTOFSCOPE

- Charlie


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
12
Loading...