alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@119:  *
alpar@209:  * This file is a part of LEMON, a generic C++ optimization library.
alpar@119:  *
alpar@1270:  * Copyright (C) 2003-2013
alpar@119:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@119:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@119:  *
alpar@119:  * Permission to use, modify and distribute this software is granted
alpar@119:  * provided that this copyright notice appears in all copies. For
alpar@119:  * precise terms see the accompanying LICENSE file.
alpar@119:  *
alpar@119:  * This software is provided "AS IS" with no warranty of any kind,
alpar@119:  * express or implied, and with no claim as to its suitability for any
alpar@119:  * purpose.
alpar@119:  *
alpar@119:  */
alpar@119: 
alpar@119: #ifndef LEMON_TIME_MEASURE_H
alpar@119: #define LEMON_TIME_MEASURE_H
alpar@119: 
alpar@119: ///\ingroup timecount
alpar@119: ///\file
alpar@119: ///\brief Tools for measuring cpu usage
alpar@119: 
deba@126: #ifdef WIN32
alpar@511: #include <lemon/bits/windows.h>
deba@126: #else
alpar@507: #include <unistd.h>
alpar@119: #include <sys/times.h>
deba@126: #include <sys/time.h>
deba@126: #endif
alpar@119: 
alpar@143: #include <string>
alpar@119: #include <fstream>
alpar@119: #include <iostream>
alpar@1222: #include <lemon/math.h>
alpar@119: 
alpar@119: namespace lemon {
alpar@119: 
alpar@119:   /// \addtogroup timecount
alpar@119:   /// @{
alpar@119: 
alpar@119:   /// A class to store (cpu)time instances.
alpar@119: 
alpar@119:   /// This class stores five time values.
alpar@119:   /// - a real time
alpar@119:   /// - a user cpu time
alpar@119:   /// - a system cpu time
alpar@119:   /// - a user cpu time of children
alpar@119:   /// - a system cpu time of children
alpar@119:   ///
alpar@119:   /// TimeStamp's can be added to or substracted from each other and
alpar@119:   /// they can be pushed to a stream.
alpar@119:   ///
alpar@119:   /// In most cases, perhaps the \ref Timer or the \ref TimeReport
alpar@119:   /// class is what you want to use instead.
alpar@119: 
alpar@119:   class TimeStamp
alpar@119:   {
deba@126:     double utime;
deba@126:     double stime;
deba@126:     double cutime;
deba@126:     double cstime;
deba@126:     double rtime;
alpar@209: 
alpar@1222:   public:
alpar@1222:     ///Display format specifier
alpar@1222: 
alpar@1222:     ///\e
alpar@1222:     ///
alpar@1222:     enum Format {
alpar@1222:       /// Reports all measured values
alpar@1222:       NORMAL = 0,
alpar@1222:       /// Only real time and an error indicator is displayed
alpar@1222:       SHORT = 1
alpar@1222:     };
alpar@1222: 
alpar@1222:   private:
alpar@1222:     static Format _format;
alpar@1222: 
alpar@209:     void _reset() {
deba@126:       utime = stime = cutime = cstime = rtime = 0;
alpar@119:     }
alpar@119: 
alpar@119:   public:
alpar@119: 
alpar@1222:     ///Set output format
alpar@1222: 
alpar@1222:     ///Set output format.
alpar@1222:     ///
alpar@1222:     ///The output format is global for all timestamp instances.
alpar@1222:     static void format(Format f) { _format = f; }
alpar@1222:     ///Retrieve the current output format
alpar@1222: 
alpar@1222:     ///Retrieve the current output format
alpar@1222:     ///
alpar@1222:     ///The output format is global for all timestamp instances.
alpar@1222:     static Format format() { return _format; }
alpar@1222: 
alpar@1270: 
alpar@119:     ///Read the current time values of the process
alpar@119:     void stamp()
alpar@119:     {
deba@126: #ifndef WIN32
alpar@119:       timeval tv;
deba@126:       gettimeofday(&tv, 0);
deba@126:       rtime=tv.tv_sec+double(tv.tv_usec)/1e6;
deba@126: 
deba@126:       tms ts;
deba@126:       double tck=sysconf(_SC_CLK_TCK);
deba@126:       times(&ts);
deba@126:       utime=ts.tms_utime/tck;
deba@126:       stime=ts.tms_stime/tck;
deba@126:       cutime=ts.tms_cutime/tck;
deba@126:       cstime=ts.tms_cstime/tck;
deba@126: #else
alpar@511:       bits::getWinProcTimes(rtime, utime, stime, cutime, cstime);
alpar@209: #endif
alpar@119:     }
alpar@209: 
alpar@119:     /// Constructor initializing with zero
alpar@119:     TimeStamp()
alpar@119:     { _reset(); }
alpar@119:     ///Constructor initializing with the current time values of the process
alpar@119:     TimeStamp(void *) { stamp();}
alpar@209: 
alpar@119:     ///Set every time value to zero
alpar@119:     TimeStamp &reset() {_reset();return *this;}
alpar@119: 
alpar@119:     ///\e
alpar@119:     TimeStamp &operator+=(const TimeStamp &b)
alpar@119:     {
deba@126:       utime+=b.utime;
deba@126:       stime+=b.stime;
deba@126:       cutime+=b.cutime;
deba@126:       cstime+=b.cstime;
deba@126:       rtime+=b.rtime;
alpar@119:       return *this;
alpar@119:     }
alpar@119:     ///\e
alpar@119:     TimeStamp operator+(const TimeStamp &b) const
alpar@119:     {
alpar@119:       TimeStamp t(*this);
alpar@119:       return t+=b;
alpar@119:     }
alpar@119:     ///\e
alpar@119:     TimeStamp &operator-=(const TimeStamp &b)
alpar@119:     {
deba@126:       utime-=b.utime;
deba@126:       stime-=b.stime;
deba@126:       cutime-=b.cutime;
deba@126:       cstime-=b.cstime;
deba@126:       rtime-=b.rtime;
alpar@119:       return *this;
alpar@119:     }
alpar@119:     ///\e
alpar@119:     TimeStamp operator-(const TimeStamp &b) const
alpar@119:     {
alpar@119:       TimeStamp t(*this);
alpar@119:       return t-=b;
alpar@119:     }
alpar@119:     ///\e
alpar@119:     TimeStamp &operator*=(double b)
alpar@119:     {
deba@126:       utime*=b;
deba@126:       stime*=b;
deba@126:       cutime*=b;
deba@126:       cstime*=b;
deba@126:       rtime*=b;
alpar@119:       return *this;
alpar@119:     }
alpar@119:     ///\e
alpar@119:     TimeStamp operator*(double b) const
alpar@119:     {
alpar@119:       TimeStamp t(*this);
alpar@119:       return t*=b;
alpar@119:     }
alpar@119:     friend TimeStamp operator*(double b,const TimeStamp &t);
alpar@119:     ///\e
alpar@119:     TimeStamp &operator/=(double b)
alpar@119:     {
deba@126:       utime/=b;
deba@126:       stime/=b;
deba@126:       cutime/=b;
deba@126:       cstime/=b;
deba@126:       rtime/=b;
alpar@119:       return *this;
alpar@119:     }
alpar@119:     ///\e
alpar@119:     TimeStamp operator/(double b) const
alpar@119:     {
alpar@119:       TimeStamp t(*this);
alpar@119:       return t/=b;
alpar@119:     }
alpar@119:     ///The time ellapsed since the last call of stamp()
alpar@119:     TimeStamp ellapsed() const
alpar@119:     {
alpar@119:       TimeStamp t(NULL);
alpar@119:       return t-*this;
alpar@119:     }
alpar@209: 
alpar@119:     friend std::ostream& operator<<(std::ostream& os,const TimeStamp &t);
alpar@209: 
alpar@119:     ///Gives back the user time of the process
alpar@119:     double userTime() const
alpar@119:     {
deba@126:       return utime;
alpar@119:     }
alpar@119:     ///Gives back the system time of the process
alpar@119:     double systemTime() const
alpar@119:     {
deba@126:       return stime;
alpar@119:     }
alpar@119:     ///Gives back the user time of the process' children
deba@126: 
alpar@209:     ///\note On <tt>WIN32</tt> platform this value is not calculated.
deba@126:     ///
alpar@119:     double cUserTime() const
alpar@119:     {
deba@126:       return cutime;
alpar@119:     }
alpar@119:     ///Gives back the user time of the process' children
deba@126: 
alpar@209:     ///\note On <tt>WIN32</tt> platform this value is not calculated.
deba@126:     ///
alpar@119:     double cSystemTime() const
alpar@119:     {
deba@126:       return cstime;
alpar@119:     }
alpar@119:     ///Gives back the real time
deba@126:     double realTime() const {return rtime;}
alpar@119:   };
alpar@119: 
alpar@528:   inline TimeStamp operator*(double b,const TimeStamp &t)
alpar@119:   {
alpar@119:     return t*b;
alpar@119:   }
alpar@209: 
alpar@119:   ///Prints the time counters
alpar@119: 
alpar@119:   ///Prints the time counters in the following form:
alpar@119:   ///
alpar@119:   /// <tt>u: XX.XXs s: XX.XXs cu: XX.XXs cs: XX.XXs real: XX.XXs</tt>
alpar@119:   ///
alpar@119:   /// where the values are the
alpar@119:   /// \li \c u: user cpu time,
alpar@119:   /// \li \c s: system cpu time,
alpar@119:   /// \li \c cu: user cpu time of children,
alpar@119:   /// \li \c cs: system cpu time of children,
alpar@119:   /// \li \c real: real time.
alpar@119:   /// \relates TimeStamp
deba@126:   /// \note On <tt>WIN32</tt> platform the cummulative values are not
deba@126:   /// calculated.
alpar@119:   inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t)
alpar@119:   {
alpar@1222:     switch(t._format)
alpar@1222:       {
alpar@1222:       case TimeStamp::NORMAL:
alpar@1222:         os << "u: " << t.userTime() <<
alpar@1222:           "s, s: " << t.systemTime() <<
alpar@1222:           "s, cu: " << t.cUserTime() <<
alpar@1222:           "s, cs: " << t.cSystemTime() <<
alpar@1222:           "s, real: " << t.realTime() << "s";
alpar@1222:         break;
alpar@1222:       case TimeStamp::SHORT:
alpar@1222:         double total = t.userTime()+t.systemTime()+
alpar@1222:           t.cUserTime()+t.cSystemTime();
alpar@1222:         os << t.realTime()
alpar@1222:            << "s (err: " << round((t.realTime()-total)/
alpar@1222:                                   t.realTime()*10000)/100
alpar@1222:            << "%)";
alpar@1222:         break;
alpar@1222:       }
alpar@119:     return os;
alpar@119:   }
alpar@119: 
alpar@119:   ///Class for measuring the cpu time and real time usage of the process
alpar@119: 
alpar@119:   ///Class for measuring the cpu time and real time usage of the process.
alpar@119:   ///It is quite easy-to-use, here is a short example.
alpar@119:   ///\code
alpar@119:   /// #include<lemon/time_measure.h>
alpar@119:   /// #include<iostream>
alpar@119:   ///
alpar@119:   /// int main()
alpar@119:   /// {
alpar@119:   ///
alpar@119:   ///   ...
alpar@119:   ///
alpar@119:   ///   Timer t;
alpar@119:   ///   doSomething();
alpar@119:   ///   std::cout << t << '\n';
alpar@119:   ///   t.restart();
alpar@119:   ///   doSomethingElse();
alpar@119:   ///   std::cout << t << '\n';
alpar@119:   ///
alpar@119:   ///   ...
alpar@119:   ///
alpar@119:   /// }
alpar@119:   ///\endcode
alpar@119:   ///
alpar@119:   ///The \ref Timer can also be \ref stop() "stopped" and
alpar@119:   ///\ref start() "started" again, so it is possible to compute collected
alpar@119:   ///running times.
alpar@119:   ///
alpar@119:   ///\warning Depending on the operation system and its actual configuration
alpar@119:   ///the time counters have a certain (10ms on a typical Linux system)
alpar@119:   ///granularity.
alpar@119:   ///Therefore this tool is not appropriate to measure very short times.
alpar@119:   ///Also, if you start and stop the timer very frequently, it could lead to
alpar@119:   ///distorted results.
alpar@119:   ///
alpar@119:   ///\note If you want to measure the running time of the execution of a certain
alpar@119:   ///function, consider the usage of \ref TimeReport instead.
alpar@119:   ///
alpar@119:   ///\sa TimeReport
alpar@119:   class Timer
alpar@119:   {
alpar@119:     int _running; //Timer is running iff _running>0; (_running>=0 always holds)
alpar@119:     TimeStamp start_time; //This is the relativ start-time if the timer
alpar@119:                           //is _running, the collected _running time otherwise.
alpar@209: 
alpar@119:     void _reset() {if(_running) start_time.stamp(); else start_time.reset();}
alpar@209: 
alpar@209:   public:
alpar@119:     ///Constructor.
alpar@119: 
alpar@119:     ///\param run indicates whether or not the timer starts immediately.
alpar@119:     ///
alpar@119:     Timer(bool run=true) :_running(run) {_reset();}
alpar@119: 
kpeter@631:     ///\name Control the State of the Timer
alpar@119:     ///Basically a Timer can be either running or stopped,
alpar@119:     ///but it provides a bit finer control on the execution.
kpeter@314:     ///The \ref lemon::Timer "Timer" also counts the number of
kpeter@314:     ///\ref lemon::Timer::start() "start()" executions, and it stops
kpeter@313:     ///only after the same amount (or more) \ref lemon::Timer::stop()
kpeter@313:     ///"stop()"s. This can be useful e.g. to compute the running time
alpar@119:     ///of recursive functions.
alpar@119: 
alpar@119:     ///@{
alpar@119: 
alpar@119:     ///Reset and stop the time counters
alpar@119: 
alpar@119:     ///This function resets and stops the time counters
alpar@119:     ///\sa restart()
alpar@119:     void reset()
alpar@119:     {
alpar@119:       _running=0;
alpar@119:       _reset();
alpar@119:     }
alpar@119: 
alpar@119:     ///Start the time counters
alpar@209: 
alpar@119:     ///This function starts the time counters.
alpar@119:     ///
alpar@119:     ///If the timer is started more than ones, it will remain running
alpar@119:     ///until the same amount of \ref stop() is called.
alpar@119:     ///\sa stop()
alpar@209:     void start()
alpar@119:     {
alpar@119:       if(_running) _running++;
alpar@119:       else {
alpar@209:         _running=1;
alpar@209:         TimeStamp t;
alpar@209:         t.stamp();
alpar@209:         start_time=t-start_time;
alpar@119:       }
alpar@119:     }
alpar@119: 
alpar@209: 
alpar@119:     ///Stop the time counters
alpar@119: 
alpar@119:     ///This function stops the time counters. If start() was executed more than
alpar@119:     ///once, then the same number of stop() execution is necessary the really
alpar@119:     ///stop the timer.
alpar@209:     ///
alpar@119:     ///\sa halt()
alpar@119:     ///\sa start()
alpar@119:     ///\sa restart()
alpar@119:     ///\sa reset()
alpar@119: 
alpar@209:     void stop()
alpar@119:     {
alpar@119:       if(_running && !--_running) {
alpar@209:         TimeStamp t;
alpar@209:         t.stamp();
alpar@209:         start_time=t-start_time;
alpar@119:       }
alpar@119:     }
alpar@119: 
alpar@119:     ///Halt (i.e stop immediately) the time counters
alpar@119: 
alpar@120:     ///This function stops immediately the time counters, i.e. <tt>t.halt()</tt>
alpar@119:     ///is a faster
alpar@119:     ///equivalent of the following.
alpar@119:     ///\code
alpar@119:     ///  while(t.running()) t.stop()
alpar@119:     ///\endcode
alpar@119:     ///
alpar@119:     ///
alpar@119:     ///\sa stop()
alpar@119:     ///\sa restart()
alpar@119:     ///\sa reset()
alpar@119: 
alpar@209:     void halt()
alpar@119:     {
alpar@119:       if(_running) {
alpar@209:         _running=0;
alpar@209:         TimeStamp t;
alpar@209:         t.stamp();
alpar@209:         start_time=t-start_time;
alpar@119:       }
alpar@119:     }
alpar@119: 
alpar@119:     ///Returns the running state of the timer
alpar@119: 
alpar@119:     ///This function returns the number of stop() exections that is
alpar@119:     ///necessary to really stop the timer.
kpeter@833:     ///For example, the timer
alpar@119:     ///is running if and only if the return value is \c true
alpar@119:     ///(i.e. greater than
alpar@119:     ///zero).
alpar@119:     int running()  { return _running; }
alpar@209: 
alpar@209: 
alpar@119:     ///Restart the time counters
alpar@119: 
alpar@119:     ///This function is a shorthand for
alpar@119:     ///a reset() and a start() calls.
alpar@119:     ///
alpar@209:     void restart()
alpar@119:     {
alpar@119:       reset();
alpar@119:       start();
alpar@119:     }
alpar@209: 
alpar@119:     ///@}
alpar@119: 
kpeter@631:     ///\name Query Functions for the Ellapsed Time
alpar@119: 
alpar@119:     ///@{
alpar@119: 
alpar@119:     ///Gives back the ellapsed user time of the process
alpar@119:     double userTime() const
alpar@119:     {
alpar@119:       return operator TimeStamp().userTime();
alpar@119:     }
alpar@119:     ///Gives back the ellapsed system time of the process
alpar@119:     double systemTime() const
alpar@119:     {
alpar@119:       return operator TimeStamp().systemTime();
alpar@119:     }
alpar@119:     ///Gives back the ellapsed user time of the process' children
deba@126: 
alpar@209:     ///\note On <tt>WIN32</tt> platform this value is not calculated.
deba@126:     ///
alpar@119:     double cUserTime() const
alpar@119:     {
alpar@119:       return operator TimeStamp().cUserTime();
alpar@119:     }
alpar@119:     ///Gives back the ellapsed user time of the process' children
deba@126: 
alpar@209:     ///\note On <tt>WIN32</tt> platform this value is not calculated.
deba@126:     ///
alpar@119:     double cSystemTime() const
alpar@119:     {
alpar@119:       return operator TimeStamp().cSystemTime();
alpar@119:     }
alpar@119:     ///Gives back the ellapsed real time
alpar@119:     double realTime() const
alpar@119:     {
alpar@119:       return operator TimeStamp().realTime();
alpar@119:     }
alpar@119:     ///Computes the ellapsed time
alpar@119: 
alpar@119:     ///This conversion computes the ellapsed time, therefore you can print
alpar@119:     ///the ellapsed time like this.
alpar@119:     ///\code
alpar@119:     ///  Timer t;
alpar@119:     ///  doSomething();
alpar@119:     ///  std::cout << t << '\n';
alpar@119:     ///\endcode
alpar@119:     operator TimeStamp () const
alpar@119:     {
alpar@119:       TimeStamp t;
alpar@119:       t.stamp();
alpar@119:       return _running?t-start_time:start_time;
alpar@119:     }
alpar@119: 
alpar@119: 
alpar@119:     ///@}
alpar@119:   };
alpar@119: 
kpeter@313:   ///Same as Timer but prints a report on destruction.
alpar@119: 
alpar@119:   ///Same as \ref Timer but prints a report on destruction.
alpar@119:   ///This example shows its usage.
alpar@119:   ///\code
alpar@119:   ///  void myAlg(ListGraph &g,int n)
alpar@119:   ///  {
alpar@119:   ///    TimeReport tr("Running time of myAlg: ");
alpar@119:   ///    ... //Here comes the algorithm
alpar@119:   ///  }
alpar@119:   ///\endcode
alpar@119:   ///
alpar@119:   ///\sa Timer
alpar@119:   ///\sa NoTimeReport
alpar@209:   class TimeReport : public Timer
alpar@119:   {
alpar@119:     std::string _title;
alpar@119:     std::ostream &_os;
alpar@1222:     bool _active;
alpar@119:   public:
kpeter@313:     ///Constructor
alpar@119: 
kpeter@313:     ///Constructor.
alpar@119:     ///\param title This text will be printed before the ellapsed time.
alpar@119:     ///\param os The stream to print the report to.
alpar@119:     ///\param run Sets whether the timer should start immediately.
alpar@1222:     ///\param active Sets whether the report should actually be printed
alpar@1222:     ///       on destruction.
alpar@1222:     TimeReport(std::string title,std::ostream &os=std::cerr,bool run=true,
alpar@1270:                bool active=true)
alpar@1222:       : Timer(run), _title(title), _os(os), _active(active) {}
kpeter@313:     ///Destructor that prints the ellapsed time
alpar@209:     ~TimeReport()
alpar@119:     {
alpar@1222:       if(_active) _os << _title << *this << std::endl;
alpar@119:     }
alpar@1270: 
alpar@1222:     ///Retrieve the activity status
alpar@1222: 
alpar@1222:     ///\e
alpar@1222:     ///
alpar@1222:     bool active() const { return _active; }
alpar@1222:     ///Set the activity status
alpar@1222: 
alpar@1222:     /// This function set whether the time report should actually be printed
alpar@1222:     /// on destruction.
alpar@1222:     void active(bool a) { _active=a; }
alpar@119:   };
alpar@209: 
kpeter@313:   ///'Do nothing' version of TimeReport
alpar@119: 
alpar@119:   ///\sa TimeReport
alpar@119:   ///
alpar@119:   class NoTimeReport
alpar@119:   {
alpar@119:   public:
alpar@119:     ///\e
alpar@119:     NoTimeReport(std::string,std::ostream &,bool) {}
alpar@119:     ///\e
alpar@119:     NoTimeReport(std::string,std::ostream &) {}
alpar@119:     ///\e
alpar@119:     NoTimeReport(std::string) {}
alpar@119:     ///\e Do nothing.
alpar@119:     ~NoTimeReport() {}
alpar@119: 
alpar@119:     operator TimeStamp () const { return TimeStamp(); }
alpar@119:     void reset() {}
alpar@119:     void start() {}
alpar@119:     void stop() {}
alpar@209:     void halt() {}
alpar@119:     int running() { return 0; }
alpar@119:     void restart() {}
alpar@119:     double userTime() const { return 0; }
alpar@119:     double systemTime() const { return 0; }
alpar@119:     double cUserTime() const { return 0; }
alpar@119:     double cSystemTime() const { return 0; }
alpar@119:     double realTime() const { return 0; }
alpar@119:   };
alpar@209: 
alpar@119:   ///Tool to measure the running time more exactly.
alpar@209: 
alpar@119:   ///This function calls \c f several times and returns the average
alpar@119:   ///running time. The number of the executions will be choosen in such a way
alpar@119:   ///that the full real running time will be roughly between \c min_time
alpar@119:   ///and <tt>2*min_time</tt>.
alpar@119:   ///\param f the function object to be measured.
alpar@119:   ///\param min_time the minimum total running time.
alpar@119:   ///\retval num if it is not \c NULL, then the actual
alpar@119:   ///        number of execution of \c f will be written into <tt>*num</tt>.
alpar@119:   ///\retval full_time if it is not \c NULL, then the actual
alpar@119:   ///        total running time will be written into <tt>*full_time</tt>.
alpar@119:   ///\return The average running time of \c f.
alpar@209: 
alpar@119:   template<class F>
alpar@119:   TimeStamp runningTimeTest(F f,double min_time=10,unsigned int *num = NULL,
alpar@119:                             TimeStamp *full_time=NULL)
alpar@119:   {
alpar@119:     TimeStamp full;
alpar@119:     unsigned int total=0;
alpar@119:     Timer t;
alpar@119:     for(unsigned int tn=1;tn <= 1U<<31 && full.realTime()<=min_time; tn*=2) {
alpar@119:       for(;total<tn;total++) f();
alpar@119:       full=t;
alpar@119:     }
alpar@119:     if(num) *num=total;
alpar@119:     if(full_time) *full_time=full;
alpar@119:     return full/total;
alpar@119:   }
alpar@209: 
alpar@209:   /// @}
alpar@119: 
alpar@119: 
alpar@119: } //namespace lemon
alpar@119: 
alpar@119: #endif //LEMON_TIME_MEASURE_H