Has coroutine (sather style iterator) been discussed before on this list?  Will D has something similar?


C# has it:

http://gary.burd.info/space/entry-7.html

Sather has it:

http://www.icsi.berkeley.edu/~sather/Publications/toplas.html

Python has it:

http://www.python.org/doc/current/whatsnew/section-generators.html

some discussion on comp.lang.eiffel:

http://groups.google.com/groups?dq=&hl=en&lr=&ie=UTF-8&threadm=uy8zjfnmc.fsf%40wanadoo.fr&prev=/groups%3Fdq%3D%26num%3D25%26hl%3Den%26lr%3D%26ie%3DUTF-8%26group%3Dcomp.lang.eiffel%26start%3D25

http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&frame=right&th=4cd646634db7588c&seekm=b0f57d2d.0110101547.78d69f50%40posting.google.com#link21

Coroutines are pretty cool. They aren't in D now, but they could be added in the future.

"Walter" <walter@digitalmars.com> wrote in message news:bh617r$1vst$1@digitaldaemon.com...
> Coroutines are pretty cool. They aren't in D now, but they could be added
in
> the future.
>
can't NT (98 or NT3.51+) fibers be used ?

extern(Windows) {
LPVOID CreateFiber(DWORD dwStackSize,LPFIBER_START_ROUTINE
lpStartAddress,LPVOID lpParameter);
VOID DeleteFiber(LPVOID lpFiber);
LPVOID ConvertThreadToFiber(LPVOID lpParameter);
VOID SwitchToFiber(LPVOID lpFiber);
BOOL SwitchToThread();
}

not sure if linux/pthreads have similar facilities.

I know they do work I've tried a few basic tests with fibers, if someone posts an example of what they would like I'll see if I can produce a version in current D that uses fibers as an example.

I've been reading about fibers on google, but I am not yet convinced they
are the right solutions for coroutines because:
1) seems like a lot of overhead to manage them
2) not portable

"Mike Wynn" <mike.wynn@l8night.co.uk> wrote in message news:bh63a0$21m6$1@digitaldaemon.com...
>
> "Walter" <walter@digitalmars.com> wrote in message news:bh617r$1vst$1@digitaldaemon.com...
> > Coroutines are pretty cool. They aren't in D now, but they could be
added
> in
> > the future.
> >
> can't NT (98 or NT3.51+) fibers be used ?
>
> extern(Windows) {
> LPVOID CreateFiber(DWORD dwStackSize,LPFIBER_START_ROUTINE
> lpStartAddress,LPVOID lpParameter);
> VOID DeleteFiber(LPVOID lpFiber);
> LPVOID ConvertThreadToFiber(LPVOID lpParameter);
> VOID SwitchToFiber(LPVOID lpFiber);
> BOOL SwitchToThread();
> }
>
> not sure if linux/pthreads have similar facilities.
>
> I know they do work I've tried a few basic tests with fibers, if someone posts an example of what they would like I'll see if I can produce a
version
> in current D that uses fibers as an example.
>
>

Fibers are as lightweight as you want to make them.  They have almost zero overhead compared with threads.  All it is is swapping to a different stack; very similar to cooperative multitasking.

You can implement them yourself using nothing more than setjmp/longjmp (so long as you're able to figure out what the stack pointer is in the registers structure, which is platform dependent).  Or you can use Windows fibers, but you gain nothing by it except avoiding the hairy details of switching stacks and registers.

The compiler can internally implement fibers however it wants;  it's really quite simple and I can give you advice on implementation if you'd like.  You would want a custom implementation for each platform to get the most performance.

My coworkers used to call this "stack twiddling".  ;)  It can sure clear up the logic behind a state machine like you wouldn't believe.

Coroutines are just language syntax that enables transparent utilization of fibers.  "Yield" keyword just calls out to the fiber manager and saves the state of this fiber and lets the next fiber run, or switches back to the main fiber.  Calling a coroutine starts a new fiber or switches to one that's already running, resuming at just past where the previous yield left off.

