CTreeCtrl SOOO SLOW !
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 14 of 14

Thread: CTreeCtrl SOOO SLOW !

  1. #1
    Join Date
    Sep 1999
    Location
    Salisburyl UK
    Posts
    324

    CTreeCtrl SOOO SLOW !

    Hi All..
    I have an application which has a CTreeCtrl on a dialog. I need to add a large number of Items to it. It is possible that upwards of 18000 items may be added at one time. I have tested this, and even in release, this opperation can take 50 minuits or so !!!!
    This is a bit of a show stopper for me.

    My question is, why does it take so long and what can I do to speed such an opperation up (A LOT!).

    I suspect that something is searching in the TreeCtrl (for the parent Item perhaps), as the time taken to a add an Item gets progressivly slower as Items are added.

    Id realy appriciate the help of any Gurus out there who may have any idea how I can proceed!

    Many thanks
    Phill

  2. #2
    Join Date
    Jul 2005
    Posts
    767

    Re: CTreeCtrl SOOO SLOW !

    Actaully the regedit or Explorer that we use day in and out may be holding several thousands elements. So As I think one good approach would be not to dump all the 18000 or so elements at once but add/delete them on need basis, you could use the notifications TVN_ITEMEXPANDED, TVN_ITEMEXPANDING, TVN_SETDISPINFO and/or TVN_GETDISPINFO for your purpose.

    Also have a look at this.
    Last edited by MrBeans; June 12th, 2006 at 11:10 AM.

  3. #3
    Arjay's Avatar
    Arjay is online now Moderator / MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    11,220

    Re: CTreeCtrl SOOO SLOW !

    You need to use a Virtual Tree Control and handle the TVN_GETDISPINFO message. Check out the LVSelState example in the post which contains an example for a virtual list control. This example is a dialog app which displays 10,000 -> 1 million virtual list entries. The code for a tree view is very similar.

    Code that fills the virtual listview control in LVSelState example:
    Code:
    // Method: Populate
    // Purpose: Called within the Retrieve button to add items to
    // the list control.
    HRESULT Populate( CListCtrl& ctlList )
    {
    HRESULT hr = S_OK;
     
    // Add a wait cursor
    CWaitCursor wait;
     
    long lIndex = 0;
    LVITEM lvitem = { 0 };
    lvitem.mask = LVIF_TEXT | LVIF_IMAGE | LVIF_PARAM;
    int iItem = 0, iActualItem = 0;
     
    // Lock the List Control window so it doesn't look
    // like crap while filling
    ctlList.LockWindowUpdate();
     
    // Lock the list
    CAutoLockT< CLVItemDataList > lock( &m_LVItemDataList );
     
    // Cycle through the list and add each item into the list control
    for(CLVItemDataList::iterator it = m_LVItemDataList.begin();
    	it < m_LVItemDataList.end();
    	it++)
    {
    	CLVItemData* pLVItemData = (*it);
    	lvitem.iItem = iItem;
    	lvitem.iSubItem = 0;
    	lvitem.lParam = reinterpret_cast<LPARAM>(pLVItemData);
     
    	// Tell the list control to become 'Virtual' and request display
    	// data from the lvitem.lParam.
    	// See CLVSelStateDlg::OnLvnGetdispinfoList for where this happens
    lvitem.iImage = I_IMAGECALLBACK;
    	lvitem.pszText = LPSTR_TEXTCALLBACK;
    	lvitem.cchTextMax = MAX_LVITEMLEN;
     
    	// Insert the item
    ctlList.InsertItem(&lvitem);
     
    	// Set the text for each column (all virtual callbacks)
    ctlList.SetItemText(iItem, 0, LPSTR_TEXTCALLBACK);
    	ctlList.SetItemText(iItem, 1, LPSTR_TEXTCALLBACK);
    	ctlList.SetItemText(iItem, 2, LPSTR_TEXTCALLBACK);
    	iItem++;
     
    	// Check if user cancelled operation 
    if( WAIT_OBJECT_0 
    	 == WaitForSingleObject( GetShutdownEvent(), 0 ) )
    	{
    	 return hr;
    	}
     
    	// Pump messages to allow cancel button click
    	// during control filling. Populating the control
    	// with thousands of records takes time, so we need
    	// to process messages to handle the cancel button
    	// and close messages
     
    if(!ProcessMessages( ))
    	{
    	 return hr;
    	}
     
    	// Restore the wait cursor
    	// (if you don't do this, the wait cursor may go
    	// away after pumping messages)
    wait.Restore();
    }
     
    // Unlock the List control window
    ctlList.UnlockWindowUpdate();
     
    return hr;
    }
    
    Of course, for best performance when dealing with tens of thousands or more items is to combine the virtual tree control with the on demand loading that Mr Bean mentioned.
    Last edited by Arjay; June 12th, 2006 at 11:18 AM.

  4. #4
    Join Date
    Jul 2005
    Posts
    767

    Re: CTreeCtrl SOOO SLOW !

    Arjay: I think you have mixed up Virtual List control with Virtual Tree Control . It would be nice if you can provide an Virtual Tree Control example.
    Last edited by MrBeans; June 12th, 2006 at 11:23 AM.

  5. #5
    Arjay's Avatar
    Arjay is online now Moderator / MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    11,220

    Re: CTreeCtrl SOOO SLOW !

    Quote Originally Posted by MrBeans
    Arjay: I think you have mixed up Virtual List control with Virtual Tree Control . It would be nice if you can provide an Virtual Tree Control example.
    My response includes code for the virtual list control, but mentions it's similar to the virtual tree control. Essentially, you can use the LVSelState example and replace the list view notification states and messages from LV to TV (e.g. NMLVDISPINFO becomes NMTVDISPINFO; LVITEM becomes TVITEM and so on).

    Here's the OnXXXGetDispInfo message handler, which I probably needed to include earlier. This is where all the virtual business happens:

    Code:
    // Method: OnLvnGetdispinfoList
    // Purpose: Handle the List Control Virtual callback. This handler gets
    // called everytime the list control needs to update its [visible] display
    // data.
    void CLVSelStateDlg::OnLvnGetdispinfoList(NMHDR *pNMHDR, LRESULT *pResult)
    {
      NMLVDISPINFO *pDispInfo
    	= reinterpret_cast<NMLVDISPINFO*>(pNMHDR);
     
      // Get the list control item
    LVITEM* pItem = &(pDispInfo)->item;
     
      // Retrieve the CLVItemData object associated with this item
    CLVItemData* pLVItemData 
    	= reinterpret_cast<CLVItemData*>(pItem->lParam);
     
      if( NULL != pLVItemData )
      {
     
    	// Let the item method fill out the display data 
    pLVItemData->GetListViewItemInfo( pItem );
      }
     
      *pResult = 0;
    }


    Although this example is for a list view control, the virtual tree view control code is very similar. This example shows other useful concepts:
    • Locking the control while filling so the control doesn't look strange during the filling operation.
    • The virtual list control stores its data in an stl container (std::vector).
    • The std::vector is shared between two threads, so access to the vector is protected by a critical section.
    • While the control is filling, a wait cursor is displayed
    • During the filling of the control (and the filling of the vector in the secondary thread), the user can hit Cancel at any time and either filling operation will be gracefully halted.
    I didn't have a virtual tree view control example handy, so since the two virtual controls are similar, I thought this example appropro.

  6. #6
    Join Date
    Jul 2001
    Location
    Netherlands
    Posts
    751

    Re: CTreeCtrl SOOO SLOW !

    The reason it is so slow is that you go too DEEP.
    In a tree control you only want to go 2 levels deep( so you know whether a node is expandable or not).
    So after two levels you stop adding more items.
    And then you capture the TVN_SELCHANGED event to fill up the subtree at the selected item.

  7. #7
    Join Date
    Sep 1999
    Location
    Salisburyl UK
    Posts
    324

    Re: CTreeCtrl SOOO SLOW !

    Guys..
    Thanks for your responses.
    I have concidered using the "on demand" approach suggested by MrBeans, but unfortunatly the data I am presented with is "of the moment" so as to speak, and will be lost of it is not recorded. However I have not come accross this idea of a Virtual Tree Control suggested by Arjay, so I will look further into it.
    Arjay, thanks for the code example, if you have any more examples, Id be greatful !
    You would not belief the amount of time I have already wasted trying to get this method of presenting my data working !!!!! (but then maybe you would !)
    Thanks
    Philip....

  8. #8
    Join Date
    May 2002
    Posts
    1,435

    Re: CTreeCtrl SOOO SLOW !

    I haven't tried this with a tree control, but it does speed up adding lots of items to list controls.

    VERIFY(m_treeCtrl.LockWindowUpdate());

    // Add tree control items

    m_treeCtrl.UnlockWindowUpdate();

  9. #9
    Join Date
    Sep 1999
    Location
    Salisburyl UK
    Posts
    324

    Re: CTreeCtrl SOOO SLOW !

    I haven't tried this with a tree control, but it does speed up adding lots of items to list controls.

    VERIFY(m_treeCtrl.LockWindowUpdate());

    // Add tree control items

    m_treeCtrl.UnlockWindowUpdate();
    Thanks for this suggestion, oddly, it seems t make the adding of 4500 items slightly longer if anything.

    I think I am going to have to look into Arjays suggestion of a 'Virtual' control.
    Im not entirly sure what that is at the moment, I assume it involves building the control in memory and displaying only the visible part. But where to start iludes me at the moment!

  10. #10
    Arjay's Avatar
    Arjay is online now Moderator / MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    11,220

    Re: CTreeCtrl SOOO SLOW !

    Quote Originally Posted by Phill Heald
    Thanks for this suggestion, oddly, it seems t make the adding of 4500 items slightly longer if anything.

    I think I am going to have to look into Arjays suggestion of a 'Virtual' control.
    Im not entirly sure what that is at the moment, I assume it involves building the control in memory and displaying only the visible part. But where to start iludes me at the moment!
    Check out the LVSelState link included in a previous reply. As I mentioned, this example uses a virtual listview, but the concepts are the same. Just look through the project, and see how the items are maintained in a vector, and how these items are connected to the virtual list control.

    I'm working on a virtual tree control example, but probably won't have it ready until tomorrow. Until then...

    Keep in mind that when using a virtual control (whether list or tree and, from this point forward, when I refer to list, I also mean tree), the data isn't stored in the control.

    In a 'regular' list or tree control, the display data is copied over into the control when an item is inserted. The reason why this is slow is that for every item, a copy of the data is maintained in the list. So if we have some data source (whether it be an xml doc, a std::vector, or other collection), when we cycle through the list and insert items into the list control, all string data is copied into the control. So now the list control has to manage all this string data (and the more string data that is contained in the control, the slower the control becomes). If the control needs to track state (checkbox select/unselect or image data), it copies this as well.

    What the virtual control does is that is doesn't copy any string or state data, but instead queries the underlying data structure for the data using the GetDispInfo message. In other words, if I have a std::vector as a data source and I insert 10,000 items into the virtual list control, I only actually insert 10,000 'placeholders' into the control, and when the list control needs to display the data, it sends out GetDispInfo messages (which in turn get the data for each std::vector entry). So for a list control (using the 10,000 vector entries), 10 columns of string data, and displaying 50 rows at a time, the control itself is only loading 10 * 50 = 500 items of string data (that is, 10 columns X 50 rows). If each column holds 50 chars, then overall the control is storing only 25K of data (well, there is other overhead because of the 'placeholder' data, but let's ignore that for now because it's not that significant). If we compare the same for all 10,000 records (10 cols X 10,000 items X 50 chars) we have the 'regular' list control storing 5MB of data. Big difference. This is why the virtual control is so much faster because it isn't storing all the data in the control, when the user scrolls up and down, the virtual control just swaps in the visible data on demand and doesn't have to internally track the large 5MB data set.

  11. #11
    Join Date
    Sep 1999
    Location
    Salisburyl UK
    Posts
    324

    Re: CTreeCtrl SOOO SLOW !

    Arjay..
    Thanks for your comprihensive reply. A Tree Control example would be fantastic!!!!
    In the meantime I will look more closly at your reply.
    Thanks again for your time and effort!
    Regards
    Phill

  12. #12
    Arjay's Avatar
    Arjay is online now Moderator / MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    11,220

    Re: CTreeCtrl SOOO SLOW !

    I've finally got around to posting the Virtual Tree Control sample. It's like the Virtual List Control Sample (LCSelState) in that it first creates a collection of items and the virtual tree control points to the collection for it's data.

    To populate the control, the user specifies a drive letter, a max count, and a depth. When the retrieve btn is clicked, a secondary thread is fired off to walk the file system and build up the tree hierarchy of directories. This hierarchy is stored into a std::multimap collection. Once the directory structure has been formed, the secondary thread ends and 'multiplier' is applied to the collection (x1, x5, x10). After that the collection is used to fill the virtual tree control.

    Multithreading does add complexity (not needed to show the virtual tree control functionality), but I wanted to include it because I feel it's useful to understand how to protect data shared between two threads. It's also useful to be able to cancel and clean up cleanly with multithreaded apps. This sample allows you to interrupt a current retrieval, by pressing cancel (which causes the secondary thread to exit gracefully).

    As far as the virtual tree control code, there's not very much. It amounts to specifying the LPSTR_TEXTCALLBACK constant in the TVITEM structure...

    Code:
    TVITEM tvItem;
    tvItem.mask = LVIF_TEXT | LVIF_PARAM;
    // Virtual Tree control (set pszText to callback and max item length)
    tvItem.pszText = LPSTR_TEXTCALLBACK;
    tvItem.cchTextMax = MAX_ITEMLEN;
    tvItem.lParam = reinterpret_cast<LPARAM>( &rTVItemData );
    
    ...and handling the GETDISPINFO message. We just get the TVItem,
    retrieve the underlying CTVItemData object, and let it set the display
    string

    Code:
    void CVirtualTreeDlg::OnTvnGetdispinfoTree(NMHDR *pNMHDR,
      LRESULT *pResult)
    {
      LPNMTVDISPINFO pTVDispInfo 
    	= reinterpret_cast<LPNMTVDISPINFO>(pNMHDR);
     
      // Get the tree control item
    TVITEM* pItem = &(pTVDispInfo)->item;
     
      // Just interested in text notifications
    if( ( pItem->mask & TVIF_TEXT ) != TVIF_TEXT )
      {
    	*pResult = 0;
    	return;
      }
     
      // Retrieve the CLVItemData object associated with this item
    CTVItemData* pTVItemData 
    	= reinterpret_cast<CTVItemData*>(pItem->lParam);
     
      if( NULL != pTVItemData )
      {
    	// Let the item method fill out the display data 
    pTVItemData->GetTreeViewItemInfo( pItem );
      }
     
      *pResult = 0;
    }
    
    The method that sets the display string.

    Code:
    void CTVItemData::GetTreeViewItemInfo( LPTVITEM pItem )
    {
      // Thread safe locking
    CAutoLockT<CTVItemData> lock(this);
      pItem->pszText = m_sName.GetBuffer( );
      m_sName.ReleaseBuffer( );
    }
    A couple of observations:
    1. The virtual tree control is slower than the virtual list control. There both about the same once filled (i.e. scrolling, etc.), but it seems that the virtual tree control takes longer to fill.
    2. UNICODE seems to work faster than ANSI. It makes sense since there is less string conversions going on. (you can try it both ways.
    3. Gathering the directory structure from the file system isn't exactly blazing. As a result, you may want to keep the node depth down (3 or less) and go up on the multiplier to get into the thousands of tree items.
    The attached project was built using VC2003, so sorry for all you VC6 and VS2002 users. You should be able to create an earlier dlg project and copy the relevant files over (other than the different project formats, the rest of the code should compile fine on earlier versions of VC).

    List of controls:
    • Drive droplist - gets filled with the local drive letters. This drive letter is used to retrieve the directory hierarchy
    • Max Count - a rough limit of the maximum item count
    • Multiplier - multiplies the retrieved directory items times the multiplier.
    • Depth - how deep to go when retrieving child directories
    • Retrieve btn - starts the retrieval process
    • Cancel btn - stops the retrieval process
    See the attached screen shot and zipped file.
    Attached Files Attached Files

  13. #13
    Join Date
    Sep 1999
    Location
    Salisburyl UK
    Posts
    324

    Re: CTreeCtrl SOOO SLOW !

    Arjay..

    Thanks once again for your help in answering my question. Your help is well beyond the usual.
    I will move your code to a VC6 project and look at it in detail. Im sure it will solve my problem (when I understand it !). Shame CodeGuru wont let me rate each of your responces as it surly should !!

    Regards
    Phill..

  14. #14
    Join Date
    Aug 2005
    Posts
    27

    Re: CTreeCtrl SOOO SLOW !

    I put a breakpoint in the CVirtualTreeDlg::OnTvnGetdispinfoTree function and the breakpoint is hit for every item in the tree on the first load (prior to me scrolling). Shouldn't it be calling this function only for the visible tree items? In the virtual CListCtrl, the control must be created with the Owner Data style so that it knows not to populate the list item until it is in view. Is there an option like this on the CTreeCtrl? Otherwise I think the LPSTR_TEXTCALLBACK just tells it how to populate and not when.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center