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