(Note: this is the 2nd of a 4 part post).
In order to explain why I did to speed up my code, let me first describe the general algorithm that I was working with. At the top level, the code looked (vaguely) like this:
GroupInfo[] agi = DataLayer.GetCellGroupMembers( cell ); listView.Items.Clear(); foreach( GroupInfo gi in agi) listView.Items.Add(gi);
(Note: Consider this pseudo code.)
The general idea is that the UI code calls the data layer code to get an array of items to display and then adds them to the list view so that the user can see them (a list view is the .NET name for a WIndows list box). With >10,000 items, this code would take 20 minutes to execute (on a VM, with a small memory allocation). Why was this operation so slow? There were performance bottlenecks throughout.
At the UI level, adding 10,000 items to a list view is a bad idea. This part of the algorithm alone was taking about 1 minute. Instead of adding all the items to the list box, it’s better to add items only when they’re needed. The .NET Winforms ListView supports this feature — they call it virtual mode. Instead of adding the items to the list view, you put the list view in virtual mode, tell it how many items there are in total and then let the list view ask for items when it needs them. ListView will generate .NET events when it needs items. The code now looks something like this:
// put list view into virtual mode, set up callback listView.VirtualMode = true; listView.RetrieveVirtualItem += new RetrieveVirtualItemEventHandler(RetrieveItem); ... // agi is an object member variable of type GroupInfo[] agi = DataLayer.GetCellGroupMembers( cell ); listView.Items.Clear(); listView.VirtualListSize = agi.Count; ... } private void RetrieveItem( object sender, RetrieveVirtualItemEventArgs e) { e.Item = agi[e.ItemIndex]; }
The time it takes to fill the list view is now, essentially, zero. Typically, only a few items are shown on the list box at any time so “filling it” only consists of providing those few items. When the user scrolls or pages, events are fired and you retrieve the needed items.
This simple change poses a very interesting question: Have we really sped anything up? Offhand, you’d say “yes!” — the list view comes up 30 seconds faster. Someone else might argue that, if the user scrolls from start to finish, that it would still take you 30 seconds. Who would be right?
You’d be! First of all, users will rarely need to see all the data. If, on average, they only need to scroll halfway through the list, the average saving will be at least 50%. Second, ListView is actually pretty smart. If you hold down the “Page Down” button, it won’t actually ask you for every single item. If your list is sorted, the user will look at what’s showing up on the list and “converge” on the desired item once close. The net result might be that the list view only ends up asking for 25% of the data. Third, adding 10,000 items to a list view incurs additional overhead costs that are not required in virtual mode.
Regardless of which argument you find most convincing, realize what the change has accomplished: 1) it has amortized a slow operation over a series of user operations (scrolling) and 2) it has changed the perception of performance to be in line with user time. The user perceives scrolling to be as fast as the keyboard repeat rate. It doesn’t matter if the data access is any faster once you match the keyboard repeat rate. Once you’ve matched the user’s maximum perceived UI responsiveness, you don’t need to do any better.
Switching to a virtual mode list box greatly sped up part of the overall operation, but it only shaved 30 seconds out of the 1200. My next two posts will explain where I saved another 1150 seconds.