digitalmars.D - Some Ideas for Dynamic Vtables in D
-
Michel Fortin
(5/5)
Feb 14 2009
- Frits van Bommel (7/8) Feb 14 2009 ===
- Michel Fortin (8/17) Feb 14 2009 Indeed you're right. For some reasons I though it was the other way
- Christopher Wright (32/41) Feb 14 2009 Yes.
- grauzone (10/15) Feb 14 2009 Even if the heap contained all type information, what about scope
- Michel Fortin (10/14) Feb 14 2009 Indeed. I'm aware of this reliability problem. That's in part why I
- grauzone (77/93) Feb 14 2009 I think you did. But suddenly making all virtual methods "slower" would
- Michel Fortin (32/146) Feb 14 2009 I'm currently doing some benchmarks to compare what I've proposed and
- grauzone (13/169) Feb 14 2009 Well, if you can convince the Walter...
<http://michelf.com/weblog/2009/some-ideas-for-dynamic-vtables-in-d/> -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Feb 14 2009
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
Michel Fortin <michel.fortin michelf.com> On 2009-02-14 08:00:29 -0500, Frits van Bommel <fvbommel REMwOVExCAPSs.nl> said:Michel Fortin wrote: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/<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
Frits van Bommel wrote:Michel Fortin wrote: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<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
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 object’s 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
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
Michel Fortin wrote:On 2009-02-14 14:27:51 -0500, grauzone <none example.net> said: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: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.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).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.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?
Feb 14 2009
On 2009-02-14 16:36:11 -0500, grauzone <none example.net> said:Michel Fortin wrote: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?On 2009-02-14 14:27:51 -0500, grauzone <none example.net> said:I think you did. But suddenly making all virtual methods "slower" would have a hard time to be accepted in D.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.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.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.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.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?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
Michel Fortin wrote:On 2009-02-14 16:36:11 -0500, grauzone <none example.net> said: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.Michel Fortin wrote: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?On 2009-02-14 14:27:51 -0500, grauzone <none example.net> said:I think you did. But suddenly making all virtual methods "slower" would have a hard time to be accepted in D.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.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.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.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.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.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.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?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.
Feb 14 2009