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

[Bram Kuijvenhoven]

Peter Popov wrote:
> Even if packages won't work, there is a compromise solution. One can 
> still re-arrange the existing hierarchy. The default 
> TObject.InheritsFrom is as before - traverses the tree. However, a 
> custom class may use the fact that the arrangement is linear. This way, 
> if one has a big custom hierarchy of classes in a single-sourced 
> library, then the search can be O(1) within the library and O(Depth) 
> outside. If the custom class is near the top of the tree, say 
> TPersistent, that the algorithm will be fast

I did a little research and found that there even more algorithms that can be used. There is one candidate that is of particular interest imho -- see below.

Besides the current solution -- walking vmtParents up to AClass or TObject -- and the proposed solution -- compare with vmtPreOrderIndex/vmtLastInSubtree -- there are at least two other solutions. Both have the advantage that they do not need any processing after loading a package and afaics no linker-time magic.

The first is a small adaptation of walking vmtParents; it requires storing a 'vmtLevel' (the distance to TObject in the class hierarchy), and consist simply of not going up to any level lower [closer to TObject] than that of AClass. This method 
- requires storing one additional entry in the VMT and
- is robust against dynamic loading of packages and afaics needs no linker-time magic, but
- gives only a moderate performance improvement (on average; worst case is worse performance than walking vmtParents only)

The second adaptation is O(1), but requires more VMT space. This idea is not my own -- I found it in a paper on the Japaleño JVM from IBM. The trick is to store for each class not only the level at which it resides, but also an array of VMTs pointers of its parents, starting from TObject downto the class itself. So the check in TObject.InheritsFrom(AClass) becomes:

  AClassLevel := AClass.vmtLevel;
  if AClassLevel <= Self.vmtLevel then
    InheritsFrom := Self.vmtParentArray[AClassLevel] = AClass
  else
    InheritsFrom := false;

This method
- requires storing one additional entry and table in VMT,
- is robust against dynamic loading of packages and afaics needs no linker-time magic, and
- gives a significant performance improvement: it runs in O(1) time, comparable with the vmtPreOrderIndex/vmtLastInSubtree method.

I think the latter method only needs an adaptation of TVMTWriter, which I hold responsible for writing VMTs :) So if you agree with an extra table in the VMT, I can try to make a patch (which also updates the vmt* constants and InheritsFrom in the objpas unit). Please let me know if you agree, FPC devs!

Regards,

Bram