Need advice with huge TreeView performance

[tman]

I am generating a very large tree list in my program and while it's
performance is great once loaded it takes a really long time to load.

I create a root TreeNode "offline" and go through the process of
creating building up the tree from there. Only when I am done do I go
over to the actual TreeView object on my form and add the my root to
the TreeView. This sinlge step when I add my constructed root node to
the form's TreeView control takes a really long time. Constructing the
tree and all it's objects down from the root node took about 16 seconds
at which point all my work is basically done, but the form takes a
whopping 121 seconds to finally show the tree.

Does that sound normal? Is there ANYTHING I can do to speed this up? If
not, is there any way I can somehow show the user the progress of this
TreeView control loading up?

My tree nodes are very, very simple! Most of them are plain text no
more than 3 or 4 characters long. The most commplicated tree nodes are
plain text up to perhaps 80 characters long, and those are rare. It
really should be quick to load up. The data making up the tree is about
8 megs of text (uncompressed), and the program winds up taking around
250 megs.


Is there maybe a more lightweight tree control out there that you would
recommend if the .NET is too inefficient?

Or is there any optimaization you can think of I can try?

 

[Dustin Campbell]

Or is there any optimaization you can think of I can try?

A good solution might be to only fill the nodes that are currently expanded.
Then, fill the nodes on-demand as they are expanded by listening to the BeforeExpand.
I've used this technique with success in the past. The only trick is to add
a dummy child node to each collapsed node that has children and removing
the dummy node when the children are added in the BeforeExpand event handler.

Best Regards,
Dustin Campbell
Developer Express Inc.

 

[tman]

A good solution might be to only fill the nodes that are currently expanded.
Then, fill the nodes on-demand as they are expanded by listening to the BeforeExpand.
I've used this technique with success in the past. The only trick is to add
a dummy child node to each collapsed node that has children and removing
the dummy node when the children are added in the BeforeExpand event handler.

Best Regards,
Dustin Campbell
Developer Express Inc.

sounds like a good idea and I think I will try it. Just one thing, why
fill with dummy nodes? and what would that mean doing exactly? Just
creating an empty TreeNode object and adding it? I ask because if
that's what you meant then I might as well just add the real names
because the full text is really not much bigger than no text at all !

And how did you structure your data on the back end so that when a user
goes to expand some node you know exactly what to fill it with?

 

[Dustin Campbell]

sounds like a good idea and I think I will try it. Just one thing, why

fill with dummy nodes? and what would that mean doing exactly? Just
creating an empty TreeNode object and adding it? I ask because if
that's what you meant then I might as well just add the real names
because the full text is really not much bigger than no text at all !

I find that the dummy node solution works well because it can be used as
an indicator that its parent still need to be filled with children. That
makes the code a bit easier to write.

Here's an example of what I'm talking about

Root
|
--First child (no children)
--Second child (has children)
-- Dummy node
--Third child (no children)

In order to make "Second child" expandable in the UI, it must contain at
least one node. And, since the data isn't loaded until the BeforeExpand is
fired for "Second child" we add a dummy node that indicates that "Second
child" needs to be filled. Consider this event handler code:

private void myTreeView_BeforeExpand(object sender, TreeViewCancelEventArgs
e)
{
if (FirstNodeIsDummyNode(e.Node))
{
RemoveDummyNode(e.Node);
AddChildren(e.Node);
}
}

Using a dummy node in the above code ensures that the children are only added
to the node once.

And how did you structure your data on the back end so that when a
user goes to expand some node you know exactly what to fill it with?

In a tree situation, I often find it easiest to just keep your data in some
sort of composite structure so that you can easily match the data to the
nodes.

Best Regards,
Dustin Campbell
Developer Express Inc

 

[Grant Frisken]

A good solution might be to only fill the nodes that are currently expanded.
The dummy node approach works well provided you don't have too many
nodes parented by any given node. If for example you have a 1000 nodes
under one parent node then you still have to load all 1000 (even though
you might only be displaying 30). The other disadvantage of the dummy
node approach is the disappearing expansion icon issue ie if a given
node doesn't have any children when the user clicks the expansion icon
the expansion icon then dissappears - this can be somewhat
disconcerting.

You might want to take a look at Infralution's Virtual Tree. It
addresses both of these issues and only loads the data actually
required to support the current display. This means it loads almost
instantly and has a minimal memory footprint even when viewing huge
datasources. You can get more information and download an evaluation
version from:

www.infralution.com/virtualtree.html

Regards
Grant Frisken
Infralution

 

[Peter Duniho]

And how did you structure your data on the back end so that when a user
goes to expand some node you know exactly what to fill it with?

