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

[Jonas Maebe]

On 21 Jul 2007, at 12:42, Bram Kuijvenhoven wrote:

> If the vmts are stored in memory in depth-first order [of the class  
> hierarchy], then an O(1) implementation could be made by adding  
> only one field to the vmt: vmtNextSibling; then you'd simply get  
> something like
>
>  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))

This would return true, while it's not true. You cannot solve this by  
duplicating vmt's for different inheritance paths (in fact,  
duplicating vmt's would complicate the is/as problems a lot).

> Are vmts stored in depth first order?

They are probably stored per unit in the order they are declared (not  
sure about forward-defined classes).

> If not, an alternative is to have another vmt field with a number  
> that indicates its index in depth-first order of the class hierarchy.

You would still have to determine that two classes are part of the  
same hierarchy (same branch of the inheritance tree). I also don't  
know whether changing the vmt layout is feasible at this point.


Jonas