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

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

Sorry, no, this would be (TA <= TB) and (TB < TB), so it would be ok. Still, I don't think laying out classes in memory like this is easy to do without complex linker scripts (which are not supported on all platforms).

Jonas

There is no garauntee either within a single unit. With forward defined classes you can make any order you want.

And relying on order in memory has also problems with shared libraries. afaik there is no rule that new libaries are always loaded at larger adresses

Peter

TObject - TA - TB is indeed the depth-first order [or: preorder] of the inheritance tree. I'm pretty sure the proposed algorithm is correct for arbitrary trees. If you want, I can try to write a formal proof, if there is interest in implementing the required compiler-side changes.

(Note that all classes descend from TObject, though even if this were not the case, an imaginary root node could be added to form one tree out of the 'forest' of inheritance trees.)

Still, I don't think laying out classes in memory like this is easy to do without complex linker scripts (which are not supported on all platforms).

I understand the compiler internals can limit the applicability of my proposal. In particular, if the vmts are stored and written per unit, this would need to be changed.

If changing the order in which the vmts are written is hard, maybe it's still possible to change particular fields in the vmts afterwards? That is, we'd have these two vmt fields:

vmtDepthFirstIndex, vmtDepthFirstNextSiblingIndex [or: vmtDepthFirstLastChildIndex]

and they'd be filled somewhere near the linking stage; the comparisons in InheritsFrom would then use these fields. Of course using the vmt addresses themselves would be even more optimal, but this would still be a reasonable option.

Bram

Thank you for this information, Peter. I hadn't thought of shared libraries yet.

Anyway, as far as I understood shared libraries each have their own VMTs, so you can't compare classes that come from different dll's or the main executable. Is that correct?

Can we then assume that at some moment in time the compiler has access to the whole class hierarchy of the whole application? At such a time could it then either re-order the VMTs, or, more simply, fill in a VMT field that is reserved to hold an index, as well as the NextSubtree/LastInSubtree field [see below]?

BTW I now realize that I was using a little bit confusing terminology; with 'depth-first order traversal' I meant 'preorder traversal'. The 'NextSibling' and 'LastChild' names are also confusing. What I actually meant, I'd rather call 'NextSubtree' and 'LastInSubtree'.

Consider the following example:

TObject
|
+- TPersistent
| |
| +- TMyPersistent
| |
+ +- TComponent
| |
| +- TDataset
|
+- TList

Here:
- TMyPersistent.NextSubtree = TComponent, .LastInSubtree = TMyPersistent
- TComponent .NextSubtree = TList, .LastInSubtree = TDataset
- TDataSet .NextSubtree = TList, .LastInSubtree = TDataset
- TList .NextSubtree = <inf>, .LastInSubtree = TList

An every-day example is a directory treeview, such as e.g. the left pane in Windows Explorer. When all nodes are expanded, iterating the rows from top to bottom corresponds exactly with preorder traversal. With this picture in mind, it is relatively easy to see the correctness of the proposed InheritsFrom implementation.

Regards,

Bram

For pure shared libraries yes, for packages no. For packages, Peter is right.

Assume everything on the 1st and 2nd level above is in a package A.

Progam B and C both use package A. What do we do about lastinsubtree?

Before I could answer that question, I needed to know a little bit more about packages and of how VMTs are handled in packages. ... Found http://wiki.freepascal.org/packages. So I assume we are talking about 'library packages' here.

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.

BTW does the compiler optimize

  if (obj is TMyObject) then
    SomeCodeWith(obj as TMyObject)

to

if (obj is TMyObject)
SomeCodeWith(TMyObject(obj))

(under the condition that SomeCodeWith does not change obj.)

Regards,

Bram

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

Peter Popov

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 I give more details of an efficient VMT re-indexing algorithm.

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 vmtnil do
firstChild = vmt.FirstChild
vmt.vmtPreOrderIndex = index

  if firstChildnil then
    vmt = firstChild
  else // find next sibling of first ancestor that has one
    while vmtnil do
      nextSibling = vmt.nextSibling
      vmt.LastInSubtreeIndex = index
      if nextSiblingnil 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

Bram Kuijvenhoven schrieb:

Just curious, did anybody have profiling results which indicate that as/is are really a bottleneck?

