www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - RFC: Adding an alternative dispatch mechanism

reply Austin Hastings <ah08010-d yahoo.com> writes:
Howdy,

One of the design patterns that doesn't see much publicity in the 
mainstream is the Flyweight pattern.

To save you a trip, Flyweight basically implements large numbers of 
virtual objects - an array of bits, for example, is usually implemented 
via this pattern.

Iould be nice to be able to dodge the relatively high "object tax" for 
small objects, without having to sacrifice all the features that 
switching from class to struct requires. That is, if each object stores 
a vtable, then a class with a single int member pays a 32bit tax on 
32bits of storage, and I suppose 64bits of tax on 32bits of storage in 
64-bit land.

Obviously, this eventually fades away - your 1kbyte uberclass probably 
isn't bothered by the tax. But I've got some 2-byte data that isn't 
about to become a class, for obvious reasons.

Anyway, I'd very much like to preserve the ability to derive subclasses. 
This isn't about converting to struct, but about ways to lower the cost 
of being an object.

To that end, I'd like to propose a sort of opVtable - name obviously 
subject to change - that would somehow report the class of the target 
object, thus enabling virtual function dispatch.

This would be static type based, so if you have a reference to a 
BaseClass, then obviously the call will go to BaseClass.opVtable for 
resolution.

But there are lots of ways to encode type info, so BaseClass could 
implement a trivial approach - all children get the same vtable (this is 
Flyweight, really) - or BaseClass could use some characteristic of the 
target object to determine a child class.

This is for the most part syntactic sugar. But it's pretty powerful 
sugar, since there are some edge cases (the object reference is the 
data) where the amount of code-around to get the same result is pretty high.

As a thinking point, consider UTF-8 "character" sequences. The objects 
are variable sized, and benefit strongly from being closely packed. I 
don't think anyone wants to insert 32 bits of pointer at the front of 
each sequence :).  But there are a LOT of different questions one might 
ask about a UTF8 "object" - is it lower case? what is the upper case 
version? is it in character class 'X'?

A simple implementation would use opVtable to decode enough for size and 
code page info, then proceed from there. The result would be that each 
pointer into a buffer was effectively an object pointer.

Comments?

=Austin
Oct 01 2010
next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Fri, 01 Oct 2010 17:00:39 -0400, Austin Hastings <ah08010-d yahoo.com>  
wrote:


 Howdy,

 One of the design patterns that doesn't see much publicity in the  
 mainstream is the Flyweight pattern.

 To save you a trip, Flyweight basically implements large numbers of  
 virtual objects - an array of bits, for example, is usually implemented  
 via this pattern.

 Iould be nice to be able to dodge the relatively high "object tax" for  
 small objects, without having to sacrifice all the features that  
 switching from class to struct requires. That is, if each object stores  
 a vtable, then a class with a single int member pays a 32bit tax on  
 32bits of storage, and I suppose 64bits of tax on 32bits of storage in  
 64-bit land.

 Obviously, this eventually fades away - your 1kbyte uberclass probably  
 isn't bothered by the tax. But I've got some 2-byte data that isn't  
 about to become a class, for obvious reasons.

 Anyway, I'd very much like to preserve the ability to derive subclasses.  
 This isn't about converting to struct, but about ways to lower the cost  
 of being an object.

 To that end, I'd like to propose a sort of opVtable - name obviously  
 subject to change - that would somehow report the class of the target  
 object, thus enabling virtual function dispatch.

 This would be static type based, so if you have a reference to a  
 BaseClass, then obviously the call will go to BaseClass.opVtable for  
 resolution.

 But there are lots of ways to encode type info, so BaseClass could  
 implement a trivial approach - all children get the same vtable (this is  
 Flyweight, really) - or BaseClass could use some characteristic of the  
 target object to determine a child class.

 This is for the most part syntactic sugar. But it's pretty powerful  
 sugar, since there are some edge cases (the object reference is the  
 data) where the amount of code-around to get the same result is pretty  
 high.

 As a thinking point, consider UTF-8 "character" sequences. The objects  
 are variable sized, and benefit strongly from being closely packed. I  
 don't think anyone wants to insert 32 bits of pointer at the front of  
 each sequence :).  But there are a LOT of different questions one might  
 ask about a UTF8 "object" - is it lower case? what is the upper case  
 version? is it in character class 'X'?

 A simple implementation would use opVtable to decode enough for size and  
 code page info, then proceed from there. The result would be that each  
 pointer into a buffer was effectively an object pointer.

 Comments?

 =Austin


The wikipedia article on the Flyweight pattern seems to describe something  
very different. That flyweight pattern was about conserving overall memory  
by sharing instantiations of immutable objects. Might this be a case of  
two different patterns with the same name? Do you have a link to a paper  
or page explaining the pattern you are talking about? Regarding the rest  
of the post, what features do you think are important and are lost going  
 from a class to a struct and can't be emulated using alias this,  
opDispatch, etc?
Oct 01 2010
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Austin Hastings <ah08010-d yahoo.com> wrote:


 Comments?


To me, this sounds like it could be done with alias this[1] and
references and maybe a pinch of opDispatch[2] (though I am no
longer sure why I thought of the latter).

If I'm wrong, would you care to elucidate?

[1]: http://digitalmars.com/d/2.0/class.html#AliasThis
[2]: http://digitalmars.com/d/2.0/operatoroverloading.html#Dispatch

-- 
Simen
Oct 01 2010
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Austin Hastings:


 if each object stores 
 a vtable, then a class with a single int member pays a 32bit tax on 
 32bits of storage, and I suppose 64bits of tax on 32bits of storage in 
 64-bit land.


Beside the pointer to the virtual table, D objects have a 'monitor' (so the
overhead is two CPU words), plus they may contain padding between the fields,
plus for small memory blocks the allocator uses only power of two sizes, plus
probably there is some GC overhead.

Regarding your idea I have found something related for C++:
http://www.boost.org/doc/libs/1_44_0/libs/flyweight/doc/index.html

Bye,
bearophile
Oct 01 2010