Looping through child nodes on TTreeView is slooooow

[Andrew Smith]

Hi all,

Using BCB 6 - I put a TTreeView with a single top node onto a form and
populated it like this:

tree->Items->BeginUpdate();
for (int i=0; i < 1000; i++)
{
tree->Items->AddChild(tree->TopItem, IntToStr(i));
}
tree->Items->EndUpdate();

That takes no time at all. I have a button on the form which does this when
clicked:

for (int i=0; i < tree->TopItem->Count; i++)
{
TreeNode *node = tree->TopItem->Items[i];
}

For some reason, this takes about 10 seconds on my 2GHz Core 2 Duo. Am I
missing something here? Shouldn't this be pretty much instantaneous?
Interestingly, it only seems slow to loop through a node's children. If I
add the 1000 nodes to the root of the tree and loop through those, it's done
instantly.

Anyone got any suggestions?

Cheers,

Andrew

[Andrew Smith]

Bugger it, should have copied and pasted the code instead of retyping.
Second for loop should be this:

for (int i=0; i < tree->TopItem->Count; i++)
{
TreeNode *node = tree->TopItem->Item[i];
}

Post by Andrew Smith
Hi all,
Using BCB 6 - I put a TTreeView with a single top node onto a form and
tree->Items->BeginUpdate();
for (int i=0; i < 1000; i++)
{
tree->Items->AddChild(tree->TopItem, IntToStr(i));
}
tree->Items->EndUpdate();
That takes no time at all. I have a button on the form which does this
for (int i=0; i < tree->TopItem->Count; i++)
{
TreeNode *node = tree->TopItem->Items[i];
}
For some reason, this takes about 10 seconds on my 2GHz Core 2 Duo. Am I
missing something here? Shouldn't this be pretty much instantaneous?
Interestingly, it only seems slow to loop through a node's children. If I
add the 1000 nodes to the root of the tree and loop through those, it's
done instantly.
Anyone got any suggestions?
Cheers,
Andrew

[Remy Lebeau (TeamB)]

Post by Andrew Smith
For some reason, this takes about 10 seconds on my 2GHz Core 2 Duo.

Indexing to a particular child node has to reiterate through the parent
node's child chain from the beginning each time. In other words, to move to
index 2, for example, the first child node has to be retreived, then its
next sibling retreived, then its next sibling retreived. The higher the
index, the longer it takes to find the appropriate child node.

For what you are attempting, use the TTreeNode::GetNext() and related
methods instead (which is what the Items[] property uses internally), ie:

TTreeNode *node = tree->TopItem->getFirstChild();
while( node )
{
node = node->GetNext();
}

Post by Andrew Smith
Shouldn't this be pretty much instantaneous?

Not when using indexes, no. Trees are implemented using double-linked
lists, and thus are not directly indexable in general. The
TTreeNode::Items[] property is provided for convenience, not speed.

Post by Andrew Smith
Interestingly, it only seems slow to loop through a node's children. If I
add the 1000 nodes to the root of the tree and loop through those,
it's done instantly.

The TTreeNodes::Items[] property has additional caching implemented to
prevent the extra reiterating. The TTreeNode::Items[] property does not
have that same caching (I do not know why).


Gambit

[Andrew Smith]

Thanks Gambit, a very reasonable explanation. I've tried what you've
suggested and that definitely solves the speed issues I was having.

Post by Remy Lebeau (TeamB)

Post by Andrew Smith
For some reason, this takes about 10 seconds on my 2GHz Core 2 Duo.

Indexing to a particular child node has to reiterate through the parent
node's child chain from the beginning each time. In other words, to move
to index 2, for example, the first child node has to be retreived, then
its next sibling retreived, then its next sibling retreived. The higher
the index, the longer it takes to find the appropriate child node.
For what you are attempting, use the TTreeNode::GetNext() and related
TTreeNode *node = tree->TopItem->getFirstChild();
while( node )
{
node = node->GetNext();
}

Post by Andrew Smith
Shouldn't this be pretty much instantaneous?

Not when using indexes, no. Trees are implemented using double-linked
lists, and thus are not directly indexable in general. The
TTreeNode::Items[] property is provided for convenience, not speed.

Post by Andrew Smith
Interestingly, it only seems slow to loop through a node's children. If I
add the 1000 nodes to the root of the tree and loop through those,
it's done instantly.

The TTreeNodes::Items[] property has additional caching implemented to
prevent the extra reiterating. The TTreeNode::Items[] property does not
have that same caching (I do not know why).
Gambit