Progress Reporting Framework

Doc Lobster

4.82/5 (10 votes)

Sep 7, 2011

CPOL

9 min read

31822

836

Reporting Progress for Complex Algorithms

Download source - 30.22 KB

Introduction
Project Goals
Background
The Sample Application
Using the Code

Preparing the Algorithm to be Tracked
Tracking of Complex Algorithms
Preparing the Windows Forms Perspective

Points of Interest
References
History

Introduction

When it comes to reporting progress from a background algorithm, the key problem seems to be selecting a nice, trendy and bug-free progress bar that displays exactly where you want it to be. For this, please have a look at the category Progress Controls.

This article is not about showing the progress of an operation, but on how to estimate its progress correctly. This is a topic often neglected.

Beware of the "subtle" irony in the following: It is a well-known fact that progress bars indicate anything but the progress - therefore it is perfectly sensible if a progress bar rushes from 0 to 75% within 3 seconds, waits there for 5 minutes (okay, people tend to start wondering intensely what's going on after 1-3 minutes of idling) and then immediately jumps to completion.

An example for this behavior in progress reporting is found in the MSDN example for the BackgroundWorker class. If you make the effort to copy and paste the example into a blank project, you will notice that the progress indication starts fast and then gradually slows down while the progressing.

This is because of a good idea gone bad. The sample uses the recursive calculation of a Fibonacci number as a sample and reports progress on it. This algorithm basically is as follows:

private long ComputeRecursive(int n)
{
    long result = 0;

    if (n < 2)
    {
        result = n;
    }
    else
    {
        result = ComputeRecursive(n - 1) +
                 ComputeRecursive(n - 2);
    }
}

In order to report the progress, it is extended in the following way:

public class MSDNStyleFibonacci
{
    private int numberToCompute = 0;
    private double highestPercentageReached = 0;

    public long Compute(int n)
    {
        this.numberToCompute = n;
        this.highestPercentageReached = 0;

        return ComputeRecursive(n);
    }

    private long ComputeRecursive(int n)
    {
        long result = 0;

        if (n < 2)
        {
            result = n;
        }
        else
        {
            result = ComputeRecursive(n - 1) +
                     ComputeRecursive(n - 2);
        }

        // Report progress as a percentage of the total algorithm.
        double percentComplete =
            ((double)n / (double)numberToCompute);

        if (percentComplete > highestPercentageReached)
        {
            highestPercentageReached = percentComplete;
            ReportProgress();
        }

        return result;
    }

		private void ReportProgress() {
        // Report the progress ...
		}
}

The current progress is therefore stored in highestPercentageReached (At the moment, we don't talk about how this value is reported - this is discussed in the MSDN sample and is not of interest here).

The problem with this sample is that highestPercentageReached does not resemble the progress of the algorithm accurately. It is true that there is a dependency between both values, but they are not identical.

The good thing mentioned above about this way of progress calculation is that it does not cause progress report spamming. For fib(40), there will logically not more than 40 progress updates. This is a good thing, as progress updates occur over thread boundaries and therefore take substantial time. Too many of these transitions will effectively stall an application.

Project Goals

The ProgressTracker project aims at:

Delivering a reusable and extensible framework that simplifies progress tracking of an algorithm running in a background thread
Giving a realistic time estimation for the entire algorithm so the application user can tell whether its permissible to take the whole day off or just to go for a coffee break

The following side considerations have been identified:

Minimize the risk of update spamming
Minimize the time needed for progress calculation (It is of no use if the progress calculation is the part of the algorithm that makes progress tracking necessary)
Allow for the fact that progress tracking is not always necessary and therefore can be disabled without changing the tracked algorithm

Things that are out of scope:

Reporting progress from an algorithm consisting of more than one thread
Other threading mechanisms than the one (ThreadPool.QueueUserWorkItem(...)) used in the sample code
Loosely related functionality such as algorithm cancellation are not included

Background

In order to work with this project properly, fundamental knowledge about working with Windows Forms and background threads is advised. Please see the references list at the bottom of this article for more information.

The Sample Application

The sample application allows to calculate progress on the Fibonacci algorithm in two different ways which are selectable in a drop-down box. As the progress calculation for the TrackedFibonacci is more complex than the MSDNStyleFibonacci sample, there are different numbers of n useful as testing values (the maximal accepted value is 40):

Algorithm	`n`
`TrackedFibonacci`	~30
`MSDNStyleFibonacci`	~40

The sample application

In order to visualize the progress tracking quality, the library code (not the sample code) provides a dialog that shows how the progress and the time estimation evolves over time:

Using the Code

The basic concept is a symbiosis of the following classes:

A NewsCaster object responsible for calculating the process of the entire algorithm and enforcing the update of the UI according to it
A hierarchy of IReporter(Imp) objects that report the progress of tracked sub-algorithms to the news caster

In the following, the usage of these classes and interfaces will be explained.

Preparing the Algorithm to be Tracked

The basic idea behind the progress tracker is to provide a IReporter reference to the tracked algorithm represented by a function. In the Fibonacci example (see "fibonacci.cs"), this function is represented by the Compute(...) method:

public class TrackedFibonacci : IFibonacci
{
    public long Compute(int n, IReporter updater) {
        ...
    }
    ...
}

As the caller of this method does not know anything on how the progress is going to be reported, the IReporter is not a class to be used directly. Instead an interface is provided that is adapted by an object that implements the actual method of reporting. There currently are four options for this:

Class	Description
`ReporterImpDirect`	The direct reporter represents simple progress tracking object which is fed directly with a value between `0` and `1` representing the progress.
`ReporterImpDirectNull`	This class implements the same interface (`IReporterImpDirect`) as `ReporterImpDirect` but does not provide any functionality. It is used as transparent replacement when the progress is not tracked.
`ReporterImpStep`	This reporter implementation represents the tracked algorithm as a series of steps. These steps may have individual weights so an `EvenWeights` or `IndividualWeights` object may be passed when the reporter object is created. Also, for each step a sub-reporter may be created so sub-algorithms can be called with a `IReporter` object that works in the same way as the original one.
`ReporterImpStepNull`	This class provides the same interface (`IReporterImpStep`) as the `ReporterImpStep` class; however it does not provide any functionality.

The basic idea is as follows: If the given IReporter parameter is null, the ReporterImp...Null class variant is used. For that, a simple factory pattern is used; reporter implementation objects have to be created through the static methods of the ReporterImpFactory class.

The following example is taken from the MSDNStyleFibonacci class in the sample project:

...
private IReporterImpDirect directReporter = null;

public long Compute(int n, IReporter reporter)
{
    this.numberToCompute = n;
    this.highestPercentageReached = 0;
    this.directReporter = ReporterImpFactory.CreateDirect(reporter);

    return ComputeRecursive(n);
}
...

The progress is then set by assigning the direct reporter a new value:

...
// Report progress as a percentage of the total algorithm.
double percentComplete =
    ((double)n / (double)numberToCompute);

if (percentComplete > highestPercentageReached)
{
    highestPercentageReached = percentComplete;
    directReporter.Progress = percentComplete;
}
...

Tracking of Complex Algorithms

Imagine a situation where your algorithm calls a number of sub-algorithms that are lengthy operations by themselves. Also these sub-algorithms may divide up into others:

void f() {
    g();
    h();
    i();
}

void g() {
    // Do something tedious
    ...
}

void h() {
    // Do something creative
    ...
}

void i() {
    // Do something spectacular
    ...
}

For this type of progress tracking situation, we can use classes derived from the IReporterImpStep interface. It offers the option to spawn sub-reporters that can be used to report progress from functions called within the algorithm using IReporterImpStep.CreateSubReporter(). Alternatively, the progress may be indicated by simply stepping forward (IReporterImpStep.Step()). The tracked variant of the code sample above could look like follows:

void f(IReporter r) {
    // For the step reporter, it is necessary to inform the implementation about
    // the number of steps to take:
    IReporterImpStep i = ReporterImpFactory.CreateStep(r,
        new EvenSteps(3));

    g(i.CreateSubReporter());
    h(i.CreateSubReporter()); // Calling CreateSubReporter repetitively
    i(i.CreateSubReporter()); // automatically finishes the previous step

   i.Step(); // Make sure the third step is finished before returning
}

void g(IReporter r) {
    IReporterImpStep i = ReporterImpFactory.CreateStep(r, new EvenSteps(100));
    for (int j=0; j < 100; j++) {
        // Do something repetitively
        ...
        i.Step();
    }
}

void h(IReporter r) {
    // Do something which doubles its calculation time with every step
    IReporterImpStep i = ReporterImpFactory.CreateStep(r,
        new IndividualSteps(1, 2, 4, 8));

    for (int j=0; j < 4; j++) {
        ...
        i.Step();
    }
}

void i(IReporter r) {
    // Do something spectacular that reporting cannot be done on
    ...
}

The TrackedFibonacci sample class shows how to make use of the IReporterImpStep interface and the IndividualSteps helper class:

public class TrackedFibonacci : IFibonacci
{
    public long Compute(int n, IReporter updater)
    {
        return ComputeRecursive(n, updater);
    }

    private long ComputeRecursive(int n, IReporter reporter)
    {
        long result = 0;

        if (n < 2)
        {
            // It is acceptable to add a progress reporter for n = 0, 
            // 1 but the result is only
            // a performance drag.
            // var reporterImpl = 
            //	ReporterImpFactory.CreateStep(reporter, new EvenSteps(1));
            result = n;
            // reporterImpl.Step();
        }
        else
        {
            // use golden ratio for relative effort: fib(n)/fib(n-1) = 1.618
            var reporterImpl = ReporterImpFactory.CreateStep
				(reporter, new IndividualSteps(1.618, 1));

            result = ComputeRecursive(n - 1, reporterImpl.CreateSubReporter());
            result += ComputeRecursive(n - 2, reporterImpl.CreateSubReporter());
        }

        return result;
    }
}

In the following class diagram, the classes and interfaces needed for the algorithm perspective are shown:

Preparing the Windows Forms Perspective

The first thing to do is adding a news caster object to the function that is going to start the tracked algorithm. In the sample application, this is the Form1.Go_Click(...) method. The news caster object provides a property NewsCaster.Progress that can be bound to a progress control in the form. Alternatively, the PropertyChanged event provided by the news caster object may be handled directly.

When the tracked algorithm is started, it has to be given a root reporter that is generated by the news caster object. This is done using the NewsCaster.CreateReporter() method.

Before the tracked algorithm completes, the tracked algorithm should call NewsCaster.Finish() in order to signal that it has ended (whatever the current progress value says). This is a safeguard in case the progress calculation is broken for some reason and therefore the algorithm does not finish exactly on reaching 100%.

The whole Go_Click-method is shown in the following:

private void Go_Click(object sender, EventArgs e)
{
    // If a tracked algorithm is already running, disconnect it from
    // the progress bar
    if (this.currentProgressBinding != null)
    {
        this.barProgress.DataBindings.Remove(this.currentProgressBinding);
        this.currentProgressBinding = null;
    }

    {
        int nUpdates = 0;

        // Instantiate the news caster object:
        NewsCaster newsCaster = new NewsCaster();

        // Optionally show the results in a diagram. Storing the data for
        // the diagrams may take some time, so expect that the algorithm will
        // take longer if this is enabled.
        if (Control.ModifierKeys == Keys.Control) 
			newsCaster.EnableProgressResultDlg = true;

        // Add a databinding for the progress bar
        this.currentProgressBinding = 
		this.barProgress.DataBindings.Add("Value", newsCaster, "Progress");

        // Use the ProperyChanges event for text box updates (this is just to
        // explain the difference)
        newsCaster.PropertyChanged += (_sender, _e) =>
        {
            lblUpdates.Text = nUpdates.ToString();
            lblTimeElapsed.Text = newsCaster.TimeElapsed.ToString();
            lblTimeEstimated.Text = newsCaster.TimeEstimated.ToString();

            nUpdates++;
        };

        newsCaster.Finished += () => {
            // The Finished event may be used to perform an operation in the UI
            // thread once the tracked algorithm finishes.
        };

        IFibonacci fib = comboFib.SelectedItem as IFibonacci;

        int paramN = Convert.ToInt32(textBoxParamN.Text);
        if (paramN < 2) paramN = 2;
        if (paramN > 40) paramN = 40;
        textBoxParamN.Text = paramN.ToString();

        ThreadPool.QueueUserWorkItem((state) =>
        {
            // Pass the newly created root reporter to
            // the tracked algorithm
            fib.Compute(paramN, newsCaster.CreateReporter());

            // Signal Finalization (will disallow further progress
            // updates and will raise the Finished event in the UI thread)
            newsCaster.Finish();
        });
    }
}

The class diagram for the news caster construct is shown here:

Points of Interest

There are two ways of moving pieces of information between separate contexts; pushing and polling. Here, pushing would be that the news caster object updates the UI as soon as its progress increases. On the other hand, polling would be to initialize a timer in the UI thread and update the progress in a fixed time interval.

The advantage of polling is that update spamming is inherently prevented. The primary cost is that the UI thread itself has to ask for updates which is typically done using a timer. In Windows Forms, this would be Windows.Forms.Timer. An alternative is the System.Threading.DispatcherTimer which is typically used in WPF.

The advantage of pushing is that a timer is not required, the major drawback is that if updates are pushed to the UI too often, the application will stall. Therefore, I decided to use a combination of both approaches; updates are pushed to the UI, but only if a certain time span (currently hard-coded to 100 ms) has passed since the last update.

Still, it is sensible to think about progress tracking operations and reducing them to a number so that they are minimal regarding to the tracked operation. On the other hand, there should be still enough updates in order to show the current progress properly.

That's it for now, happy progress tracking!