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 

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

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.

Comments

Comments posted:


That reminds me of a certain large company's mainframe using Bubble sort for file names in its CD-ROM FS (what directory handling code was doing in the CD-ROM driver is also a good question). Inserting a CD with 10000+ files in a single directory froze the mainframe for over 12 hours. The code had previously been tested with no more than 10 filenames.

I like the fact that the C++ STL is very upfront about the complexity of the operations, it helps prevent idiotic situations.

Stefan - 02 02 08 - 22:49


it doesnt occur to me why the treeview doesnt simply keep a pointer to the last element. probably 99% of the time the tree view is filled sequentially. i personally also had trouble with the list controls which become unusable when inserting a large number of items because of initialization cost. scrolling through the data is fast though (because it is O(N)). i will ocassionally try your solution.

Tobias Rieper - 03 02 08 - 08:04


There are "hidden treasures" everywhere on the Microsoft Windows platform. It is the only platform I know where qsort() calls the compare function twice for two equal entries of a list to figure out which one is greater...

Martin - 06 02 08 - 16:39


I normally think of O(N) and O(N log(N)) as the same, since log(N) is usually a relatively small constant for typical N. Often a simple O(N log N) algorithm will be faster on average than a complicated O(N) algorithm.

Landrew - 09 02 08 - 02:43

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.