Beyond Hello World - Update 5, TreeMap Control Working, Perf Issues
CLCV V5 now has a fully working TreeMap control that zooms, supports mouse over events and looks pretty good. The regions are laid out with the Squarified TreeMap algorithm. Even better, the tree map itself scales to large numbers of nodes - easily 100's of thousands, and on my lap top, it will handle a couple of million nodes relatively well. But there are two major performance problems: 1) WPF rendering seems to be very expensive. 2) Tree Map nodes are relatively expensive in terms of memory size. This limits the number of nodes to a ~2 million. You can find a link to the source code at the end of this post.
Note - all performance numbers (number of objects, times and profile data) are gathered from my new Acer Ferrari 5000 laptop.
From a memory usage perspective the control performs acceptably for even a few hundred thousand nodes. Tens of thousands of nodes are no problem. But, it does begin to struggle with about a million, with two million being a empirical limit. A future post on this WPF version of CLCV will focus on memory optimizations and usage in detail.
For this post, I'll focus on WPF rendering performance. In summary, the primary performance issue that limits the scaling of my treemap control isn't memory or CPU time to compute or render the layout - it is actual physical rendering of the rectangles and text by WPF itself. WPF cannot keep up with more than about 750 rectangles and a small number of scaled text items.
My treemap control is pretty well optimized (there is still some work to do) - but the computational performance of the control itself is not the limiting factor. The most important aspect of my treemap implementation is that it is smart about how much work it does -limiting its computations and rendering to only the nods that are reasonably large.
When learning about treemaps, I looked at some existing code and read all the web material I could find. It looks like most implementations are pretty basic - they compute the size and location of each rectangle for the entire tree. I thought this was a bit odd. It seemed to me that it would be more efficient to only process the part of the tree that would be visible - e.g. computing and rendering tiny or invisible rectangles didn't seem like a good design decision to me.
My first implementation took the straight forward approach as well. As I suspected, for larger trees - even those with a only a few thousands nodes, computing and rendering tiny rectangles was a waste of computation and rendering time. As you can see in the image to the right, rectangles that are smaller than some limit are too small to effectively mouse over or to meaningfully discern their relative area with respect to their parent.
So, I modified both the layout code and the rendering code to stop when the area of the rectangles became less than some threshold. This worked very well both from a visual perspective and performance standpoint. It also allows the data tree to become very large as it means that neither the layout and rendering costs grow with the overall tree size as the number of nodes surpasses the number of rectangles that the algorithm decides to actually render.
Experiment: CLC V5 includes a unit test for the treemap control that allows you to control the size of the three and set the treemap parameters such as the Area Limit.
The area limit is the minimum size of the rectangles that will be rendered. Assuming there are enough nodes, the larger this number, the fewer rectangles will be visible.
From empirical testing I determined that a value of 64 works pretty well.
For trees over a one or two thousand nodes, there are usually more nodes than can be displayed. In these scenarios, the scaling limitations are inherent to WPF itself, not the layout computations, or rendering in the treemap control.
Its important to understand how the control works and when WPF actually does the visible rendering. The treemap control has two main steps: the first is the actual layout computations of the tree, and the second is the rendering of the tree. Once the control is rendered, then WPF will take the rendering data generated in the control's OnRender function and actually turn that into DirectX commands that become visible on the screen. Its this third step that is the limiting factor.
The layout computations are handled by a function called ComputeAllNodeBoundingRects. This function starts at the root node and recursively computes the size of each visible rectangle for the nodes in the tree. This function stops its recursion when it reaches nodes that have visible areas less than the Area Limit. You can experiment with area limit values using the unit test (see above). If you set the area limit to zero, then the layout computations will compute a rectangle for every node in the tree.
Computing the bounding rectangles only needs to happen when the treemap control receives a new data tree (by setting the TreeMapData property), or when the render size changes (handled by the OnRenderSizeChanged event).
When WPF determines that a control needs to be rendered, it calls the controls OnRender method. This control's OnRender method recursively paints each of the rectangles computed in ComputeAllNodeBoundingRects. It also renders the text for the root nodes and first level nodes.
Both of these functions are relatively fast - here are some statistics for the initial random tree. LQ means 'lower quartile', UQ means 'upper quartile', IQ range is the inter quartile range divided by the median value. Range is the total range (max-min) divided by the median. Times are in milliseconds.
| Count | Min | LQ | Median | Mean | UQ | Max | IQ Range % | Range % | |
| Compute | 100 | 2.6 | 2.8 | 3.0 | 3.4 | 3.4 | 7.7 | 18.4% | 171.7% |
| Render | 100 | 5.8 | 6.2 | 6.7 | 7.3 | 7.7 | 19.6 | 21.8% | 204.9% |
These times are for computing and rendering from 1,316 to 1,539 visible nodes. As you can see from the times, neither compute nor rendering times in the control itself should inhibit the control from rendering smoothly. This is especially true when the control is rendering due to events other than size changes.
But, even with the times above, the control still struggles to render - you can see this by just rolling the mouse over the control and watching the lagging mouse-over node changes, or by resizing the control. In both cases, if the control is painting more than 700 rectangles or so, then it can't keep up.
While relatively anecdotal, the CPU utilization for the control also seems on the high side. Just continually moving the mouse over the control uses considerable CPU, 70 to 80%. This is high, especially considering that my lap top has a dual core AMD Turion processor with has a WinEI rating of 4.8.
While there does seem to be some material performance and scaling issues with WPF, there is a lot to like about the programming model. I'll talk about this more in subsequent posts.
Source Code for this post: CLCV-BLOG-5.ZIP contains the source code to this post. I didn't include the data files in this zip file as they haven't changed - you can simply use the ones from CLCV-BLOG-3.ZIP.
Comments
- Anonymous
March 30, 2007
Hi there. I was just wondering when CLC would be made available on Codeplex as you stated back in December? It's ok to try this with your sample files but it would be much nicer to try it against my own projects. And many thanks for a fine series of articles.