Saturday, April 08, 2006

Dynamic methods compiler implementation

In a previous article, we have covered how the compiler implements non-virtual and virtual method calls. We have also discussed the rationale and semantics of dynamic methods. You’ll recall that dynamic methods works just like virtual methods, only slower. In this article we’ll dig down into the compiler magic and RTL support that is used to support dynamic methods. Note that most of the mechanics used for dynamic methods is also used by message methods – the only difference is that message methods let the programmer decide the index of the method (the message number, a positive 16-bit number).

Call to dynamic method
While a non-virtual method encodes the address of the target method directly in the CPU instruction, and a virtual method looks up the address in the VMT using a fixed offset, calling a dynamic method is very different. All dynamic method calls targets the same routine – a compiler magic RTL routine in the System unit called _CallDynaInst. This routine takes two parameters – the instance pointer (in EAX) and a 16-bit Smallint selector (in SI).

For instance:

type
TMyClass = class
procedure FirstDynamic; dynamic;
procedure SecondDynamic; dynamic;
end;
// …
var
Instance: TMyClass;
begin
Instance := TMyDescendent.Create;
Instance.FirstDynamic;
Instance.SecondDynamic;
end.

Generates the following code for the two dynamic method calls:

TestDmt.dpr.334: Instance.FirstDynamic;
004096D6 8BC3             mov eax,ebx
004096D8 66BEFFFF         mov si,$ffff
004096DC E8E7A2FFFF       call @CallDynaInst
TestDmt.dpr.335: Instance.SecondDynamic;
004096E1 8BC3             mov eax,ebx
004096E3 66BEFEFF         mov si,$fffe
004096E7 E8DCA2FFFF       call @CallDynaInst

Notice the two different constants loaded into the SI register (the low-word of the ESI register); $ffff and $fffe. As it happens this is the binary (or hex) representation of the Smallint values -1 and -2, respectively. So the effect of calling different dynamic methods is to pass different numeric constants to the magic _CallDynaInst helper routine. At compile time the compiler assigns a unique negative number to each dynamic method in a class – this means that you can have no more than 32768 dynamic methods in a class – more than enough for most cases, I should think(!

When the compiler assigns numeric values to the dynamic methods of a class, it also populates a dynamic method table (DMT), associating the value (aka. selector or DMT index) with the address of the method. The _CallDynaInst routine scans this table at runtime, trying to find a match for the DMT index it was given in the SI register. If it succeeds, it JMPs to the correct address. If not it continues the scan in the parent class’ DMT. If there are no matches it triggers a Run Time Error 210 (which SysUtils converts into an EAbstractError exception).

Calling a dynamic method from BASM
If you find yourself in the (unlikely?) event of having to call a dynamic method from an assembly language routine, you can use the relatively new DMTINDEX directive to get the dynamic method index for a specific method. Lets first just retrieve the index for a gentle start:

function MyDynamicMethodIndex: integer;
asm
MOV EAX, DMTIndex TMyClass.FirstDynamic
end;



procedure Test;
begin
Writeln(MyDynamicMethodIndex);
end;

Provided we have the TMyClass definition from above this code snippet will output the number -1. Very useful and interesting, right? :-P Lets go one step further and actually call the method from the assembly code

procedure CallFirstDynamicMethod(Self: TMyClass);
asm
MOV ESI, DMTIndex TMyClass.FirstDynamic;
CALL System.@CallDynaInst
end;

So the way to call a dynamic method from BASM is to first load the index into ESI using the DMTIndex directive with the full name of the class and method, and then call the magic routine System.@CallDynaInst (the compiler maps the _-prefix of the compiler magic RTL routines into a @-prefix, making them impossible to call explicitly from Pascal code). Notice that _CallDynaInst (and its friend _CallDynaClass) uses the unconventional parameter passing register (E)SI - the reason is that it cannot use the registers that the dynamic method itself may be using for passing parameters (ECX and EDX). In all cases EAX contains the Self pointer.

Note that BASM also supports calling a dynamic method statically, without polymorphic dispatch:

procedure StaticCallFirstDynamicMethod(Self: TMyClass);
asm
CALL TMyClass.FirstDynamic // Static call
end;

But that is normally not what you want.

Speeding up calls to dynamic methods
If you have a time sensitive routine that needs to call a dynamic method inside a long-running loop, you can use a trick to speed it up. Instead of incurring the expensive dynamic dispatch lookup in each iteration, move the loop-invariant lookup outside the loop by assigning the method address to a procedure pointer.

If the instance reference stays the same throughout the loop, you can use a procedure of object variable.

procedure SlowDynamicLoop(Instance: TMyClass);
var
i: integer;
begin
for i := 0 to 1000000 do
Instance.FirstDynamic;
end;

procedure FasterDynamicLoop(Instance: TMyClass);
var
i: integer;
FirstDynamic: procedure of object;
begin
FirstDynamic := Instance.FirstDynamic;
for i := 0 to 1000000 do
FirstDynamic;
end;

Here we have optimized the loop by moving the dynamic method lookup outside the loop. If the algorithm runs through a list of different instances, and you can guarantee that the list is homogenous, you can use a procedure variable and explicitly pass the Self instance pointer:

procedure SlowDynamicListLoop(Instances: TList);
var
i: integer;
Instance: TMyClass;
begin
for i := 0 to Instances.Count-1 do
begin
Instance := Instances.List[i];
Instance.FirstDynamic;
end;
end;

procedure FasterDynamicListLoop(Instances: TList);
var
i: integer;
Instance: TMyClass;
FirstDynamic: procedure(Self: TObject);
begin
FirstDynamic := @TMyClass.FirstDynamic;
for i := 0 to Instances.Count-1 do
begin
Instance := Instances.List[i];
Assert(TObject(Instance) TMyClass);
FirstDynamic(Instance);
end;
end;

In assert-mode we check that our assumption holds. In fact, this optimization would work even in cases where you have a heterogeneous list of TMyClass objects, as long as none of the subclasses override the dynamic method. We can check that like this:

function TMyClassFirstDynamicNotOverridden
(Instance: TMyClass): boolean;
var
FirstDynamic: procedure of object;
begin
FirstDynamic := Instance.FirstDynamic;
Result := TMethod(FirstDynamic).Code = @TMyClass.FirstDynamic;
end;

procedure FasterDynamicListLoop2(Instances: TList);
type
PMethod = TMethod;
var
i: integer;
Instance: TMyClass;
FirstDynamic: procedure (Self: TObject);
begin
FirstDynamic := @TMyClass.FirstDynamic;
for i := 0 to Instances.Count-1 do
begin
Instance := Instances.List[i];
Assert(TObject(Instance) is TMyClass);
Assert(TMyClassFirstDynamicNotOverridden(Instance));
FirstDynamic(Instance);
end;
end;

Note that these optimizations are normally not very useful. Well-designed software should probably not use dynamic methods in the first place, and it should definitively not use dynamic methods for time critical operations. Never-the-less, in the rare case where you must call a 3rd party dynamic method in a loop, you now know how you can optimize such loops.

In a later article we’ll dig even further, exposing the structure of the DMT.

[Delphi syntax highlighting provided by DelphiDabbler PasH]

5 comments:

Lars Fosdal said...

This topic wouldn't happen to have spawned from working with TeeChart?
Just curious :)