You don't need language support to do this, but it would be cleaner, and the portability hassle of switching stacks would be best done in the compiler or standard library.

Sean

"Walter" <walter@digitalmars.com> wrote in message news:bh667t$24js$1@digitaldaemon.com...
> I've been reading about fibers on google, but I am not yet convinced they
> are the right solutions for coroutines because:
> 1) seems like a lot of overhead to manage them
> 2) not portable
>
> "Mike Wynn" <mike.wynn@l8night.co.uk> wrote in message news:bh63a0$21m6$1@digitaldaemon.com...
> >
> > "Walter" <walter@digitalmars.com> wrote in message news:bh617r$1vst$1@digitaldaemon.com...
> > > Coroutines are pretty cool. They aren't in D now, but they could be
> added
> > in
> > > the future.
> > >
> > can't NT (98 or NT3.51+) fibers be used ?
> >
> > extern(Windows) {
> > LPVOID CreateFiber(DWORD dwStackSize,LPFIBER_START_ROUTINE
> > lpStartAddress,LPVOID lpParameter);
> > VOID DeleteFiber(LPVOID lpFiber);
> > LPVOID ConvertThreadToFiber(LPVOID lpParameter);
> > VOID SwitchToFiber(LPVOID lpFiber);
> > BOOL SwitchToThread();
> > }
> >
> > not sure if linux/pthreads have similar facilities.
> >
> > I know they do work I've tried a few basic tests with fibers, if someone posts an example of what they would like I'll see if I can produce a
> version
> > in current D that uses fibers as an example.

Win32 fibers have various problems, such as not being able to de-fiberise a thread, nor to have multiple fibers within a thread, or the prosaic one of not being implemented in 9x.

I've wanted to do a platform-independent fibers API for ages, but just have never got round to it. I'd love to help do that for D, but alas would probably be more hindrance than help, asm not being my speciality ... <blushes>.

They definitely should be in D, as they're very useful things to have, but should be D's own, not layered on top of Win32.

"Sean L. Palmer" <palmer.sean@verizon.net> wrote in message news:bh6euu$2ci7$1@digitaldaemon.com...
> Fibers are as lightweight as you want to make them.  They have almost zero overhead compared with threads.  All it is is swapping to a different
stack;
> very similar to cooperative multitasking.
>
> You can implement them yourself using nothing more than setjmp/longjmp (so long as you're able to figure out what the stack pointer is in the
registers
> structure, which is platform dependent).  Or you can use Windows fibers,
but
> you gain nothing by it except avoiding the hairy details of switching
stacks
> and registers.
>
> The compiler can internally implement fibers however it wants;  it's
really
> quite simple and I can give you advice on implementation if you'd like.
You
> would want a custom implementation for each platform to get the most performance.
>
> My coworkers used to call this "stack twiddling".  ;)  It can sure clear
up
> the logic behind a state machine like you wouldn't believe.
>
> Coroutines are just language syntax that enables transparent utilization
of
> fibers.  "Yield" keyword just calls out to the fiber manager and saves the state of this fiber and lets the next fiber run, or switches back to the main fiber.  Calling a coroutine starts a new fiber or switches to one that's already running, resuming at just past where the previous yield
left
> off.
>
> You don't need language support to do this, but it would be cleaner, and
the
> portability hassle of switching stacks would be best done in the compiler
or
> standard library.
>
> Sean
>
> "Walter" <walter@digitalmars.com> wrote in message news:bh667t$24js$1@digitaldaemon.com...
> > I've been reading about fibers on google, but I am not yet convinced
they
> > are the right solutions for coroutines because:
> > 1) seems like a lot of overhead to manage them
> > 2) not portable
> >
> > "Mike Wynn" <mike.wynn@l8night.co.uk> wrote in message news:bh63a0$21m6$1@digitaldaemon.com...
> > >
> > > "Walter" <walter@digitalmars.com> wrote in message news:bh617r$1vst$1@digitaldaemon.com...
> > > > Coroutines are pretty cool. They aren't in D now, but they could be
> > added
> > > in
> > > > the future.
> > > >
> > > can't NT (98 or NT3.51+) fibers be used ?
> > >
> > > extern(Windows) {
> > > LPVOID CreateFiber(DWORD dwStackSize,LPFIBER_START_ROUTINE
> > > lpStartAddress,LPVOID lpParameter);
> > > VOID DeleteFiber(LPVOID lpFiber);
> > > LPVOID ConvertThreadToFiber(LPVOID lpParameter);
> > > VOID SwitchToFiber(LPVOID lpFiber);
> > > BOOL SwitchToThread();
> > > }
> > >
> > > not sure if linux/pthreads have similar facilities.
> > >
> > > I know they do work I've tried a few basic tests with fibers, if
someone
> > > posts an example of what they would like I'll see if I can produce a
> > version
> > > in current D that uses fibers as an example.
>
>

