www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Some Ideas for Dynamic Vtables in D

reply Michel Fortin <michel.fortin michelf.com> writes:
<http://michelf.com/weblog/2009/some-ideas-for-dynamic-vtables-in-d/>

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Feb 14 2009
next sibling parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Michel Fortin wrote:
 <http://michelf.com/weblog/2009/some-ideas-for-dynamic-vtables-in-d/>

=== In the current vtable system, each D object begins with a monitor pointer, followed by a pointer to the vtable, followed by the object’s members. === Isn't it { vtable, monitor, <members> } ?
Feb 14 2009
next sibling parent Michel Fortin <michel.fortin michelf.com> writes:
On 2009-02-14 08:00:29 -0500, Frits van Bommel 
<fvbommel REMwOVExCAPSs.nl> said:

 Michel Fortin wrote:
 <http://michelf.com/weblog/2009/some-ideas-for-dynamic-vtables-in-d/>

=== In the current vtable system, each D object begins with a monitor pointer, followed by a pointer to the vtable, followed by the object’s members. === Isn't it { vtable, monitor, <members> } ?

Indeed you're right. For some reasons I though it was the other way around. I've updated the text to fix that. Thanks. -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Feb 14 2009
prev sibling parent Christopher Wright <dhasenan gmail.com> writes:
Frits van Bommel wrote:
 Michel Fortin wrote:
 <http://michelf.com/weblog/2009/some-ideas-for-dynamic-vtables-in-d/>

=== In the current vtable system, each D object begins with a monitor pointer, followed by a pointer to the vtable, followed by the object’s members. === Isn't it { vtable, monitor, <members> } ?

Yes. import tango.io.Stdout; class Foo { uint i = 14; uint j = 10; } void main () { auto foo1 = new Foo; auto foo2 = new Foo; show(foo1); show(foo2); } void show (Foo foo) { void** ptr = *cast(void***)&foo; for (int i = 0; i < foo.sizeof; i++) { Stdout.formatln("{}\t{}", i, ptr[i]); } } outputs: 0 805ec80 1 0 2 e 3 a 0 805ec80 1 0 2 e 3 a
Feb 14 2009
prev sibling parent reply grauzone <none example.net> writes:
Michel Fortin wrote:
 <http://michelf.com/weblog/2009/some-ideas-for-dynamic-vtables-in-d/>
 

I think this will never work in D:
This process could cause vtables to be relocated in memory. To solve
this, we could fix each objects vtable pointer using the GC type
information about each memory block could be used.

Even if the heap contained all type information, what about scope classes on the stack? For extension methods, if would probably be better to use some kind of separate vtable for this. To prevent ABI breakage with normal methods, one could use the linker, probably. I really should try to write some proof-of-concept assembler code to find out, if it's possible to use the linker to allocate vtable offsets.
Feb 14 2009
parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2009-02-14 14:27:51 -0500, grauzone <none example.net> said:

 Even if the heap contained all type information, what about scope 
 classes on the stack?

Indeed. I'm aware of this reliability problem. That's in part why I also proposed to add one new level of indirection to the vtable instead, although I haven't mentioned it.
 For extension methods, if would probably be better to use some kind of 
 separate vtable for this.

But how do you find the vtable for a given object? Surely you're not proposing dynamically adding new vtable fields to objects? -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Feb 14 2009
parent reply grauzone <none example.net> writes:
Michel Fortin wrote:
 On 2009-02-14 14:27:51 -0500, grauzone <none example.net> said:
 
 Even if the heap contained all type information, what about scope 
 classes on the stack?

Indeed. I'm aware of this reliability problem. That's in part why I also proposed to add one new level of indirection to the vtable instead, although I haven't mentioned it.

I think you did. But suddenly making all virtual methods "slower" would have a hard time to be accepted in D. By the way, you wrote in your blog posting:
Updating the vtable would need to be an atomic operation, but how to do
this without imposing a lock at each function call?

I'm not sure, but I think at least on x86, this is not a problem. You can simply exchange the pointer atomically. To prevent corruption when several threads update the pointer, you can either use a central lock in the updater library code, or you use RCU (read copy update).
 
 For extension methods, if would probably be better to use some kind of 
 separate vtable for this.

But how do you find the vtable for a given object? Surely you're not proposing dynamically adding new vtable fields to objects?

