¶When ExtTextOut() runs deathly slow
I've been writing a custom tree view control to work around a couple of serious limitations of the Win32 tree view control. The main one is that, as I've noted in the past, it has quadratic time performance if you add nodes at the end of a branch, due to unoptimized linked list usage. Typically I work around this by adding nodes in reverse at the head, which executes in linear time instead, but this time I need to incrementally extend the tree. You might think that using the hInsertAfter of TVINSERTSTRUCT would fix this, but sadly, no: the tree view control implements this too by walking the child list from the head. The only way I can think of to work around this is to use virtual text nodes and rotate the text entries while inserting dummy entries at the top, but that's hacker than I like and there are other features that are missing too (columns).
I got as far as getting the node structure set up and started on rendering, only to hit on a problem: the text rendering was slooooowwww. Specifically, ExtTextOut() was taking a long time to run, and display updates were below 10 fps. Well, the problem was that due to some code transformations, I was accidentally printing out a newline (\n) at the end of the string, and that somehow causes ExtTextOut() to drop to an extremely slow code path. To give you an idea of just how horribly slow this is, here's a chart of ExtTextOut() performance when control characters are added:
This chart shows how long it takes to execute 200 calls to ExtTextOut() with a 255 character string, consisting of a mix A and ^A characters. The font is a fixed-width font, so the fill load is the same. Notice how the slope of the line increases. Notice also that when the string consisted of solely ^A characters, it took four seconds to draw 200 lines of text. That's almost as slow as the .NET DataGridView control. I omitted the line for the second text that uses Bs instead of ^As because it's so much faster it doesn't even show up, topping out at 12ms. I'm guessing this problem is caused to font substitution kicking in, but whatever's going on, it's disasterous: on this system, just including a single control character cuts text rendering rate by at least a fourth, and by the time you get to thirty control characters, it takes more than ten times longer to render the string. I should note that there definitely seems to be a system-dependent aspect here, as this was on an a 2.5GHz Core 2 with a NVIDIA Quadro NVS 140M, and the test ran a lot faster on a 1.4GHz Pentium M with an ATI RADEON Mobility. The text with control characters still ran at less than one-fourth speed, though, so it's still a really bad case.
Moral of the story: make sure ExtTextOut() receives only printable characters.