ListView_control_optimization

Optimization of a ListView Control - A Case Study

Introduction

One of the commonly used controls in Windows application programming is the ListView control.

For example, it is used in the FolderSize sample application to display the list of files and subfolders in a folder selected in the tree.

In most cases the list is shown pretty quickly. But if it contains a lot of items, then it does not work well. A common example is the C:\Windows\WinSxS folder which can contain tens of thousands of subfolders.

When selecting this folder in FolderSize 1.1.0, the application seemingly freezes for 30 or more seconds before displaying it's contents, which is not a good behavior from the user's viewpoint.

Clearly there is room for improvement.

Optimization strategy

To optimize a program, we need to identify the parts where the performance is slow. In the case of the ListView control usage, there are two main steps:

1. Retrieving and preparing the data.
2. Populating the data in the ListView control.

After profiling the code, we discovered that step 1 was taking the bulk of the time.

Optimizing data retrieval

Examining the code, the first observations was that it was looping over all the files and subfolders in the folder, and calling two Windows API functions for each of them:

• SHGetFileInfo — to retrieve a user readable file type, and
• GetCompressedFileSize — to retrieve the compressed size of a file on the disk.

In the case of subfolders, it does not make sense to call those functions, as the file type will be "File Folder", and the size is reported as 0. Making sure that the functions were called only for files reduced the time by several seconds, but that was not enough.

Next we noticed that for each folder, there was a lookup performed into another array to get additional data. The lookup was linear and it was taking a lot of time. Changing it to a dictionary lookup lead to almost instantaneous execution of the data retrieval and preparation step.

Optimizing the populating of the ListView control

The second step, populating tens of thousands of items in the ListView, was taking around 5-6 seconds. To improve that, we have to use a Virtual ListView control. To do this, we need to do the following:

1. Keep and array the data to be displayed.
2. Instead of calling LVM_INSERTITEM or OWLNext methods TListViewCtrl::AddItem/TListViewCtrl::InsertItem, call LVM_SETITEMCOUNT or TListViewCtrl::SetItemCount.
3. Handle LVN_GETDISPINFO notification, retrieve the corresponding item from the data array, and set the item or subitem text in the NMLVDISPINFO.item.pszText member. Important: pszText should not be assigned to a temporary variable.
4. Handle the sorting - when a column is clicked, instead of calling LVM_SORTITEMS, sort the data array by the sort column. Note: non-virtual ListView controls use a callback function int CALLBACK CompareFunc(LPARAM lParam1, LPARAM lParam2, LPARAM lParamSort), which returns a negative value if the first item should precede the second, a positive value if the first item should follow the second, or zero if the two items are equivalent. When sorting the data ourselves, we can use std::sort, and we can use the same comparator function with the caveat that the sort function expects a predicate that returns true if the first item should precede the second, and false otherwise. So, we can use the call CompareFunc(...) < 0.

And after implementing all those changes, the C:\Windows\WinSxS folder is listed immediately!

More optimizations

So far we have handled the case of a folder containing thousands of subfolders, but only few files. But what about the case of a folder with thousands of files? It still takes substantial time to load.
Profiling the code points to again the two Windows API calls - SHGetFileInfo and GetCompressedSize - to be the culprit.

Handling GetCompressedSize is easy - instead of populating it for every file when preparing the data, we move that code in the LVN_GETDISPINFO handler, when we have to set the text for the Size subitem. If the data member for that field is empty, we call GetCompressedSize and then cache the result.

Handling SHGetFileInfo is more complicated, because we use the retrieved file type when sorting on that column - so the lazy initialization won't work well. Instead, we make two assumptions:

1. The file type returned by SHGetFileInfo depends solely on the file extension.
2. The files may be many, but the different file extensions among them will be much less.

The solution is to use an in-memory dictionary that stores extension/file type pairs, and call SHGetFileInfo only when an extension is not yet present in it.

With those changes, the displaying of a folder with tens of thousands of files almost instantly.

Handling searching in the virtualized list view

One functionality of the standard list view control is when the user types one or more letters on the keyboard, the first or next matching item is selected.
To provide this functionality in the virtualized list view, we need to handle the LVN_ODFINDITEM message, find the matching item in the data array and return its index.

Source code

The full source code of the FolderSize example is available here: https://sourceforge.net/p/owlnext/code/HEAD/tree/trunk/examples/foldersize/
The list view control that was optimized is encapsulated by the class TFilesList in FolderSizeWnd.cpp. While all the code in it is based on the OWLNext framework, the same principles can be applied to code that uses directly the Windows API, or other frameworks like MFC.

[Vidar Hasfjord]

Hi Jogy, great article!

Note: For Markdown lists to be formatted properly, you need to make sure there is a blank line before and after the list. I have updated the article for you!