Click here to Skip to main content
Click here to Skip to main content
Go to top

Remaining Timer

, 2 Jul 2008
Rate this:
Please Sign up or sign in to vote.
Estimate the duration of an operation using linear regression.

Introduction

This article suggests a simple way to estimate the remaining time of a running process. In many cases, when a process is active or a progress bar is shown, it can be very helpful showing the estimated time left for the process to complete. While everybody has experienced cases where an estimated time box jumps from 10 minutes to 3 hours and back to 4 minutes, the estimate procedure described in this article will try to deal with this phenomenon and other annoying effects by making use of limited history and linear regression.

Background

From time to time, developers have faced a situation where a user is requested to wait for quite some time before he can regain control over his computer. If could be a long upgrade procedure, a heavy disk scan, re-indexing, network scan… you name it. While some users will go to the coffee machine every time they see ‘This could take a while’, others might get very annoyed if the process takes more than a reasonable amount of time. Defining reasonable can sometimes be based on how old and temperate the user is.

So, I was facing some of these issues, on different occasions, like when upgrading a database, parsing large data files, compressing and encoding files etc. Some of these processes can be 10 minutes long, others could take as much as two days (even when all four cores are working 100%). A time estimator was needed, but a kind that would be able to deal with the following guidelines:

  • Simple and not too resource consuming.
  • Estimate by recent history – If the computer was hanged by a virus scan at 4:00am for half an hour, it shouldn’t make a difference if the user checks the remaining time at 9:00am.
  • Deals with performance change – Some of the processes might take longer than others, some processes are multi-threaded while others are not, and a background process may slow down if a user decided to view a movie while the process is running.
  • Deals with different types of progress – From percent (1-100) to number of files.

The Algorithm

Maintaining the History

The idea is simple. While the process is running, the developer updates the timer by adding a mark with a specific value which is stored in a linked list (oldest to newest). The mark's timestamp is taken from the internal clock running since the initialization of the timer. The list is kept within a specific time frame, which means:

LastItemOnTheList.Time – FirsItemOnTheListt.Time <= Time Frame

This is done so the estimation will be done only according to the recent history. The Time Frame can be defined by the user according to what he estimates will be the overall time of the process. If a process should take around 15 minutes, then a one minute time frame is fine. If a process should take 2 days, then a 10-15 minutes time frame will produce better results.

Updating the timer is important, and it should be done wherever possible, and not necessarily in even time periods. For instance, if the process is running and the process has some sort of a completion value, add it every time it changes.

Estimating

Once enough data is gathered, the user can initiate a ‘Get remaining time estimate’ by calling the right method. I used linear regression on the recent history to determine the estimated elapsed time of the process, and by subtracting the current clock from the elapsed time, the estimated remaining time is found.

You can read more about linear regression here.

Using the Code

The code is easy to follow, and I didn’t add any of the optimizations in order to make the code simple to follow.

Mark’ is used to add a value to the list. Estimation is done only if new data is added or removed from the list.

public void Mark(double Value) {
   TimedValue TV = new TimedValue(_SW.ElapsedMilliseconds, Value);
   lock (_SyncLock) {
      _Data.AddFirst(TV);
      _NeedToRecomputeEstimation = true;
      ClearOutOfWindowData(); // remove out of window data
   }
}

Getting the remaining estimation is done by recomputing the linear coefficients (using linear regression) and then computing the remaining time (imagine the Y axis contains the values and the X axis contains the time).

public TimeSpan GetRemainingEstimation() {
   if (_NeedToRecomputeEstimation) {
      lock (_SyncLock) {
         ClearOutOfWindowData();
         if (_Data.Count != 0) {
            // compute linear coefficients using linear regression
            ComputeLinearCoefficients();
            double RemeiningMilliseconds = (_TargetValue - _LastYint) / 
                   _LastSlope; //  y = m*x+b --> (y-b)/m = x
            if (double.IsNaN(RemeiningMilliseconds) || 
                       double.IsInfinity(RemeiningMilliseconds)) {
               _LastElapsed = TimeSpan.MaxValue;
               // no data ot invalid data
            } else {
               _LastElapsed = TimeSpan.FromMilliseconds(RemeiningMilliseconds);
            }
            _NeedToRecomputeEstimation = false;
            // until data list is changed again.
         }
      }
   }
   if (_LastElapsed != TimeSpan.MaxValue) {
      return _LastElapsed - _SW.Elapsed;
   } else {
      return TimeSpan.MaxValue;
   }
}

To the code, I’ve attached a short test program. Clicking any key will increase the value (0-100). Experiment by clicking fast\slow. The correlation of the data (in brackets) can represent ‘how good the estimation is’, where 0.0 is bad and 1.0 is very good.

Remarks

  • The complexity of the algorithem is O(1) for adding data and O(N) for estimating the computation. It is also possible to estimate in O(1) but then the code is less understandable (add\subtract the data to global summaries and compute the estimation, if needed).
  • There are some issues like what happens if there is no data in the time frame and maybe there is a threshold for the number of elements in the linked list. All improvements and comments are most welcomed.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Gilad Kapelushnik
Team Leader
Israel Israel
Gilad holds a B.Sc in Computer Eng. from the Technion IIT.

Comments and Discussions

 
Generalremaining time is still growing! Pinmemberrapid2k228-Jul-09 7:38 
GeneralRe: remaining time is still growing! PinmemberGilad Kapelushnik29-Jul-09 6:55 
GeneralRe: remaining time is still growing! Pinmemberrapid2k230-Jul-09 11:22 
GeneralRe: remaining time is still growing! Pinmemberrapid2k230-Jul-09 11:29 
GeneralMy vote of 1 PinmemberMember 195047220-Jun-09 6:03 
GeneralRe: My vote of 1 PinmemberGilad Kapelushnik28-Jul-09 21:16 
GeneralGood work PinmemberJames Ogunsan7-May-09 4:01 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140916.1 | Last Updated 2 Jul 2008
Article Copyright 2008 by Gilad Kapelushnik
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid