Invalidate Often, Update Once

|

I’ve recently been watching a bunch of the longer sessions from MIX09, mainly Hiking Mount Avalon and Robbie Ingebretsen’s session(s) Design Fundamentals for Developers; both of which are about 3 hours long but well worth the time spent watching.

During these sessions I’ve taken copious notes (by using Evernote) and for a few of the more complex and/or unexplored topics I want to write a post, as well as put together some code, on my own to make sure I’ve understood the concept, and to generally share the wealth: this is first post in what I suspect will be a series.

This post is about updating UI elements on the UI thread. A lot. Time consuming updates. On the UI thread. A lot of updates.

The example application I’ve written to discuss this technique is described by the following class diagram:

ObjectModel_UpdateOnce1

And this screenshot:

UI_UpdateOnce1

The application consists of a ListBox where the ItemsSource property is set to an ObservableCollection<int>, and then when the Add Items button is clicked a method called OnAddItems appends ten thousand random integer values to the collection. There is also a listener wired to the CollectionChanged event on the ObservableCollection<int>, which simply invokes a method called UpdateTotal that adds up all the integers currently in the collection, and then presents the calculated value in the UI as the Total.

What this application is attempting to simulate is a situation where a large number of items need to be added to the UI in quick succession, but where there is also some additional action required after an item has been added, a calculated value in the example application. Here’s the code for OnAddItems, OnCollectionChanged and UpdateTotal which outlines how these methods interact:

private void OnAddItems(object sender, RoutedEventArgs e)
{
    Random rnd = new Random((int)DateTime.Now.Ticks);
    for (int i = 0; i < 10000; i++)
        this.list.Add(rnd.Next(0, 100));
}

private void OnCollectionChanged(object sender, NotifyCollectionChangedEventArgs e)
{
    UpdateTotal();
}

private void UpdateTotal()
{
    int total = 0;
    foreach (var item in this.list)
        total += item;

    this.Total.Text = total.ToString();
}

The problem with the code is simply that it’s too noisy on the UI thread. The OnCollectionChanged method is called ten thousand times, and the list is totalled ten thousand times as each integer and the UI is also updated tens of thousands of times. Obviously this example is a little contrived but I’m sure you can think of some real world scenarios or maybe you’ve seen code like this in the wild.

To give you some idea of how the performance degrades on my machine here’s the debug output for this sample application, which displays the total time it takes, in milliseconds, along with how many items are currently in the list; remember that ten thousand items are appended each time Add Items is clicked:

Time taken (milliseconds): 787.375,   # List Items: 10000
Time taken (milliseconds): 2084.1261, # List Items: 20000
Time taken (milliseconds): 3344.678,  # List Items: 30000
Time taken (milliseconds): 4715.5841, # List Items: 40000
Time taken (milliseconds): 5948.9176, # List Items: 50000
Time taken (milliseconds): 7232.911,  # List Items: 60000

Assuming that we all agree that while this is a contrived example it is still a real world problem that needs a solution; and that solution is the WPF Dispatcher and a single boolean flag. Take a look at the following video that I put together to demonstrate how badly the current code impacts the UI thread, and how massive the improvement is by using the Dispatcher and an invalidate approach, as opposed to update approach:

Here are the the changes to OnCollectionChanged and UpdateTotal methods, and the new InvalidateTotal method that makes this approach work:

private bool isTotalValid;

private void OnCollectionChanged(object sender, NotifyCollectionChangedEventArgs e)
{
    InvalidateTotal();
}

private void InvalidateTotal()
{
    if (this.isTotalValid)
    {
        this.isTotalValid = false;
        this.Dispatcher.BeginInvoke(DispatcherPriority.Normal, (ThreadStart)delegate
        {
            UpdateTotal();
        });
    }
}

private void UpdateTotal()
{
    int total = 0;
    foreach (var item in this.list)
        total += item;

    this.Total.Text = total.ToString();
    this.isTotalValid = true;
}

With the code above, a new flag has been introduced: isTotalValid, which indicates whether the UpdateTotal method should be called. The OnCollectionChanged method no longer invokes UpdateTotal directly, instead it calls a new method called InvalidateTotal. The new method checks the isTotalValid flag, and if the total is valid promptly marks the total as invalid and queues a asynchronous call to UpdateTotal by using the Dispatcher.

By doing this the call to UpdateTotal has been placed on the Dispatcher’s message queue behind the currently executing call, effectively delaying the call to the UpdateTotal method until after the current thread becomes idle or the scheduler decides to let someone else have a turn, meaning that in most cases the UpdateTotal method is called only once, but InvalidateTotal is called thousands of times. Finally, the UpdateTotal method marks the total as valid once more, and the cycle begins again.

The key takeaway here, is invalidate rather than update; this is an approach adopted all over WPF, and one that I will certainly be adopting in my WPF code. I also want to offer a big thank you to Robby Ingebretsen, Jaime Rodriguez, Mike Hillberg, Lee Brenner, Laurent Bugnion and particularly for his help with this post Jonathan Russ, who explained this concept in the Hiking Mount Avalon session.

You can download the sample application from here: PaulJ.InvalidateOftenUpdateOnce.zip

As usual if you have any comments, questions, flames, enhancements I would love to hear from you. In the meantime think deeply and enjoy.

2 comments:

Oleg Mihailik said...

There's a race condition in your implementation.

Should be:

private void InvalidateTotal()
{
if (this.isTotalValid)
{
this.isTotalValid = false;
this.Dispatcher.BeginInvoke(DispatcherPriority.Normal, (ThreadStart)delegate
{
// put this BEFORE calculation
this.isTotalValid = true;
UpdateTotal();
});
}
}

Imagine a new change occurs during UpdateTotal. In this case you would need to recalculate again, but with your version that change will be lost.

Because of that I usually call the flag isRecalculationQueried, because the meaning is slightly different. The decision of whether to query another update depends not on whether the total is already valid. The key question is whether the recalculation is already posted.

Paul said...

Hey Oleg, thank you very much for your feedback, I greatly appreciate it; you are right, there is a race condition in there. In fact, there are a number of, arguably bigger, issues with the code when it comes to production ready multithreading. To name but one, the access to the list is not synchronized therefore we could try to update the list whist it is being enumerated – incidentally if we fix that one issue the race condition you mention is massively reduced to the point where it may never occur.

I really appreciate your comments and you taking the time to read the post; however, I wanted to keep the code as simple as possible to illustrate the point of the technique. My hope is that I achieved that goal and that your comment will make obvious to others what I failed to do, which is point out that this code needs some work before you should use it in a production system.

Thanks again
-PJ