www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Fiber is better than go's goroutine?

reply "FrankLike" <1150015857 qq.com> writes:
Many persons like go's goroutine,but how about is the same thing 
in D?
Thank you everyone.
Oct 26 2014
parent reply "Sean Kelly" <sean invisibleduck.org> writes:
On Sunday, 26 October 2014 at 15:35:28 UTC, FrankLike wrote:

 Many persons like go's goroutine,but how about is the same 
 thing in D?


We need a better Scheduler.  It's something I've been planning to 
do, but had held off until the base Scheduler proposal was 
accepted.  At that point I think D will be in pretty good shape.  
The FiberScheduler is a good start though, if you want to 
experiment.
Oct 26 2014
next sibling parent reply Martin Nowak <code+news.digitalmars dawg.eu> writes:
On 10/26/2014 05:12 PM, Sean Kelly wrote:

 We need a better Scheduler.  It's something I've been planning to do,
 but had held off until the base Scheduler proposal was accepted.  At
 that point I think D will be in pretty good shape. The FiberScheduler is
 a good start though, if you want to experiment.


How do you want to tackle the integration of Fibers/Schedulers and 
blocking APIs? That's the more important part of goroutines.
http://blog.nindalf.com/how-goroutines-work/#goroutinesblocking
Oct 26 2014
parent reply "Sean Kelly" <sean invisibleduck.org> writes:
On Sunday, 26 October 2014 at 20:47:47 UTC, Martin Nowak wrote:

 How do you want to tackle the integration of Fibers/Schedulers 
 and blocking APIs? That's the more important part of goroutines.
 http://blog.nindalf.com/how-goroutines-work/#goroutinesblocking


That will be tricky, since some of our blocking APIs are in 
Druntime (core.thread and core.sync) and std.concurrency is in 
Phobos.  I may have to add a yield() hook in Druntime that can be 
set by std concurrency.  But for now I think it's reasonable to 
say that std.concurrency will work as expected so long as you 
stick to Phobos functions and that Druntime simply operates at a 
lower level.

