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

[Bram Kuijvenhoven]

Hi FPC devels,

The current implementation of the class method TObject.InheritsFrom(AClass) walks up the class hierarchy searching for the vmt of AClass. This algorithm is linear in the depth of the class hierarchy. Since I use lots of 'is' and 'as' in my applications I wondered whether this could be improved. (fpc_do_is and fpc_do_as both call InheritsFrom.)

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.)

Are vmts stored in depth first order? Is it possible to do so?

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.

Regards,

Bram