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>

Comments (0)

Skip to main content