"Matthew Wilson" <matthew@stlsoft.org> wrote in message news:bh6g92$2dpv$1@digitaldaemon.com...
> Win32 fibers have various problems, such as not being able to de-fiberise
a
> thread, nor to have multiple fibers within a thread, or the prosaic one of not being implemented in 9x.
>
> I've wanted to do a platform-independent fibers API for ages, but just
have
> never got round to it. I'd love to help do that for D, but alas would probably be more hindrance than help, asm not being my speciality ... <blushes>.
>
> They definitely should be in D, as they're very useful things to have, but should be D's own, not layered on top of Win32.
why? the OS gives you a feature and you want to manually stack switch!

you don't need to de-fiber, they are cooperative so once you finish with a
fiber (other than main) you delete it
the only reason to "fiberise" main is to allow you to get back to it. the OS
could make all threads single fibers initially, but why when fiber use is
rare. (same might be said for a process why have a process with a thread,
why not have a process, that then has to do ConvertProcessToThread is you
want threading)

fibers are a lot better than trying to do coroutines with setjump/longjump
no manual manipulation of the stack
from my MS docs fibers are supported on win98+ and NT3.51 sp 3
you can have multipul fibers in a thread (my D test code had 3)
there are 2 ways to do coroutines (that I know of) (threads and semaphores
or monitors (rendezvous are better)) should work cross platform or abuse the
stack and use setjump/longjump to get between then but you can either rely
on the stack not getting shrunk by the OS or if is checks ESP as task switch
and free unused stack pages you'll have to use alloca or similar to get your
stack back and run into issues there.
and I believe there are OS's that have non contiguious stacks (you can think
of the stack as a singly linked list of frames) usual function epilog is
`get my old sp back and jump to the instruction after the one that called
me`
so on most arch's you can alloc a block of memory, store the sp params and
anything else in the block as required change the SP so the pop in the
epilog will get it and the back, and jump. (on risc arch's its very easy to
do (they have link registers so the return address is stored by the callee
(and usually no in leaf funcs) not the caller).
getting OT, but as I see it use fibers on win32, on other platform you'll
have to do something else.
to get fiber like behavoiur you need :
    a way to stop the current and switch to an existing thread/process (I
belive that on freebsd threads are just processes that share data space,
from the OS each threads is a process rather than a process containing
several threads)



>
> "Sean L. Palmer" <palmer.sean@verizon.net> wrote in message news:bh6euu$2ci7$1@digitaldaemon.com...
> > Fibers are as lightweight as you want to make them.  They have almost
zero
> > overhead compared with threads.  All it is is swapping to a different
> stack;
> > very similar to cooperative multitasking.
> >
from what I see they are cooperative multithreading (within your thread
which is prementively threaded just (don't you just love the random priority
boosting)).

"Sean L. Palmer" <palmer.sean@verizon.net> wrote in message news:bh6euu$2ci7$1@digitaldaemon.com...
> Fibers are as lightweight as you want to make them.  They have almost zero overhead compared with threads.  All it is is swapping to a different
stack;
> very similar to cooperative multitasking.
>
> You can implement them yourself using nothing more than setjmp/longjmp (so long as you're able to figure out what the stack pointer is in the
registers
> structure, which is platform dependent).  Or you can use Windows fibers,
but
> you gain nothing by it except avoiding the hairy details of switching
stacks
> and registers.
>
> The compiler can internally implement fibers however it wants;  it's
really
> quite simple and I can give you advice on implementation if you'd like.
You
> would want a custom implementation for each platform to get the most performance.
>
> My coworkers used to call this "stack twiddling".  ;)  It can sure clear
up
> the logic behind a state machine like you wouldn't believe.
>
> Coroutines are just language syntax that enables transparent utilization
of
> fibers.  "Yield" keyword just calls out to the fiber manager and saves the state of this fiber and lets the next fiber run, or switches back to the main fiber.  Calling a coroutine starts a new fiber or switches to one that's already running, resuming at just past where the previous yield
left
> off.
>
> You don't need language support to do this, but it would be cleaner, and
the
> portability hassle of switching stacks would be best done in the compiler
or
> standard library.