Hallvard Vassbotn said...

Hi Lars!

No, not really. We do work with TeeChart and have infact changed and enhanced it in various ways to add functionality and improve performance in our specific use of it.

I'm writing this article series about the implementation details of the Delphi language and the VMT mostly for fun.

Why do you ask - does TeeChart have some slow dynamic methods?

Lars Fosdal said...

At the time of my comment, my man on the charts suspected something bogus as AQtime indicated significant time spent through CallDynaInst.

As CallDynaInst was a white spot on the map, I did a google and was pleasantly surprised to find you doing your excellent indepth coverage on just the right topic :)

However, it turned that a forgotten assert was the time consumer.

Still, having worked with TeeChart for years - I guess we are somewhat superstitious around all the magic that goes on in it's unexposed innards :P

Anonymous said...

Hi, you wouldnt happen to know if the procedure address is available from within the procedure.

I want to log procedure calls, so I am intending to keep the address of each procedure. I want to do this inside the procedure. Because I am inside it, I do not know its address.

It is similar to the use of self for the use of objects.

best regards

Colin Carter

Hallvard Vassbotn said...

Hi Colin,

> if the procedure address is available from within the procedure.

Well, yes. You can explicitly take the address of the current method by using the address operator. This works on both global routines and object methods, like this:

procedure Log(const Msg: string; FromProc: pointer); overload;
begin
Writeln(Format('%s from %p', [Msg, FromProc]));
end;

procedure Foo;
begin
Log('Hello', @Foo);
end;

procedure TMyClass.Foo;
begin
Log('Hello', @TMyClass.Foo);
end;

If you are willing to use a little hackish BASM you can even remove the explicit address parameter and have the called routine get the return address from the stack, like this:procedure Log(const Msg: string; FromProc: pointer); overload;
begin
Writeln(Format('%s from %p', [Msg, FromProc]));
end;

procedure Log(const Msg: string); overload;
function ReturnAddr: Pointer;
asm
MOV EAX,[ESP+8]
end;
begin
Log(Msg, ReturnAddr);
end;

procedure Foo;
begin
Log('Hello');
end;

procedure TMyClass.Bar;
begin
Log('Hello');
end;

Note that this will log an address inside the method (the return address), not the start of the routine. Note that the index (8) is dependent on the number of local variables in the outer routine (Log).

The addresses can be looked up in the .MAP file to find the corresponding symbolic name.

It is also possible to directly get the current instruction pointer by calling a function like:

function GetIP: Pointer;
asm
MOV EAX, [ESP]
end;



Copyright © 2004-2007 by Hallvard Vassbotn