www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Feature Request: Change the delegate type to void[] data instead

reply downs <default_357-line yahoo.de> writes:
This could be made backwards compatible by the introduction of a void
*ptr() { return data.ptr; }

If the delegate is of a method, data references the object's data.
If the delegate is an inline function or nested function, data
references *the stack space in all the superior functions that it uses*.


Disadvantages: Delegates take size_t.sizeof bytes more space in RAM.
Advantages: I'll let the following function speak for itself.
 R delegate(T) close(R, T...)(R delegate(T) dg)
 {
   typeof(dg) res=dg;
   res.data=res.data.dup; // eventually moves area of stack into RAM
   return res;
 }

What do you think? --downs
Oct 03 2007
next sibling parent reply Gregor Richards <Richards codu.org> writes:
Downside #2: Calculating that range requires at best n pointer lookups 
where n is the depth of the delegate. Creating delegates right now is free.

  - Gregor Richards
Oct 03 2007
parent reply downs <default_357-line yahoo.de> writes:
Gregor Richards wrote:
 Downside #2: Calculating that range requires at best n pointer lookups
 where n is the depth of the delegate. Creating delegates right now is free.
 
  - Gregor Richards

a problem. Alternatively, just set the array pointer to null initially and have the compiler fill it in when requested. --downs
Oct 03 2007
parent reply Gregor Richards <Richards codu.org> writes:
downs wrote:
 Gregor Richards wrote:
 Downside #2: Calculating that range requires at best n pointer lookups
 where n is the depth of the delegate. Creating delegates right now is free.

  - Gregor Richards

a problem. Alternatively, just set the array pointer to null initially and have the compiler fill it in when requested. --downs

The delegate is created as soon as you do &foo. After that point, whatever receives &foo doesn't know anything about it, so it doesn't know how many pointers it would have to jump through to get the right depth. So, you'd need to either accept that creating delegates incurs n cost (something that's fine by me since n is actually a constant), or have a special syntax for delegates which have the extra information. - Gregor Richards
Oct 03 2007
next sibling parent downs <default_357-line yahoo.de> writes:
Gregor Richards wrote:
 downs wrote:
 Gregor Richards wrote:
 Downside #2: Calculating that range requires at best n pointer lookups
 where n is the depth of the delegate. Creating delegates right now is
 free.

  - Gregor Richards

a problem. Alternatively, just set the array pointer to null initially and have the compiler fill it in when requested. --downs

The delegate is created as soon as you do &foo. After that point, whatever receives &foo doesn't know anything about it, so it doesn't know how many pointers it would have to jump through to get the right depth. So, you'd need to either accept that creating delegates incurs n cost (something that's fine by me since n is actually a constant), or have a special syntax for delegates which have the extra information. - Gregor Richards

