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
_______________________________________________
fpc-devel maillist - [email protected]
http://lists.freepascal.org/mailman/listinfo/fpc-devel
