Some Ideas for Dynamic Vtables in D

[Michel Fortin]

On 2009-02-14 16:36:11 -0500, grauzone <none at example.net> said:

> Michel Fortin wrote:
>> On 2009-02-14 14:27:51 -0500, grauzone <none at 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 at michelf.com
http://michelf.com/