Current version

v1.10.4 (stable)

Navigation

Main page
Archived news
Downloads
Documentation
   Capture
   Compiling
   Processing
   Crashes
Features
Filters
Plugin SDK
Knowledge base
Donate
Contact info
Forum
 
Other projects
   Altirra

Search

Archives

01 Dec - 31 Dec 2013
01 Oct - 31 Oct 2013
01 Aug - 31 Aug 2013
01 May - 31 May 2013
01 Mar - 31 Mar 2013
01 Feb - 29 Feb 2013
01 Dec - 31 Dec 2012
01 Nov - 30 Nov 2012
01 Oct - 31 Oct 2012
01 Sep - 30 Sep 2012
01 Aug - 31 Aug 2012
01 June - 30 June 2012
01 May - 31 May 2012
01 Apr - 30 Apr 2012
01 Dec - 31 Dec 2011
01 Nov - 30 Nov 2011
01 Oct - 31 Oct 2011
01 Sep - 30 Sep 2011
01 Aug - 31 Aug 2011
01 Jul - 31 Jul 2011
01 June - 30 June 2011
01 May - 31 May 2011
01 Apr - 30 Apr 2011
01 Mar - 31 Mar 2011
01 Feb - 29 Feb 2011
01 Jan - 31 Jan 2011
01 Dec - 31 Dec 2010
01 Nov - 30 Nov 2010
01 Oct - 31 Oct 2010
01 Sep - 30 Sep 2010
01 Aug - 31 Aug 2010
01 Jul - 31 Jul 2010
01 June - 30 June 2010
01 May - 31 May 2010
01 Apr - 30 Apr 2010
01 Mar - 31 Mar 2010
01 Feb - 29 Feb 2010
01 Jan - 31 Jan 2010
01 Dec - 31 Dec 2009
01 Nov - 30 Nov 2009
01 Oct - 31 Oct 2009
01 Sep - 30 Sep 2009
01 Aug - 31 Aug 2009
01 Jul - 31 Jul 2009
01 June - 30 June 2009
01 May - 31 May 2009
01 Apr - 30 Apr 2009
01 Mar - 31 Mar 2009
01 Feb - 29 Feb 2009
01 Jan - 31 Jan 2009
01 Dec - 31 Dec 2008
01 Nov - 30 Nov 2008
01 Oct - 31 Oct 2008
01 Sep - 30 Sep 2008
01 Aug - 31 Aug 2008
01 Jul - 31 Jul 2008
01 June - 30 June 2008
01 May - 31 May 2008
01 Apr - 30 Apr 2008
01 Mar - 31 Mar 2008
01 Feb - 29 Feb 2008
01 Jan - 31 Jan 2008
01 Dec - 31 Dec 2007
01 Nov - 30 Nov 2007
01 Oct - 31 Oct 2007
01 Sep - 30 Sep 2007
01 Aug - 31 Aug 2007
01 Jul - 31 Jul 2007
01 June - 30 June 2007
01 May - 31 May 2007
01 Apr - 30 Apr 2007
01 Mar - 31 Mar 2007
01 Feb - 29 Feb 2007
01 Jan - 31 Jan 2007
01 Dec - 31 Dec 2006
01 Nov - 30 Nov 2006
01 Oct - 31 Oct 2006
01 Sep - 30 Sep 2006
01 Aug - 31 Aug 2006
01 Jul - 31 Jul 2006
01 June - 30 June 2006
01 May - 31 May 2006
01 Apr - 30 Apr 2006
01 Mar - 31 Mar 2006
01 Feb - 29 Feb 2006
01 Jan - 31 Jan 2006
01 Dec - 31 Dec 2005
01 Nov - 30 Nov 2005
01 Oct - 31 Oct 2005
01 Sep - 30 Sep 2005
01 Aug - 31 Aug 2005
01 Jul - 31 Jul 2005
01 June - 30 June 2005
01 May - 31 May 2005
01 Apr - 30 Apr 2005
01 Mar - 31 Mar 2005
01 Feb - 29 Feb 2005
01 Jan - 31 Jan 2005
01 Dec - 31 Dec 2004
01 Nov - 30 Nov 2004
01 Oct - 31 Oct 2004
01 Sep - 30 Sep 2004
01 Aug - 31 Aug 2004

Stuff

Powered by Pivot  
XML: RSS feed 
XML: Atom feed 

§ 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:

ExtTextOut() performance chart

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.

Comments

Comments posted:


it always feels good to replace some crappy 3thr party component with a custom one that is well written. i hope the new treeview will be factored enough that the community can rip it out and reuse it somewhere else. you are not the only one that is a bit angry about some of the common controls.

major - 05 05 09 - 04:19


