Introduction
When loading items into Windows Forms standard TreeView
, you will find it can take an enormous time when loading many items! This simple extension will make loading lightning fast.
In this simple demo application, I use my own TreeViewFast
control and compare it with the standard TreeView
. As you can see, the difference is substantial.
Background
In my project, I need to load ~100 000 items in one go. When using the TreeView
control, I was kind of depressed when I found out it took me 40-50 minutes ....
My first attempt was to reorganize the items using the SQL Server 2008 HierarchyId
. That was interesting and useful in many ways, but for my case, it made very little difference. We have a typical "adjacency" table list where each item is stored in a table with a possible reference to a parentId
.
When adding items to TreeView
nodes collection, I don't know their structure except for the reference to the parent. That means I am forced to use the Find
method of the TreeViewNodesCollection
to get hold of parent. Obviously, the TreeView
has a very poor performance on the inner data structure making it painfully slow for large item collections.
I know there are many nice controls to buy having many nice features. But I just wanted to prove the case that if all you need is better performance, then a simple extension to the existing TreeView
will actually do.
Standard Approach
I start by generating a large set of demo items. In this case, they are employee
s with a consecutive Id
property and randomly generated name combinations. Each employee
is related to a manager by an optional ManagerId
. If set to NULL
, it means the employee
is at the top level.
The standard way of adding these as nodes in TreeView
control is like this:
foreach (var employee in employees)
{
var node = new TreeNode { Name = employee.EmployeeId.ToString(),
Text = employee.Name,
Tag = employee };
if (employee.ManagerId.HasValue)
{
var parentId = employee.ManagerId.Value.ToString();
var parentNode = myTreeView.Nodes.Find(parentId, true)[0];
parentNode.Nodes.Add(node);
}
else
{
myTreeView.Nodes.Add(node);
}
}
When having small collections, this is fine, but when you start to count in thousands, it is terrible. In fact, the loading time is exponential to the number of items as seen in the following table.
Given times are in milliseconds. 100 000 items take 3 427 380 ms to load into standard TreeView
. That's the same as 57 minutes! In the TreeViewFast
, it takes 1 467 ms, that is 1.4 seconds.
I skipped trying to load 1 000 000 items into the normal TreeView
....
In the TreeViewFast
implementation, the loading times are proportional or even faster.
Optimized Approach
I decided to use the standard TreeView
but just extend it slightly. So I created a class TreeViewFast
that inherits from the TreeView
. The major trick is to create an internal Dictionary
to store all nodes. That way, all parent lookups will always be fast, even for large collections.
I decided to use int
as data type for item Id
and int?
for parentId
. That can be questioned but in most cases, I think it will fit the existing data structure. I tried to use string
but found it will give 10% slower times. If you need string
or guid
, it is very simple to just modify the code.
private readonly Dictionary<int, TreeNode> _treeNodes = new Dictionary<int, TreeNode>();
As you can see, I decided to store the TreeNode
items in the Dictionary
. That will make it convenient to use. The item
objects will be stored in the TreeNode
generic Tag
property. That way, we have easy access to the item objects all the time.
Ideally, we would like to have a generic constructor of the control class. Something like:
public class TreeViewFast<T> : TreeView
That would make it really easy to refer to the type everywhere in the class. But unfortunately, the Windows Forms designer cannot handle controls with generic constructors.
A better idea would be to use types implementing a common interface, like ITreeViewFastItem
.
But that would force all entities to have access to that interface. In my setup, the entities are defined in projects that must not have any dependency to the Windows Forms project where I define all controls.
So in my case, I decided to allow each method to have a T
specifier and where necessary, I enter parsing functions to help the loader to interpret the object. This means the Load
method will look like this:
public void LoadItems<T>(IEnumerable<T> items, Func<T, int> getId,
Func<T, int?> getParentId, Func<T, string> getDisplayName)
{
Nodes.Clear();
_treeNodes.Clear();
foreach (var item in items)
{
var id = getId(item);
var displayName = getDisplayName(item);
var node = new TreeNode { Name = id.ToString(),
Text = displayName,
Tag = item };
_treeNodes.Add(getId(item), node);
}
foreach (var id in _treeNodes.Keys)
{
var node = GetNode(id);
var obj = (T)node.Tag;
var parentId = getParentId(obj);
if (parentId.HasValue)
{
var parentNode = GetNode(parentId.Value);
parentNode.Nodes.Add(node);
}
else
{
Nodes.Add(node);
}
}
}
The actual storage of nodes and objects is in the Dictionary
.
To make the nodes visible, they are added to the TreeView
internal Nodes
collection making the expected hierarchy be seen as expected. The Nodes
collection will in fact only hold references to the Dictionary
objects so we don't waste any memory.
The important difference is the GetNode
lookup which can now make use of the fast Dictionary
lookup.
public TreeNode GetNode(int id)
{
return _treeNodes[id];
}
Calling the above Load
method is simple:
Func<Employee, int> getId = (x => x.EmployeeId);
Func<Employee, int?> getParentId = (x => x.ManagerId);
Func<Employee, string> getDisplayName = (x => x.Name);
myTreeViewFast.LoadItems(employees, getId, getParentId, getDisplayName);
Some additional methods are added to the control for convenience: GetItems
and GetDescendants
. They are useful when you need to search the internal items collection or lookup children to a specific item.
Lessons Learned
- It is always useful to do detailed performance measuring to find crucial bottlenecks!
- Large sets of data is in itself not a problem as long as you handle them with care.
- I love Dictionaries. They seem to rescue me over and over again.
History