Damn, you're right. How much of a problem is this? Note that the cost only occurs if the delegate actually uses outside variables. --downs
Oct 03 2007
prev sibling parent "Rioshin an'Harthen" <rharth75 hotmail.com> writes:
"Gregor Richards" <Richards codu.org> kirjoitti viestissä 
news:fe1t1b$kvn$1 digitalmars.com...
 The delegate is created as soon as you do &foo. After that point, whatever 
 receives &foo doesn't know anything about it, so it doesn't know how many 
 pointers it would have to jump through to get the right depth. So, you'd 
 need to either accept that creating delegates incurs n cost (something 
 that's fine by me since n is actually a constant), or have a special 
 syntax for delegates which have the extra information.

I have a small proposal for the syntax of delegates storing the extra information. Currently we define a delegate with something akin to R delegate(T) dg = &foo; Now, we want a syntax for delegates storing the stack context for the superior functions. According to the quote above, this looks like a case of needing extra dereferencing when used, so should be visible in declaring the delegate and assigning to it. Thus, I came up with the following: R delegate(T) &dg = &&foo; where the extra ampersands - kind of like in C(++) - show that there's another step or multiple steps to (de)reference.
Oct 04 2007
prev sibling next sibling parent reply BCS <ao pathlink.com> writes:
Reply to Downs,

 R delegate(T) close(R, T...)(R delegate(T) dg)
 {
 typeof(dg) res=dg;
 res.data=res.data.dup; // eventually moves area of stack into RAM
 return res;
 }


how will that more stack data into ram? If the delegate gets an array of pointers to stack frames (or objects) then what you get is a copy of the pointers that still point into the stack (or objects). If what you have is a slice of the stack, then what about the next function out? you will either still have a reference to another stack frame, or won't have access to it at all. You might get something with a void[][], but then you need to do an alloc on each delegate creation, not to mention Gregor's issue.
Oct 03 2007
parent reply downs <default_357-line yahoo.de> writes:
BCS wrote:
 Reply to Downs,
 
 R delegate(T) close(R, T...)(R delegate(T) dg)
 {
 typeof(dg) res=dg;
 res.data=res.data.dup; // eventually moves area of stack into RAM
 return res;
 }


how will that more stack data into ram? If the delegate gets an array of pointers to stack frames (or objects) then what you get is a copy of the pointers that still point into the stack (or objects).

void[] is not an array of void pointers, but a continuous segment of memory; that being, all the stack the method does access.
 If what you have
 is a slice of the stack, then what about the next function out? you will
 either still have a reference to another stack frame, or won't have
 access to it at all.

The compiler can determine at compile-time which stack frames the function does access. It can then use that data to calculate the pointer (as an offset to the SP) and length of the array.
 You might get something with a void[][], but then
 you need to do an alloc on each delegate creation, not to mention
 Gregor's issue.
 
 

caveat - I do not believe the cost overhead of delegate _creation_ to be a significant problem. Thanks for your feedback :) --downs
Oct 03 2007
parent reply BCS <ao pathlink.com> writes:
Reply to Downs,

 BCS wrote:
 
 Reply to Downs,
 
 R delegate(T) close(R, T...)(R delegate(T) dg)
 {
 typeof(dg) res=dg;
 res.data=res.data.dup; // eventually moves area of stack into RAM
 return res;
 }


of pointers to stack frames (or objects) then what you get is a copy of the pointers that still point into the stack (or objects).

void[] is not an array of void pointers, but a continuous segment of memory; that being, all the stack the method does access.
 If what you have
 is a slice of the stack, then what about the next function out? you
 will
 either still have a reference to another stack frame, or won't have
 access to it at all.

The compiler can determine at compile-time which stack frames the function does access. It can then use that data to calculate the pointer (as an offset to the SP) and length of the array.
 You might get something with a void[][], but then
 you need to do an alloc on each delegate creation, not to mention
 Gregor's issue.

a caveat - I do not believe the cost overhead of delegate _creation_ to be a significant problem. Thanks for your feedback :) --downs

|class Bar { int opApply( int delegate(inout int) dg) {...} } | |void Fun(Bar b) | { | int i; | foreach(inout j ; b) | { | i+=j; | h=0 | int nest(inout int k) | { | i+=k; | h-=k; | return 0; | } | b.opApply(&nest) | } |} There are three nested function here. Fun, the foreach body and the nest function when the nest function is turned into a delegate in the opApply function, the stack looks like this Fun Bar.opApply <<<<< Fun.foreachBody_1 potentially, I could add code later that would put an even bigger (or smaller) chunk of data between the Fun stack frame and the foreach body stack frame. In general this can't be detected at compile time because I could do this by deriving a class from Bar.
Oct 04 2007
parent reply downs <default_357-line yahoo.de> writes:
BCS wrote:
 Reply to Downs,
 
 BCS wrote:

 Reply to Downs,

 R delegate(T) close(R, T...)(R delegate(T) dg)
 {
 typeof(dg) res=dg;
 res.data=res.data.dup; // eventually moves area of stack into RAM
 return res;
 }


of pointers to stack frames (or objects) then what you get is a copy of the pointers that still point into the stack (or objects).

void[] is not an array of void pointers, but a continuous segment of memory; that being, all the stack the method does access.
 If what you have
 is a slice of the stack, then what about the next function out? you
 will
 either still have a reference to another stack frame, or won't have
 access to it at all.