The extension vtable can be a pointer inside the normal vtable (just like ClassInfo, I think). This pointer would provide an additional indirection, like in your proposal. Extension methods would be slightly slower than virtual methods, and normal virtual methods could stay as fast as they are now. This solution is a bit complex/redundant, but nobody would complain about performance issues. Maybe one could implement extension methods as a library. The D runtime only needs to provide a way to add fields to ClassInfo. Like you could write the following code: --------- //return value is a handle to the extension method int addMethod() { //add an extension slot to _all_ ClassInfos //later, this slot is used like a vtable entry int extension_slot = ClassInfo.allocateExtensionSlot(); return extension_slot; } //method_handle = return value of addMethod() //in_class = class, which implements the method //method_address = address of the method void implementMethod(int method_handle, ClassInfo in_class, void* method_address) { void** p = in_class.getExtensionSlotPtr(method_handle); //set vtable entry *p = method_address; } //method_handle = same as above //target = Object on which the method should be invoked //args = arguments to the method void callMethod(Args...)(int method_handle, Object target, Args args) { //read method address from vtable ClassInfo target_class = target.classinfo; void** method_address_ptr = target_class.getExtensionSlotPtr(method_handle); void* method_address = *method_address_ptr; //use some weird assembler code here for the actual invocation call_method(target, method_address, &args[0]); } --------- How to use this: --------- class SomeClass { } void my_extension_method(SomeClass this, int some_arg) { //do stuff } int ext = addMethod(); implementMethod(ext, SomeClass.classinfo, &my_extension_method); Object x = new SomeClass(); // the virtual extension method my_extension_method(x, 123) is called callMethod!(int)(ext, x, 123); --------- Unlike calling my_extension_method() directly, this can use virtual dispatch. How to implement the additional ClassInfo methods? static ClassInfo.allocateExtensionSlot() just increments a global counter to reserve slot entries in all ClassInfos. ClassInfo.getExtensionSlotPtr() accesses an array internal to the ClassInfo instance, using its argument as an index into the array. It works lazily: if the extension slot doesn't exist yet in the ClassInfo, it extends the slot array to make place for it. The good thing is, that you use this for other code, that needs to associate additional information to a ClassInfo. Actually, I would need something like this in my serialization code to get the per-class serialization metadata (call it custom RTTI) from a plain object reference. Not sure if all this makes sense, though.
Feb 14 2009
parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2009-02-14 16:36:11 -0500, grauzone <none example.net> said:

 Michel Fortin wrote:
 On 2009-02-14 14:27:51 -0500, grauzone <none example.net> said:
 
 Even if the heap contained all type information, what about scope 
 classes on the stack?

Indeed. I'm aware of this reliability problem. That's in part why I also proposed to add one new level of indirection to the vtable instead, although I haven't mentioned it.

I think you did. But suddenly making all virtual methods "slower" would have a hard time to be accepted in D.

I'm currently doing some benchmarks to compare what I've proposed and regular vtables. My preliminary findings tend to show that the added overhead is pretty small. I'm wondering, say we change the current system to allow a non-fragile ABI for class methods, how much slower would it have to be in order to be acceptable? And if it allows class extensions, loadable dynamically while the program is running, what overhead would be acceptable?
 By the way, you wrote in your blog posting:
  >Updating the vtable would need to be an atomic operation, but how to do
  >this without imposing a lock at each function call?
 
 I'm not sure, but I think at least on x86, this is not a problem. You 
 can simply exchange the pointer atomically. To prevent corruption when 
 several threads update the pointer, you can either use a central lock 
 in the updater library code, or you use RCU (read copy update).

Atomic operaions won't help that much. What could happen and that we need to avoid is this: 1. Thread 1 reads a function offset from global variable 2. Thread 2 updates the vtable and update the offset global variables 3. Thread 1 calls the function at the offset it has read If thread 2 changes the offset of the function thread 1 is attempting to call, thread 1 will call the wrong function. So not only the vtable and offset update need to be atomic, but each read of the offset and the pointer on the vtable need to be too. Obviously, locking a mutex at each virtual call would ruin the speed more than anything else, so I was wondering if there was an other option.
 For extension methods, if would probably be better to use some kind of 
 separate vtable for this.

But how do you find the vtable for a given object? Surely you're not proposing dynamically adding new vtable fields to objects?

