Memory use of Dynamically expanding TreeView
I created a tool a few years ago that uses a WPF TreeView with huge numbers of nodes. The branching factor is pretty high (the number of branches per level), and the depth can be several hundred levels. Of course, creating the whole tree would consume huge amounts of memory and processing time. This is the same problem as Windows File Explorer when showing files and directories on your disk. It doesn’t read the entire disk to start, but only reads and shows the current directory, and expands nodes on demand.
To consume fewer resources, my WPF code similarly expands only the nodes the user selects as being interesting, and creates the children of the selected node on demand. This hugely alleviates the resource problem.
To indicate that a node is expandable a visual indicator like an isosceles triangle can be displayed on the nodes that can have children. When the node is expanded, the triangle rotates. When a WPF TreeViewItem has children, the display automatically shows such a triangle.
My original implementation used a class MyTreeViewItem which inherits from TreeViewItem. To display nodes as expandable, I added a dummy MyTreeViewItem node as a child. When the node is selected, the Expanded Event handler removes the dummy node and adds the real child nodes. This works fine, but consumes more memory than necessary.
Because a TreeViewItem’s Items collection can hold any kind of object, not necessarily a TreeViewItem, another optimization can be made: Instead of adding an empty MyTreeViewItem object with a _IsDummy = true, just add a Boolean.
Then the code that tests to see whether or not the current node’s children have been calculated already is a simple cast test ((itemParent.Items[0] as MyTreeViewItem == null)).
The number of leaf nodes can be quite large, and the memory savings is not insignificant.
For example, the bool adds 4 bytes to the size of the class. So not only can I remove 4 bytes per every node instance, I can reduce the leaf node instance from a size of 276 bytes to 4 bytes.
Below is the layout of the class MyTreeViewItem, showing the classes in inheritance order and the members in offset order contributed by each level of inheritance (or “no members”).
Each layout line also indicates the value of the member. So for example at offset 84, there are four 4 byte values making up the System.Windows.Media.Visual._offset, and thus the next offset is 84 + 16 = 100.
Below the layout is the callstack showing the code path that creates the treeview item. From it we can see that there is a message being Dispatched to an InputFilter which does a MouseLeftButtonDown, etc.
Below the callstack is the actual memory content for this particular item.
{ Address = 0338dd3c, SeqNo = 374314, Size = 276, Thread = 17216M, Gen = 2, Moved = 2, Srviv = 3, Classid = 07650ffc, ClassName = WpfApplication1.MyTreeViewItem, NumItems = 0, _HeapAllocationContainer = Address=0x0338dd3c, SeqNo=374,314, Size=276, BlkType=ClrObject Thread=17216M WpfApplication1.MyTreeViewItem } Heap = __MemSpect
ClassId = 0x07650ffc WpfApplication1.MyTreeViewItem GCGen=2 GCMoved=2 GCSurvived=3 RootKind = Handle RootFlags = "WeakRef" RootId 0x011d3860
System.Object (no members)
4 System.Windows.Threading.DispatcherObject._dispatcher System.Windows.Threading.Dispatcher 0x031e7dd0
8 System.Windows.DependencyObject._dType System.Windows.DependencyObjectType 0x03268d0c
12 System.Windows.DependencyObject._contextStorage Object 0x00000000
16 System.Windows.DependencyObject._effectiveValues ValueType[](Count=28)(Array) 0x0338e8b8
20 System.Windows.DependencyObject._packedData U4 0x00b82015
24 System.Windows.Media.Visual._parent System.Windows.DependencyObject 0x00000000
28 System.Windows.Media.Visual._parentIndex I4 0x00000000
32 System.Windows.Media.Visual._flags ValueType 0x00000204
36 System.Windows.Media.Visual._proxy ValueType 0x00000000 0x00000000 0x00000000 0x00000000
52 System.Windows.Media.Visual._bboxSubgraph ValueType 0x00000000 0x7ff00000 0x00000000 0x7ff00000 0x00000000 0xfff00000 0x00000000 0xfff00000
84 System.Windows.Media.Visual._offset ValueType 0x00000000 0x00000000 0x00000000 0x00000000
100 System.Windows.UIElement._drawingContent System.Windows.Media.IDrawingContent 0x00000000
104 System.Windows.UIElement.MeasureRequest Request 0x00000000
108 System.Windows.UIElement.ArrangeRequest Request 0x00000000
112 System.Windows.UIElement.sizeChangedInfo System.Windows.SizeChangedInfo 0x00000000
116 System.Windows.UIElement._flags ValueType 0x000000cd
120 System.Windows.UIElement._persistId I4 0x00000000
124 System.Windows.UIElement._finalRect ValueType 0x00000000 0x00000000 0x00000000 0x00000000 0x00000000 0x00000000 0x00000000 0x00000000
156 System.Windows.UIElement._desiredSize ValueType 0x00000000 0x00000000 0x00000000 0x00000000
172 System.Windows.UIElement._previousAvailableSize ValueType 0x00000000 0x00000000 0x00000000 0x00000000
188 System.Windows.UIElement._size ValueType 0x00000000 0x00000000 0x00000000 0x00000000
204 System.Windows.FrameworkElement._themeStyleCache System.Windows.Style 0x0326cb50
208 System.Windows.FrameworkElement._styleCache System.Windows.Style 0x00000000
212 System.Windows.FrameworkElement._templatedParent System.Windows.DependencyObject 0x00000000
216 System.Windows.FrameworkElement._templateChild System.Windows.UIElement 0x00000000
220 System.Windows.FrameworkElement._parent WpfApplication1.MyTreeViewItem(System.Windows.DependencyObject) 0x0338d6b8
224 System.Windows.FrameworkElement._inheritableProperties MS.Utility.FrugalObjectList`1 0x00000000
228 System.Windows.FrameworkElement._flags ValueType 0x00608001
232 System.Windows.FrameworkElement._flags2 ValueType 0x0880ffff
236 System.Windows.Controls.Control._templateCache System.Windows.Controls.ControlTemplate 0x0326d5c4
240 System.Windows.Controls.Control._controlBoolField ValueType 0x00000000
244 System.Windows.Controls.ItemsControl._focusedInfo ItemInfo 0x00000000
248 System.Windows.Controls.ItemsControl._items System.Windows.Controls.ItemCollection 0x00000000
252 System.Windows.Controls.ItemsControl._itemContainerGenerator System.Windows.Controls.ItemContainerGenerator 0x00000000
256 System.Windows.Controls.ItemsControl._itemsHost System.Windows.Controls.Panel 0x00000000
260 System.Windows.Controls.ItemsControl._scrollHost System.Windows.Controls.ScrollViewer 0x00000000
264 System.Windows.Controls.ItemsControl._groupStyle System.Collections.ObjectModel.ObservableCollection`1 0x0338de50
System.Windows.Controls.HeaderedItemsControl (no members)
System.Windows.Controls.TreeViewItem (no members)
268 WpfApplication1.MyTreeViewItem.k__BackingField Boolean 0x00000001
Call Stack:
c:\memspect\vsassert\stackman.cpp(1026) : MemSpectDll.dll!MyProfiler::ObjectAllocated + 86 bytes
f:\dd\ndp\clr\src\vm\eetoprofinterfaceimpl.cpp(5576) : clr.dll!EEToProfInterfaceImpl::ObjectAllocated + 87 bytes
f:\dd\ndp\clr\src\vm\proftoeeinterfaceimpl.cpp(649) : clr.dll!ProfilerObjectAllocatedCallback + 136 bytes
f:\dd\ndp\clr\src\vm\gcscan.cpp(1929) : clr.dll!AllocateObject + 265 bytes
f:\dd\ndp\clr\src\vm\jithelpers.cpp(2829) : clr.dll!JIT_New + 107 bytes
WpfApplication1.exe!WpfApplication1.MainWindow.c__DisplayClass2_0.b__0
WpfApplication1.exe!WpfApplication1.MainWindow.c__DisplayClass2_1.b__1
PresentationCore.dll!System.Windows.RoutedEventHandlerInfo.InvokeHandler
PresentationCore.dll!System.Windows.EventRoute.InvokeHandlersImpl
PresentationCore.dll!System.Windows.UIElement.RaiseEventImpl
PresentationCore.dll!System.Windows.UIElement.RaiseEvent
PresentationFramework.dll!System.Windows.Controls.TreeViewItem.OnExpanded
PresentationFramework.dll!System.Windows.Controls.TreeViewItem.OnIsExpandedChanged
WindowsBase.dll!System.Windows.DependencyObject.OnPropertyChanged
PresentationFramework.dll!System.Windows.FrameworkElement.OnPropertyChanged
WindowsBase.dll!System.Windows.DependencyObject.NotifyPropertyChange
WindowsBase.dll!System.Windows.DependencyObject.UpdateEffectiveValue
WindowsBase.dll!System.Windows.DependencyObject.SetValueCommon
PresentationFramework.dll!MS.Internal.Data.PropertyPathWorker.SetValue
PresentationFramework.dll!MS.Internal.Data.ClrBindingWorker.UpdateValue
PresentationFramework.dll!System.Windows.Data.BindingExpression.UpdateSource
PresentationFramework.dll!System.Windows.Data.BindingExpressionBase.UpdateValue
PresentationFramework.dll!System.Windows.Data.BindingExpression.UpdateOverride
PresentationFramework.dll!System.Windows.Data.BindingExpressionBase.Update
PresentationFramework.dll!System.Windows.Data.BindingExpressionBase.ProcessDirty
PresentationFramework.dll!System.Windows.Data.BindingExpressionBase.Dirty
PresentationFramework.dll!System.Windows.Data.BindingExpressionBase.SetValue
WindowsBase.dll!System.Windows.DependencyObject.SetValueCommon
WindowsBase.dll!System.Windows.DependencyObject.SetCurrentValueInternal
PresentationFramework.dll!System.Windows.Controls.Primitives.ToggleButton.OnToggle
PresentationFramework.dll!System.Windows.Controls.Primitives.ToggleButton.OnClick
PresentationFramework.dll!System.Windows.Controls.Primitives.ButtonBase.OnMouseLeftButtonDown
PresentationCore.dll!System.Windows.UIElement.OnMouseLeftButtonDownThunk
PresentationCore.dll!System.Windows.Input.MouseButtonEventArgs.InvokeEventHandler
PresentationCore.dll!System.Windows.RoutedEventArgs.InvokeHandler
PresentationCore.dll!System.Windows.RoutedEventHandlerInfo.InvokeHandler
PresentationCore.dll!System.Windows.EventRoute.InvokeHandlersImpl
PresentationCore.dll!System.Windows.UIElement.ReRaiseEventAs
PresentationCore.dll!System.Windows.UIElement.OnMouseDownThunk
PresentationCore.dll!System.Windows.Input.MouseButtonEventArgs.InvokeEventHandler
PresentationCore.dll!System.Windows.RoutedEventArgs.InvokeHandler
PresentationCore.dll!System.Windows.RoutedEventHandlerInfo.InvokeHandler
PresentationCore.dll!System.Windows.EventRoute.InvokeHandlersImpl
PresentationCore.dll!System.Windows.UIElement.RaiseEventImpl
PresentationCore.dll!System.Windows.UIElement.RaiseTrustedEvent
PresentationCore.dll!System.Windows.UIElement.RaiseEvent
PresentationCore.dll!System.Windows.Input.InputManager.ProcessStagingArea
PresentationCore.dll!System.Windows.Input.InputManager.ProcessInput
PresentationCore.dll!System.Windows.Input.InputProviderSite.ReportInput
PresentationCore.dll!System.Windows.Interop.HwndMouseInputProvider.ReportInput
PresentationCore.dll!System.Windows.Interop.HwndMouseInputProvider.FilterMessage
PresentationCore.dll!System.Windows.Interop.HwndSource.InputFilterMessage
WindowsBase.dll!MS.Win32.HwndWrapper.WndProc
WindowsBase.dll!MS.Win32.HwndSubclass.DispatcherCallbackOperation
WindowsBase.dll!System.Windows.Threading.ExceptionWrapper.InternalRealCall
WindowsBase.dll!System.Windows.Threading.ExceptionWrapper.TryCatchWhen
WindowsBase.dll!System.Windows.Threading.Dispatcher.LegacyInvokeImpl
WindowsBase.dll!MS.Win32.HwndSubclass.SubclassWndProc
d:\blue\windows\core\ntuser\client\i386\callproc.asm(116) : USER32.dll!_InternalCallWinProc + 43 bytes
d:\blue\windows\core\ntuser\client\clmsg.c(168) : USER32.dll!UserCallWinProcCheckWow + 398 bytes
d:\blue\windows\core\ntuser\client\clmsg.c(2680) : USER32.dll!DispatchMessageWorker + 520 bytes
d:\blue\windows\core\ntuser\client\cltxt.h(1000) : USER32.dll!DispatchMessageW + 16 bytes
WindowsBase.ni.dll!0x6D79EFF4 SymErr = 0x1e7
WindowsBase.dll!System.Windows.Threading.Dispatcher.PushFrameImpl
WindowsBase.dll!System.Windows.Threading.Dispatcher.PushFrame
PresentationFramework.dll!System.Windows.Application.RunDispatcher
PresentationFramework.dll!System.Windows.Application.RunInternal
PresentationFramework.dll!System.Windows.Application.Run
PresentationFramework.dll!System.Windows.Application.Run
WpfApplication1.exe!WpfApplication1.App.Main
f:\dd\ndp\clr\src\vm\callhelpers.cpp(91) : clr.dll!CallDescrWorkerWithHandler + 107 bytes
f:\dd\ndp\clr\src\vm\callhelpers.cpp(649) : clr.dll!MethodDescCallSite::CallTargetWorker + 344 bytes
f:\dd\ndp\clr\src\vm\assembly.cpp(2605) : clr.dll!RunMain + 426 bytes
f:\dd\ndp\clr\src\vm\assembly.cpp(2719) : clr.dll!Assembly::ExecuteMainMethod + 292 bytes
f:\dd\ndp\clr\src\vm\appdomain.cpp(3739) : clr.dll!SystemDomain::ExecuteMainMethod + 1617 bytes
f:\dd\ndp\clr\src\vm\ceemain.cpp(3018) : clr.dll!ExecuteEXE + 76 bytes
f:\dd\ndp\clr\src\vm\ceemain.cpp(2850) : clr.dll!_CorExeMainInternal + 220 bytes
f:\dd\ndp\clr\src\vm\ceemain.cpp(2782) : clr.dll!_CorExeMain + 77 bytes
f:\dd\ndp\clr\src\dlls\shim\shim.cpp(6420) : mscoreei.dll!_CorExeMain + 266 bytes
d:\wbrtm\com\netfx\windowsbuilt\shell_shim\v2api.cpp(1222) : MSCOREE.DLL!_CorExeMain_Exported + 140 bytes
d:\9147\base\win32\client\thread.c(78) : KERNEL32.dll!BaseThreadInitThunk + 36 bytes
d:\blue\minkernel\ntdll\rtlstrt.c(1029) : ntdll.dll!__RtlUserThreadStart + 47 bytes
d:\blue\minkernel\ntdll\rtlstrt.c(944) : ntdll.dll!_RtlUserThreadStart + 27 bytes
0338dd38 : 00000000 07650ffc 031e7dd0 03268d0c 00000000 0338e8b8 00b82015 00000000 00 00 00 00 fc 0f 65 07 d0 7d 1e 03 0c 8d 26 03 00 00 00 00 b8 e8 38 03 15 20 b8 00 00 00 00 00 e } & 8
0338dd58 : 00000000 00000204 00000000 00000000 00000000 00000000 00000000 7ff00000 00 00 00 00 04 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 f0 7f
0338dd78 : 00000000 7ff00000 00000000 fff00000 00000000 fff00000 00000000 00000000 00 00 00 00 00 00 f0 7f 00 00 00 00 00 00 f0 ff 00 00 00 00 00 00 f0 ff 00 00 00 00 00 00 00 00
0338dd98 : 00000000 00000000 00000000 00000000 00000000 00000000 000000cd 00000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 cd 00 00 00 00 00 00 00
0338ddb8 : 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0338ddd8 : 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0338ddf8 : 00000000 00000000 00000000 00000000 0326cb50 00000000 00000000 00000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 50 cb 26 03 00 00 00 00 00 00 00 00 00 00 00 00 P &
0338de18 : 0338d6b8 00000000 00608001 0880ffff 0326d5c4 00000000 00000000 00000000 b8 d6 38 03 00 00 00 00 01 80 60 00 ff ff 80 08 c4 d5 26 03 00 00 00 00 00 00 00 00 00 00 00 00 8 ` &
0338de38 : 00000000 00000000 00000000 0338de50 00000001 00 00 00 00 00 00 00 00 00 00 00 00 50 de 38 03 01 00 00 00 P 8
Below is some sample code:
1. If you run the “FillTreeViewWithFakeData” code, it will just blindly generate huge numbers of nodes. Try changing the NumItemsPerDepth and MaxDepth values and watch how quickly you consume memory
2. The “FillTreeViewWithDynamicallyGeneratedData” uses your disk drive as a default source of hierarchical data and behaves much as File Explorer does. As you navigate nodes, they are generated.
a. If you run with “USEBIGDUMMY” defined, then the nodes that are expandable (the leaf nodes) will have a child MyTreeViewItem with _IsDummy = True.
b. If you comment out the ”USEBIGDUMMY” definition, then the leaf nodes are marked with a child = TRUE, saving memory
See also Create your own CLR Profiler
<code>
// Start VS.
// File->New->Project->C# WPF Application
// Replace MainWindow.xaml.cs with this code
// comment out this definition of USEBIGDUMMY to use less memory
#define USEBIGDUMMY
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Media;
namespace WpfApplication1
{
class MyTreeViewItem : TreeViewItem
{
#if USEBIGDUMMY
// an item with a dummy child means we haven't expanded the children yet
// the dummy child is just a placeholder, allowing the UI to show the node is expandable
public bool _IsDummy { get; set; }
public MyTreeViewItem(bool IsDummy = false)
{
_IsDummy = IsDummy;
}
#endif //USEBIGDUMMY
}
public partial class MainWindow : Window
{
public MainWindow()
{
InitializeComponent();
this.Loaded += MainWindow_Loaded;
}
void FillTreeViewWithFakeData(ItemsControl nodeParent)
{
int NumItemsPerDepth = 10;
int maxDepth = 5;
/*
* This is an example of prefilling an entire treeview
* with a huge amount of data. This is very inefficient.
* The # of items is NumItemsPerDepth ^ 5 = 10000
*
*/
Action<ItemsControl, string, int> action = null; // recursive lambda
action = (parent, partName, depth) =>
{
if (depth == maxDepth)
{
return;
}
for (int i = 0; i < NumItemsPerDepth; i++)
{
var child = new MyTreeViewItem()
{
Header = $"{partName}{i}"
};
parent.Items.Add(child);
action(child, $"{partName}{i}", depth + 1);
child.IsExpanded = true;
}
};
action(nodeParent, "item", 1);
}
void FillTreeViewWithDynamicallyGeneratedData(TreeView tv)
{
// this will create a treeview showing only the top level
// items. Upon expansion, nodes are generated
var pathRoot = new DirectoryInfo(@"c:\");
var rootNode = new MyTreeViewItem()
{
Header = pathRoot,
Tag = pathRoot // we'll store the DirectoryInfo in the Tag
};
#if USEBIGDUMMY
rootNode.Items.Add(new MyTreeViewItem(IsDummy: true));
#else
rootNode.Items.Add(true);
#endif //USEBIGDUMMY
Action<MyTreeViewItem> lambdaExpand = null; //recursive lambda
lambdaExpand = (nodeParent) =>
{
if (nodeParent.Items.Count == 1 &&
#if USEBIGDUMMY
((MyTreeViewItem)nodeParent.Items[0])._IsDummy
#else
(nodeParent.Items[0] as MyTreeViewItem == null)
#endif //USEBIGDUMMY
)
{
nodeParent.Items.Clear();//remove dummy item
// calculate child nodes
var dirInfo = (DirectoryInfo)nodeParent.Tag;
// let's get all file and dir info into an enumerable
var lstEntries =
from entry in dirInfo.EnumerateFileSystemInfos
("*.*", SearchOption.TopDirectoryOnly)
// let's sort: directories first, then files
orderby ((entry.Attributes & FileAttributes.Directory) != 0 ? "0" : "1")
+ entry.Name
select entry;
foreach (var finfo in lstEntries)
{
var sp = new StackPanel()
{
Orientation = Orientation.Horizontal
};
sp.Children.Add(new TextBlock()
{
Text = finfo.Name
});
sp.Children.Add(new TextBlock()
{
Text = finfo.CreationTime.ToString(),
Margin = new Thickness(10, 0, 0, 0),
Foreground = Brushes.Blue
});
var nodeChild = new MyTreeViewItem()
{
Tag = finfo,
Header = sp
};
// only dirs are expandable
if ((finfo.Attributes & FileAttributes.Directory) != 0)
{
#if USEBIGDUMMY
nodeChild.Items.Add(new MyTreeViewItem(IsDummy: true));
#else
childItem.Items.Add(true);
#endif //USEBIGDUMMY
nodeChild.Expanded += (oe, ee) =>
{
lambdaExpand(nodeChild); //recur
};
}
else
{
// only files have length and can be double clicked
sp.Children.Add(new TextBlock()
{
Text = ((FileInfo)finfo).Length.ToString("n0"),
Margin = new Thickness(10, 0, 0, 0),
Foreground = Brushes.Green
});
nodeChild.MouseDoubleClick += (od, ed) =>
{
try
{
Process.Start(((FileInfo)nodeChild.Tag).FullName);
}
catch (Exception ex)
{
MessageBox.Show(ex.Message);
}
};
}
nodeChild.ToolTip = finfo.FullName;
nodeParent.Items.Add(nodeChild);
}
}
};
tv.Items.Add(rootNode);
lambdaExpand(rootNode);
rootNode.IsExpanded = true;
}
private void MainWindow_Loaded(object sender, RoutedEventArgs e)
{
try
{
this.WindowState = WindowState.Maximized;
var tv = new TreeView();
this.Content = tv;
//FillTreeViewWithFakeData(tv);
//return;
FillTreeViewWithDynamicallyGeneratedData(tv);
}
catch (Exception ex)
{
this.Content = ex.ToString();
}
}
}
}
</code>