How to improve TreeView’s performance – Part I
Update: This post is partially out of date. With .NET 3.5 SP1, TreeView now provides opt-in UI virtualization. You can see this feature working by setting VirtualizingStackPanel.IsVirtualizing=”True” on the TreeView itself. TreeView also supports container recycling, which you can control by setting the VirtualizingStackPanel.VirtualizationMode property. With .NET 3.5 SP1, there is still no support for data virtualization, so the data virtualization portions of this blog post series still apply.
This is the first of three blog posts where I will discuss TreeView performance. This post will cover the problems with our current implementation of TreeView; the next post will show a solution that will enable binding to a large data set; and the third post will discuss a simple idea that adds UI virtualization to a hierarchical data representation.
There are currently three aspects of TreeView’s implementation that affect performance when binding to large data sets:
- UI elements stay in memory after collapsed.
- There is no UI virtualization.
- There is no data virtualization.
I will discuss each of these problems after describing a typical scenario.
Suppose I want to display my registry keys in a TreeView. To do so, I first need to create a hierarchical data structure that is able to hold the registry key data in memory. I defined a “RegistryKeyHolder1″ class containing a property called “Key” that holds the actual RegistryKey, and a property called “SubKeys” of type ObservableCollection. This class also has a “PopulateSubKeys” method that populates the SubKeys property:
public class RegistryKeyHolder1
{
…
public void PopulateSubKeys()
{
try
{
string[] subKeyNames = this.key.GetSubKeyNames();
for (int i = 0; i < subKeyNames.Length; i++)
{
this.subKeys.Add(new RegistryKeyHolder1(this.key.OpenSubKey(subKeyNames[i])));
}
}
catch (SecurityException se)
{
System.Console.WriteLine(se.Message);
}
}
}
I also defined a “RegistryData1″ class that contains a “RootKeys” property, and a “PopulateSubKeys” method. To populate the entire data structure, I start with a collection of RootKeys and use the following recursive method:
public class RegistryData1
{
…
private void PopulateSubKeys(ObservableCollection<RegistryKeyHolder1> keys)
{
foreach (RegistryKeyHolder1 keyHolder in keys)
{
keyHolder.PopulateSubKeys();
this.dataItemsCount += keyHolder.SubKeys.Count;
// It will take forever if I get all registry keys
if (this.dataItemsCount >= 5000)
{
return;
}
PopulateSubKeys(keyHolder.SubKeys);
}
}
}
With this data structure in place, I am now able to bind the TreeView to the RootKeys property directly.
public Window1()
{
InitializeComponent();
this.grid1.DataContext = new RegistryData1();
…
}
<TreeView ItemsSource="{Binding Path=RootKeys}" Name="treeView1" … />
<TreeView.Resources>
<HierarchicalDataTemplate DataType="{x:Type local:RegistryKeyHolder1}" ItemsSource="{Binding Path=SubKeys}">
<TextBlock Text="{Binding Path=ShortName}" />
</HierarchicalDataTemplate>
</TreeView.Resources>
</TreeView>
This data structure makes it really easy to provide a default look for all levels of the hierarchy by using a HierarchicalDataTemplate. Notice the TextBlock in the template, bound to the ShortName property. Since the Name property of RegistryKey returns the whole path of that key, I added a ShortName property to RegistryKeyHolder1 that returns only the interesting part of the key. I use the ItemsSource property of the HierarchicalDataTemplate to specify the items that should be displayed in the next level of the hierarchy - in this case, the subkeys.
UI elements stay in memory after collapsed
If you run this post’s project, you will see that the initial number of visuals of this TreeView is 49. You can use Snoop to see exactly which elements are in the visual tree (although Snoop includes GridColumns in its count and I don’t, so you may see some differences in the results). Now expand the first node and collapse it again. This time the number of visuals is 169, even after you collapsed the node. In our current implementation of TreeView, we let the children items stay around in memory, even after they are collapsed. If your TreeView has a usage pattern where the same few nodes are often expanded and collapsed, then you will get better perf with our current design because the children items don’t have to be garbage collected and re-created every time. However, we realize that in most situations, customers would rather have their items be garbage collected when a node is collapsed. So, overall, I consider this a limitation of our current design of TreeView.
There is no UI virtualization
There are two WPF controls that support UI virtualization currently: ListBox and ListView. This happens because their default panel is a VirtualizingStackPanel, which behaves like a StackPanel but provides UI virtualization.
By UI virtualization, I mean that when you bind a ListBox to a large collection of data, we only create UI containers for the items that are visually displayed (plus a few more before and after, to improve the speed of scrolling). When you scroll, we create new containers for the items that are newly visible, and dispose of the ones that are no longer visible. This greatly improves the performance of binding a ListBox to a large collection.
What about the other Controls in WPF? ComboBox has StackPanel as its default panel, but a user can easily change that to be a VirtualizingStackPanel. TreeView, however, can not use VirtualizingStackPanel to display its items because this panel doesn’t know how to display a hierarchy. The same applies to a ListBox with grouping enabled - a ListBox without grouping has UI virtualization by default, but once you group the data, the UI virtualization is lost.
If you run this post’s code sample, you can easily tell that TreeView does not support UI virtualization. If you expand several nodes so that the scroll bar on the right is enabled, you will see that the number of visuals keeps increasing. Even though many of the items that you expanded are outside of the visible portion of the scroll viewer, WPF still creates all of the visuals necessary to display them.
There is no data virtualization
None of the WPF controls supports data virtualization at the moment. Providing a generic data virtualization solution is a hard problem that everyone on the team is eager to solve, but it hasn’t been our highest priority.
If we had data virtualization for ListBox, that would mean that only the data items displayed are kept in memory. As the user scrolls through the ListBox, new items are brought into memory, and the old ones are discarded. For TreeView, in addition to swapping items in and out of memory due to scrolling, we would also want to load and unload items from memory when their parent item is expanded and collapsed.
So, what is the difference between UI and data virtualization? With UI virtualization we keep in memory only the UI elements (e.g. ListBoxItems) that are displayed visually, but we may still have the whole data structure in memory. Data virtualization goes one step further: we only keep in memory the data items that are being displayed on the screen.
By running this post’s code sample, you can easily tell that there is no data virtualization. You will see, even right after you run it the first time, that the number of data items in memory is over 5000. Since initially only two items are displayed, it’s easy to see that we’re keeping in memory many more items than the ones we need to build up that UI.
That’s all for today’s post. I’ve explained some of the current limitations of TreeView, and in the next two posts I will provide some solutions to these problems. So stay tuned.
Here you can find the VS project with this sample code. This works with Orcas Beta2 bits.
Ben
I’ve been dealing a lot with custom UI virtualization on hierarchical data the past few days, and would like to see what kind of stuff you come up with. I’m also interested in the data virtualization part. Can’t wait!
August 31, 2007 at 3:18 pm
Bea
Hi Ben,
My tricks are very simple to implement. It is definetely possible to implement really fancy and solid data and UI virtualization custom solutions specific to particular scenarios, but I am not planning to cover that.
I appreciate your excitement though
Bea
September 4, 2007 at 9:57 am
Yuval Gilboa
As always, your post touches an extremely useful topic and is written very clearly. I’m really looking forward for the next two parts of this post.
I’ve some comments about the performance of the existing VirtualizingStackPanel when used with large data sets. I don’t know what can be done about these problems in the current version, but hopefully you’ll be able to improve on them in the future:
1) Initial rendering speed is fixed and at an acceptable level, but scrolling/repainting speed degrades linearly as the number of items displayed is increased and/or the complexity of the item templates is increased. There is a noticeable delay when the scrollbar is moved to an area that was not previously rendered (the scrollbar thumb lags significantly behind the mouse cursor), and the scrolling experience becomes choppy.
2) I noticed that as long as the user continues scrolling (without releasing the mouse button) and returns to items that were already visited, the scrolling becomes smooth. It seems that the off-screen items that were visited are retained during the scrolling interaction. However, once the user releases the mouse button, all off-screen items are immediately discarded, and on the next scrolling the same choppy behavior will be manifested. I found no programmatic way to control the latency of the discarding of off-screen items, which can be useful in many cases.
3) I also found no programmatic way to inform the VirtualizingStackPanel that all items have uniform display templates (a very common occurrence), which could provide a useful performance optimization hint (similar to the “table-layout:fixed” property that exists in IE/HTML).
4) Scrolling using the keyboard is also considerably slower than I would expect.
September 1, 2007 at 3:47 pm
Bea
Hi Yuval,
Your thorough comment is very very appreciated! I brought your ideas to my team, and here is what we discussed:
1) You mention that scrolling speed degrades linearly with the number of items displayed. If you want to scroll from item 1 to item 30, the total number of items in your ListBox should not affect perf that much. It will affect a little because of the lack of data virtualization, but since ListBox has UI virtualization, we don’t create wrappers for the items that are not visible. However, if you are constantly scrolling to sections that haven’t been rendered before, then there will be a delay because we need to create the UI wrappers for those items every time you scroll. This is the price we pay to have good initial rendering speed.
Having said that, I must add that we’ve been investigating possible improvements for this scenario. It’s heard to say at this point whether we’ll be able to improve it or not, but I’m keeping my fingers crossed.
2) That’s a great idea - giving the user the capability to control the latency of the discarding of off-screen items. I’ve already added it to our list of feature ideas for the future. I don’t think we should allow customers to specify the delay in the form of time, but we could certainly allow control about the priority of this operation in the dispatcher queue. You would like the discarding of the items to have a lower priority, and we got feedback recently from another customer that would like that operation to have higher priority. The other customer mentioned to us that, if you keep scrolling up and down very quickly, the non-visible items are not discarded, and the memory consumption keep growing. By giving him an API to increase the priority of the discarding operation, he could adjust the behavior of his scenario.
3) Actually, we already detect that scenario today, and it’s possible we’ll be able to improve this scenario a little. We are not looking into layout optimizations in particular, we’re mostly researching the implications of recycling containers. But here’s a tip that you can use today: the more fixed widths and heights you have in your elements, the cheaper the layout will be.
4) Actually, this is the first time we hear this. Do you have a specific sample that you can share with us that shows slow keyboard scrolling? We would be happy to run perf tests on your scenario and see if there is anything we can do to improve that.
Thank you so much for your thorough comment! Feedback like yours greatly helps us improve WPF, and make sure that it solves what customers want!
Bea
September 8, 2007 at 10:24 pm
Laurent
Hi Bea,
It’s great to see you posting again. I have trained quite a few people to WPF lately in my firm, and always mention your blog as *the* place to find information about binding. I unfortunately had to add “but she didn’t post much recently”. Hopefully now I can stop saying this
Side note for the binding team: We really need to be able to bind constructor parameters or method parameters to other elements in XAML. For example something like:
<ObjectDataProvider x:Key=”MyODP”>
<ObjectDataProvider.ConstructorParameters>
<sys:Int32>
<Binding ElementName=”MainWindow” Path=”ActualWidth”/>
</sys:Int32>
</ObjectDataProvider.ConstructorParameters>
</ObjectDataProvider>
Also, why not do ConverterParameter a DP so that we can bind to it:
<Button>
<Binding Source=”{StaticResource Something}”
Path=”MyProperty”
Converter=”{StaticResource MyConverter}”
ConverterParameter=”{Binding ElementName=MyElement, Path=MyValue}”>
</Binding>
</Button>
That would be really helpful!
Keep posting
Laurent
September 8, 2007 at 3:37 pm
Bea
Hi Laurent,
I appreciate your nice words. I’m planning to starting being more active in my blog. It’s been really hard to manage a more than full time job, an active blog, and a life. However, I really miss writing and plan to do it more often.
Yes, we’ve heard that suggestion before. I explained a partial workaround in this blog post, under the “Binding to methods” section. However, it’s not a complete workaround - it doesn’t work for many common scenarios.
We would like to support this scenario, but we can’t simply make those properties DPs because that would mean Binding and ObjectDataProvider would have to be DOs. Apart from possibly affecting perf, it would open up many illegal scenarios that would greatly increase our test matrix. We would like to come up with a design that would allow a Binding to depend on data without necessarily allowing it to be data bound. We have a work item to do this, but it will require some cleaver designing.
Thanks a lot for your suggestions!
Bea
September 10, 2007 at 11:07 am
Laurent
Hi Bea,
Oh yes I know how hard it can be to combine family life, programming as a work, programming as a passion, and additional hobbies
I am aware of the “reverse binding” (Target To Source”) scenario, but thanks for reminding me. Maybe I can use that in some cases.
In the typical case where I need this, however, I don’t think it’s possible. Typically, I’d like to pass a reference to a FrameworkElement to the converter, so that I can perform a “TryFindResource” on that element. Currently, I am using a MultiBinding to do that, where the first Binding is the FrameworkElement (RelativeSource Self), and the second value is the actual value I want to convert. That’s a neat trick (Thanks Dr WPF…) but it’s just a trick.
Anyway
Finding a workaround to these problems has been a very interesting and creative task for me these last weeks, so thank the team for me 
Greetings,
Laurent
September 11, 2007 at 7:43 am
Bea
Hi Laurent,
Yes, that is a good trick.
I’m glad you’re enjoying working with our platform
Although we have some rough edges, I am overall very proud of what we have accomplished.
Bea
September 11, 2007 at 12:59 pm