The compiler can determine at compile-time which stack frames the function does access. It can then use that data to calculate the pointer (as an offset to the SP) and length of the array.
 You might get something with a void[][], but then
 you need to do an alloc on each delegate creation, not to mention
 Gregor's issue.

a caveat - I do not believe the cost overhead of delegate _creation_ to be a significant problem. Thanks for your feedback :) --downs

|class Bar { int opApply( int delegate(inout int) dg) {...} } | |void Fun(Bar b) | { | int i; | foreach(inout j ; b) | { | i+=j; | h=0 | int nest(inout int k) | { | i+=k; | h-=k; | return 0; | } | b.opApply(&nest) | } |} There are three nested function here. Fun, the foreach body and the nest function when the nest function is turned into a delegate in the opApply function, the stack looks like this Fun Bar.opApply <<<<< Fun.foreachBody_1 potentially, I could add code later that would put an even bigger (or smaller) chunk of data between the Fun stack frame and the foreach body stack frame. In general this can't be detected at compile time because I could do this by deriving a class from Bar.

The void[] data property I'm proposing does not contain the complete stack of the delegate. Since part of that stack (the delegate's) doesn't even EXIST when the delegate is created, this would be rather pointless. Instead, data references the stack area _outside_ of the delegate that the delegate uses. So in this case, that would be Fun, directly followed by its foreach body; two parts of the stack which indeed form a continuous area. I hope that clears things up. --downs
Oct 04 2007
parent reply BCS <ao pathlink.com> writes:
Reply to Downs,

 BCS wrote:
 
 Fun
 Bar.opApply  <<<<<
 Fun.foreachBody_1

Again, you're missing something. The void[] data property I'm proposing does not contain the complete stack of the delegate. Since part of that stack (the delegate's) doesn't even EXIST when the delegate is created, this would be rather pointless. Instead, data references the stack area _outside_ of the delegate that the delegate uses. So in this case, that would be Fun, directly followed by its foreach body; two parts of the stack which indeed form a continuous area. I hope that clears things up. --downs

In between the Fun frame and the foreach frame is the opApply frame (or several frames). If you keep nesting function and passing delegate to arbitrary code to be called deeper in the stack, sooner or later, you get a gap of unknown size.
Oct 04 2007
parent reply downs <default_357-line yahoo.de> writes:
BCS wrote:
 Reply to Downs,
 
 BCS wrote:

 Fun
 Bar.opApply  <<<<<
 Fun.foreachBody_1

Again, you're missing something. The void[] data property I'm proposing does not contain the complete stack of the delegate. Since part of that stack (the delegate's) doesn't even EXIST when the delegate is created, this would be rather pointless. Instead, data references the stack area _outside_ of the delegate that the delegate uses. So in this case, that would be Fun, directly followed by its foreach body; two parts of the stack which indeed form a continuous area. I hope that clears things up. --downs

In between the Fun frame and the foreach frame is the opApply frame (or several frames). If you keep nesting function and passing delegate to arbitrary code to be called deeper in the stack, sooner or later, you get a gap of unknown size.

And since the void[] data and the immediate stack space of the function don't need to have any direct relationship, it isn't a problem. The stack space of the function is accessed via the SP or an equivalent register. The outer stack area is accessed via (currently) void *ptr or (proposed) void[] data. The two are separate areas. I don't see the problem. --downs
Oct 04 2007
parent reply BCS <ao pathlink.com> writes:
Reply to Downs,

 BCS wrote:
 
 Reply to Downs,
 
 BCS wrote:
 
 Fun
 Bar.opApply  <<<<<
 Fun.foreachBody_1

The void[] data property I'm proposing does not contain the complete stack of the delegate. Since part of that stack (the delegate's) doesn't even EXIST when the delegate is created, this would be rather pointless. Instead, data references the stack area _outside_ of the delegate that the delegate uses. So in this case, that would be Fun, directly followed by its foreach body; two parts of the stack which indeed form a continuous area. I hope that clears things up. --downs

(or several frames). If you keep nesting function and passing delegate to arbitrary code to be called deeper in the stack, sooner or later, you get a gap of unknown size.

And since the void[] data and the immediate stack space of the function don't need to have any direct relationship, it isn't a problem. The stack space of the function is accessed via the SP or an equivalent register. The outer stack area is accessed via (currently) void *ptr or (proposed) void[] data. The two are separate areas. I don't see the problem. --downs

but from within the delegate the delegates frame is accessed with the SP, the foreach body's frame is accessed with the void *ptr or void[] data. But what is the outermost frame accessed with? Currently I think it is accessed with chained indirection (look in my outer function for his outer function's pointer, then use that pointer to find the next one etc.). This would still work with your proposal, but it gets all the issues of deep vs. shallow copies, which kinda defeats the point of the proposal. If you don't see my point for this case, consider this; the accusable scope of a nested function can contain an arbitrary number of non adjacent stack frames simply by passing callbacks to other function where the callback does the same. This can be done to as many levels as you wish.
Oct 04 2007
parent reply downs <default_357-line yahoo.de> writes:
BCS wrote:
 Reply to Downs,
 
 BCS wrote:

 Reply to Downs,

 BCS wrote:

 Fun
 Bar.opApply  <<<<<
 Fun.foreachBody_1

