¶The hidden danger of the Win32 TreeView
Random performance anecdote time.
I once had a bug filed on VirtualDub regarding a performance problem in its hex viewer on large files. (I have a habit of putting random features into my open-source tools; it never ceases to amaze me that people actually use them.) The problem turned out to be in a code fragment like this:
while(GetNextChunk(chunkInfo)) {
TVINSERTSTRUCT tvItem;
CreateTreeViewItem(tvItem, chunkInfo);
TreeView_InsertItem(hwndTV, tvItem);
}I had expected that I'd done something stupid in the hex viewer code. When I profiled the routine under VTune revealed that for large files, though, I discovered that this routine was spending almost no time in VirtualDub.exe itself -- it was spending a huge amount of time in the TreeView_InsertItem() call. This is a call to the Win32 tree view control to insert an item. Investigation into the disassembly around the hotspot revealed that the Win32 tree view internally stores its nodes as a singly-linked list and adding an item to the end takes linear time according to the number of items. This meant that in order to add N items to the tree list, a total of N^2 steps were required, making the tree initialization quadratic time. In case you're not familiar with asymptotic complexity, here's my cheat sheet:
- O(1) / constant time: Wheeeeeeeee!!!!!
- O(N) / linear time: Very fast.
- O(N log N): Fairly fast, scales OK.
- O(N^2) / quadratic time: Go to lunch and hope it's done by the time you get back.
I ended up solving this problem in two ways: I changed the routine to insert items in reverse order at the beginning instead of in forward order at the end, and I split the chunk list into two levels to reduce the maximum child count within a tree node.
Scalability problems are the worst kind of performance issues to deal with because the performance effects can be drastic and the fixes dangerously invasive, i.e. rewrite. The main danger is that it's really easy to nest fairly fast operations and end up with a composite operation that is O(N^2) or worse. On more than one occasion I've seen people unnecessarily calling linear-time operations like strlen() in a loop, and that simple error ends up turning an ordinarily fast operation into a painfully slow one.