Improving UpdateControls for WinForms

Developer
Mar 29, 2011 at 12:15 AM

Hello Micheal/Mike (as you prefer), on the blog I was asking about what "Performance hit" could come from not using RecycleBin and you mentioned...

"In the case of ListBox and ListView, I could have used RecycleBin to manage the contents of the list more efficiently. Instead of clearing and rebuilding the Items collection, I could have determined the fewest number of Inserts and Removes required to get the desired results. This is a patterns I've started using in WPF to manage ObservableCollections, but I never applied it to WinForms. Please let me know if you find any performance issues here, and we can work on improving this code."

While I suspect performance will be an issue in a new application I'm writing (due to ListBoxes/ListViews being refilled from scratch), a bigger issue is the way that the list control responds to changes that are not caused by the user. In my application, there will be changes to the list streaming in frequently from a network connection (I expect several updates per second). Many of these changes will potentially change the text label of an item in the list; it will be rare to add/remove items.

Currently I'm using UpdateListBox but I'm likely to switch to an UpdateListView later. The way UpdateListBox is currently written causes two problems:

  1. If the user scrolls down the list and selects some item down there, the list will scroll upward when any update arrives. The selected item is still visible, but it moves to the bottom of the client area.
  2. If the user is clicking on an item when any update arrives (i.e. he has pressed the mouse button but not yet released it), the click is "cancelled"; the previously selected item is re-selected.

Most likely, these problems will be reduced by doing a "diff" between the current list and the updated list, and only removing/adding the minimum necessary amount, as you suggested. Also, the text of each item must be updated if it has changed. I might be able to make these improvements myself, but you said you wrote an algorithm for this already, so maybe it can be shared between WPF and WinForms somehow.

Coordinator
Mar 29, 2011 at 3:05 PM

The diff certainly would fix the re-scrolling and mouse cancel issues. I was actually surprised when I opened up the code and found that I wasn't diffing the lists.

The diff algorithm I mentioned is implemented in /Desktop/UpdateControls.XAML/Wrapper/ObjectPropertyCollection.cs and it's assistant CollectionItem.cs. It wraps each item in a CollectionItem, which keeps track of whether the item was already in the ObservableCollection or not. Then it runs the whole list through the recycle bin, producing a new list of CollectionItems. Because of recycling, some of the items in the new list were in the old one. EnsureInCollection will insert items that weren't there before, and move items that ended up in a different place. Dispose (called when the RecycleBin is disposed, hence the former IDisposable constraint) will remove items that are no longer in the collection.

As I look back on this algorithm, I notice that it will behave poorly when an item is removed. It will shuffle each following item up, pushing the old item down one slot at a time. I'm starting to see a two-pass algorithm that would work better.

If you'd like to tackle this, I'll be glad for you to send me a patch. If not, I'll set aside some time tonight to implement the two-pass algorithm in UpdateListBox and UpdateListView.

Developer
Mar 30, 2011 at 12:10 AM
Edited Mar 30, 2011 at 12:11 AM