Florian Klaempfl wrote

Just curious, did anybody have profiling results which indicate that as/is are really a bottleneck?

Though it can heavily depend on the particular application, the results for a large project I'm working on is as follows:

(Used tool: valgrind-callgrind, FPC 2.1.4, i386, Debian Sarge)

105,233,754 PROGRAM TOTALS

6,417,954 ???:0x00071C80 [/lib/libc-2.3.2.so]
5,350,079 ???:malloc [/lib/libc-2.3.2.so]
4,918,460 ???:fpc_ansistr_setlength
4,687,338 ???:0x00072260 [/lib/libc-2.3.2.so]
4,471,026 <snip>
4,458,735 ???:free [/lib/libc-2.3.2.so]
3,588,596 ???:fpc_pushexceptaddr
3,375,706 ???:fpc_ansistr_decr_ref
3,287,077 ???:SYSTEM_READPCHARLEN$TEXT$PCHAR$LONGINT$$LONGINT 3,099,242 ???:fpc_popaddrstack
2,609,888 ???:SYSTEM_SETJMP$JMP_BUF$$LONGINT
2,237,355 <snip>
2,180,774 <snip>
2,108,772 ???:CMEM_CGETMEM$LONGINT$$POINTER
2,082,456 ???:realloc
1,860,684 ???:fpc_ansistr_concat
1,847,952 ???:0x000725B0 [/lib/libc-2.3.2.so]
1,807,053 ???:SYSTEM_UPCASE$CHAR$$CHAR
1,767,843 ???:SYSTEM_UPCASE$SHORTSTRING$$SHORTSTRING 1,743,218 <snip>
1,664,880 ???:CMEM_CFREEMEM$POINTER$$LONGINT
1,648,998 ???:fpc_ansistr_compare_equal
1,438,248 ???:SYSTEM_GETMEM$POINTER$LONGINT
1,332,799 ???:SYSTEM_FREEMEM$POINTER$$LONGINT
1,328,215 <snip>
1,284,030 <snip>
1,239,614 ???:fpc_ansistr_copy
1,189,035 ???:SYSTEM_TOBJECT_$__INHERITSFROM$TCLASS$$BOOLEAN !!! Here it is !!! 1,046,717 ???:CMEM_CREALLOCMEM$POINTER$LONGINT$$POINTER 1,023,076 ???:0x00015C8D [/lib/libc-2.3.2.so]
837,834 <snip>
788,966 <snip>
764,608 ???:fpc_ansistr_incr_ref
762,624 ???:SYSTEM_MOVE$formal$formal$LONGINT

(<snip> means its a routine from my app.)

The application does not have a very deep inheritance tree (when compared with e.g. the LCL). It uses 'is'/'as' at some places where polymorphism cannot be used. (Comparable with situations like TPersistent.Assign)

The above shows that it takes a reasonable amount of time (about 1.1%), comparable with some of the other 'time-eaters'. I also profiled with other input files, and the results varied, depending on which part of the program was getting focus (e.g. parsing input files (1.6%), or processing image files (0.4%)).

More profiling could be done to get a more objective point of view, so everyone is invited to provide his or her results :)

Still, I think the above already shows that InheritsFrom is worth /some/ attention.

Regards,

Bram

Florian Klaempfl wrote

Just curious, did anybody have profiling results which indicate that as/is are really a bottleneck?

For Lazarus, I found that about 0.5% of the time is spent in TObject.InheritsFrom (I did two runs). About 50% of this comes from calls in TCustomForm.UpdateActions; the rest is mainly scattered. It is comparable with FillChar, CompareMemRange and CompareText.

So what's a bottleneck? I'm happy it doesn't eat say 10%, 20% or even 50% of CPU time, but imho a serious improvement for a function taking 0.5% -- or more -- is worth some attention.

When using '(AClass.vmtPreOrderIndex <= Self) and (Self <= AClass.vmtLastInSubtreeIndex)', those 0.5% will surely go to less than 0.1%. (Especially if it gets inlined :) )

BTW I played around a bit with valgrind/callgrind and KCacheGrind; these are very nice tools for profiling! The call graphs in KCacheGrind are really nice.

Bram

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