Thursday, September 21, 2006

.Net 2.0 TreeView Performance Problem

No doubt some of you may have noticed some pretty poor performance in NCoverExplorer when running it under .Net 2.0. I've made some tweaks recently for the imminent NCoverExplorer 1.3.5 release which should improve things, but it still sucks big time in performance compared to .Net 1.1.

I thought that all things .Net 2.0 were supposed to be brighter, shinier and faster I hear you say? Anyone who has had the misfortune to use the dog turd that is the VS.Net 2005 IDE will happily put that "generalisation" to rest (I'm saving that rant for another post). It appears that sadly the same "Microsoft Improvement Programme" has been applied to the TreeView control and it's giving me the heebies.

The problem? I need to update the .Text of the nodes in the tree dynamically. I do this on a lazy loaded basis (mostly for speed reasons that worked under .Net 1.1). As many NCoverExplorer users will know, I offer a variety of "views" such as %, #unvisited nodes, function visits etc - all of which require updating the .Text property of the nodes as you expand them.

In .Net 2.0, Microsoft changed the internal implementation of the TreeView control - but not for the better for my requirements.

In .Net 1.1, calling .BeginUpdate/.EndUpdate around your updates to .Text did absolutely nothing in terms of performance gains. In .Net 2.0 however, you absolutely MUST wrap those same updates to .Text in this call, or else your performance really goes to hell and back (under the hood it generates literally millions of windows messages for a 10MB coverage file loaded). Sure enough this does improve performance considerably - but still nowhere near .Net 1.1 levels as you can see below.

You can download a little test app I knocked up from here. The results of loading around 15,000 nodes in a 1 x 25 x 25 x 25 hierarchy and expanding a node to see it's 25 children are shown. It's a standard TreeView with an override to OnBeforeExpand, which simply loops through the immediate child nodes only and updates the .Text with/without a BeginUpdate/EndUpdate wrapper.

Under .Net 1.1 (time to expand a node):
0.2 secs (using .BeginUpdate/.EndUpdate and updating .Text of the children)
0.2 secs (just updating .Text with no .BeginUpdate/.EndUpdate wrapper)
0.007 secs (just calling .BeginUpdate/.EndUpdate and not updating anything)

Looks pretty good right? Now the bad news:

Under .Net 2.0
1.1 secs (using .BeginUpdate/.EndUpdate and updating .Text of the children)
30.6 secs (just updating .Text with no .BeginUpdate/.EndUpdate wrapper)
1.1 secs (just calling .BeginUpdate/.EndUpdate and not updating anything)

So using .BeginUpdate/.EndUpdate (as you are now forced into under .Net 2.0 as you can see by the nightmare time of not using it) it is still around six times slower using .Net 2.0. That's just crap.

Interestingly with the third of those statistics above you can see that the problem is the .EndUpdate call, which in .Net 2.0 now does a whole lot of windows message blasting - regardless of whether there actually was anything updated as there wasn't in this case.

It is also obviously related to the size of the tree. Below is a graph showing the results with progressively 5, 10, 15, 20, 25, 30 and 35 child nodes under each node. Remember I am only updating the immediate child nodes, not every node in the tree!


It's pretty obvious that the .Net 1.1 implementation both performs and scales a heck of a lot better than .Net 2.0. If there is a reason for this garbage I'd love to hear it...

I'm open to suggestions from anyone else out there who has hit the same problem and figured out a solution. I started a thread on the Microsoft forums in desperation. I already lazy load so users should only incur the hit the first time they expand a node. However it's still pretty darn annoying to wait over a second every first node click to see just a couple of child nodes appear underneath!

15 Comments:

At October 03, 2006 5:36 pm, Anonymous Anonymous said...

Better contact Lutz Roeder (creator of Reflector). His treeview seems to be speedy.

 
At October 03, 2006 6:04 pm, Anonymous Anonymous said...

Try using ngen. It should speed up things.

 
At October 21, 2006 7:04 pm, Blogger kiwidude said...

I have indeed talked to Lutz but he is not in the same situation of having to update text dynamically, hence he does not hit the problem.

As for ngen - that would not I believe make any appreciable difference. The issue is the Microsoft implementation with inefficient bloatware of windows messages - ngen isn't going to reduce the number of those that occur.

 
At November 06, 2006 5:20 pm, Anonymous Anonymous said...

Probably it will not change anything, but make a bug report on Microsoft Connect.

I have this idea that Winforms is by far the worst part of the libraries: there are thousands of bugs and performances hits if you read all the reports already present (and not fixed).

A lot of these problems are caused by incommensurably stupid programmers. I could not believe my eyes when I saw their replies either.

Look here and watch the votes:

https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=93559

As always the problems are solved only if there is enough bitching, so, keep alive your thread.

 
At November 06, 2006 6:31 pm, Blogger kiwidude said...

Hi FullMetal,

I did indeed raise the issue on Connect shortly after the attempt on the newsgroups. It has been the "cone of silence" as far as replies to that are concerned unfortunately. For anyone who wants to try to "bump this" with your added support, the ID is "213142" entitled "Poor .Net 2.0 TreeView Performance for updates".

As you say it's just one of a long list - would be nice if they at least bothered to acknowledge the posting in the first place though.

 
At November 07, 2006 5:52 pm, Anonymous Anonymous said...

Well, I have voted your feedback. I believe TreeView ought to be completely revamped.

By the way did you succeed to contact Lutz? Is he using some special technique for Reflector's TreeView?

As you said I've seen that turning off "Scrollable" the tree is usable enough.
If I could find a way to make a node visible when scrollable==false, I could use an external scrollbar control and do the trick, but so far I had no luck.

 
At November 07, 2006 6:10 pm, Blogger kiwidude said...

Hi FullMetal,

Thanks for the "vote".

Lutz doesnt need to update the text in the tree, which is where the problems lie. He just needs speed of initial population. He looked at his code for me and the tricks he mentioned were to (1) use AddRange for the nodes, and (2) override WndProc so that the WM_ERASEBKGND message is ignored.

As for how I contacted Lutz - I met him through Jamie Cansdale and we chat now and then... both are insanely clever developers (and top blokes too).

 
At December 22, 2006 10:19 am, Blogger Unknown said...

Hi. I have a similar problem with my application (see http://www.site-vault.com), just bumped into this issue 2 days ago when I tested it under .NET 2.0.
You said that there is to much repaint (or too many messages generated/sent by the control). I used to override some messages in order to avoid excessive background repaint.
Here is how my tree is implemented.

public class CustomTree : TreeView
{
public CustomTree() : base(){}
public void EnableDoubleBuffering()
{
// Set the value of the double-buffering style bits to true.
this.SetStyle(ControlStyles.DoubleBuffer |
// ControlStyles.UserPaint |
ControlStyles.AllPaintingInWmPaint,
true);
this.UpdateStyles();
}
protected override void WndProc(ref Message m)
{
// Stop erase background message
if (m.Msg == (int)0x0014) m.Msg = (int)0x0000; // Set to null
base.WndProc(ref m);
}
}

Note: Sorry if the code looks bad in HTML I just copy/paste it.
My idea is to identify that message and stop it. The override of the WndProc function stops the erase background message by setting it to zero.
I did not have enough time to get deep into it but I will.
I hope you are interested in exchanging some info to get this fixed. My email is ealexs@gmail.com

 
At March 16, 2007 3:27 pm, Blogger Unknown said...

My friend and I found a workaround. The problem is that there is a storm of redraw messages send when the text is updated. We have replaced the way the text is set and there is no more performance problem.

#define useThreads
#define useCustomTextProperty

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.Threading;
using System.Runtime.InteropServices;

namespace net20_WindowsApplication1
{
public partial class Form2 : Form
{
const int nodecount = 1000;
public Form2()
{
InitializeComponent();
}

private void populateTree(object o)
{
TreeNode[] items = new TreeNode[nodecount];
for (int a = 0; a < nodecount; a++)
{
#if useCustomTextProperty
items[a] = new CustomTreeNode("hello");
#else
items[a] = new TreeNode("hello");
#endif
}
if (treeView1.InvokeRequired)
treeView1.BeginInvoke(new addItemsdelegate(treeView1.Nodes.AddRange), new object[] { items });
else
treeView1.Nodes.AddRange(items);
#if useThreads
ThreadPool.QueueUserWorkItem(new WaitCallback(populateText), items);
#else
populateText(items);
#endif
}
private void populateText(object o)
{
TreeNode[] items = (TreeNode[])o;
for (int a = 0; a < nodecount/10; a++)
{
for (int b = 0; b < 10; b++)
{
if(treeView1.InvokeRequired)
treeView1.BeginInvoke(new setTextdelegate(setText), new object[] { items[a * 10 + b], "this text has been set " + (a * 10 + b).ToString()});
else
setText(items[a * 10 + b],"this text has been set " + (a * 10 + b).ToString());
}
}

}

private delegate void setTextdelegate(TreeNode i_Node, string text);
private void setText(TreeNode i_Node,string text)
{
#if useCustomTextProperty
((CustomTreeNode)i_Node).NodeText = text;
#else
i_Node.Text = text;
#endif
}
private delegate void addItemsdelegate(TreeNode[] items);

private void Form2_Load(object sender, EventArgs e)
{
#if useThreads
ThreadPool.QueueUserWorkItem(new WaitCallback(populateTree));
#else
populateTree(null);
#endif
}

private void button1_Click(object sender, EventArgs e)
{
treeView1.Nodes.Clear();
#if useThreads
ThreadPool.QueueUserWorkItem(new WaitCallback(populateTree));
#else
populateTree(null);
#endif
}
}

class CustomTreeNode : TreeNode
{
public CustomTreeNode(string i_Text):base(i_Text)
{
}
public const int TV_FIRST = 4352;
public const int TVM_SETITEM = TV_FIRST + 63;
const int TVIF_TEXT = 0x0001;
const int TVIF_IMAGE = 0x0002;
const int TVIF_PARAM = 0x0004;
const int TVIF_STATE = 0x0008;
const int TVIF_HANDLE = 0x0010;
const int TVIF_SELECTEDIMAGE = 0x0020;
const int TVIF_CHILDREN = 0x0040;
const int TVIS_SELECTED = 0x0002;
const int TVIS_CUT = 0x0004;
const int TVIS_DROPHILITED = 0x0008;
const int TVIS_BOLD = 0x0010;
const int TVIS_EXPANDED = 0x0020;
const int TVIS_EXPANDEDONCE = 0x0040;
const int TVIS_OVERLAYMASK = 0x0F00;
const int TVIS_STATEIMAGEMASK = 0xF000;
const int TVIS_USERMASK = 0xF000;

//KAH030807 - Hack around .NET 2.0's text update bug.
public string NodeText
{
get { return Text; }
set
{
System.Reflection.FieldInfo fi = GetType().BaseType.GetField("text", System.Reflection.BindingFlags.Instance | System.Reflection.BindingFlags.Public |
System.Reflection.BindingFlags.NonPublic);
if (fi != null)
fi.SetValue(this, value);
else
Text = value;
TV_ITEM tvItem = new TV_ITEM();
tvItem.hItem = this.Handle;

if (tvItem.hItem != IntPtr.Zero)
{
tvItem.pszText = System.Runtime.InteropServices.Marshal.StringToHGlobalAuto(value);

tvItem.mask = TVIF_TEXT;
int p = SendMessage(this.TreeView.Handle, TVM_SETITEM, IntPtr.Zero, ref tvItem);
System.Runtime.InteropServices.Marshal.FreeHGlobal(tvItem.pszText);
}
}

}
[DllImport("user32.dll")]
private static extern int SendMessage(IntPtr hWnd, int wMsg, IntPtr wParam, ref TV_ITEM tvi);
[StructLayoutAttribute(LayoutKind.Sequential, Pack = 1, Size = 0, CharSet = CharSet.Auto)]
internal struct TV_ITEM
{
public int mask;
public IntPtr hItem;
public int state;
public int stateMask;
public IntPtr pszText;
public int cchTextMax;
public int iImage;
public int iSelectedImage;
public int cChildren;
public IntPtr lParam;
}
}
}

 
At March 17, 2007 9:18 am, Blogger kiwidude said...

Kelly,

Thanks very much for sharing this code - I shall give it a try. I see that you have 3 different conditional compilation constants in there to test different permutations. Which combination did you find gave the best performance?

Incidentally Microsoft closed the bug report with "will not fix" after it sat there for 3 months - with not a single comment or explanation as to why. Gee thanks guys, you really know how to make your customers feel that reporting issues to you is worthwhile. That you can't fix everything I accept - but at least do me the courtesy of an explanation. T*ssers.

 
At November 29, 2007 3:57 pm, Blogger Jams said...

Just found this post today after I had similar performance problems while dynamically changing node text. Kellys workaround worked like an absolute dream for me!!

 
At May 03, 2008 4:03 pm, Blogger Torsten said...

I did not understand Kellys workaround so I invented a new one as follows:


Sub RenameNode(ByVal n As TreeNode, ByVal Name As String, Optional ByVal Reposition As Boolean = True)
Dim p As TreeNode = n.Parent
Dim nn As TreeNodeCollection
If p Is Nothing Then nn = n.TreeView.Nodes Else nn = p.Nodes
n.Remove()
n.Text = Name
nn.Insert(n.Index, n)
If Reposition Then
If n.IsVisible Then n.TreeView.SelectedNode = n
End If
End Sub

This shorts down the renaming of nodes to milliseconds if the node has no children... somewhat longer times for nodes with children.

 
At May 03, 2008 7:52 pm, Blogger Torsten said...

And here it is rewritten for better display:


Sub RenameNode(ByVal n As TreeNode, ByVal Name As String, Optional ByVal Reposition As Boolean = True)
    Dim nn As TreeNodeCollection = frmMain.tvwBox.Nodes
    If n.Parent IsNot Nothing Then nn = n.Parent.Nodes
    n.Remove()
    n.Text = Name
    nn.Insert(n.Index, n)
    If Reposition Then
        If n.IsVisible Then n.TreeView.SelectedNode = n
    End If
End Sub

 
At July 10, 2008 7:43 am, Blogger Zach Saw said...

Looks like there are lots of problems with the TreeView control in .NET 2.0 / 3.0 / 3.5 (they're all the same).

Have a look at my treeview which is fully compatible with the original treeview (and uses the normal TreeNode) and is a true SysTreeView32 control.


http://www.zachsaw.co.cc/?pg=advanced_treeview


Seriously, Microsoft should've done what I did to wrap the SysTreeView32 common control.

 
At August 14, 2009 11:09 am, Anonymous Anonymous said...

I tried out both workarounds posted here.

The first one (reflection + TVM_SETITEM message) works fast, but does not update horizontal scrollbar's range, so if the node's original text was the longest text displayed and you shortened it, the scrollbar will keep the range for the long text. Fortunately, in case the new text is longer than the old one, the h-scrollbar's range will increase correctly.
Actually, the only difference between this workaround's code and the normal Text setter code is that the original one triggers h-scrollbar update in the end. But it does it really stupid way (everything is recalculated and redrawn => the slowdown).

The second workaround does not suffer from the problem mentioned above, however, when removing/reinserting nodes, the entire TreeView will flicker. When updating node text, it first erases its background with white, then it is calculating something (which takes time) and finally the control is redrawn, so the effect is quite ugly and unacceptable for me.
Tried to encapsulate the change with BeginUpdate/EndUpdate, but this suffers from the same slowdown as the origital property setter. Maybe disabling background erasing would do the job, but this can have side graphic effects...

 

Post a Comment

<< Home