www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - logical const idea - scratchspace

reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
I have an idea on how to create logical const without any language or  
compiler changes -- it will exist purely in druntime.

The idea is based on this:  Whenever you allocate an object, you use a  
memory block.  An object, by default, has the following memory layout:

monitor - (void *).sizeof bytes
vtbl - (void *).sizeof bytes
interface_vtbls[] - (void *)sizeof x number of interfaces.

So by default, 8 bytes on 32bit, 16 bytes on 64 bit.

Add any members, and they may increase the size.

This object goes into the GC heap.  Yet the GC heap has only 16, 32, 64,  
128, etc. sized blocks.

So for instance a class object that requires 24 bytes actually consumes  
32.  This leaves 8 bytes of "scratch space".  Using a druntime lookup we  
can get access to that entire memory block, including the scratch space.   
And since we use druntime to look it up, *not* the object and its  
contained members (which remember don't include the scratch space), it is  
*not* typed as const or immutable, or whatever the class data is.

In essence, a const(MyObj) is a pointer to a struct that looks like:

struct FicticiousMyObjStruct
{
   const(MyObj_data); // not a reference, the actual data
   ubyte[8] scratchspace;
}

So we need two pieces for this proposal:

1. An accessor in Object for this scratch space.  This should be a)  
efficient, and b) opaque.
2. An allocator for a new object that can allocate a minimal scratch  
space.  So for instance, if your object consumes 32 bytes, but you need 20  
bytes of scratch space, you want the runtime to allocate a 64 byte block.   
So instead of saying new MyObject, you'd say newScratchSpace!MyObject(20)

And I think that's it.  Since nothing before this proposal ever referred  
to or used that scratch space, it's not in danger of breaking existing  
code.  The only caveat is, it can't properly be typed as shared or not (it  
could be accessible from multiple threads, depending on if the actual type  
is immutable).

It also should be recommended that the scratch space not contain any GC  
pointers, since it's *not* participating in the type system properly, the  
GC may not treat it as a pointer.

And of course, we need a better name than newScratchSpace.

-Steve
May 14 2012
next sibling parent reply =?UTF-8?B?QWxleCBSw7hubmUgUGV0ZXJzZW4=?= <xtzgzorex gmail.com> writes:
On 14-05-2012 21:51, Steven Schveighoffer wrote:
 I have an idea on how to create logical const without any language or
 compiler changes -- it will exist purely in druntime.

 The idea is based on this: Whenever you allocate an object, you use a
 memory block. An object, by default, has the following memory layout:

 monitor - (void *).sizeof bytes
 vtbl - (void *).sizeof bytes
 interface_vtbls[] - (void *)sizeof x number of interfaces.

 So by default, 8 bytes on 32bit, 16 bytes on 64 bit.

 Add any members, and they may increase the size.

 This object goes into the GC heap. Yet the GC heap has only 16, 32, 64,
 128, etc. sized blocks.

 So for instance a class object that requires 24 bytes actually consumes
 32. This leaves 8 bytes of "scratch space". Using a druntime lookup we
 can get access to that entire memory block, including the scratch space.
 And since we use druntime to look it up, *not* the object and its
 contained members (which remember don't include the scratch space), it
 is *not* typed as const or immutable, or whatever the class data is.

 In essence, a const(MyObj) is a pointer to a struct that looks like:

 struct FicticiousMyObjStruct
 {
 const(MyObj_data); // not a reference, the actual data
 ubyte[8] scratchspace;
 }

 So we need two pieces for this proposal:

 1. An accessor in Object for this scratch space. This should be a)
 efficient, and b) opaque.
 2. An allocator for a new object that can allocate a minimal scratch
 space. So for instance, if your object consumes 32 bytes, but you need
 20 bytes of scratch space, you want the runtime to allocate a 64 byte
 block. So instead of saying new MyObject, you'd say
 newScratchSpace!MyObject(20)

 And I think that's it. Since nothing before this proposal ever referred
 to or used that scratch space, it's not in danger of breaking existing
 code. The only caveat is, it can't properly be typed as shared or not
 (it could be accessible from multiple threads, depending on if the
 actual type is immutable).

 It also should be recommended that the scratch space not contain any GC
 pointers, since it's *not* participating in the type system properly,
 the GC may not treat it as a pointer.

That renders it useless for caching e.g. a string though...
 And of course, we need a better name than newScratchSpace.

 -Steve