I'd like to eventually add coroutines to D, but there are other things that need to be done first. If you'd like to do a coroutine class, sort of like some of the C++ ones out there, that could become part of Phobos. It could hide the portability issues.

> you don't need to de-fiber, they are cooperative so once you finish with a
> fiber (other than main) you delete it
> the only reason to "fiberise" main is to allow you to get back to it. the
OS
> could make all threads single fibers initially, but why when fiber use is rare. (same might be said for a process why have a process with a thread, why not have a process, that then has to do ConvertProcessToThread is you want threading)

This is not true. (Don't ask me to explain, as this is all in an article that's yet-to-be-published, and I want to keep my powder dry. I'm know that's an *incredibly* lame thing to say, so I'm not going to attempt to press any points on this thread further.)

> fibers are a lot better than trying to do coroutines with setjump/longjump no manual manipulation of the stack

Indeed. Fibers are great, and have lots of unforeseen uses. If only they were implemented a bit better in Win32, or, better, were a standard part of C.

I started a SourceForge project last year - http://fiberspp.sourceforge.net/ - but have yet to do anything. I'm looking for talented people who know more about asm stuff than me to help me out ...

> from my MS docs fibers are supported on win98+ and NT3.51 sp 3

True, I forgot that.

> you can have multipul fibers in a thread (my D test code had 3)

Hmm. This does not correspond with my understanding and experience of them. Can you post your code?

> there are 2 ways to do coroutines (that I know of) (threads and semaphores
> or monitors (rendezvous are better)) should work cross platform or abuse
the
> stack and use setjump/longjump to get between then but you can either rely on the stack not getting shrunk by the OS or if is checks ESP as task
switch
> and free unused stack pages you'll have to use alloca or similar to get
your
> stack back and run into issues there.
> and I believe there are OS's that have non contiguious stacks (you can
think
> of the stack as a singly linked list of frames) usual function epilog is
> `get my old sp back and jump to the instruction after the one that called
> me`
> so on most arch's you can alloc a block of memory, store the sp params and
> anything else in the block as required change the SP so the pop in the
> epilog will get it and the back, and jump. (on risc arch's its very easy
to
> do (they have link registers so the return address is stored by the callee
> (and usually no in leaf funcs) not the caller).
> getting OT, but as I see it use fibers on win32, on other platform you'll
> have to do something else.
> to get fiber like behavoiur you need :
>     a way to stop the current and switch to an existing thread/process (I
> belive that on freebsd threads are just processes that share data space,
> from the OS each threads is a process rather than a process containing
> several threads)

import c.stdio;
import windows;
import object;

extern(Windows) {

alias void function( LPVOID ) LPFIBER_START_ROUTINE;
LPVOID CreateFiber(DWORD dwStackSize,LPFIBER_START_ROUTINE
lpStartAddress,LPVOID lpParameter);
VOID DeleteFiber(LPVOID lpFiber);
LPVOID ConvertThreadToFiber(LPVOID lpParameter);
VOID SwitchToFiber(LPVOID lpFiber);
}

// T is the return type from the co-routine
// U is the user context for the co-routine
class CoManagerBase {
 static LPVOID mainFiber = null;
 Exception throw_me = null;
 LPVOID this_fiber  = null;
 bit delete_me      = false;

 static void initForCoRoutines() {
  if ( mainFiber === null ) {
   mainFiber = ConvertThreadToFiber( null );
  }
 }
 ~this() {
  if ( this_fiber ) { endCoRoutine(); }
 }
 void createCoRoutine( LPFIBER_START_ROUTINE start_up ) {
  assert( this_fiber === null );
  this_fiber = CreateFiber( 16384, start_up, cast(LPVOID)this );
 }
 void yeildCoRoutine() {
  assert( CoManagerBase.mainFiber );
  SwitchToFiber( CoManagerBase.mainFiber );   // fiber->main fiber
(original)
 }

 void deleteCoRoutine() {
  assert( this_fiber );
  DeleteFiber( this_fiber );
  this_fiber = null;
  delete_me  = false;
 }

 void endCoRoutine() {
  delete_me = true;
  SwitchToFiber( CoManagerBase.mainFiber );
 }

 void processCoRoutine() {
  assert( this_fiber );
  SwitchToFiber( this_fiber );
 }

 bit isActive() { return (this_fiber !== null); }
}

template coroutine( T, U ) {
 alias void (*user_func)( CoManagerBase cm, U uservalue );

 class CoManager : CoManagerBase {
  user_func func;
  U         value;
  T         return_value;
 public:
  this() {
   initForCoRoutines();
  }
  this( user_func func0, U user_value ) {
   this();
   begin( func0, user_value );
  }
  void begin( user_func func0, U user_value ) {
   assert( isActive() == false );
   func = func0;
   value = user_value;
   createCoRoutine( fiberCoRoutine );
  }

  void yield( T rv ) {
   return_value = rv;
   yeildCoRoutine();
  }

  void end( T rv ) {
   return_value = rv;
   endCoRoutine();
  }

  T process() {
   processCoRoutine();
   if ( throw_me )  { throw throw_me; }
   if ( delete_me ) { deleteCoRoutine(); }
   return return_value;
  }
 }
 extern (Windows) void
 fiberCoRoutine( LPVOID param )
 {
  CoManager cm = cast(CoManager)param;
  cm.func( cm, cm.value );
  while( true ){
   cm.throw_me = new Exception( "CoRoutine overrun" );
   SwitchToFiber( CoManagerBase.mainFiber );   // fiber->main fiber
(original)
  }
 }
// alias void function( CoManager mgr, U uservalue ) user_func;
}

struct Range { int start, end; }
instance coroutine( int, Range ) cr_I_R;
instance coroutine( int, int ) cr_I_I;

void inc_by( CoManagerBase mgr, int incr ) {
 int i = 0;
 while(true) {
  i += incr;
  (cast(cr_I_I.CoManager)mgr).yield( i );
 }
}

void counter( CoManagerBase mgr, Range r ) {
 int i = r.start;
 while( i < r.end ) {
  (cast(cr_I_R.CoManager)mgr).yield( i );
  i++;
 }
 (cast(cr_I_R.CoManager)mgr).end( i );
}

int main( char[][] argv )
{
 static Range r = { start:4, end:9 };
 cr_I_I.CoManager coI = new cr_I_I.CoManager( cast(cr_I_I.user_func)&inc_by,
11 );
 cr_I_R.CoManager coR = new cr_I_R.CoManager( cast(cr_I_R.user_func)counter,
r );

 printf( "being some corountines\n" );
 while( coR.isActive() ) {
  printf( "   incrementer : %d\n", coI.process() );
  printf( "counter[range] : %d\n", coR.process() );
 }
 printf( "*done*\n" );

 return 0;
}
----------------

how's that for proof that fibers are A easy and B do the job.

>
> I'd like to eventually add coroutines to D, but there are other things
that
> need to be done first. If you'd like to do a coroutine class, sort of like some of the C++ ones out there, that could become part of Phobos. It could hide the portability issues.
>

I've attached the versions I'd rather use (less casting) but form some
reason (looks like a forward ref problem)
I cant define two mutually dependant types within a template :(