Estimating time left in C++11

Question

I'm writing a progress bar class that outputs an updated progress bar every n ticks to an std::ostream:

class progress_bar
{
public:
  progress_bar(uint64_t ticks)
    : _total_ticks(ticks), ticks_occured(0),
      _begin(std::chrono::steady_clock::now())
  ...
  void tick()
  {
    // test to see if enough progress has elapsed
    //  to warrant updating the progress bar
    //  that way we aren't wasting resources printing
    //  something that hasn't changed
    if (/* should we update */)
    {
      ...
    }
  }
private:
  std::uint64_t _total_ticks;
  std::uint64_t _ticks_occurred;
  std::chrono::steady_clock::time_point _begin;
  ...
}

I would like to also output the time remaining. I found a formula on another question that states time remaining is (variable names changed to fit my class):

time_left = (time_taken / _total_ticks) * (_total_ticks - _ticks_occured)

The parts I would like to fill in for my class are the time_left and the time_taken, using C++11's new <chrono> header.

I know I need to use a std::chrono::steady_clock, but I'm not sure how to integrate it into code. I assume the best way to measure the time would be a std::uint64_t as nanoseconds.

My questions are:

1. Is there a function in <chrono> that will convert the nanoseconds into an std::string, say something like "3m12s"?
2. Should I use the std::chrono::steady_clock::now() each time I update my progress bar, and subtract that from _begin to determine time_left?
3. Is there a better algorithm to determine time_left

Answer 1

Is there a function in that will convert the nanoseconds into an std::string, say something like "3m12s"?

No. But I'll show you how you can easily do this below.

Should I use the std::chrono::steady_clock::now() each time I update my progress bar, and subtract that from _begin to determine time_left?

Yes.

Is there a better algorithm to determine time_left

Yes. See below.

Edit

I had originally misinterpreted "ticks" as "clock ticks", when in actuality "ticks" has units of work and _ticks_occurred/_total_ticks can be interpreted as %job_done. So I've changed the proposed progress_bar below accordingly.

I believe the equation:

time_left = (time_taken / _total_ticks) * (_total_ticks - _ticks_occured)

is incorrect. It doesn't pass a sanity check: If _ticks_occured == 1 and _total_ticks is large, then time_left approximately equals (ok, slightly less) time_taken. That doesn't make sense.

I am rewriting the above equation to be:

time_left = time_taken * (1/percent_done - 1)

where

percent_done = _ticks_occurred/_total_ticks

Now as percent_done approaches zero, time_left approaches infinity, and when percent_done approaches 1, 'time_left approaches 0. When percent_done is 10%, time_left is 9*time_taken. This meets my expectations, assuming a roughly linear time cost per work-tick.

class progress_bar
{
public:
  progress_bar(uint64_t ticks)
    : _total_ticks(ticks), _ticks_occurred(0),
      _begin(std::chrono::steady_clock::now())
//  ...
    {}
  void tick()
  {
    using namespace std::chrono;
    // test to see if enough progress has elapsed
    //  to warrant updating the progress bar
    //  that way we aren't wasting resources printing
    //  something that hasn't changed
    if (/* should we update */)
    {
        // somehow _ticks_occurred is updated here and is not zero
        duration time_taken = Clock::now() - _begin;
        float percent_done = (float)_ticks_occurred/_total_ticks;
        duration time_left = time_taken * static_cast<rep>(1/percent_done - 1);
        minutes minutes_left = duration_cast<minutes>(time_left);
        seconds seconds_left = duration_cast<seconds>(time_left - minutes_left);
    }
  }
private:
  typedef std::chrono::steady_clock Clock;
  typedef Clock::time_point time_point;
  typedef Clock::duration duration;
  typedef Clock::rep rep;
  std::uint64_t _total_ticks;
  std::uint64_t _ticks_occurred;
  time_point _begin;
  //...
};