-- - Alex
May 14 2012
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 14 May 2012 15:56:37 -0400, Alex R=C3=B8nne Petersen
<xtzgzorex gmail.com> wrote:

 On 14-05-2012 21:51, Steven Schveighoffer wrote:

 It also should be recommended that the scratch space not contain any =


 pointers, since it's *not* participating in the type system properly,=


 the GC may not treat it as a pointer.

That renders it useless for caching e.g. a string though...

Yes, it does. Unless you know the size of the string (so you can alloca= te enough scratch space to hold it). It's not perfect, for sure. But it might be better than nothing... -Steve
May 14 2012
parent reply =?UTF-8?B?QWxleCBSw7hubmUgUGV0ZXJzZW4=?= <xtzgzorex gmail.com> writes:
On 14-05-2012 22:13, Steven Schveighoffer wrote:
 On Mon, 14 May 2012 15:56:37 -0400, Alex Rønne Petersen
 <xtzgzorex gmail.com> wrote:

 On 14-05-2012 21:51, Steven Schveighoffer wrote:

 It also should be recommended that the scratch space not contain any GC
 pointers, since it's *not* participating in the type system properly,
 the GC may not treat it as a pointer.

That renders it useless for caching e.g. a string though...

Yes, it does. Unless you know the size of the string (so you can allocate enough scratch space to hold it). It's not perfect, for sure. But it might be better than nothing... -Steve

But is there any reason we can't just have the GC check the scratch space? If it's all zero, it clearly contains nothing of interest, but if it's non-zero, just scan it like regular object memory. -- - Alex
May 14 2012
parent =?UTF-8?B?QWxleCBSw7hubmUgUGV0ZXJzZW4=?= <xtzgzorex gmail.com> writes:
On 14-05-2012 23:06, Alex Rønne Petersen wrote:
 On 14-05-2012 22:13, Steven Schveighoffer wrote:
 On Mon, 14 May 2012 15:56:37 -0400, Alex Rønne Petersen
 <xtzgzorex gmail.com> wrote:

 On 14-05-2012 21:51, Steven Schveighoffer wrote:

 It also should be recommended that the scratch space not contain any GC
 pointers, since it's *not* participating in the type system properly,
 the GC may not treat it as a pointer.

That renders it useless for caching e.g. a string though...

Yes, it does. Unless you know the size of the string (so you can allocate enough scratch space to hold it). It's not perfect, for sure. But it might be better than nothing... -Steve

But is there any reason we can't just have the GC check the scratch space? If it's all zero, it clearly contains nothing of interest, but if it's non-zero, just scan it like regular object memory.

Further, we could use a user marking scheme where writing anything non-zero to the space flags it "dirty" or something. There are probably lots of ways we could do this. -- - Alex
May 14 2012
prev sibling next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 14.05.2012 23:51, Steven Schveighoffer wrote:
 I have an idea on how to create logical const without any language or
 compiler changes -- it will exist purely in druntime.

 The idea is based on this: Whenever you allocate an object, you use a
 memory block. An object, by default, has the following memory layout:

 monitor - (void *).sizeof bytes
 vtbl - (void *).sizeof bytes
 interface_vtbls[] - (void *)sizeof x number of interfaces.

 So by default, 8 bytes on 32bit, 16 bytes on 64 bit.

 Add any members, and they may increase the size.

 This object goes into the GC heap. Yet the GC heap has only 16, 32, 64,
 128, etc. sized blocks.

 So for instance a class object that requires 24 bytes actually consumes
 32. This leaves 8 bytes of "scratch space". Using a druntime lookup we
 can get access to that entire memory block, including the scratch space.
 And since we use druntime to look it up, *not* the object and its
 contained members (which remember don't include the scratch space), it
 is *not* typed as const or immutable, or whatever the class data is.

 In essence, a const(MyObj) is a pointer to a struct that looks like:

 struct FicticiousMyObjStruct
 {
 const(MyObj_data); // not a reference, the actual data
 ubyte[8] scratchspace;
 }

 So we need two pieces for this proposal:

 1. An accessor in Object for this scratch space. This should be a)
 efficient, and b) opaque.
 2. An allocator for a new object that can allocate a minimal scratch
 space. So for instance, if your object consumes 32 bytes, but you need
 20 bytes of scratch space, you want the runtime to allocate a 64 byte
 block. So instead of saying new MyObject, you'd say
 newScratchSpace!MyObject(20)

Hack of the year? It looks somewhat backwards but I like it. Especially the "no changes in the compiler/language".
 And I think that's it. Since nothing before this proposal ever referred
 to or used that scratch space, it's not in danger of breaking existing
 code. The only caveat is, it can't properly be typed as shared or not
 (it could be accessible from multiple threads, depending on if the
 actual type is immutable).

