Quantum Bit Designs

The Grand Solution – Thread safe binding to a collection and properties that are modified from any thread.

History
-WPF supports cross thread property change notification.
-WPF does not support cross thread collection change notification.
-Part 1 introduced the ObservableBackgroundList<T> that allows cross thread collection change notification from a single worker thread.
-Part 2 described WPF’s lack of support for cross thread property change notification for items that are in the cross thread collection binding.
-Part 3 introduced a solution that allows cross thread property change notification from any thread for the items in the cross thread collection binding.

We are now ready to make the final leap and introduce a solution that supports binding to a collection that can be modified from any thread (including the UI thread). The class is called ObservableList<T>. Here is how to use it:

1. Pass in the UI’s Dispatcher to the constructor
2. Bind to the ObservableCollection property
3. Use the list from any thread by wrapping all list operations in a using block that utilizes the method AcquireLock.

The ObservableList is made thread-safe by acquiring a lock before accessing the list (including just reads). The AcquireLock method is the way to lock the list and prevent other threads from modifying the list while the list is being accessed by the thread owning the lock. Below is a screenshot of a sample application that demonstrates simulating a server that has many worker threads that update the collection and modify properties.

This is an example of how to wrap all list operations in a using block where _activeTasks is an ObservableList<Task>:

using (TimedLock timedLock = this._activeTasks.AcquireLock())
{
foreach (Task task in this._activeTasks)
{
task.PercentComplete = 100;
}
}

The TimedLock is an IDisposable class that locks on an object passed into its constructor and then unlocks when the TimedLock is disposed. ‘Using’ ensures that no matter what happens inside the using parenthesis, the IDisposable.Dispose() method will be called on the TimedLock, thus releasing the lock. If any single thread has acquired the TimedLock then all other threads will block (provided they follow the same pattern). Even the UI thread must acquire the lock before accessing the ObservableList (but WPF does not need to lock on the ObservableCollection). The TimedLock was taken from IanG’s blog and is nothing more than a lock with a timeout to help debugging scenarios.

Quiz for the experts: In the ObservableList<T> all change requests are always posted to the UI thread via the Dispatcher, even when the UI thread is the thread accessing the list. Why did I design it so the UI thread takes a performance hit and still posts change requests to itself? One might think that when the UI thread is executing, all change requests from other threads are automatically blocked until the UI is done, so it should be safe to update the list directly. This turns out to be false. I myself am not a threading guru, but if anyone gets the right answer you can wear that award

We now have solution with the following features:

Features
-Allows WPF to bind to a collection that is modified from any thread
-Allows WPF to bind to properties of items in the collection that are modified from any thread
-No lock required if used from a single worker thread
-Relatively simple (compared to some other attempts)
-Non-blocking

Downsides
-Requires two lists internally
-The ObservableCollection list should not be modified
-Disposable or DependencyObjects should not be used

Despite these negatives, the community now has a solution to suit developers’ WPF, binding, and multithreading needs.

Disclaimer: Although I spent a considerable amount of time studying and testing the design and concepts described in this series, as well as beating the heck out of the ObservableList<T> with a quad core CPU and 10+ threads each modifying the collection and properties at full speed, I am still human and this is just a blog post. Do your own research and testing, and as always, use at your own risk. I will keep this post updated if there are any issues. I personally believe we can put this topic to rest until WPF adds native support for all of these features.

UPDATE: Microsoft has recognized the property/collection change race condition bug and will fix it in a future version of the framework.

Download the Sample: MultithreadedObservableListSample

Property Change Notification from Worker Threads Solution

Update: The final solution has been posted.

Part 2 described why you should not modify properties of items in a collection that is on a worker thread. The solution is to listen for the events ourselves and then raise the PropertyChanged event from the UI thread. If we can do this, property and collection change events will be raised on the UI thread, WPF will be happy, and everything will work. The first step to catching the property change event is to create a new interface:

public interface ICollectionItemNotifyPropertyChanged : INotifyPropertyChanged
{
event PropertyChangedEventHandler CollectionItemPropertyChanged;
void NotifyPropertyChanged(PropertyChangedEventArgs e);
}

Items in our collection now must implement ICollectionItemNotifyPropertyChanged such as:

public class Task : ICollectionItemNotifyPropertyChanged
{
public event PropertyChangedEventHandler PropertyChanged;
public event PropertyChangedEventHandler CollectionItemPropertyChanged;
public int PercentComplete
{
get { return _percentComplete; }
set
{
_percentComplete = value;
OnCollectionItemPropertyChanged(”PercentComplete”);
}
}
public void NotifyPropertyChanged(PropertyChangedEventArgs e)
{
OnPropertyChanged(e);
}
protected void OnPropertyChanged(PropertyChangedEventArgs e)
{
PropertyChangedEventHandler handler = this.PropertyChanged;
if (handler != null)
{
handler(this, e);
}
}
protected void OnCollectionItemPropertyChanged(string propertyName)
{
PropertyChangedEventHandler handler = this.CollectionItemPropertyChanged;
if (handler != null)
{
handler(this, new PropertyChangedEventArgs(propertyName));
}
}
}

