[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

This is indeed a comprise solution if re-numbering VMTs on package loading is not feasible or not desired. Of course the compiler must still number the VMTs within the package, and since InheritsFrom is not virtual, any use of 'is' and 'as' will still call TObject.InheritsFrom. In other words: the programmer must replace 'is' by calls to TMyRootObject.InheritsFrom, and 'as' by a macro at best.

Below I give more details of an efficient VMT re-indexing algorithm.

> On Sat, 21 Jul 2007 15:14:56 -0500, Bram Kuijvenhoven 
> <kuifwaremailinglists at xs4all.nl> wrote:
>> If a package is loaded dynamically, the preorder indices in the VMTs 
>> would need to be recalculated. If it is loaded statically, the 
>> compiler can do the calculation on beforehand. Of course the loading 
>> of packages must be done synchronized (in a critical section), but 
>> that might already have been the case. Also, it should be made 
>> possible to enumerate the VMTs that do reside in a package.
>>
>> I think this outweighs the performance gain for InheritsFrom (and 'is' 
>> and 'as'), and it is most beneficial for applications that do not use 
>> packages.

In fact I have figured out that the renumbering can be done without additional memory requirements and in linear time.

So we add two fields to the VMT:
- vmtPreOrderIndex
- vmtLastInSubtreeIndex
Both are to be of type PtrUInt, so they can be casted to pointers. This is used in the algorithm below.

The algorithm consists of three steps:
1) Set the vmtPreOrderIndex and vmtLastInSubtreeIndex fields of all VMTs to nil
2) Build linked lists of childs for each class by using vmtPreOrderIndex as FirstChild and vmtLastInSubtreeIndex as NextSibling
3) Walk the class hierarchy in a depth first fashion, replacing vmtPreOrderIndex/FirstChild by the current Index when a node is encountered first, and replacing vmtLastInSubtreeIndex/NextSibling when the node is encountered last (i.e. its entire subtree has been walked)

(Step 2) gathers exactly that information about the class hierarchy that is required for the depth-first walk in step 3).)

The nice thing is that steps 2) and 3) can be done in *linear time* and *without stack requirements* (i.e. without recursion)!

Pseudo-code for 2):

for vmt in VMTs do
  parent = vmt.parent
  if parent = nil then
    root := vmt  // this will be TObject
  else // add vmt to linked list of children of parent
    if parent.FirstChild = nil then
      parent.FirstChild = vmt
    else
      vmt.NextSibling = parent.FirstChild
      parent.FirstChild = vmt

Pseudo-code for 3):

vmt = root  // the vmt of TObject
index = 0
while vmt<>nil do
  firstChild = vmt.FirstChild
  vmt.vmtPreOrderIndex = index
  if firstChild<>nil then
    vmt = firstChild
  else // find next sibling of first ancestor that has one
    while vmt<>nil do
      nextSibling = vmt.nextSibling
      vmt.LastInSubtreeIndex = index
      if nextSibling<>nil then
        vmt = nextSibling
        Break
      else
        vmt = vmt.parent

So how about implementing this? The same could could be used in the compiler to fill in the initial values of vmtPreOrderIndex/vmtLastInSubtreeIndex.

Bram