Quantum Bit Designs

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.

Rebuilding…