How can I eliminate the "jitter" from my "estimated time remaining" (and ETA) calculation?

Question

I have an application that, while performing a background task, shows a progress bar with an "estimated time remaining" calculation (eg "5 seconds remaining") and a "estimated time of completion" (eg "complete at 12:59:59"), or as I call it, the ETA.

The algorithm for calculating this ETA basically takes the "rolling average" of progress over time:
1. Each progress event gets added to a queue with the current time.
2. After a certain duration (eg. 10s), items are removed from the queue.
3. The ETA is extrapolated from the first and last items in the queue.
The source code is available if you care: ETACalculator.cs

However, there's a jitter problem. As each progress event is added to the calculation, the ETA will be updated slightly. Let's say that the ETA changes by only 0.1s. This small jitter easily causes the ETA to "flutter". For example, instead of seeing a smooth progression from 5s, 4s, 3s, etc..., I see 5-5-5-4-5-4-5-4-5-4-4-4.

I was thinking of just reducing the updates to 1-per-second, but then the progress bar is less smooth, and also I'd really like "actual" slowdowns to be shown real time.

I'm having trouble coming up with a simple algorithm that reduces this jumpy jitter. How can I remove the jitter?

Answer 1

Separate the actual jittery progress and the displayed progress into two separate variables.

Update the jittery progress as you do now.

At a regular (relatively quick) interval, update the displayed progress to approach the actual progress.

A simple approach algorithm would be to average the two values

display_progress = (display_progress + actual_progress) / 2 

This will dampen the value to reflect past values and not just the immediate value.

You can also refine the smoothness by using:

display_progress = (P) * display_progress + (1.0-P) * actual_progress 

Where P is a constant value between 0.0 and 1.0.

Edit:

This is one of many filters that could be used. This one is nice in that it doesn't require much bookkeeping.

However, getting perfect output is not going to be an option, because the flaw is in your input. The difference between "jitter" and "actual slowdowns" is only observable after it has happened.

Answer 2

Not quite clear on your algorithm without seeing code, but when you update your ETA just first check the current ETA and only update it if the new value is lower than the old.