Traffic in std::chrono::durations whenever you can. That way <chrono> does all the conversions for you. typedefs can ease the typing with the long names. And breaking down the time into minutes and seconds is as easy as shown above.

As bames53 notes in his answer, if you want to use my <chrono_io> facility, that's cool too. Your needs may be simple enough that you don't want to. It is a judgement call. bames53's answer is a good answer. I thought these extra details might be helpful too.

Edit

I accidentally left a bug in the code above. And instead of just patch the code above, I thought it would be a good idea to point out the bug and show how to use <chrono> to fix it.

The bug is here:

duration time_left = time_taken * static_cast<rep>(1/percent_done - 1);

and here:

typedef Clock::duration duration;

In practice steady_clock::duration is usually based on an integral type. <chrono> calls this the rep (short for representation). And when percent_done is greater than 50%, the factor being multiplied by time_taken is going to be less than 1. And when rep is integral, that gets cast to 0. So this progress_bar only behaves well during the first 50% and predicts 0 time left during the last 50%.

The key to fixing this is to traffic in durations that are based on floating point instead of integers. And <chrono> makes this very easy to do.

typedef std::chrono::steady_clock Clock;
typedef Clock::time_point time_point;
typedef Clock::period period;
typedef std::chrono::duration<float, period> duration;

duration now has the same tick period as steady_clock::duration but uses a float for the representation. And now the computation for time_left can leave off the static_cast:

duration time_left = time_taken * (1/percent_done - 1);

Here's the whole package again with these fixes:

class progress_bar
{
public:
  progress_bar(uint64_t ticks)
    : _total_ticks(ticks), _ticks_occurred(0),
      _begin(std::chrono::steady_clock::now())
//  ...
    {}
  void tick()
  {
    using namespace std::chrono;
    // test to see if enough progress has elapsed
    //  to warrant updating the progress bar
    //  that way we aren't wasting resources printing
    //  something that hasn't changed
    if (/* should we update */)
    {
        // somehow _ticks_occurred is updated here and is not zero
        duration time_taken = Clock::now() - _begin;
        float percent_done = (float)_ticks_occurred/_total_ticks;
        duration time_left = time_taken * (1/percent_done - 1);
        minutes minutes_left = duration_cast<minutes>(time_left);
        seconds seconds_left = duration_cast<seconds>(time_left - minutes_left);
        std::cout << minutes_left.count() << "m " << seconds_left.count() << "s\n";
    }
  }
private:
  typedef std::chrono::steady_clock Clock;
  typedef Clock::time_point time_point;
  typedef Clock::period period;
  typedef std::chrono::duration<float, period> duration;
  std::uint64_t _total_ticks;
  std::uint64_t _ticks_occurred;
  time_point _begin;
  //...
};

Nothing like a little testing... ;-)

Answer 2

The chrono library includes types for representing durations. You shouldn't convert that to a flat integer of some 'known' unit. When you want a known unit just use the chrono types, e.g. 'std::chrono::nanoseconds', and duration_cast. Or create your own duration type using a floating point representation and one of the SI ratios. E.g. std::chrono::duration<double,std::nano>. Without duration_cast or a floating point duration rounding is prohibited at compile time.

The IO facilities for chrono didn't make it into C++11, but you can get source from here. Using this you can just ignore the duration type, and it will print the right units. I don't think there's anything there to that will show the time in minutes, seconds, etc., but such a thing shouldn't be too hard to write.

I don't know that there's too much reason to be concerned about calling steady_clock::now() frequently, if that's what your asking. I'd expect most platforms to have a pretty fast timer for just that sort of thing. It does depend on the implementation though. Obviously it's causing an issue for you, so maybe you could only call steady_clock::now() inside the if (/* should we update */) block, which should put a reasonable limit on the call frequency.

Obviously there are other ways to estimate the time remaining. For example instead of taking the average over the progress so far (which is what the formula you show does), you could take the average from the last N ticks. Or do both and take a weighted average of the two estimates.