I'm afraid it's a bit hardcoded at the moment, particularly since I don't have too many occasions to use a tree view. I usually end up using list views more often. It's also missing a substantial amount of functionality; it took a while just to get basic keyboard actions working.

The main problem with making any sort of reusable UI widget library in C++ is that it tends to turn in a whole framework that begins consuming everything in its path. It's one of the reasons I've shied away from using something like wxWindows or Qt -- you're not just taking a UI library, you're also taking on lots of other stuff like an I/O layer, container library, regex engine, threading system....

Phaeron - 05 05 09 - 07:03


Is using something like Qt or wxWidgets really such a bad thing though? Wouldn't it make it easier to maintain overall if you used the framework API over the core OS API whenever possible?

King InuYasha (link) - 05 05 09 - 08:35


"That's almost as slow as the .NET DataGridView control. "

I assume you mean in non-virtual mode, though 200 lines in that mode should display faster than 4 seconds either way.

Also QT just went LGPL, which may be more up your alley. I know a lot of C++ guys are really into QT.

Trimbo (link) - 05 05 09 - 11:28


I already have my own framework at this point, so adding another one wouldn't be productive. Fortunately, file I/O APIs don't change often.

DataGridView is also slow due to text rendering, but apparently for a different reason: it spends a ton of time in surface locks, presumably due to mixing GDI and GDI+ rendering. And no, I'm not kidding about the four seconds. Get a fairly dense grid like what you'd see on a spreadsheet, and on a 1920x1200 display you really can see it paint down the screen. I once tried to write a quick modding tool using it and I gave up because it was so slow as to be useless.

Phaeron - 05 05 09 - 16:16


AFAIK, both wxWidgets and Qt are normally compiled in a form where you can cherry pick which parts of the framework you actually want to use. For example, Qt4 has the Qt4Gui.dll file for the UI rendering, and it also has the phonon.dll for sound. wxWidgets optionally can be monolithic, but by default I believe it splits itself.

King InuYasha (link) - 05 05 09 - 18:26


I took on your Datagridview challenge just now. Made a .NET Forms app that displays 400K cells (400 columns, 1K rows). The Datagridview is in virtual mode and using an Lorem Ipsum generator I wrote to continually generate text for the cells. Then double-clicked to enlarge the window and counted to see how long it took to repaint (sorry, I was too lazy to subclass and do OnPaint override).

With 5,561 full cells on screen @ 2560x1600: barely 4 seconds (I'm on "4-onethou" of the "4-onethousand").

With the far more reasonable 1,675 cells on screen: 2 seconds.

While I agree that text rendering in .NET is slow due to no hardware acceleration, I fear your "almost as slow" measurement is off here and DataGridView is getting a slightly bad wrap.

That said, bring on WPF.

Trimbo (link) - 07 05 09 - 23:21


Let me get this straight. You have a modern machine with an accelerated graphics card and a JITted execution environment, with an application that is simply drawing a grid with text, and you don't see a problem with it taking FOUR SECONDS to repaint? Try scrolling between rows or moving columns, and you'll see why that turns into a usability issue. Could you imagine using Microsoft Excel if it were that slow to update?

The problem isn't just software rendering, by the way -- you could easily software render that in 1/4th of a second or less. The problem is that .NET is mixing both hardware and software rendering and thus spending a ton of time waiting on surface locks.

Phaeron - 07 05 09 - 23:35


"and you don't see a problem with it taking FOUR SECONDS to repaint"

4 seconds for 5,561 cells of random, ever changing data on a massive screen... I'm not saying it's good, I'm saying that it's better than your ExtTextOut performance. :p

Trimbo (link) - 08 05 09 - 01:09


> I'm saying that it's better than your ExtTextOut performance.

How does the DataGridView perform with control characters? :)

Phaeron - 08 05 09 - 02:02


I'd be curious about whether double buffering that datagridview helps performance any. I had to do that in an app, because computers with older NVIDIA drivers would paint the grid at a rate of about 1 row per second - and it was a very simple one, too.

Matt - 15 05 09 - 02:54


You know, it probably would. I seem to recall there was some annoyance with setting double buffering on it, though, like you had to subclass it because the required method was protected. It would run pretty badly on Remote Desktop, though, unless WinForms was smart enough to auto-disable it.

Phaeron - 15 05 09 - 16:57

Comment form


Please keep comments on-topic for this entry. If you have unrelated comments about VirtualDub, the forum is a better place to post them.
Name:  
Remember personal info?

Email (Optional):
Your email address is only revealed to the blog owner and is not shown to the public.
URL (Optional):
Comment: /

An authentication dialog may appear when you click Post Comment. Simply type in "post" as the user and "now" as the password. I have had to do this to stop automated comment spam.



Small print: All html tags except <b> and <i> will be removed from your comment. You can make links by just typing the url or mail-address.