Some Ideas for Dynamic Vtables in D

[grauzone]

Michel Fortin wrote:
> 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?

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.