Introduction
I ran across a web-page on the internet where people were voting for enhancements to the next .NET Framework. On the page, I noticed there were a lot of people voting for a safe multi-threaded way of dispatching an INotifyCollectionChanged event, mostly regarding the ObservableCollection. That made me remember the initial pains I had with this issue and the many articles devoted to trying to remedy it, one of the earliest if not first solutions coming from Bea Stollnitz (love her blog). I have long since put this behind me since I solved it on my own a few years ago but completely forgot that it's still very much the pain in the neck it was back then, so I've decided to pull the relevant classes out of my library and share it with everyone.
The good thing about my solution is that it's simple doesn't have the limitations of most of the other solutions I've seen such as the inability to modify the collection in certain threads, the inability to databind to the collection from other UI threads, the need to keep two collections internally and keep them in sync, or the necessity of passing in a Dispatcher, etc... My solution allows you to modify the collection by *any* thread whether it's the owner UI thread, some other UI thread that isn't the owner, or a background thread.
Please take your time to read this article so that you can understand some of the problems I intend to deal with and let me know whether or not this solution was helpful to you as well as any bugs you may have encountered. Also, don't forget to vote!
Major Update : In the previous version of this article I solved the problem that resulted in the infamous "This type of CollectionView ..." exception but my job wasn't really done. You see, there are other issues as to why you can't update a collection from another thread that will cause exceptions and I hadn't addressed those. One major problem is that the UI thread may be trying to display your collection and while it's in the middle of displaying it on the screen a background thread might remove an item without the UI thread knowing about it and when it tries to display the item it finds it doesn't exist and throws an exception. Another major problem is that two or more threads might try to add or remove items at the same time and end up corrupting the collection resulting in an exception. I have now addressed these other issues as well. The main class I will be dealing with in this article is the ObservableImmutableList class because this class is the one that will replace the ObservableCollection class you would normally use. However, my library now includes other collection classes (such as ObservableImmutableDictionary) that share the same thread-safety properties and now implement INotifyCollectionChanged as well. I will keep expanding this library as I find the time to do so.
Background
There are already numerous articles out there detailing the issue in depth, so I'll only give a brief synopsis here. The problem, in a nutshell, is that the INotifyCollectionChanged event, when triggered from a thread other than the originating thread, will give you the infamous "This type of CollectionView does not support changes to its SourceCollection from a thread different from the Dispatcher thread." You can test this yourself by creating an ObservableCollection and binding it to an ItemsControl/ListBox/ListView; note that when you do this, you are doing it on the UI thread. Then, add an item to it via a worker thread, such as through a Timer event or ThreadPool.QueueUserWorkItem and you'll get an exception. The problem is that the NotifyCollectionChanged event (the one your ItemsControl/ListBox/ListView automagically subscribes to in order to determine if something has been added or removed from the collection) gets triggered from the worker thread because the worker thread is trying to modify the collection and since the worker thread isn't a UI thread it throws an exception. This explanation is a tad-bit simplified, but you get the idea.
Using the Code
The magic to solving the "This type of CollectionView does not support changes to its SourceCollection from a thread different from the Dispatcher thread." problem in a simple manner happens when you realize that the problem only occurs at the notification side. If I want to be notified of an event, what would I have to do? I would have to subscribe to it, of course. This is where the magic happens; it happens during the subscription process.
What I've done is override the CollectionChanged subscription mechanism so that whenever any changes occur to the collection, it will trigger it from the relevant thread.
protected virtual void OnCollectionChanged(NotifyCollectionChangedEventArgs args)
{
var notifyCollectionChangedEventHandler = CollectionChanged;
if (notifyCollectionChangedEventHandler == null)
return;
foreach (NotifyCollectionChangedEventHandler handler in notifyCollectionChangedEventHandler.GetInvocationList())
{
var dispatcherObject = handler.Target as DispatcherObject;
if (dispatcherObject != null && !dispatcherObject.CheckAccess())
{
dispatcherObject.Dispatcher.Invoke(DispatcherPriority.DataBind, handler, this, args);
}
else
handler(this, args);
}
}
As you can see I am getting the DispatcherObject associated with each event handler and if it's a UI thread then I use it to marshall the call to the UI thread; if not then it's a background thread and I simply execute that on the spot. That's all that's needed to fix that infamous exception. Now in order to resolve the other thread-safety issues I needed to make sure that 1) changes that are made to the collection occur atomically (that is, they occur in one fell-swoop without moving the ground from underneath you) and 2) that no further changes can occur while the NotifyCollectionChanged event is executing on each thread.
The solution to problem #1 is to change the underlying data-structure from an ObservableCollection to an ImmutableList and add Observable functionality to it. The reason for this is that the ObservableCollection is full of state that changes underneath you while the ImmutableList is immutable and can't change underneath you; if you need to add or remote an item from an ImmutableList it creates another ImmutableList for you (which is how strings work). Now you may think this may incur a huge performance hit but it's actually doing some very clever things behind the scenes so it's pretty fast.
The solution to #2 was to wrap the modification of the collection and the NotifyCollectionChanged in a lock so that for every change that occurs each thread is immediately and synchronously notified before any further changes can occur. Now the problem with locks is that they're slow but that's nothing compared to the major problem with locking... If a background thread obtains the lock and proceeds to modify the collection it will then call each NotifyCollectionChanged event on their respective threads. However, if the UI thread it's trying to call is blocking (ie. waiting) on the lock then you run into a deadlock; that is, the background thread is calling the UI thread and waiting for it to execute the NotifyCollectionChanged event but the UI thread is blocking on the lock that the background thread took so it can't execute anything and you end up with both threads waiting for each other and stuck for all eternity. To solves the speed issue I allow the user to specify (via the LockType property) whether they want to use a SpinWait lock or a Monitor lock; SpinWait is a lockless lock that is good for scenarios in which your NotifyCollectionChanged logic doesn't take too long while Monitor is a lock that is good for scenarios in which your NotifyCollectionChanged logic may be doing some heavy lifting. In either case you still end up blocking the UI thread so I implemented a locking mechanism specifically for the UI so that while it's trying to acquire the lock it's still pumping messages; this was accomplished using the Dispatcher and DispatcherFrame.
private void PumpWait_PumpUntil(Dispatcher dispatcher, Func<bool> condition)
{
var frame = new DispatcherFrame();
BeginInvokePump(dispatcher, frame, condition);
Dispatcher.PushFrame(frame);
}
private void BeginInvokePump(Dispatcher dispatcher, DispatcherFrame frame, Func<bool> condition)
{
dispatcher.BeginInvoke
(
DispatcherPriority.DataBind,
(Action)
(
() =>
{
frame.Continue = !condition();
if (frame.Continue)
BeginInvokePump(dispatcher, frame, condition);
}
)
);
}
When I make either of the following calls on a UI thread (depending on the LockType you specify) :
PumpWait_PumpUntil(dispatcher, () => Interlocked.CompareExchange(ref _lock, 1, 0) == 0);
PumpWait_PumpUntil(dispatcher, () => Monitor.TryEnter(_lockObj));
it will keep trying to acquire a lock until the condition is met and while it's doing so it will continue processing UI messages. It is able to do this because it created a message-pump within the original message-pump that can still process messages while it's busy acquiring the lock.
One important thing to note is that you can no longer use any of the modification methods you're used to using such as Add, Remove, etc... because they are not thread-safe. I have supplied thread-safe methods that you should be using called TryOperation and DoOperation. TryOperation will attempt to perform the operation once and if it succeeds it will return true but if it is unable to acquire the lock because some other thread is trying to make changes to it then it will return false. DoOperation works pretty much the same way except that it keeps trying until it succeeds. Here is an example of using DoOperation to remove an item :
items.DoOperation(currentItems => currentItems.Count > 0 ? currentItems.RemoveAt(0) : null);
Here I am attempting to remove an item at index 0 but other threads might be trying to do the same thing! Both TryOperation and DoOperation offers me thread-safe ImmutableList that I should be performing all my modifications on and in this example I name it 'currentItems'. Since other threads can be doing things to the collection at the same time I need to check whether or not the 'current' list has an item count greater than zero and if it does then I can safely remove the item at index zero. If the count is zero then there are no items to remove and I simply return 'null' which tells the DoOperation to cancel the operation. You can actually perform as many changes to ImmutableList as you want in a thread-safe manner :
items.DoOperation(currentItems => currentItems.Clear().Add("Hello").Add("Cruel").Add("World").Remove("Cruel"));
There are a couple of caveats : 1) Don't modify the collection within the NotifyCollectionChanged event! You can read it just fine just don't try to modify it or you'll end up in hell; just trust me on this. 2) There's something about the VirtualizingStackPanel that doesn't play well with this class so you can't use it, sorry; instead replace it with a StackPanel like I did, just check out my xaml in the uxViewWindow class. If anyonce can figure out what it is about the VirtualizingStackPanel that poops on my parade I'd love to hear it.
Attached you will find a Visual Studio 2012 solution that contains a test project so that you can see the class at work. When you run the test solution, the main window will appear.
The main window consists of an ObservableImmutableList, an ItemsControl bound to the collection, and a button for spawning separate views of the same data. If you look at the window title, you will see the thread ID associated with the window (i.e., the UI Thread ID). The main window has an internal timer that triggers every 100 milliseconds; every time it gets triggered it will add, remove, or change a string in the list and it will do this from either the UI thread or a background thread. In the above snapshot, you can see that even though the ItemsControl is bound to the collection on Thread1, worker threads 5 and 6 are both able to add items to the collection without a problem.
Another benefit of using the ObservableImmutableList is that you're not limited to just one UI control; you can bind *multiple* UI controls to it. You can even get your own custom ICollectionView instance from it using the CollectionView class! For those of you that don't know about views, the concept is simple: each view is simply another way of looking at the exact same data. For example, imagine that you have an address book containing the names, phone numbers, and addresses of all your friends. Now imagine that you want to have three windows showing your address book: one window to display them sorted by last name, another window to group them by state, and another window to edit the address book. Wouldn't it be a pain to pass the first window a copy of your address book sorted by last name, the second window a copy grouped by state, and the third window an editable instance of your address book? There's really no need for that with views since each view abstracts the presentation from the source. However, experimenting with all the great things you can accomplish with views is a topic for another article and not the point of my demo; I simply want to let you know that my ObservableImmutableList supports it and affords it the same multi-threaded protection.
If you click on the "Open View On Separate Thread" button, you will open another window that is on a completely different thread. Click on this button twice and you will get the following:
What you're seeing are three windows, each on completely different UI threads, each displaying a different view of the same data.
As you can see the timer able to add/remove/modify items to the ObservableImmutableList from either the background or UI thread with no exceptions whatsoever.
Please feel free to dissect the code any which way you like; I hope this has saved you many months of nail-biting agony. If you have any questions, please feel free to ask, and don't forget to rate this article below!
Points of Interest
As I wrote this article, I came across another solution very similar to mine by Muljadi Budiman at geekswithblogs; essentially the same approach except that he gets the dispatcher from the invocation list while I saved mine manually. I have to give it to him, the thought of getting the dispatcher from the invocation list never occurred to me and I have since updated my code to use his approach which results in less lines of code. You can find his article here (note : his solution only resolves the infamous problem I mentioned earlier and does not address the ObservableCollection's inherent thread-safety issues)
History
- March 11, 2010: Initial post
- March 12, 2010: Added snapshots and information related to the demo application
- March 14, 2014: Major update to fix the remaining thread-safety issues.
- March 15, 2014: Added specific TryXXX and DoXXX methods for add/insert/remove/set functionality.
- March 18, 2014: Refactored code-base, enhanced methods to produce specific NotifyCollectionChangedAction when possible for improved performance and added the ObservableImmutableDictionary class.
- August 14, 2014: Fixed an issue where you were unable to bind to an element of the collection via its indexed property. Example : {Binding Path=[0]}
