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

[Bram Kuijvenhoven]

Peter Vreman wrote:
>> On 21 Jul 2007, at 15:06, Jonas Maebe wrote:
>> 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).
> 
> 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

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