The void[] data property I'm proposing does not contain the complete stack of the delegate. Since part of that stack (the delegate's) doesn't even EXIST when the delegate is created, this would be rather pointless. Instead, data references the stack area _outside_ of the delegate that the delegate uses. So in this case, that would be Fun, directly followed by its foreach body; two parts of the stack which indeed form a continuous area. I hope that clears things up. --downs

(or several frames). If you keep nesting function and passing delegate to arbitrary code to be called deeper in the stack, sooner or later, you get a gap of unknown size.

And since the void[] data and the immediate stack space of the function don't need to have any direct relationship, it isn't a problem. The stack space of the function is accessed via the SP or an equivalent register. The outer stack area is accessed via (currently) void *ptr or (proposed) void[] data. The two are separate areas. I don't see the problem. --downs

but from within the delegate the delegates frame is accessed with the SP, the foreach body's frame is accessed with the void *ptr or void[] data. But what is the outermost frame accessed with? Currently I think it is accessed with chained indirection (look in my outer function for his outer function's pointer, then use that pointer to find the next one etc.). This would still work with your proposal, but it gets all the issues of deep vs. shallow copies, which kinda defeats the point of the proposal.

The idea is, since chained indirection only accesses consecutive stack frames anyway, void[] data contains _all_ the *outer* stack frames which the function *does* access, information which is definitely known at compile time. Since their size is also known, we can do away with chained indirection as well and simply use a fixed index in data.
 If you don't see my point for this case, consider this; the accessable (sp.)
 scope of a nested function can contain an arbitrary number of non
 adjacent stack frames simply by passing callbacks to other function
 where the callback does the same.

The stack space of other passed-in functions is not directly accessible from the current function. Thus, it is entirely irrelevant to this debate. How to access this space is the problem of the passed-in functions alone. --downs
Oct 04 2007
parent reply BCS <ao pathlink.com> writes:
Reply to Downs,

 Yes.
 The idea is, since chained indirection only accesses consecutive stack
 frames anyway, void[] data contains _all_ the *outer* stack frames

my assertion is that, in general, the outer stack frames are *NOT consecutive* consider this code: |Foo(void delegate() dg) |{ | dg(); |} | |void Bar() |{ | int i; | Foo({ | int j; | Foo({ | int k; | Foo({ | int l; | Foo({ | int m; | Foo({ | int n = 1; | Foo({ | i += j += k += l += m += n; | }); | }); | }); | }); | }); | }); |} when the most nested delegate gets called it accesses six non-consecutive stack frames (Bar calls Foo calls delegate calls Foo ..., each delegate stack frame is seperated by a Foo stack frame) If the code for Foo is not known at compile time then their is no way to know where the outer stack frames are short of looking through a chain of pointers. To better illustrate this consider where Foo is this: |Foo(void delegate() dg) |{ | dg(); | int | dg(); |} with the second call in Foo, the offset of the called stack frame (the next more nested delegate) to the calling stack frame (the next delegate out) is different than for the first call. Without knowing which time you are being called you can't find the outer stack frames without a pointer chain to them.
 The stack space of other passed-in functions is not directly
 accessible from the current function.