The real tricky part, which is something that even Go doesn't 
address as far as I know, is what to do about third-party APIs 
that block.  The easiest way around this is to launch threads 
that deal with these APIs in actual kernel threads instead of 
fibers, or try to make the scheduler smart enough to recognize 
that blocking is occurring (or more generally, that a given 
logical thread isn't playing nice) and move that fiber into a 
dedicated kernel thread automatically.  This latter approach 
seems entirely possible but will likely mean kernel calls to 
gather statistics regarding how long a given thread executes 
before yielding, etc.
Oct 27 2014
next sibling parent reply "Martin Nowak" <code dawg.eu> writes:
On Monday, 27 October 2014 at 16:32:25 UTC, Sean Kelly wrote:
That's the reason why the await adapter is so powerful.
It's should be possible to await a promise (future) to let the 
scheduler know that it should resume the Fiber only after the 
promise (future) was set.
Oct 28 2014
parent "Sean Kelly" <sean invisibleduck.org> writes:
On Tuesday, 28 October 2014 at 07:59:32 UTC, Martin Nowak wrote:

 On Monday, 27 October 2014 at 16:32:25 UTC, Sean Kelly wrote:
 That's the reason why the await adapter is so powerful.
 It's should be possible to await a promise (future) to let the 
 scheduler know that it should resume the Fiber only after the 
 promise (future) was set.


What's in the guts of the await adapter is the important part.  I 
already have that from a functional standpoint within the 
Scheduler, but the thread is basically polling state, which is 
terribly inefficient.
Oct 28 2014
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/27/14 9:32 AM, Sean Kelly wrote:

 The real tricky part, which is something that even Go doesn't address as
 far as I know, is what to do about third-party APIs that block.  The
 easiest way around this is to launch threads that deal with these APIs
 in actual kernel threads instead of fibers, or try to make the scheduler
 smart enough to recognize that blocking is occurring (or more generally,
 that a given logical thread isn't playing nice) and move that fiber into
 a dedicated kernel thread automatically.  This latter approach seems
 entirely possible but will likely mean kernel calls to gather statistics
 regarding how long a given thread executes before yielding, etc.


I'm not sure but as far as I understand this one issue forces Go code to 
have a strong networking effect (must call into Go code designed 
especially for cooperative threading). That forces a lot of rewriting of 
existing code.

Andrei
Oct 28 2014
parent "Martin Nowak" <code dawg.eu> writes:
On Tuesday, 28 October 2014 at 17:05:13 UTC, Andrei Alexandrescu
wrote:

 I'm not sure but as far as I understand this one issue forces 
 Go code to have a strong networking effect (must call into Go 
 code designed especially for cooperative threading). That 
 forces a lot of rewriting of existing code.


Yes these things only work with coroutine aware functions,
because they need to yield execution back to the scheduler when
some function blocks.
This is also true for our Fibers and the reason why vibe.d and
libasync implement their own Socket, File and Mutex primitives.

The await proposal mentioned in the other thread
(http://forum.dlang.org/post/izosaywbnlxnbzyhjbnu forum.dlang.org)
solve this problem by using generic constructs (based on Promises
and Awaitable adapters).

It should be possible to define a notion of Resumable that is
compatible with Fibers, Stackless Resumable Functions and even
Callbacks (.then(doThis)).

So a scheduler would only need to know that it should resume a
Resumable once the associated Promise finishes. How the promise
is computed is irrelevant.
Oct 28 2014
prev sibling parent reply "Sean Kelly" <sean invisibleduck.org> writes:
On Sunday, 26 October 2014 at 16:12:29 UTC, Sean Kelly wrote:

 On Sunday, 26 October 2014 at 15:35:28 UTC, FrankLike wrote:

 Many persons like go's goroutine,but how about is the same 
 thing in D?


 We need a better Scheduler.  It's something I've been planning 
 to do, but had held off until the base Scheduler proposal was 
 accepted.  At that point I think D will be in pretty good 
 shape.  The FiberScheduler is a good start though, if you want 
 to experiment.


One thing I just ran into while working on MultiScheduler is that 
if a spawned thread is holding a lock when it yields, and by 
yielding is picked up and executed by another thread, Bad Things 
happen.  In hindsight this sees obvious, but it's something I 
hadn't considered until now.

I think this shouldn't be much of a concern given that you're not 
supposed to be doing any more inside a mutex than necessary, and 
so things like sending and receiving messages should never occur 
within a synchronized block anyway, but it's an important issue 
to be aware of.  I'm still mulling over whether it's worth the 
cost to try and detect this and throw an Error.

In related news, MultiScheduler is coming along nicely.  It's 
already functional, and I'm polishing the implementation.  I 
found the issue with mutexes because of an implementation bug in 
MultiScheduler, since fixed, so this shouldn't be a concern for 
normal use.  This scheduler is still pretty basic, so an even 
fancier one may be worth creating that tracks execution times and 
such to ensure progress in the presence of misbehaved user 
threads.
Oct 27 2014
parent reply "Brad Anderson" <eco gnuk.net> writes:
On Monday, 27 October 2014 at 20:37:26 UTC, Sean Kelly wrote:

 One thing I just ran into while working on MultiScheduler is 
 that if a spawned thread is holding a lock when it yields, and 
 by yielding is picked up and executed by another thread, Bad 
 Things happen.  In hindsight this sees obvious, but it's 
 something I hadn't considered until now.


Just out of curiosity, what's the goal of MultiScheduler? Is it 
intended to be an M:N scheduler?
Oct 27 2014
parent reply "Sean Kelly" <sean invisibleduck.org> writes:
On Monday, 27 October 2014 at 20:54:38 UTC, Brad Anderson wrote:

 Just out of curiosity, what's the goal of MultiScheduler? Is it 
 intended to be an M:N scheduler?


Yep.  Every logical thread is a Fiber executed in a round-robin 
manner by a pool of kernel threads.  Pooled threads are spun up 
on demand (to a set upper limit) and terminate when there are no 
fibers waiting to execute.  It should make for a good "millions 
of threads" baseline scheduler.
Oct 27 2014
next sibling parent reply "Brad Anderson" <eco gnuk.net> writes:
On Monday, 27 October 2014 at 21:43:47 UTC, Sean Kelly wrote:

 On Monday, 27 October 2014 at 20:54:38 UTC, Brad Anderson wrote:

 Just out of curiosity, what's the goal of MultiScheduler? Is 
 it intended to be an M:N scheduler?


 Yep.  Every logical thread is a Fiber executed in a round-robin 
 manner by a pool of kernel threads.  Pooled threads are spun up 
 on demand (to a set upper limit) and terminate when there are 
 no fibers waiting to execute.  It should make for a good 
 "millions of threads" baseline scheduler.


Again, just out of curiosity, have you ever looked at Windows 
user-mode scheduling or Google's user-level threads[1][2] (under 
200ns context-switch times)? I first heard of them from a post on 
the Rust forum[3] which suggested M:N may be a dead end. I 
believe Rust decided to try to make sure either 1:1 or M:N could 
be used but I don't actively follow Rust's development so I may 
be mistaken.

M:N is certainly a step up from our current situation in any case.

1. Talk: https://www.youtube.com/watch?v=KXuZi9aeGTw
2. Slides: 
http://www.linuxplumbersconf.org/2013/ocw//system/presentations/1653/original/LPC%20-%20User%20Threading.pdf
3. 
https://mail.mozilla.org/pipermail/rust-dev/2013-November/006550.html
Oct 27 2014
parent "Sean Kelly" <sean invisibleduck.org> writes:
On Monday, 27 October 2014 at 22:59:50 UTC, Brad Anderson wrote:

 Again, just out of curiosity, have you ever looked at Windows 
 user-mode scheduling or Google's user-level threads[1][2] 
 (under 200ns context-switch times)? I first heard of them from 
 a post on the Rust forum[3] which suggested M:N may be a dead 
 end. I believe Rust decided to try to make sure either 1:1 or 
 M:N could be used but I don't actively follow Rust's 
 development so I may be mistaken.


No, but I will.  The round robin scheduling is turning out to be 
considerably better than using all kernel threads in some cases 
and far far worse in others.  Really, any case where you have a 
large percentage of "threads" waiting to be notified, round robin 
wastes a lot of time.  Fixing this means treating "just yield" 
threads, "wait forever until notified" threads, and "wait N 
seconds unless notified" threads all differently in terms of the 
CPU time devoted to checking their state.  Something like 
libevent would help here, but I'll see what I can do.  I suspect 
WaitForMultipleObjects or the like will be needed on Windows, 
etc.  Thanks for the references.
Oct 28 2014
prev sibling parent reply "Martin Nowak" <code dawg.eu> writes:
On Monday, 27 October 2014 at 21:43:47 UTC, Sean Kelly wrote:

 Yep.  Every logical thread is a Fiber executed in a round-robin 
 manner by a pool of kernel threads.  Pooled threads are spun up 
 on demand (to a set upper limit) and terminate when there are 
 no fibers waiting to execute.  It should make for a good 
 "millions of threads" baseline scheduler.


Will you reuse std.parallel's task scheduler for that?
I always thought that the std.parallel and Fibers should work 
together but it wasn't easily possible to adapt Fibers to Tasks.
Oct 28 2014
parent "Sean Kelly" <sean invisibleduck.org> writes:
On Tuesday, 28 October 2014 at 08:02:23 UTC, Martin Nowak wrote:

 On Monday, 27 October 2014 at 21:43:47 UTC, Sean Kelly wrote:

 Yep.  Every logical thread is a Fiber executed in a 
 round-robin manner by a pool of kernel threads.  Pooled 
 threads are spun up on demand (to a set upper limit) and 
 terminate when there are no fibers waiting to execute.  It 
 should make for a good "millions of threads" baseline 
 scheduler.


 Will you reuse std.parallel's task scheduler for that?
 I always thought that the std.parallel and Fibers should work 
 together but it wasn't easily possible to adapt Fibers to Tasks.


This wasn't really a natural fit for std.parallelism.  There are 
very few lines of code dedicated to thread management though 
anyway.  The code as-is isn't much bigger than FiberScheduler.  
The complicated bit will be making scheduling efficient, which 
I've decided has to happen for MultiScheduler to be actually 
worth using.  It isn't as much of a proof of concept like 
FiberScheduler.
Oct 28 2014