Increasing List creation speed

[Alhexx]

I need your help once again.
As you might have noticed in the scrollbar topic, I'm working on an archive (de)compressor called Kaddy. The tool works pretty well, but I have one problem that makes my head ache (or maybe it's the maths exam I wrote today...  :erm: )

Well, okay. When I load an archive, let's say battle.lgp, Kaddy opens the file and creates a file list. This goes very fast.
However, I use a CListView class (the "same" as CListCtrl) to display this file list. Here's a screenshot
As you might know, battle.lgp has over 11K files...

Now the problem is:
It takes almost 2 mintues (!) until Kaddy has added all items to the CListCtrl view class!

Here's the code I currently use:

Code: [Select]

void CKaddyView::RenderNode()
{
CListCtrl& lst = GetListCtrl();
// Clear current list
lst.DeleteAllItems();

if(m_pcurDir == NULL)
return;

unsigned long ulIndex = 0;

// Is this not the root dir?
if(m_pcurDir->pParent != NULL)
{
lst.InsertItem(LVS_INS, ulIndex, "..", 0, 0, 0, ulIndex);
lst.SetItemText(ulIndex++, 3, "p");
}

CString strId;
// Do we have sub-dirs?
for(unsigned long i = 0; i < m_pcurDir->ulNumSubDirs; i++)
{
strId.Format("d%i", i);
lst.InsertItem(LVS_INS, ulIndex, &m_pcurDir->pNames[m_pcurDir->pSubDirs[i].ulNameOffset], 0, 0, 0, ulIndex);
lst.SetItemText(ulIndex++, 3, strId);
}

CString Buf;
// Do we have files?
for(unsigned long i = 0; i < m_pcurDir->ulNumFiles; i++)
{
strId.Format("f%i", i);
lst.InsertItem(LVS_INS, ulIndex, &m_pcurDir->pNames[m_pcurDir->pFiles[i].ulNameOffset], 0, 0, 2, ulIndex);
Buf.Format("%i", m_pcurDir->pFiles[i].ulFileSize);
lst.SetItemText(ulIndex, 1, Buf);
Buf.Format("%i", m_pcurDir->pFiles[i].ulCompressedSize);
lst.SetItemText(ulIndex, 2, Buf);
lst.SetItemText(ulIndex++, 3, strId);
}

// That's it
UpdateWindow();
}


The part where most of the time is spend is the last for-loop.
Now my question is:
Is there any possibility to modify that code to increase the speed?
I'm not sure, but I suppose that the CString.Format method need that much time...

I cannot allow Kaddy to need 2 minutes for rendering a 10K file list...  

Any ideas?


 - Alhexx

[EmperorSteele]

You could go the lgp tools route and ahve it only display 1000 or so at a time.

I would reccomend maybe making a cahce lsit, so Kaddy already knows what to display, but with the number of mods out there (hands patch, battle-2-field, high poly Cloud, etc), the "cached list" might become worthless.

[Alhexx]

You could go the lgp tools route and ahve it only display 1000 or so at a time.

I thought about that, too, and I think this is one thing I will also implement.

Any other ideas?

 - Alhexx

[bulk_4me]

OOP freaks... j/k

Anyway I think the problem is here:

&m_pcurDir->pNames[m_pcurDir->pFiles.ulNameOffset]

Explaining what's the purpouse of each access could help.

[ficedula]

If this is a standard Windows listview control, there are two things you can try to speed up it:

1) It's possible your calls to add items are actually updating the list there and then. I don't know if your library has anything similar, but in Delphi you can often call BeginUpdate() and EndUpdate() methods when you're updating big blocks of stuff - Delphi won't repaint or recalculate anything until you call EndUpdate() to let it know you're finished changing things.

2) More complicated - set the listview to OwnerDraw. This means you don't actually add the items to the list at all, which is obviously fast  Instead, you tell it how many items there are in the list and when Windows needs to display an item, it calls one of your functions (well, probably it's sending a message) to get the text etc. to display.

This is obviously quick, because the startup time is zilch, and Windows only asks for the text on items the user is actually displaying

If your listbox class doesn't support OwnerDraw, you are of course screwed as far as this optimisation goes...

[mirex]

I found three approaches so far.
1) load it into one list (CListCtrl), and fill it quick. I used it in Unmass. It fills 10k list in hmm ..20 seconds ? But freeing the list takes 30 seconds, dunno why. Not good
2) splitting the list into more parts, by count lets say, 1000 ... quick, but its handled hard, you have 2 controlls to control one list. Bad
3) use virtual list control. its just like a normal CListCtrl, except that its empty, and only on redraw it asks you for the data, for each cell which is displayed. Can be seen in the newest Biturn when you load big 3d file and click on the Data info button. Its shows data in instant. Great, i recommend it.
Right now I cannot remember the correct name of the controll, but it's part of MFC, something with Virtual, and there is probably reference to it in CListCtrl help page. maybe its CVirtualListCtrl.

[Alhexx]

bulk_4me:
m_pcurDir->pNames is the file name buffer of the directory. The names of all sub directories and files are stored in this buffer, every one terminated by a null char.
m_pcurDir->pFiles.ulNameOffset is the offset of file "i" within this directory filename buffer.


ficedula:
Yeah, that list control supports owner draw. This sounds interesting, I'll try it.

btw: Do you have been able to recalculate those checksums in the LGP format???

 - Alhexx

[ficedula]

The checksums are really an index - Qhimm figured out the format ages ago. I think the latest version of LGP Tools can write them correctly, but I honestly can't remember; it's years since I worked on that...

[Alhexx]

I see.
So I'm going to have a closer look at the nice "Search" button here...  
This will allow my Kaddy LGP Plugin also to write LGP files then...

 - Alhexx

[mirex]

I would not go by way of handling the OwnerDraw, because then you have to care about drawing of the items and stuff; by virtual list you only suppply the data when needed.

So I looked it up, its a little larger topic,  if you have MSDN you can see it when going to CListCtrl class overview, and then clicking the 'Using CListCtrl; Virtual List Controls' in the middle of the text.

It is used by checking the LVS_OWNERDATA property of CListCtrl, and then adding the LVN_GETDISPINFO handler for the list. Not hard to implement, and its good for the big databases, really, try it.

[bulk_4me]

Maybe this can help:

http://www.pocketpcdn.com/articles/list_view.html

[Alhexx]

mirex: Okay, I'll try that first.

bulk_4me: thanx


 - Alhexx

[Micky]

Like Mirex i had good success with a virtual list control. But I wrote it directly with the Win32 API and not through MFC...
But it makes a lot of sense, instead of storing the data twice, once in your app and once in the control, you just handle the messages requesting the data for specific columns/rows.

[Alhexx]

Okay, I did it with virtual lists as mirex said, and the speed increase is really incredible...
Now Kaddy needs less than 10 seconds to load battle.lgp  

This one is not only for mirex, but for all of you who tried to help me:



 - Alhexx