www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Coroutine's Communication

reply davidl <davidl 126.com> writes:
For a typical use case of coroutine, a producer/a consumer

var q := new queue

generator produce
     loop
         while q is not full
             create some new items
             add the items to q
         yield consume

generator consume
     loop
         while q is not empty
             remove some items from q
             use the items
         yield produce

subroutine dispatcher
     var d := new dictionary〈generator → iterator〉
     d[produce] := start produce
     d[consume] := start consume
     var current := produce
     loop
         current := next d[current]

We can see the typical example from wikipedia uses the global var for  
communication. It's bad , because it pollutes global name space, and q can  
be accessed by any other threads, thus unexpected behavior may occur.

 From the tango implementation:
     int s0 = 0;
     static int s1 = 0;

     Fiber a = new Fiber(
     delegate void()
     {
         s0++;
     });
     Fiber c = new Fiber(
         delegate void() { assert(false); });

There we can see we can wrap those two funcs into a class and also s0,s1.

Yet isn't that trivial to rewrap the coroutine to a class??

Coroutine addresses the cooperativeness of two routines, not their Object  
Oriented Programming relation.

I suggest compiler accepts Function type arg as a scope referer.

Use case:

void func(int i)
{
    int j;
    func1(get_current_scope, i);     	// which equivalent to j=i;
    assert(j==i);
}

void func1(func scope func_scope, ref int j)
{
     j = func_scope.j;
}

The trick here is that routines are still routines, and you defaultly get  
their local vars consisting an object. Sometimes routines need to access  
some trivial

For the simpleness sake , currently we can force the routines can only  
access top level local vars which are visible in the whole func scope.

func scope type is a syntax sugar for referencing the local vars of func  
by the func_scope stack frame pointer.

This is a useful syntax for optimizing coroutine.

Coroutine performance boosts , because one routine accesses its local var  
directly through stack frame pointer.

and this programming paradigm requires get_current_scope primitive for  
yielding. Though it can be done by the fiber dispatcher, it can get the  
pointer from the context, but it's nicer to have that primitive and yield  
that to the dispatcher.

The typical coroutine example can be rewritten as following(with  
imaginable syntax):

generator produce
     var q := new queue
     loop
         while q is not full
             create some new items
             add the items to q
	var scope := get_current_scope
         yield consume(scope)

generator consume(volatile produce scope produce_scope)

// if yield is sufficient enough to be a memory
// barrier for this specific var produce_scope , we don't need the  
volatile.

     loop
         while produce_scope.q is not empty
             remove some items from produce_scope.q
             use the items
         yield produce

The following is *only* for ***optimization*** purposes:

Even advance compiler technology can optimize this case a bit further.
Since produce doesn't use any local vars of consume. (And this could be  
most cases of coroutines.)

And we notice that they only yield to each other. They won't result the  
yield chain path any deeper.

So they can be rewritten as two new funcs:

generator produce
     var q := new queue
     loop
         while q is not full
             create some new items
             add the items to q
	var scope := get_current_scope
         goto consume.label1
	label1:

generator consume:produce(volatile produce scope produce_scope)
     loop
         while produce_scope.q is not empty
             remove some items from produce_scope.q
             use the items
	    goto produce.label1
	label1:

It might look confusing at the very first sight. but the point is consume  
is never being called as a func.
The semantic of consume:produce is that consume _reuses_ the stack frame  
as produce do. Consume only extends the local stack a little bit bigger.

People may ask : Why this is safe?
It's simply because consume works as a nested func of produce.

And you may ask : Why write it in a coroutine syntax?

It's because it provides you the chance to overload both consume/produce.
The only thing they need to extend is their "goto consume.label1"/"goto  
produce.label1"

If you want it to have the ability to accept two producers , compiler does  
it as following:

produce_label1_address pla;

generator produce
     var q := new queue


generator produce1:produce     // this semantic means produce1 extends the  
produce func stack frame
     loop
         while q is not full
             create some new items
             add the items to q
	var scope := get_current_scope
         goto consume.label1
	label1:

generator produce2:produce
     loop
         while q is not full
             create some new items
             add the items to q
	var scope := get_current_scope
         goto consume.label1
	label1:

generator consume:produce(volatile produce scope produce_scope)
     loop
         while produce_scope.q is not empty
             remove some items from produce_scope.q
             use the items
	    goto *pla
	label1:

compiler assigns pla produce1.label1 to  when you do switching between  
produce1/consume, and compiler assigns pla produce2.label2 to  when you do  
switching between produce2/consume, vice versa for consume.