Now when the ObservableBackgroundList gets a request to add or remove an item from its ObservableCollection, it can attach to the CollectionItemPropertyChanged event. When that event is raised (from any thread) the handler will always post to the UI thread a method that will raise the PropertyChanged event.

private void StartListening(T source)
{
ICollectionItemNotifyPropertyChanged item = source as ICollectionItemNotifyPropertyChanged;
if (item != null)
{
item.CollectionItemPropertyChanged += new PropertyChangedEventHandler(item_CollectionItemPropertyChanged);
}
}
private void StopListening(T source)
{
ICollectionItemNotifyPropertyChanged item = source as ICollectionItemNotifyPropertyChanged;
if (item != null)
{
item.CollectionItemPropertyChanged -= new PropertyChangedEventHandler(item_CollectionItemPropertyChanged);
}
}
void item_CollectionItemPropertyChanged(object sender, PropertyChangedEventArgs e)
{
this._dispatcher.BeginInvoke(DispatcherPriority.Send,
new PropertyChangedCallback(PropertyChangedFromDispatcherThread),
sender,
new object[] { e }
);
}
private void PropertyChangedFromDispatcherThread(T source, PropertyChangedEventArgs e)
{
ICollectionItemNotifyPropertyChanged item = source as ICollectionItemNotifyPropertyChanged;
item.NotifyPropertyChanged(e);
}

Here is a diagram that shows how CollectionItemPropertyChanged events are caught and used to raise PropertyChanged events from the UI thread:

Now all PropertyChanged events are raised from the UI thread and there are no threading issues to worry about. We can even raise the CollectionItemPropertyChanged events from any number of workers, but the collection can still only be modified from one worker. The following sample demonstrates these concepts in action.

ObservableListSample1

Update: The final solution has been posted.

Update: The final solution has been posted.

As it turns out, I was not the first to design a simple, lock-free, cross-thread collection binding solution. Beatriz Costa’s InvokeOC<T> class works too, and she did it in 2006. Her article can be found here. In her sample she uses locks to simulate using it from multiple threads, but what I did not realize during my research is that it will work perfectly without locks from a single worker thread (provided the UI thread does not modify the collection). Thanks Josh Smith for making me revisit her sample. Her design consists of a single collection deriving from ObservableCollection, overriding the collection change methods, and enforcing that the collection is synchronously updated on the UI thread. Here is example code that shows an overridden method:

protected override void InsertItem(int index, T item)
{
if (dispatcherUIThread.CheckAccess())
{
base.InsertItem(index, item);
}
else
{
dispatcherUIThread.Invoke(DispatcherPriority.Send,
new InsertItemCallback(InsertItem), index, new object[] { item });
}
}

By using ‘Invoke’ the worker thread will block until the UI updates the collection. This blocking ensures that both the worker and UI thread will be reading the most up to date copy at the same time, therefore both threads can read the collection at the same time. However, without locks it is not thread-safe, so you can only modify the collection from one worker thread. She also includes another class called BeginInvokeOC<T>, but it is not reliable so do not use it under any circumstance.

At this point there are two solutions for cross thread collection binding to a collection on a single worker thread:
-InvokeOC<T>: A blocking single collection
-ObservableBackgroundList<T>: A non-blocking double collection

Property Change Notification from Worker Threads

I mentioned in the previous article that I was going to address the issue of potentially flooding the UI thread with notifications. After some research into the solution I decided that the added complexity was not worth the gain and I may revisit the scenario another time. Instead, I want to move on to the guts of the issues at hand for cross thread collection binding.

Developers that bind to a collection from a separate thread will almost certainly bind to properties on the objects in the collection. A percentage of these developers will then want to change some of these properties from the worker thread. Unfortunately, this is not supported out of the box in .NET 3.5 and 3.0 SP1 (I am not sure about .NET 3.0). The reason has to do with the way WPF listens for property and collection change events. In short it is believed that the lack of support is because the static event manager that is handling the change events is not properly synchronized when property changes come from a worker thread. Here is another diagram to illustrate what happens when collection and property change events are raised:

Since the ‘Event Manager’ is static, it is inherently shared between any thread that accesses it. And since collection change events are required to come from the UI thread but property change events are not, the two events can conflict with each other when a property change occurs from a worker thread. An exception that can result from this conflict is:

“Unable to cast object of type ‘System.Collections.Specialized.HybridDictionary’ to type ‘ListenerList’.”

All hope is not lost, since Part 3 will include a solution to get around this problem.

Update: The final solution has been posted.