I take it that you just love reusing slack space found after the sloppy D runtime in some beneficial nontrivial way! :)
 It also should be recommended that the scratch space not contain any GC
 pointers, since it's *not* participating in the type system properly,
 the GC may not treat it as a pointer.

 And of course, we need a better name than newScratchSpace.

 -Steve

-- Dmitry Olshansky
May 14 2012
prev sibling parent reply =?UTF-8?B?QWxleCBSw7hubmUgUGV0ZXJzZW4=?= <xtzgzorex gmail.com> writes:
On 14-05-2012 21:51, Steven Schveighoffer wrote:
 I have an idea on how to create logical const without any language or
 compiler changes -- it will exist purely in druntime.

 The idea is based on this: Whenever you allocate an object, you use a
 memory block. An object, by default, has the following memory layout:

 monitor - (void *).sizeof bytes
 vtbl - (void *).sizeof bytes
 interface_vtbls[] - (void *)sizeof x number of interfaces.

 So by default, 8 bytes on 32bit, 16 bytes on 64 bit.

 Add any members, and they may increase the size.

 This object goes into the GC heap. Yet the GC heap has only 16, 32, 64,
 128, etc. sized blocks.

 So for instance a class object that requires 24 bytes actually consumes
 32. This leaves 8 bytes of "scratch space". Using a druntime lookup we
 can get access to that entire memory block, including the scratch space.
 And since we use druntime to look it up, *not* the object and its
 contained members (which remember don't include the scratch space), it
 is *not* typed as const or immutable, or whatever the class data is.

 In essence, a const(MyObj) is a pointer to a struct that looks like:

 struct FicticiousMyObjStruct
 {
 const(MyObj_data); // not a reference, the actual data
 ubyte[8] scratchspace;
 }

 So we need two pieces for this proposal:

 1. An accessor in Object for this scratch space. This should be a)
 efficient, and b) opaque.
 2. An allocator for a new object that can allocate a minimal scratch
 space. So for instance, if your object consumes 32 bytes, but you need
 20 bytes of scratch space, you want the runtime to allocate a 64 byte
 block. So instead of saying new MyObject, you'd say
 newScratchSpace!MyObject(20)

 And I think that's it. Since nothing before this proposal ever referred
 to or used that scratch space, it's not in danger of breaking existing
 code. The only caveat is, it can't properly be typed as shared or not
 (it could be accessible from multiple threads, depending on if the
 actual type is immutable).

 It also should be recommended that the scratch space not contain any GC
 pointers, since it's *not* participating in the type system properly,
 the GC may not treat it as a pointer.

 And of course, we need a better name than newScratchSpace.

 -Steve

Another concern I have is that this couples a feature tightly to the implementation of the GC. What if another GC doesn't use the same allocation scheme? -- - Alex
May 14 2012
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 14 May 2012 17:11:14 -0400, Alex R=C3=B8nne Petersen
<xtzgzorex gmail.com> wrote:

 Another concern I have is that this couples a feature tightly to the  =

 implementation of the GC. What if another GC doesn't use the same  =

 allocation scheme?

newScratchSpace uses GC.malloc to ensure the block is big enough. The G= C must support returning a block of memory large enough to hold the requested bytes. It's not tightly coupled, even though it depends on the GC. -Steve
May 14 2012
prev sibling parent "Tove" <tove fransson.se> writes:
On Monday, 14 May 2012 at 21:19:43 UTC, Steven Schveighoffer 
wrote:
 On Mon, 14 May 2012 17:11:14 -0400, Alex Rønne Petersen
 <xtzgzorex gmail.com> wrote:

 Another concern I have is that this couples a feature tightly 
 to the implementation of the GC. What if another GC doesn't 
 use the same allocation scheme?

newScratchSpace uses GC.malloc to ensure the block is big enough. The GC must support returning a block of memory large enough to hold the requested bytes. It's not tightly coupled, even though it depends on the GC. -Steve

It is an interesting idea..., but... we cannot assume that none of the current/future D compilers can make false 'alias assumptions' since it only sees const pointers? something similar to 'mutable' is needed... A way to work around it would be to use 'volatile this' access, that would kinda force the compiler to do the right thing when overriding const... but sadly it's deprecated, and as far as I know there is no alternative... btw how is that intended to work when using a pointer to a hardware register?
May 14 2012