This gives the chance to flatten the coroutines to simple nested funcs,  
while without harming any coroutine syntax.



-- 
使用 Opera 革命性的电子邮件客户程序: http://www.opera.com/mail/
Apr 28 2008
next sibling parent reply terranium <spam here.lot> writes:
davidl Wrote:

 The trick here is that routines are still routines, and you defaultly get  
 their local vars consisting an object.


Function's local variables don't comprise and object. func1 obvously wants a
state object, so should accept it using normal parameter declaration. If you
want to pass func1 various state objects you can declare func1 as a templated
function.
Apr 29 2008
parent reply DavidL <Davidl 126.com> writes:
terranium Wrote:


 davidl Wrote:

 The trick here is that routines are still routines, and you defaultly get  
 their local vars consisting an object.


 
 Function's local variables don't comprise and object. func1 obvously wants a
state object, so should accept it using normal parameter declaration. If you
want to pass func1 various state objects you can declare func1 as a templated
function.


OO not always bring you the good thing. Somtimes they fail in the abstraction.

Consider:
void provider()
{
   // I need to sum some field of the record for some specific consumers, but
not all consumers need this sum !
   my_rec_struct rec;
   open_table();
   bool done=false
   while (fetch_first_record(&rec)!=0)
  {
     yield consumer(get_current_scope);
  }
  done = true;
}

void consumer(provider_scope scope)
{
   int sum;
   while(!scope.done)
   {
       sum += provider_scope.rec.amount;
       yield provider();
   }
}

in this specific consumer we need the sum result. while not *every* consumer
needs this, some consumer just need to iterate over the data, they do not
necessarily need the sum of amount. How do you solve in your oo state object??
It's ridiculous to do it in OOP, and it's definitely unsuitable and stupid.
Apr 29 2008
parent terranium <spam here.lot> writes:
DavidL Wrote:

 How do you solve in your oo state object??


I'm not sure what are you trying to do. And I'm not sure what the yield is. May

http://msdn.microsoft.com/en-us/library/9k7k7cf0(VS.80).aspx


 It's ridiculous to do it in OOP, and it's definitely unsuitable and stupid.


At least it will work faster and make less bloat.
Apr 30 2008
prev sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2008-04-29 00:33:40 -0400, davidl <davidl 126.com> said:


 I suggest compiler accepts Function type arg as a scope referer.
 
 Use case:
 
 void func(int i)
 {
     int j;
     func1(get_current_scope, i);     	// which equivalent to j=i;
     assert(j==i);
 }
 
 void func1(func scope func_scope, ref int j)
 {
      j = func_scope.j;
 }
 
 The trick here is that routines are still routines, and you defaultly 
 get  their local vars consisting an object. Sometimes routines need to 
 access  some trivial


But can't you already do this in D with nested functions?

	void func(int i)
	{
		int j;
		void func1(ref int j1)
		{
			j = j1;
		}
		func1(i); // which is equivalent to j = i;
		assert(j == i);
	}

The scope of func is passed implicitly to func1 as a hidden pointer in 
the above call, and func1 can thus access any of func's variables.

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Apr 29 2008
parent DavidL <Davidl 126.com> writes:
Michel Fortin Wrote:


 On 2008-04-29 00:33:40 -0400, davidl <davidl 126.com> said:
 

 I suggest compiler accepts Function type arg as a scope referer.
 
 Use case:
 
 void func(int i)
 {
     int j;
     func1(get_current_scope, i);     	// which equivalent to j=i;
     assert(j==i);
 }
 
 void func1(func scope func_scope, ref int j)
 {
      j = func_scope.j;
 }
 
 The trick here is that routines are still routines, and you defaultly 
 get  their local vars consisting an object. Sometimes routines need to 
 access  some trivial


 
 But can't you already do this in D with nested functions?
 
 	void func(int i)
 	{
 		int j;
 		void func1(ref int j1)
 		{
 			j = j1;
 		}
 		func1(i); // which is equivalent to j = i;
 		assert(j == i);
 	}
 
 The scope of func is passed implicitly to func1 as a hidden pointer in 
 the above call, and func1 can thus access any of func's variables.
 
 -- 
 Michel Fortin
 michel.fortin michelf.com
 http://michelf.com/
 


Yeah, I've stated that in this exact case we got the same effect as nestedfunc,
but nested func loses the chance of overloading, so if you want different
provider(nested func) behavior in the cunsumer(host func), you will have to
include different providers in the cunsumer func. That bloats the consumer
func.
Apr 29 2008