The extension vtable can be a pointer inside the normal vtable (just like ClassInfo, I think). This pointer would provide an additional indirection, like in your proposal. Extension methods would be slightly slower than virtual methods, and normal virtual methods could stay as fast as they are now. This solution is a bit complex/redundant, but nobody would complain about performance issues.

I'd rather go for the simpler solution unless we can show there is a significant speed advantage in the more complicated one. One thing I'd like to avoid is to make class extensions slower. Having class extensions in the language is an encouragement to separate the core functions of a class, the parts that need to access private variables, from all the bells and whistles you may add around that for more convenience. If class extensions are slower, people will want to avoid them.
 Maybe one could implement extension methods as a library. The D runtime 
 only needs to provide a way to add fields to ClassInfo. Like you could 
 write the following code:
 
 ---------
 
 //return value is a handle to the extension method
 int addMethod()
 {
 	//add an extension slot to _all_ ClassInfos
 	//later, this slot is used like a vtable entry
 	int extension_slot = ClassInfo.allocateExtensionSlot();
 	return extension_slot;
 }
 
 //method_handle = return value of addMethod()
 //in_class = class, which implements the method
 //method_address = address of the method
 void implementMethod(int method_handle, ClassInfo in_class,
 	             void* method_address)
 {
 	void** p = in_class.getExtensionSlotPtr(method_handle);
 	//set vtable entry
 	*p = method_address;
 }
 
 //method_handle = same as above
 //target = Object on which the method should be invoked
 //args = arguments to the method
 void callMethod(Args...)(int method_handle, Object target, Args args) {
 	//read method address from vtable
 	ClassInfo target_class = target.classinfo;
 	void** method_address_ptr =
 		target_class.getExtensionSlotPtr(method_handle);
 	void* method_address = *method_address_ptr;
 	//use some weird assembler code here for the actual invocation
 	call_method(target, method_address, &args[0]);
 }
 
 ---------
 
 How to use this:
 
 ---------
 
 class SomeClass {
 }
 
 void my_extension_method(SomeClass this, int some_arg)
 {
 	//do stuff
 }
 
 int ext = addMethod();
 implementMethod(ext, SomeClass.classinfo, &my_extension_method);
 
 Object x = new SomeClass();
 
 // the virtual extension method my_extension_method(x, 123) is called
 callMethod!(int)(ext, x, 123);
 
 ---------
 
 Unlike calling my_extension_method() directly, this can use virtual dispatch.
 
 How to implement the additional ClassInfo methods?
 
 static ClassInfo.allocateExtensionSlot() just increments a global 
 counter to reserve slot entries in all ClassInfos.
 
 ClassInfo.getExtensionSlotPtr() accesses an array internal to the 
 ClassInfo instance, using its argument as an index into the array. It 
 works lazily: if the extension slot doesn't exist yet in the ClassInfo, 
 it extends the slot array to make place for it.
 
 The good thing is, that you use this for other code, that needs to 
 associate additional information to a ClassInfo. Actually, I would need 
 something like this in my serialization code to get the per-class 
 serialization metadata (call it custom RTTI) from a plain object 
 reference.
 
 Not sure if all this makes sense, though.

Seems to be too much complicated for me to like it. -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Feb 14 2009
parent grauzone <none example.net> writes:
Michel Fortin wrote:
 On 2009-02-14 16:36:11 -0500, grauzone <none example.net> said:
 
 Michel Fortin wrote:
 On 2009-02-14 14:27:51 -0500, grauzone <none example.net> said:

 Even if the heap contained all type information, what about scope 
 classes on the stack?

Indeed. I'm aware of this reliability problem. That's in part why I also proposed to add one new level of indirection to the vtable instead, although I haven't mentioned it.

I think you did. But suddenly making all virtual methods "slower" would have a hard time to be accepted in D.

I'm currently doing some benchmarks to compare what I've proposed and regular vtables. My preliminary findings tend to show that the added overhead is pretty small. I'm wondering, say we change the current system to allow a non-fragile ABI for class methods, how much slower would it have to be in order to be acceptable? And if it allows class extensions, loadable dynamically while the program is running, what overhead would be acceptable?

Well, if you can convince the Walter... I'm all for it. I'd argument that if you need performance in a special case (like an inner loop), you shouldn't use virtual methods anyway. Also, you can always use delegates to have a single indirection only.
 
 By the way, you wrote in your blog posting:
  >Updating the vtable would need to be an atomic operation, but how to do
  >this without imposing a lock at each function call?

 I'm not sure, but I think at least on x86, this is not a problem. You 
 can simply exchange the pointer atomically. To prevent corruption when 
 several threads update the pointer, you can either use a central lock 
 in the updater library code, or you use RCU (read copy update).

