[fpc-devel] Optimization for TObject.InheritsFrom (and the 'is' operator)

[Bram Kuijvenhoven]

Jonas Maebe wrote:
> 
> On 21 Jul 2007, at 15:06, Jonas Maebe wrote:
> 
>>>  InheritsFrom := (AClass <= Self) and (Self < PClass(pointer(AClass) 
>>> + vmtNextSibling)^);
>>>
>>> (In this implementation vmtNextSibling should not be nil for those 
>>> classes that have no NextSibling in the hierarchy, but have a value 
>>> larger than all vmts. An alternative is to have an vmtLastChild, 
>>> which is always properly defined; it points to the last one of: 
>>> itself, its children, its grandchildren, etc.)
>>
>> I don't think this can work, since a class hierarchy is a tree and not 
>> a list. So in case of
>>
>> TObject
>> |
>> +-- TA
>> |
>> +-- TB
>>
>> How would you linearise that in memory? As TObject - TA - TB ?
>>
>> In that case, TB inherirtsFrom TA would be (afaics)
>>
>> (TA <= TB) and (TB < TA+(inf))
> 
> Sorry, no, this would be (TA <= TB) and (TB < TB), so it would be ok. 

TObject - TA - TB is indeed the depth-first order [or: preorder] of the inheritance tree. I'm pretty sure the proposed algorithm is correct for arbitrary trees. If you want, I can try to write a formal proof, if there is interest in implementing the required compiler-side changes.

(Note that all classes descend from TObject, though even if this were not the case, an imaginary root node could be added to form one tree out of the 'forest' of inheritance trees.)

> Still, I don't think laying out classes in memory like this is easy to 
> do without complex linker scripts (which are not supported on all 
> platforms).

I understand the compiler internals can limit the applicability of my proposal. In particular, if the vmts are stored and written per unit, this would need to be changed.

If changing the order in which the vmts are written is hard, maybe it's still possible to change particular fields in the vmts afterwards? That is, we'd have these two vmt fields: 

  vmtDepthFirstIndex, vmtDepthFirstNextSiblingIndex [or: vmtDepthFirstLastChildIndex]

and they'd be filled somewhere near the linking stage; the comparisons in InheritsFrom would then use these fields. Of course using the vmt addresses themselves would be even more optimal, but this would still be a reasonable option.

Bram