ObjectPropertyCollection makes me wonder about the best way to trigger updates. The WinForms controls subscribe to Application.OnIdle and call Dependent.OnGet to check for updates, whereas ObjectPropertyCollection responds to  the Dependent.Invalidated event by doing a BeginInvoke that calls Dependent.OnGet, using a funny little thing called NotificationGate (what's that?). I'm guessing that the second approach is safer, because perhaps an Idle event could be delayed indefinitely in a busy application. On the other hand, using Idle might be more efficient, because many updates that happen at the same time will only cause a single UI update.

I've been looking into diff algorithms today. If you give me more time I'll try to write a proper generic diff algorithm, probably starting from a 1986 paper and the library described here: http://www.codeproject.com/KB/recipes/DiffAlgorithmCS.aspx#xx2296416xx .... The problem with this algorithm is that it's O(ND) which means it's very slow if N (the list length) and D (the number of changed items) is large. The trick, it seems to me, is to find a way to detect that the lists are very different and abort the diff operation if so. Two common cases where the list changes drastically are (1) when it is sorted, and (2) when the data source for the list changes.

Then again, maybe a proper diff is not worth the trouble... if you can think of an approximate O(N) or O(N log N) algorithm I'd be very interested to hear about it.

Coordinator
Mar 30, 2011 at 2:54 AM

I think I used the wrong term when I mentioned the "diff algorithm". Reordering a list is much less complex than finding the differences between two text files. In my case, I already know exactly where each item should end up in the new collection. It's just a matter of choosing the fewest operations to shuffle them there.

Upon further analysis of the ObjectPropertyCollection algorithm, I realize it's not as bad as I mentioned earlier today. The items that are no longer in the collection are removed before the remaining items are shuffled. So while you will still get the one-slot-at-a-time behavior to push an item further down in the list, you won't incur that overhead while removing an item. Removing is much more common than reordering.

The two-pass algorithm that I'm thinking of is to make one pass to assign items their new index, and then a second pass to move them there. At each step, decide whether to move the current item down to its proper place, or move the proper item up to the current place. Make that decision based on the size of the jump: favor larger jumps. I haven't analyzed the algorithm to determine its order or worst-case behavior, yet.

I'm having a hard time trying to figure out how to test this algorithm. I used to be able to write code without tests, but I can't bring myself to do that anymore. I don't want to test directly on a ListBox control, so I have to find the right way to isolate it. That might take longer than expected.

 

On Application.OnIdle vs. BeginInvoke, they both perform updates at the same time. It's just the WinForms way vs. the WPF/Silverlight way.

NotificationGate let's me tell the difference between a change that I made vs. one that the user made. I BeginOutbound before doing something that I know will reenter. Then if IsInbound, I know it really came from the user.

Coordinator
Mar 30, 2011 at 3:27 PM

Please get the latest and test with your list box. I haven't implemented the two-pass algorithm, since on further reflection in appears more complicated than I first thought. But this should give you better behavior.

If that works, I'll apply the same fix to UpdateListView and UpdateTreeView, and then create a new release.

Developer
Mar 30, 2011 at 7:12 PM
Edited Mar 30, 2011 at 7:45 PM

The latest version fixes the mouse scrolling problem, but not the mouse-click-cancelled problem. The mouse click is cancelled even if no items were inserted or removed, and even if none of the text labels actually changed.

I took a step back from the "diff problem" and realized two things:

  1. Most list updates in most applications will either add or remove one or more items at a single location in the list, OR change the list dramatically (sort / change data set)
  2. IList.Insert() and RemoveAt() are O(N) operations. Therefore, the number of insert and remove operations must always be small, if the list is large. If the list is large and the number of changes to make is not small, it's better to reset the list.

Therefore I propose the following simple algorithm:

  1. Scan the beginning of the two versions of the list to find out how many items are the same ("sameAtStart").
  2. Scan the end of the two versions of the list to find out how many items are the same ("sameAtEnd").
  3. What remains is a "changed" region. In general, the regions will be different sizes in the two versions.
  4. Record the set of "selected" items in the changed region.
  5. Compute common=Math.Min(sizeO, sizeN) where sizeO and sizeN are the size of the "old" and "new" regions, and use the list indexer (O(1)) to transfer 'common' new items into the list.
  6. If sizeN > sizeO, use InsertRange to insert the rest
  7. If sizeN < sizeO, use RemoveRange to -- oops, there is no such thing as RemoveRange. (Edit: I thought of a better idea than I originally posted). So instead, if more than one item is to be removed, you could implement and call your own RemoveRange method, it'll just have to take care to maintain the selection state correctly (for the items that follow the removed ones).
  8. Restore the set of selected items in the changed region.

I suppose something extra may have to be done to update the text labels when the object has not changed but its ToString() representation has changed.

Developer
Mar 30, 2011 at 7:56 PM
Edited Mar 30, 2011 at 10:02 PM

Wow, this is interesting. If I switch the ListBox.SelectionMode from Single to MultiExtended, the click-cancelling problem disappears and selections are maintained perfectly. I can even click and drag a selection while items are being added continuously to the bottom of the list. However, this is without writing a handler for GetItemSelected/SetItemSelected. (I only handle SetSelectedItem/GetSelectedItem right now.) I'll add those handlers and let you know how it works.

Update: something really weird is going on. After implementing GetItemSelected/SetItemSelected, the selection is cleared after every update, and if I double-click on an item then I get an exception on UpdateListBox.cs:198 where base.SelectedItem throws IndexOutOfRangeException. In the debugger, this.SelectedIndex also throws IndexOutOfRangeException. Update2: Actually the exception only happens if I double-click and an update occurs between the first click and the second click. WEIRD!

Developer
Mar 30, 2011 at 10:33 PM
Edited Mar 30, 2011 at 10:50 PM

Update3: Okay, the key problem was that I forgot to implement GetHashCode and Equals on the ViewModel. The exception remains unexplained, but it seems to be triggered by the fact that the selection disappeared during an update. By implementing Equals and GetHashCode, the selection to stays the same after an update, and the exception goes away.

Unfortunately, the click-cancelling problem is back. The problem appears to be that ListBox.OnSelectedIndexChanged is called when the mouse button is released, even though the item is visually selected when the button is pressed. When an update arrives and the listbox is updated, the selection states are updated from the ViewModel (which doesn't know that a new item was selected). OnSelectedIndexChanged is still called when the mouse button is released, but it doesn't matter because the selection states have already been reset.

Update4: The problem is fixed by handling OnMouseDown too:

	protected override void OnSelectedIndexChanged(EventArgs e)
	{
		// Respond to selection changes, as long as they aren't updates.
		if (_updating == 0) SaveSelectionChanges();
		base.OnSelectedIndexChanged(e);
	}
	protected override void OnMouseDown( MouseEventArgs e )
	{
		if (e.Button == MouseButtons.Left) SaveSelectionChanges();
		base.OnMouseDown( e );
	}
	private void SaveSelectionChanges()
	{
		if (base.SelectionMode == SelectionMode.One)
		{
			// Set the one selected item.
			ListBoxItem item = (ListBoxItem)base.SelectedItem;
			if (SetSelectedItem != null)
				SetSelectedItem(item == null ? null : item.Tag);
			_dynSelectedItem.OnSet();
		}
		else if (base.SelectionMode == SelectionMode.MultiSimple ||
			base.SelectionMode == SelectionMode.MultiExtended)
		{
			// Record the selected items.
			if (SetItemSelected != null)
			{
				int index = 0;
				foreach (ListBoxItem item in base.Items)
				{
					item.Selected = base.GetSelected(index);
					++index;
				}
			}
			_dynSelectedItem.OnSet();
		}
	}

Note that only overriding OnMouseDown is insufficient, since the user might drag the mouse before releasing the mouse button. So, as wasteful as it seems, I think it's necessary to handle both of these events.

Coordinator
Mar 31, 2011 at 1:31 AM

I think what I would prefer to do is to freeze all updates while the user is interacting with the control. The background thread should be allowed to populate the list, but the UpdateListBox should not reflect those changes until mouse up. I do something similar in UpdateTextBox while it has focus. Let me see what I can do.

Coordinator
Mar 31, 2011 at 2:28 AM

It looks like freezing the updates solves the problem. I had to add Get/SetSelectedItem handlers to my test to repro the bug. Let me know if it works for you.

Developer
Apr 1, 2011 at 8:19 PM

It's not working for me. The selection state is cleared to nothing whenever an update comes in. I don't know why yet; my IsSelected property is being set to true, yet the selection doesn't stick.

Developer
Apr 2, 2011 at 2:49 AM

Never mind! It is working. I think a design change in my program that I did at the same time caused the problem--just another missing GetHashCode/Equals implementation, this time in the model, which prevented the corresponding viewmodels from being recycled. Basically I switched from displaying the model itself to showing a "view" of the model at a specific point in time.... why do I keep making this mistake?

When something doesn't work in UpdateControls, I wish it were easier to figure out what's going wrong. Another common problem is failing to use Dependents/Independents correctly. The problem is that when we use UpdateControls incorrectly, the UI "just doesn't work right". I guess it'll take some time to develop an intuition about what programming mistakes correspond to what GUI misbehaviors.

Hey, is there a word to describe the concept of a "dependent or independent"? Maybe ... "antecedent"? Nah, it sounds too pretentious.

Coordinator
Apr 2, 2011 at 1:38 PM

Since you were able to get that working, I'll apply the change to the other controls and release a new build.

Forgetting Equals and GetHashCode is a common mistake. I can't think of a way for the library to detect that you've made that mistake, though. It certainly would be useful.

I call that concept "precedent". That which has come before, and upon which your decision depends. You'll see that I use a class called Precedent in both Independent and Dependent.

Developer
Jul 7, 2011 at 9:20 PM

Okay, remember all those troubles I was having with ListBox selections? Well, I switched to a ListView, to fix the problems with text not updating. Now I'm having a selection problem with ListView.

Specifically, shift+clicking to select a range of items does not work correctly. Instead of selecting a range of items starting at the currently selected item, the ListView seems to choose a random starting point for the selection range. I'm sure it's not really random, but it keeps changing. The most common starting point is the end of the list, i.e. the ListView likes to select a range of items starting at the end of the list and going up to the item that I clicked on.