Atomic operaions won't help that much. What could happen and that we need to avoid is this: 1. Thread 1 reads a function offset from global variable 2. Thread 2 updates the vtable and update the offset global variables 3. Thread 1 calls the function at the offset it has read If thread 2 changes the offset of the function thread 1 is attempting to call, thread 1 will call the wrong function. So not only the vtable and offset update need to be atomic, but each read of the offset and the pointer on the vtable need to be too. Obviously, locking a mutex at each virtual call would ruin the speed more than anything else, so I was wondering if there was an other option.

You would copy the vtable, modify it, and then write the pointer to it. No need to change the old one. You need to be able to reallocate the vtable anyway: it's the only way to add new methods to it.
 
 For extension methods, if would probably be better to use some kind 
 of separate vtable for this.

But how do you find the vtable for a given object? Surely you're not proposing dynamically adding new vtable fields to objects?

The extension vtable can be a pointer inside the normal vtable (just like ClassInfo, I think). This pointer would provide an additional indirection, like in your proposal. Extension methods would be slightly slower than virtual methods, and normal virtual methods could stay as fast as they are now. This solution is a bit complex/redundant, but nobody would complain about performance issues.

I'd rather go for the simpler solution unless we can show there is a significant speed advantage in the more complicated one. One thing I'd like to avoid is to make class extensions slower. Having class extensions in the language is an encouragement to separate the core functions of a class, the parts that need to access private variables, from all the bells and whistles you may add around that for more convenience. If class extensions are slower, people will want to avoid them.
 Maybe one could implement extension methods as a library. The D 
 runtime only needs to provide a way to add fields to ClassInfo. Like 
 you could write the following code:

 ---------

 //return value is a handle to the extension method
 int addMethod()
 {
     //add an extension slot to _all_ ClassInfos
     //later, this slot is used like a vtable entry
     int extension_slot = ClassInfo.allocateExtensionSlot();
     return extension_slot;
 }

 //method_handle = return value of addMethod()
 //in_class = class, which implements the method
 //method_address = address of the method
 void implementMethod(int method_handle, ClassInfo in_class,
                  void* method_address)
 {
     void** p = in_class.getExtensionSlotPtr(method_handle);
     //set vtable entry
     *p = method_address;
 }

 //method_handle = same as above
 //target = Object on which the method should be invoked
 //args = arguments to the method
 void callMethod(Args...)(int method_handle, Object target, Args args) {
     //read method address from vtable
     ClassInfo target_class = target.classinfo;
     void** method_address_ptr =
         target_class.getExtensionSlotPtr(method_handle);
     void* method_address = *method_address_ptr;
     //use some weird assembler code here for the actual invocation
     call_method(target, method_address, &args[0]);
 }

 ---------

 How to use this:

 ---------

 class SomeClass {
 }

 void my_extension_method(SomeClass this, int some_arg)
 {
     //do stuff
 }

 int ext = addMethod();
 implementMethod(ext, SomeClass.classinfo, &my_extension_method);

 Object x = new SomeClass();

 // the virtual extension method my_extension_method(x, 123) is called
 callMethod!(int)(ext, x, 123);

 ---------

 Unlike calling my_extension_method() directly, this can use virtual 
 dispatch.

 How to implement the additional ClassInfo methods?

 static ClassInfo.allocateExtensionSlot() just increments a global 
 counter to reserve slot entries in all ClassInfos.

 ClassInfo.getExtensionSlotPtr() accesses an array internal to the 
 ClassInfo instance, using its argument as an index into the array. It 
 works lazily: if the extension slot doesn't exist yet in the 
 ClassInfo, it extends the slot array to make place for it.

 The good thing is, that you use this for other code, that needs to 
 associate additional information to a ClassInfo. Actually, I would 
 need something like this in my serialization code to get the per-class 
 serialization metadata (call it custom RTTI) from a plain object 
 reference.

 Not sure if all this makes sense, though.

Seems to be too much complicated for me to like it.

It was just an example how you could put stuff like this into a library. A library could use some weird template stuff to provide a nicer interface to the end user. And in fact, you could extend all objects with extra members using this approach, not only ClassInfos.
Feb 14 2009