WPF supports binding to properties that change from any thread, but does it not support collection binding from any thread that is not the UI. Many people have faced the need to be able to bind to some collection that is being operated on by a worker thread. Since WPF does not support this feature out of the box, several people have attempted to come up with a solution. Most of these solutions try to solve the problem by posting the change events to the UI thread so that WPF is notified from the UI thread and not the worker. Unfortunately there is one major flaw that exists with this solution, and it has to do with two threads (UI and worker) sharing the same collection. Here is a diagram of the solution many have come up with:

To initialize this solution, the software developer binds their UI ItemsControl (such as a ListView or ListBox) to their special collection, then they hand off that same collection to their worker thread. Now the solution is set up, and here is what happens:

1. The worker adds or removes an item from the list.
2. This special list internally detects an item is being added from the worker thread, so instead of raising the CollectionChanged event externally, it posts the event internally to itself (to the UI thread).
3. When the event is received internally on the UI thread, the special collection then detects that it can safely raise the CollectionChanged event externally to notify WPF.

WPF then does what it needs to do, such as reading the updated list. Looks great right? This is the flaw:

The moment an item is being added to the collection from the worker thread, the UI thread could be reading/enumerating the same collection at the same time.

This will cause an exception that will cause a crash. The fundamental problem is that the collection is shared between two threads. When data is shared between two threads, the threads need to be synchronized (using locks for example). Since WPF does not lock the UI thread when it reads the collection, there is no way to synchronize the UI thread and the worker thread to prevent both from accessing the collection at the same time.

Let’s step back for a moment and study what is really needed:

A worker thread to be able to modify/update a collection
A UI control to display the collection

Do we need to modify the collection from the UI thread? If not, our requirements just became much easier. This is the direction we will be going.

Disclaimer: Although I came up with my solution on my own, Miral was the first to post a fantastic write-up on the implications of cross-thread collection binding, and I believe his is the first implementation that actually works correctly. However, the solution posted here is more simple and does not require locks.

The Solution
I believe the following solution is the first simple, rock-solid, lock-free, cross-thread collection binding implementation. Given that all we need to do is display the data on the UI thread, we can choose to utilize two collections. The worker thread can work with one collection while the UI thread can bind to the other. Any time the worker changes its collection, the change will be posted to the UI thread where the UI collection will be updated. Here is the diagram:

This special collection will be called an ObservableBackgroundList. It is a list that is only accessible by one thread only (a non UI thread). It is also observable, because it has a property called ObservableCollection that exposes the internal ObservableCollection<T>. The ObservableBackgroundList contains a list for the worker thread to utilize, an ObservableCollection for the UI thread, and a Dispatcher to post change notifications and items to the UI thread.

public class ObservableBackgroundList<T> : IList<T>
{
private Dispatcher _dispatcher;
private List<T> _list;
private ObservableCollection<T> _observableCollection;
…
}

Here is the ObservableCollection property that is exposed for WPF’s binding:

public ObservableCollection<T> ObservableCollection
{
get
{
return this._observableCollection;
}
}

WPF’s items controls bind to this property for their items source. Since this ObservableCollection will always only be updated from the UI thread, no locks are needed. To demonstrate how the ObservableBackgroundList updates its own list as well as updates the UI’s ObservableCollection, we will take a look at the Add method.

public void Add(T item)
{
this._list.Add(item);
this._dispatcher.BeginInvoke(DispatcherPriority.Send,
new AddCallback(AddFromDispatcherThread),
item
);
}

First the ObservableBackgroundList adds the item to its own list. Then, using a constructor supplied Dispatcher, the item is posted to the UI thread where the following method is executed:

private void AddFromDispatcherThread(T item)
{
this._observableCollection.Add(item);
}

Again, since the AddFromDispatcherThread is executing on the UI thread, WPF’s binding to the observable collection will work perfectly.

So, is this solution the grand solution to solve all cross-thread collection binding requirements? Absolutely not. Every design has its tradeoffs, and though this design has its downsides, it will probably be a solution that will work for the majority of people that need cross-thread collection binding. Intelligent readers probably already thought of one potential problem: what if there are so many changes to the collection from the worker thread that all of the posts flood the UI thread? This can happen for sure, but the counter argument is that this is true for any background operation that notifies the UI. Fortunately, this problem will be addressed in Part 2 of this series. Here are the pros and cons of the current design:

Pros
-Simple
-No locks
-Non-blocking
-Easy to use (just like any other list)
-Fast
-Works!

Cons
-It is NOT threadsafe (only 1 thread can work with the list at a time)
-The UI control must not modify its ObservableCollection source (it just displays the collection)
-Disposable or Dependency objects should not be used
-Too many changes too quickly on the worker will flood/block the UI thread
-The UI collection will lag behind the worker collection by an extremely small amount of time
-Two collections are required (but the extra memory usage is very small)

Update: The final solution has been posted.