Saturday, January 12, 2008

Cross-thread Collection Binding in WPF Take 2

A colleague asked me whether I'd found a solution to my previous post on binding to a collection that is modified on a background thread. If you haven't already read the post, you should do so before proceeding. Make sure you read the comments too.

As it turns out, I had completely forgotten about this problem. Therefore, I decided to revisit it and see what I could come up with. I believe I have a satisfactory solution now, but I will walk you through some of the unsatisfactory ones first (got to build up some tension, don't you know).

To start with, I took my original sample and hammered the collection with 10 background threads doing insertions every few milliseconds (and this was a dual core machine). The crash would occur between 1 and 4 seconds after starting, but your mileage may vary. Now if your business objects are being hammered that much then you probably have more important things to worry about. All the same, it's disconcerting knowing that the issue is there and it would be nice to fix it.

The first thing I considered was having the dispatching collection keep a separate list of references that are maintained on the UI thread. The UI thread only sees this separate list, which is maintained on the UI thread in response to the CollectionChanged event on the underlying collection (which may occur on a worker thread).

The Add() method looked like this:

public void Add(TItem item)
{
    Dispatcher.VerifyAccess();
    _underlyingCollection.Add(item);
}

And the OnCollectionChanged() handler looked like this (only adding is implemented):

private void OnCollectionChanged(NotifyCollectionChangedEventArgs e)
{
    //marshal the event to the dispatcher's thread
    if (_dispatcher.CheckAccess())
    {
        //now apply whatever happened to the underlying collection to our copy
        switch (e.Action)
        {
            case NotifyCollectionChangedAction.Add:
                for (int i = 0; i < e.NewItems.Count; ++i)
                {
                    _items.Insert(i + e.NewStartingIndex, (TItem)e.NewItems[i]);
                }
                break;
        }

        //now that we've applied the changes, raise the CollectionChanged event
        EventHelper.Raise(CollectionChanged, this, e);
    }
    else
    {
        _dispatcher.Invoke(DispatcherPriority.Send, new OnCollectionChangedHandler(OnCollectionChanged), e);
    }
}

However, I realized this would only work when there is only a single background thread modifying the underlying collection. Otherwise, the indexes reported in the NotifyCollectionChangedEventArgs will get out of sync and all sorts of nasty things can - and will - happen.

I considered what would happen if I didn't use the reported index and instead just added the item to the end of _items. That means the underlying collection and the copy maintained by the dispatching collection would get out of sync. Therefore, this would cause problems elsewhere such as when moving items.

At this point I decided to do away with the notion of maintaining a separate collection. It appears impossible to keep the two correctly in sync without the underlying collection being aware of the dispatching collection.

I decided to investigate something I hinted at in the comments of my previous post: using SynchronizationContext. A SynchronizationContext is an environment-agnostic way of providing thread affinity. WPF provides a SynchronizationContext subclass called DispatcherSynchronizationContext and Winforms has one called WindowsFormsSynchronizationContext, but by using only SynchronizationContext.Current, our collection can be agnostic of the environment in which it is executing.

That is precisely what the SynchronizationContextCollection<T> class does in the attached code. When a SynchronizationContext is available, it will use it to marshal collection modifications to the correct thread. In a WPF application, this means that if a background thread adds an item to the collection, that item will be added on the UI thread, and the background thread will block until the UI thread has processed the request.

One nice thing about the SynchronizationContextCollection<T> class is that it will work with or without a SynchronizationContext (as the example demonstrates - see _collection3). When there is no SynchronizationContext in play, no marshaling will take place and all changes occur on the thread on which the call was made. This means it will work equally well where you don't have a SynchronizationContext, such as in a server environment.

I have also included serialization support, since you'd typically want this in your business objects. Suppose you have a server that passes business objects back to clients. On the server, these business objects may have no SynchronizationContext associated with their collections. But when they are deserialized on the client, the collections will assume the current SynchronizationContext.

Another nice thing is that it is agnostic of the particular SynchronizationContext in use. This means it will work equally well with your own custom SynchronizationContext, or with WCF's, for example.

You may wonder whether it will work in a Winforms environment. Yes, and no. It will correctly marshal changes to the UI thread, but Winforms will not recognize those changes because it doesn't understand the INotifyCollectionChanged interface. This means you'd have to change the collection to implement IBindingList instead.

In a sense, your business layer is still tied to the presentation layer, because your presentation layer dictates which interface you need to implement in order to support data binding. This sux, but I don't see any way around it. You could implement both interfaces, but that means your Winforms apps will have to be running against .NET 3.0.

One final thing I want to note. You'll see in the download that there is a collection being hammered by a bunch of threads (30). Some threads are adding items, some are removing items, and some are swapping items. You'll see that these operations are protected by a lock, such that only one background thread is modifying the collection at any one time.

Does this defeat the purpose of SynchronizationContextCollection<T>? Not at all. Its purpose is to ensure those changes are marshaled to the correct thread before being applied, not to allow a free-for-all on the collection. If there were no locks, the logic around adding and removing items would not be thread-safe and would fail even in the absence of a presentation layer.

You can download the source below.

3 comments:

Kevin Kerr said...

Hi Kent,

I am glad you were able to revisit the topic, I find it very interesting... so interesting that I implemented a solution as well:

http://blog.quantumbitdesigns.com/?p=8

I went the 2 collection route, and the UI collection is updated asynchronously from any thread.

I tried a similar design to yours, but I identified a rare deadlock that can exist if both the UI thread and a worker thread are trying to modify the list. Here are the conceptual steps that would cause the problem:

1. A worker aquires the lock to the list.
2. The UI attempts to acquire the lock, but is blocked by the lock.
3. The worker modifies the list, which performs the Send operation which blocks until complete.
4. Since the Send is waiting on the UI and the UI is waiting on the lock, deadlock occurs.

However, if all threads modifying the collection are workers, no deadlock will ever occur. Bea Costa's InvokeOC class has this same deadlock risk since it uses Invoke.

On the flip side, the event can't be posted asynchronously because then the worker thread would not have the latest copy of the list! Ultimately I believe the only solution that will work across the board is having two lists. What do you think?

On a side note, I really like how you used the SynchronizationContext. Would you care if I updated my post/code to do something similar, giving you credit and referencing your blog/post? :)

Kent Boogaart said...

Thanks Kevin,

Sure, feel free to incorporate my ideas into your work. This is a team effort! :)

You're right - my download currently focuses on a readonly UI thread with many changes being made by background threads. However, I believe it is possible to change the UI thread to be read/write without deadlocking. I have updated my sample locally and have it working (as far as I can tell anyway). This deserves another blog post, but the key ingredients are:

1. UI thread must use Monitor.TryEnter to acquire lock
2. UI thread must handle failure of TryEnter by pumping the dispatcher so that background operations are processed whilst awaiting the lock

I'll have an update hopefully later this week. My Internet connection is down (posting this via my phone) so I'll see what I can do.

Cheers,
Kent

Kevin Kerr said...

Nice... I'm looking forward to seeing that.

One downside of my implementation is that it is read only to the observable collection, but the UI thread and other threads can modify the source collection. Basically WPF just displays the collection and never changes it itself since WPF does not lock the collection.