Table of Contents
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);
}
double percentComplete =
((double)n / (double)numberToCompute);
if (percentComplete > highestPercentageReached)
{
highestPercentageReached = percentComplete;
ReportProgress();
}
return result;
}
private void ReportProgress() {
}
}
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.
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
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 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 |
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:
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.
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:
...
double percentComplete =
((double)n / (double)numberToCompute);
if (percentComplete > highestPercentageReached)
{
highestPercentageReached = percentComplete;
directReporter.Progress = percentComplete;
}
...
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() {
...
}
void h() {
...
}
void i() {
...
}
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) {
IReporterImpStep i = ReporterImpFactory.CreateStep(r,
new EvenSteps(3));
g(i.CreateSubReporter());
h(i.CreateSubReporter()); i(i.CreateSubReporter());
i.Step(); }
void g(IReporter r) {
IReporterImpStep i = ReporterImpFactory.CreateStep(r, new EvenSteps(100));
for (int j=0; j < 100; j++) {
...
i.Step();
}
}
void h(IReporter r) {
IReporterImpStep i = ReporterImpFactory.CreateStep(r,
new IndividualSteps(1, 2, 4, 8));
for (int j=0; j < 4; j++) {
...
i.Step();
}
}
void i(IReporter r) {
...
}
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)
{
result = n;
}
else
{
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:
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 (this.currentProgressBinding != null)
{
this.barProgress.DataBindings.Remove(this.currentProgressBinding);
this.currentProgressBinding = null;
}
{
int nUpdates = 0;
NewsCaster newsCaster = new NewsCaster();
if (Control.ModifierKeys == Keys.Control)
newsCaster.EnableProgressResultDlg = true;
this.currentProgressBinding =
this.barProgress.DataBindings.Add("Value", newsCaster, "Progress");
newsCaster.PropertyChanged += (_sender, _e) =>
{
lblUpdates.Text = nUpdates.ToString();
lblTimeElapsed.Text = newsCaster.TimeElapsed.ToString();
lblTimeEstimated.Text = newsCaster.TimeEstimated.ToString();
nUpdates++;
};
newsCaster.Finished += () => {
};
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) =>
{
fib.Compute(paramN, newsCaster.CreateReporter());
newsCaster.Finish();
});
}
}
The class diagram for the news caster construct is shown here:
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!
During research for this article, I found the following resources helpful:
- On threading in C# in general:
- On the .NET
BackgroundWorker class, a simple way of creating a background task. The ProgressTracker library can be used together with the BackgroundWorker class.
- On the
System.Threading namespace:
- On synchronization contexts (is used in the news caster object to allow the transition of events from the worker to the UI thread)
- On the Task Parallel Library (TPL) (
System.Threading.Tasks namespace) introduced in the .NET Framework 4:
- On Cancellation:
