Introduction
This article reviews different types of display APIs in WPF. We define a problem statement that shows why the currently available Tree Map control [4] has performance limitations that can raise problems in a disk space usage tool called Space Navigator. We use the case of the Space Navigator application to compare different APIs in WPF. This comparison is focused on performance using test applications that are available for download.
The article and attached source code gives sample implementations for the following WPF technologies and concepts:
- ZoomableCanvas,
- WriteableBitmaps, and
- Drawing Geometry.
Sample codes and projects on these technologies are not widely available and should, therefore, for others, be interesting.
Background
The Space Navigator application displays usage information about the size of each directory on each drive in the Windows file system. This information can be used to analyze and optimize storage space since the usage information is aggregated towards the root (eg.: 'C:\') and can be inspected in detail via drill down from top to bottom.
The Space Navigator application kicked off the evaluation presented in this article. We therefore, explore the attached prototype to set the stage and come back to this when we evaluate each alternative solution in turn.
Space Navigator
A standard approach for displaying space usage in a chart control is the Squarified Tree Map [2], which displays the space usage distribution of a file system. The basic idea of tree maps is to display the size of each directory with a rectangle that approximates a square and has a UI area (width*height) that corresponds in a relative way to the size of all other items shown in the display. A typical output of the Space Navigator prototype looks like this:
The above screenshot shows the contents of a Recycle Bin using the tree map control from the referenced project [4] at GitHub: dotnetprojects/WpfToolkit. We can see through the tool tip on the left side (over the tree view item [3]) that the Recycle Bin contains about 7.33 Gb of data. The structure break down of this data is visible in the tree view below the $RecycleBin folder, while a size corresponding breakdown is visible in the Tree Map on the right side of the screenshot.
You can download the attached source code for this prototype to review the contents of your file system in terms of their required space usage. The application should start to analyse the directory size of the current Windows user on first start-up and you might be surprised to see how much space is usually wasted in some hidden temp folders somewhere deep down in the file system structure. The Windows user's directory is visible in the top-left Quick Access area (review tool tip to see full path) and should also be shown below the Computer node in the tree view.
We can use the tree view to select an alternative directory to display its space usage (expander in tree view is not implemented, yet). The context menu can also be used on the tree view (left) to open a directory in the Windows Explorer.
This prototype is already quit useful considering that it took me only a couple of days to get things from here and there [4], - plug them together and get something running. We will, however, be surprised, if we try to analyse a directory that contains a large number (eg.: 16,000) of direct sub-directories. This large number of direct sub-directories causes the tree map control to attempt to layout and display, for example, 16,000 controls as defined at Views/SpaceInfoView.xaml. I encountered 16,910 sub-directories in my Windows/WinSxS folder and I would like to show a tree map screenshot of it, but I cannot do it with the above control, because the WPF application freezes when asked to layout and display too many controls (and too many depends on the configuration of the actual system).
I was able to verify the cause of the problem by limiting the foreach loop in the BuildTreeMapTree method in Components\TreeMapLib\TreeMap.cs which in turn will limit the items being layout in the overall tree map. Another way of verifying the actual cause of the freeze is to change the templated visuals to display only borders. This barely worked on my system (the application was quit slow) and produced the following screenshot with the 16,910 sub-directories in the WinSxS folder:
Both of the above attempts to work around the freeze, plus timings, plus more background information convinced me that we are looking at a not so well known limit of WPF. This limitation is on the actual number of controls that WPF can layout and display at any given time. The author of the ZoomableCanvas control, Keal Rowen, has blogged about this in 2010 [5] stating:
WPF can only handle between about 1,000 to 10,000 primitives on the screen while still remaining responsive, depending on your CPU and graphics card. 10,000 primitives isn’t a lot when you realize that even our simple shapes use 5 primitives each (you can use Snoop to see why).
This information enabled me to understand that I can either:
- Limit the number of controls being displayed in the tree map control or
- Search for a faster solution that could display more rectangles at any given time. Ideally, drawing rectangles would be comparable to GDI+ performance, but based on WPF. The required performance should be fast enough that nobody ever hits a limit feeding too many sub-directories into the application.
The remainder of this article is focused on the search for more efficient ways to render the above information.
Technical Details
The Space Navigator prototype contains 4 projects:
- SpaceNavigator (the main executable project)
- TreeMapLib (a version of the Tree Map chart control from here [4])
- FolderTreeViewLib (contains a tree view viewmodel implementation [3])
- FolderTreeModelsLib (contains the tree structured model than can be serialized [7])
- and 5th noteworthy component, the TreeLib, which is added via Nuget.
The application start-up is performed through the code in SpaceNavigator/Views/MainWindow.cs. The MainView.xaml contains the definition of the file system tree view, the GridSplitter, and a ContentPresenter (at about line 381) which is bound to a SelectedPage property in the AppViewModel class. The resources section of the Grid in which the ContentPresenter is defined contains 3 DataTemplates for the different views that are used in dependence of the currently selected tree view item (see also code in the AppViewModel class).
The algorithm for aggregating the size of each directory should become clear, if we review the Level-Order and Post-Order traversal algorithms mentioned here [6] with the code in the LoadPathModels method in the AppViewModel class:
public List<IItem> LoadPathModels(IPathItem pathItem)
{
List<IItem> itemsRoot = null;
if (pathItem == null)
return null;
using (var res = new CrawlPathItemResult())
{
var Order = new LevelOrder<CrawlPathItemResult, DirectoryInfo>();
Order.Traverse(new DirectoryInfo(pathItem.Path)
, i => i.GetDirectories()
, res
, res.ComputeDirSize
, i => { }
, (i, exc, j) =>
{
return i;
}
);
itemsRoot = res.Children;
if (itemsRoot == null)
return null;
using (var resTotal = new CrawlPathItemResult())
{
var PostOrder = new PostOrder<CrawlPathItemResult, IItem>();
PostOrder.Traverse(itemsRoot.First()
, i => i.Children
, resTotal
, resTotal.ComputeTotalDirSize
, i => { }
, (i, exc, j) =>
{
return i;
}
);
}
return itemsRoot;
}
}
This approach implements 2 passes. The first pass is top down and collects all information with regard to number of files (their size) and directories for each directory. The second pass is bottom-up (or post order) and is implemented to aggregate the values, collected in the first pass, towards the root.
The heart of the tree view implementation, which is also a data source of the data displayed in the TreeMap control, is the viewmodel in the FolderTreeViewLib project::
The PathModel and FSItemType on the right side of the diagram are used to interact directly with the file system, while everything else is designed to drive the tree view and, for the selected element, the Tree Map control.
A SpaceItemViewModel is in this context anything that can have a size of bytes in the file system. That's a drive or folder in our limited view of the file system reality. All other items complete the tree view implementation.
I hope this short overview gives everyone a good understanding of how the prototype works. The other prototypes are designed very similar but slightly different when it comes to the TreeMap control implementation. Please do use the forum below, if you have questions about any of the attached prototypes.
ZoomableCanvas
The attached test application SpaceNavigator_Test_ZoomableCanvas.zip loads its test data from an Xml file instead of the file system, because I wanted to concentrate on the performance issue in the tree map chart control instead of having to re-build the complete prototype for each development/test step. The project includes, thus, an Xml resource in the BusinessLib project at Testing\BusinessLib\Resources\DataExport_Small.zip. This Xml file contains the directory space usage information that was drawn from the previously mentioned Windows/WinSxS folder. Using this Xml file enables us to simulate the file system as a data source and we can also look at each case with the same test data.
The test application screen is initially empty, but you should see something similar to the above screenshot after clicking the Analyze button. Loading the complete view took about 2 minutes on my system, which is not a bad improvement since we went from a frozen screen to slow performance. But we have to note that screen updates are rather slow when resizing or zooming the window with Ctrl + Mouse Wheel (dragging canvas with left mouse click should also work).
This test was possible, because Keal Rowen has done quit a bit of research and coding to come up with a virtualized canvas that can load and display 1 million items [5]. He states in his blog entries that the ZoomableCanvas can display 1 million items, only:
- if the user either zooms far enough into the space to see only parts of the collection or
- if the user zooms far enough away, such that items that are too small, are skipped for drawing (which is not implemented here).
These restrictions form an important part of the reason why the ZoomableCanvas is not useful to display tree maps out-of-the-box. The point of a tree map is that we can have an overview over the relative size of all items in a given directory. Therefore, this approach would only work, if we could come up with a clever way of rendering the overview in the above screenshot in one control, and then switch to displaying individual controls, when the zoom level is far enough into the view.
Technical Details
The ZoomableCanvas prototype consists of the following components:
- SpaceNaviZCTest (the main executable project)
- ZoomableCanvasLib (a version of the Zoomable Canvas [5])
- FolderTreeViewLib (contains a tree view viewmodel implementation [3])
- FolderTreeModelsLib (contains the tree structured model than can be serialized [7])
- BusinessLib (contains the serialized Xml file resource [7])
The implementation of the ZoomableCanvas prototype also comes to life through the MainWindow_Loaded method. This is where loading the Xml data is initialized.
The user can then click the Analyze button to actually bind the canvas to some useful information. The corresponding command is, as usual, implemented in the AnaylzeCommand property of the AppViewModel class. This command adjusts the DataItems property, which is bound to the ItemsSource of the ZoomableCanvas (in the TreeMapChart) control. The DataItems property is implemented through the GridLikeItemsSource class which is an advanced development from Keal Rowen's original blog post on that class.
We note that the the RealizationLimit property in the ZoomableCanvas control in SpaceNaviZCTest\Controls\TreeMapChart.xaml was adjusted to display the controls for the mentioned 16,910 sub-directories:
<zc:ZoomableCanvas behav:MouseWheelChangedBehavior.ChangedCommand="{Binding MouseWheelChangedCommand}"
behav:MouseDoubleClick.ChangedCommand="{Binding MouseDoubleClickCommand}"
behav:MouseMoveChangedBehavior.ChangedCommand="{Binding MouseMovedCommand}"
RealizationLimit="20000"
RealizationRate="10"
RealizationPriority="Input"
ApplyTransform="False"
Background="Transparent"
SnapsToDevicePixels="True"
Scale="{Binding Scale,Mode=TwoWay,UpdateSourceTrigger=PropertyChanged}"
Offset="{Binding Offset,Mode=TwoWay,UpdateSourceTrigger=PropertyChanged}"
/>
This setting overcomes the previously mentioned limitation [5] for the test data we are using here. But the resulting experience is bad enough to not recommend a ZoomableCanvas solution for an out-of-the-box type of application. What we really need is a type and level of API that is, performance-wise, comparable to GDI+ in WinForms. So, lets leave the standard way of binding and displaying templated controls in WPF and review a different API in the next section.
Drawing Geometry
The solutions in the previous sections have shed some light on using WPF in a way that it should be used in 90 percent of all implementations - through Binding, ItemControls, and Templating. Instead of working with the standard high-level API we are also free to look into WPF's sub-systems to determine alternative solutions. One such alternative is a Drawing Geometry approach [8] in which we can define a custom FrameworkElement that is bound to a similar property as the ItemsSource in the previous section. This time however, we are not going to populate a new control for each item, but we will draw an Rectangle per item into the canvas of the one custom FrameworkElement.
This solution is potentially more efficient since WPF no longer has to keep track of something like 16,000 instantiated controls and we can use additional index structures, like a QuadTree, if we which to interact with a rectangle when the user clicks on it or hovers the mouse over it.
The screenshot above shows the rendering of the TreeMapChart control with the previously mentioned test data. The actual rendering algorithm is implemented in the GetGeometry method and we note, a small optimization, which is that rectangles smaller than 4 pixels are not rendered here. We can also see that the rendering depends on the _TreeMapRootNodes field, which is updated only when and if the data in the bound DisplayItem property has changed.
The above observation is important because we can better value the performance that we see when the window is changed (resized or minimized, maximized). This performance is still slow on my system since the window update takes about a second or so. Nevertheless, this is progress, if we remember that we compare this case to a frozen screen scenario.
Technical Details
The Drawing Geometry prototype consists of the following components:
- SpaceNavigatorTest (the main executable project)
- FolderTreeViewLib (contains a tree view viewmodel implementation [3])
- FolderTreeModelsLib (contains the tree structured model than can be serialized [7])
- BusinessLib (contains the serialized Xml file resource [7])
The overall set-up is very similar to the previously discussed prototype, so, we will not review these details again. A worthwhile detail to mention, however, is that the drawing objects should be freezable and frozen to get an optimal performance. Please let me know if you see other "obvious" ways of getting an even better performance for this prototype.
WriteableBitmap
The prototype in the last section was already on an exotic low level of working with the rendering system in WPF. In this section we are going one level deeper since performance results for drawing were all but sufficient. The lowest level (I know) to visit is the WriteableBitmap class [9]. The WriteableBitmap class provides a similar view as the WPF Image control that is used to view the contents of an image (JPEG, PNG etc) with the difference that a WriteableBitmap can be changed on a Pixel by Pixel base.
The required low level of coding is normally not available to many WPF developers because it really requires programming on a bit level inside of bitmaps that can by very large. The advantage of this low level programming (which feels like doing Assembler in C#) is that it is extremely fast, because the data is already formatted such that it can be consumed without much translation by the accelerated graphics system.
The WPF sub-system does not directly provide a way for drawing a line inside a WriteableBitmap. But there is an open source project teichgraf/WriteableBitmapEx on GitHub which does provide this functionality with a similar API as GDI+ in WinForms.
The screenshot above shows the output of the WriteableBitmap prototype. We note that the output appears instantaneous and does not seem to be a performance problem in any way. The structure of the prototype is almost identical to the components, described in the previou section, and we not that the Draw method in the TreeMapChart class really draws all rectangles, even those that are so small that there hardly visible. Its also worth to mention that this prototype actually draws at least twice as many items (if not more) as any of the other prototypes since it does not only draw filled rectangles but also draws a border for each tile.
The above observation is important, because it hints how much faster the WriteableBitmap solution is in comparison to all other solutions considered so far. I am happy with this performance and will definitely go with the WriteableBitmap to implement the Space Navigator application. This will, of course, have an impact on the restricted XAML development since the solution is more back to the roots in the sense that I have to implement some basic things like mouse overs and click events on my own - but I am happy to do it since the visual is that much faster in this way.
Conclusions
The WriteableBitmap clearly leaves everything else behind when it comes to implementing fast drawing algorithms. Its by far the fastest way of drawing in WPF until someone finds a faster one. The other approaches, are more or less similar in speed and the ZoomableCanvas can only be advantages, if items that are fare enough away, are drawn without all their details.
This article shows 4 different ways of implementing a Tree Map chart control with focus on performance since this is the one requirement that determines life or death when it comes to developing a data driven visual solution. I was not able to find too many solutions that show how a Tree Map can be implemented in WPF. It turns out that the Squarified Tree Map algorithm requires only the SquaringAlgorithm class provided in each sample, while everything else is just visual candy or backend data plumbing.
It is difficult to describe slow in comparison to fast, such that everyone can get an understanding what it really means, because numbers cannot express everything. Please download and execute the attached solutions to get a feeling of this.
The above comparisons were possible, because the MVVM pattern with the binding properties approach is simple enough to just plug-in a different solution. Hopefully, we can use this article as a reference in the future since I really do not know of any such thing anywhere on the Internet.
The attached solutions should be interesting for anyone who starts to look into the ZoomableCanvas, Drawing Geometry, or WriteableBitmap.
References