I don't follow that. It looks like I must have been unclear with what I was saying. The above section reiterates what I was trying to say.
 --downs
 

Oct 04 2007
parent reply downs <default_357-line yahoo.de> writes:
Okay, I see your point.
You are right.
Thanks.
Damnit.

 --downs
Oct 04 2007
parent BCS <ao pathlink.com> writes:
Reply to Downs,

 Okay, I see your point.
 You are right.
 Thanks.
 Damnit.
 --downs
 

Don't feel to bad, I was having a hard time keeping it all straight in my head.
Oct 04 2007
prev sibling parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
downs wrote:
 This could be made backwards compatible by the introduction of a void
 *ptr() { return data.ptr; }
 
 If the delegate is of a method, data references the object's data.
 If the delegate is an inline function or nested function, data
 references *the stack space in all the superior functions that it uses*.
 
 
 Disadvantages: Delegates take size_t.sizeof bytes more space in RAM.
 Advantages: I'll let the following function speak for itself.
 R delegate(T) close(R, T...)(R delegate(T) dg)
 {
   typeof(dg) res=dg;
   res.data=res.data.dup; // eventually moves area of stack into RAM
   return res;
 }

What do you think? --downs

What about this? Leave delegates as they are, but introduce a new closure class of types. In effect, these would be: struct closure(returnT, argT...) { void* func; void[] data; returnT delegate(argT) opImplicitCast() { returnT delegate(argT) result; result.func = this.func; result.ptr = this.data.ptr; return result; } typeof(*this) dup() { typeof(*this) result; result.func = this.func; result.data = this.data.dup; return result; } } And appropriate opCall overloads, yadda yadda. Now, instead of delegate literals, you have *closure* literals, and taking the address of a non-globally scoped function will result in a closure. The implicit cast allows closures to be transparently used as delegates instead, so all existing code that deals with delegates explicitly should continue to work. I think the important thing is that it's quite likely the *only* piece of code that cares about the full slice of the stack is the code where the delegate was created; other things likely just want to call the delegate, so they probably don't care *how* it works, so long as it does. Plus, this means we get to keep our 8-byte delegates. :) -- Daniel
Oct 04 2007
parent reply Christopher Wright <dhasenan gmail.com> writes:
Daniel Keep wrote:
 What about this?  Leave delegates as they are, but introduce a new
 closure class of types.  In effect, these would be:
 
 struct closure(returnT, argT...)
 {
     void* func;
     void[] data;
 
     returnT delegate(argT) opImplicitCast()
     {
         returnT delegate(argT) result;
         result.func = this.func;
         result.ptr = this.data.ptr;
         return result;
     }
 
     typeof(*this) dup()
     {
         typeof(*this) result;
         result.func = this.func;
         result.data = this.data.dup;
         return result;
     }
 }

I like it. Now just fix bug 854 and you're all set.
Oct 04 2007
parent Daniel Keep <daniel.keep.lists gmail.com> writes:
Christopher Wright wrote:
 Daniel Keep wrote:
 What about this?  Leave delegates as they are, but introduce a new
 closure class of types.  In effect, these would be:

 struct closure(returnT, argT...)
 {
     void* func;
     void[] data;

     returnT delegate(argT) opImplicitCast()
     {
         returnT delegate(argT) result;
         result.func = this.func;
         result.ptr = this.data.ptr;
         return result;
     }

     typeof(*this) dup()
     {
         typeof(*this) result;
         result.func = this.func;
         result.data = this.data.dup;
         return result;
     }
 }

I like it. Now just fix bug 854 and you're all set.

I think 854 is something of a side-concern, really. :3 Incidentally, I'd completely forgotten about that one... -- Daniel
Oct 04 2007