In addition to what Dustin wrote (his solution is almost exactly,
C#-statement-for-C#-statement what I did for a similar situation), I'll
point out that you just need to put in the dummy node whatever information
you need to tell you where to get the rest of the data.

In my case, I had code that was parsing a file that had an internal tree
structure. Each dummy node contained the file offset and length of the data
remaining to be parsed for that node. Then when it came time to expand that
node, it was a simply matter to read the data from the file and parse it
into the nodes necessary to fill that part of the tree (I only ever parsed
one level at a time, so expanding one dummy node often wound up creating a
bunch more dummy nodes one level lower ).

But what specifically you put in the dummy node just depends on what you
need in order to retrieve the data you skipped over earlier. Only you can
answer that question.

Note that to do the above, you wind up creating an actual dummy node class,
derived from the TreeNode class, so that you can actually insert an instance
of that class in the tree. Then, the tree control itself holds on to all
the dummy node instances for you, all ready to process later.

Pete

 

[Peter Duniho]

The dummy node approach works well provided you don't have too many
nodes parented by any given node. If for example you have a 1000 nodes
under one parent node then you still have to load all 1000 (even though
you might only be displaying 30).

I agree this is a potential issue. One can work around that with the
default control by only loading enough nodes to fill the current visible
portion of the control, and enough extra to provide some scrolling feedback.

That said, if you responded that the scrolling feedback is inaccurate and
misleading, I wouldn't disagree. The MSDN web site used to do something
like this for a few months recently, and I hated it. But still, it's a
possible option.

A more correct solution would be to somehow fix the scrollbars so that they
didn't require the tree view to be populated in order to correctly show the
range of data available in the tree view. I presume your custom control
does this.

Of course, even doing it that way, one runs into the problem that you are
then populating the tree view as it's being scrolled. Depending on where
the data is coming from, this may also be a poor user experience. The user
may prefer to wait a few seconds to get those 1000 nodes loaded, rather than
having to wait a quarter second for each one to load as it gets scrolled
into view. (That was certainly one of my major objections to the MSDN web
site implementation...in addition to not being able to scroll immediately to
the end, I had to wait for each little section of text to get loaded).

The other disadvantage of the dummy
node approach is the disappearing expansion icon issue ie if a given
node doesn't have any children when the user clicks the expansion icon
the expansion icon then dissappears - this can be somewhat
disconcerting.

IMHO, this is not an issue at all. The code should only be adding dummy
nodes when there is in fact additional data below the given node. Code that
creates a dummy node when no data is actually present below the given node
is buggy code, and not worth consideration here.

Pete

 

[Grant Frisken]

That said, if you responded that the scrolling feedback is inaccurate and

misleading, I wouldn't disagree. The MSDN web site used to do something
like this for a few months recently, and I hated it. But still, it's a
possible option.

Which is what I would say It is also quite difficult and messy to
code this approach (aside from it's other user drawbacks).

A more correct solution would be to somehow fix the scrollbars so that they
didn't require the tree view to be populated in order to correctly show the
range of data available in the tree view. I presume your custom control
does this.

It is extremely difficult (if not impossible) do this with the standard
treeview. Our control (along with most other commercial controls) is
written from the ground up.

Of course, even doing it that way, one runs into the problem that you are
then populating the tree view as it's being scrolled. Depending on where
the data is coming from, this may also be a poor user experience. The user
may prefer to wait a few seconds to get those 1000 nodes loaded, rather than
having to wait a quarter second for each one to load as it gets scrolled
into view. (That was certainly one of my major objections to the MSDN web
site implementation...in addition to not being able to scroll immediately to
the end, I had to wait for each little section of text to get loaded).

For very slow datasources (ie web based retrieval) this may be an
issue. For data coming from the local hard disk or database this is
not an issue. VirtualTree has a TrackVertScroll property which if set
to false, means the display is not updated as the scrollbar is dragged
(only when it is dropped).

IMHO, this is not an issue at all. The code should only be adding dummy
nodes when there is in fact additional data below the given node. Code that
creates a dummy node when no data is actually present below the given node
is buggy code, and not worth consideration here.

Actually there is a reason why you might choose to do this. The cost
to determine a given node has children can be significant -
particularly if I am adding say 100 child nodes to a given node. If
for each node I have to perform some kind of database query to find out
whether the node has any children (to work out whether I need to add
the dummy node below it) then this can have a significant performance
impact. Virtual Tree in this situation only generates queries for the
children that are actually displayed (maybe 30 or so) and so will be
much faster where there are large numbers of children of any given
node. Even so querying the nodes for children as they are displayed
can have an adverse affect on scrolling performance depending on your
data source. Virtual Tree has a LoadOnDemand option that allows you to
defer the query until the user actually clicks the expansion icon -
which of course may cause the icon to disappear if the node has no
children.