lemon/time_measure.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 22 Apr 2008 17:52:01 +0100
changeset 145 95d905b6e33d
parent 126 e1dd2a70737c
child 157 2ccc1afc2c52
permissions -rw-r--r--
Merge
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_TIME_MEASURE_H
    20 #define LEMON_TIME_MEASURE_H
    21 
    22 ///\ingroup timecount
    23 ///\file
    24 ///\brief Tools for measuring cpu usage
    25 
    26 #ifdef WIN32
    27 #define WIN32_LEAN_AND_MEAN
    28 #define NOMINMAX
    29 #include <windows.h>
    30 #include <cmath>
    31 #else
    32 #include <sys/times.h>
    33 #include <sys/time.h>
    34 #endif
    35 
    36 #include <string>
    37 #include <fstream>
    38 #include <iostream>
    39 
    40 namespace lemon {
    41 
    42   /// \addtogroup timecount
    43   /// @{
    44 
    45   /// A class to store (cpu)time instances.
    46 
    47   /// This class stores five time values.
    48   /// - a real time
    49   /// - a user cpu time
    50   /// - a system cpu time
    51   /// - a user cpu time of children
    52   /// - a system cpu time of children
    53   ///
    54   /// TimeStamp's can be added to or substracted from each other and
    55   /// they can be pushed to a stream.
    56   ///
    57   /// In most cases, perhaps the \ref Timer or the \ref TimeReport
    58   /// class is what you want to use instead.
    59   ///
    60   ///\author Alpar Juttner
    61 
    62   class TimeStamp
    63   {
    64     double utime;
    65     double stime;
    66     double cutime;
    67     double cstime;
    68     double rtime;
    69   
    70     void _reset() { 
    71       utime = stime = cutime = cstime = rtime = 0;
    72     }
    73 
    74   public:
    75 
    76     ///Read the current time values of the process
    77     void stamp()
    78     {
    79 #ifndef WIN32
    80       timeval tv;
    81       gettimeofday(&tv, 0);
    82       rtime=tv.tv_sec+double(tv.tv_usec)/1e6;
    83 
    84       tms ts;
    85       double tck=sysconf(_SC_CLK_TCK);
    86       times(&ts);
    87       utime=ts.tms_utime/tck;
    88       stime=ts.tms_stime/tck;
    89       cutime=ts.tms_cutime/tck;
    90       cstime=ts.tms_cstime/tck;
    91 #else
    92       static const double ch = 4294967296.0e-7;
    93       static const double cl = 1.0e-7;
    94 
    95       FILETIME system;
    96       GetSystemTimeAsFileTime(&system);
    97       rtime = ch * system.dwHighDateTime + cl * system.dwLowDateTime;
    98 
    99       FILETIME create, exit, kernel, user;
   100       if (GetProcessTimes(GetCurrentProcess(),&create, &exit, &kernel, &user)) {
   101 	utime = ch * user.dwHighDateTime + cl * user.dwLowDateTime;
   102 	stime = ch * kernel.dwHighDateTime + cl * kernel.dwLowDateTime;
   103 	cutime = 0;
   104 	cstime = 0;
   105       } else {
   106 	rtime = 0;
   107 	utime = 0;
   108 	stime = 0;
   109 	cutime = 0;
   110 	cstime = 0;
   111       }
   112 #endif      
   113     }
   114   
   115     /// Constructor initializing with zero
   116     TimeStamp()
   117     { _reset(); }
   118     ///Constructor initializing with the current time values of the process
   119     TimeStamp(void *) { stamp();}
   120   
   121     ///Set every time value to zero
   122     TimeStamp &reset() {_reset();return *this;}
   123 
   124     ///\e
   125     TimeStamp &operator+=(const TimeStamp &b)
   126     {
   127       utime+=b.utime;
   128       stime+=b.stime;
   129       cutime+=b.cutime;
   130       cstime+=b.cstime;
   131       rtime+=b.rtime;
   132       return *this;
   133     }
   134     ///\e
   135     TimeStamp operator+(const TimeStamp &b) const
   136     {
   137       TimeStamp t(*this);
   138       return t+=b;
   139     }
   140     ///\e
   141     TimeStamp &operator-=(const TimeStamp &b)
   142     {
   143       utime-=b.utime;
   144       stime-=b.stime;
   145       cutime-=b.cutime;
   146       cstime-=b.cstime;
   147       rtime-=b.rtime;
   148       return *this;
   149     }
   150     ///\e
   151     TimeStamp operator-(const TimeStamp &b) const
   152     {
   153       TimeStamp t(*this);
   154       return t-=b;
   155     }
   156     ///\e
   157     TimeStamp &operator*=(double b)
   158     {
   159       utime*=b;
   160       stime*=b;
   161       cutime*=b;
   162       cstime*=b;
   163       rtime*=b;
   164       return *this;
   165     }
   166     ///\e
   167     TimeStamp operator*(double b) const
   168     {
   169       TimeStamp t(*this);
   170       return t*=b;
   171     }
   172     friend TimeStamp operator*(double b,const TimeStamp &t);
   173     ///\e
   174     TimeStamp &operator/=(double b)
   175     {
   176       utime/=b;
   177       stime/=b;
   178       cutime/=b;
   179       cstime/=b;
   180       rtime/=b;
   181       return *this;
   182     }
   183     ///\e
   184     TimeStamp operator/(double b) const
   185     {
   186       TimeStamp t(*this);
   187       return t/=b;
   188     }
   189     ///The time ellapsed since the last call of stamp()
   190     TimeStamp ellapsed() const
   191     {
   192       TimeStamp t(NULL);
   193       return t-*this;
   194     }
   195   
   196     friend std::ostream& operator<<(std::ostream& os,const TimeStamp &t);
   197   
   198     ///Gives back the user time of the process
   199     double userTime() const
   200     {
   201       return utime;
   202     }
   203     ///Gives back the system time of the process
   204     double systemTime() const
   205     {
   206       return stime;
   207     }
   208     ///Gives back the user time of the process' children
   209 
   210     ///\note On <tt>WIN32</tt> platform this value is not calculated. 
   211     ///
   212     double cUserTime() const
   213     {
   214       return cutime;
   215     }
   216     ///Gives back the user time of the process' children
   217 
   218     ///\note On <tt>WIN32</tt> platform this value is not calculated. 
   219     ///
   220     double cSystemTime() const
   221     {
   222       return cstime;
   223     }
   224     ///Gives back the real time
   225     double realTime() const {return rtime;}
   226   };
   227 
   228   TimeStamp operator*(double b,const TimeStamp &t) 
   229   {
   230     return t*b;
   231   }
   232   
   233   ///Prints the time counters
   234 
   235   ///Prints the time counters in the following form:
   236   ///
   237   /// <tt>u: XX.XXs s: XX.XXs cu: XX.XXs cs: XX.XXs real: XX.XXs</tt>
   238   ///
   239   /// where the values are the
   240   /// \li \c u: user cpu time,
   241   /// \li \c s: system cpu time,
   242   /// \li \c cu: user cpu time of children,
   243   /// \li \c cs: system cpu time of children,
   244   /// \li \c real: real time.
   245   /// \relates TimeStamp
   246   /// \note On <tt>WIN32</tt> platform the cummulative values are not
   247   /// calculated.
   248   inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t)
   249   {
   250     os << "u: " << t.userTime() <<
   251       "s, s: " << t.systemTime() <<
   252       "s, cu: " << t.cUserTime() <<
   253       "s, cs: " << t.cSystemTime() <<
   254       "s, real: " << t.realTime() << "s";
   255     return os;
   256   }
   257 
   258   ///Class for measuring the cpu time and real time usage of the process
   259 
   260   ///Class for measuring the cpu time and real time usage of the process.
   261   ///It is quite easy-to-use, here is a short example.
   262   ///\code
   263   /// #include<lemon/time_measure.h>
   264   /// #include<iostream>
   265   ///
   266   /// int main()
   267   /// {
   268   ///
   269   ///   ...
   270   ///
   271   ///   Timer t;
   272   ///   doSomething();
   273   ///   std::cout << t << '\n';
   274   ///   t.restart();
   275   ///   doSomethingElse();
   276   ///   std::cout << t << '\n';
   277   ///
   278   ///   ...
   279   ///
   280   /// }
   281   ///\endcode
   282   ///
   283   ///The \ref Timer can also be \ref stop() "stopped" and
   284   ///\ref start() "started" again, so it is possible to compute collected
   285   ///running times.
   286   ///
   287   ///\warning Depending on the operation system and its actual configuration
   288   ///the time counters have a certain (10ms on a typical Linux system)
   289   ///granularity.
   290   ///Therefore this tool is not appropriate to measure very short times.
   291   ///Also, if you start and stop the timer very frequently, it could lead to
   292   ///distorted results.
   293   ///
   294   ///\note If you want to measure the running time of the execution of a certain
   295   ///function, consider the usage of \ref TimeReport instead.
   296   ///
   297   ///\todo This shouldn't be Unix (Linux) specific.
   298   ///\sa TimeReport
   299   ///
   300   ///\author Alpar Juttner
   301   class Timer
   302   {
   303     int _running; //Timer is running iff _running>0; (_running>=0 always holds)
   304     TimeStamp start_time; //This is the relativ start-time if the timer
   305                           //is _running, the collected _running time otherwise.
   306     
   307     void _reset() {if(_running) start_time.stamp(); else start_time.reset();}
   308   
   309   public: 
   310     ///Constructor.
   311 
   312     ///\param run indicates whether or not the timer starts immediately.
   313     ///
   314     Timer(bool run=true) :_running(run) {_reset();}
   315 
   316     ///\name Control the state of the timer
   317     ///Basically a Timer can be either running or stopped,
   318     ///but it provides a bit finer control on the execution.
   319     ///The \ref Timer also counts the number of \ref start()
   320     ///executions, and is stops only after the same amount (or more)
   321     ///\ref stop() "stop()"s. This can be useful e.g. to compute the running time
   322     ///of recursive functions.
   323     ///
   324 
   325     ///@{
   326 
   327     ///Reset and stop the time counters
   328 
   329     ///This function resets and stops the time counters
   330     ///\sa restart()
   331     void reset()
   332     {
   333       _running=0;
   334       _reset();
   335     }
   336 
   337     ///Start the time counters
   338     
   339     ///This function starts the time counters.
   340     ///
   341     ///If the timer is started more than ones, it will remain running
   342     ///until the same amount of \ref stop() is called.
   343     ///\sa stop()
   344     void start() 
   345     {
   346       if(_running) _running++;
   347       else {
   348 	_running=1;
   349 	TimeStamp t;
   350 	t.stamp();
   351 	start_time=t-start_time;
   352       }
   353     }
   354 
   355     
   356     ///Stop the time counters
   357 
   358     ///This function stops the time counters. If start() was executed more than
   359     ///once, then the same number of stop() execution is necessary the really
   360     ///stop the timer.
   361     /// 
   362     ///\sa halt()
   363     ///\sa start()
   364     ///\sa restart()
   365     ///\sa reset()
   366 
   367     void stop() 
   368     {
   369       if(_running && !--_running) {
   370 	TimeStamp t;
   371 	t.stamp();
   372 	start_time=t-start_time;
   373       }
   374     }
   375 
   376     ///Halt (i.e stop immediately) the time counters
   377 
   378     ///This function stops immediately the time counters, i.e. <tt>t.halt()</tt>
   379     ///is a faster
   380     ///equivalent of the following.
   381     ///\code
   382     ///  while(t.running()) t.stop()
   383     ///\endcode
   384     ///
   385     ///
   386     ///\sa stop()
   387     ///\sa restart()
   388     ///\sa reset()
   389 
   390     void halt() 
   391     {
   392       if(_running) {
   393 	_running=0;
   394 	TimeStamp t;
   395 	t.stamp();
   396 	start_time=t-start_time;
   397       }
   398     }
   399 
   400     ///Returns the running state of the timer
   401 
   402     ///This function returns the number of stop() exections that is
   403     ///necessary to really stop the timer.
   404     ///For example the timer
   405     ///is running if and only if the return value is \c true
   406     ///(i.e. greater than
   407     ///zero).
   408     int running()  { return _running; }
   409     
   410     
   411     ///Restart the time counters
   412 
   413     ///This function is a shorthand for
   414     ///a reset() and a start() calls.
   415     ///
   416     void restart() 
   417     {
   418       reset();
   419       start();
   420     }
   421     
   422     ///@}
   423 
   424     ///\name Query Functions for the ellapsed time
   425 
   426     ///@{
   427 
   428     ///Gives back the ellapsed user time of the process
   429     double userTime() const
   430     {
   431       return operator TimeStamp().userTime();
   432     }
   433     ///Gives back the ellapsed system time of the process
   434     double systemTime() const
   435     {
   436       return operator TimeStamp().systemTime();
   437     }
   438     ///Gives back the ellapsed user time of the process' children
   439 
   440     ///\note On <tt>WIN32</tt> platform this value is not calculated. 
   441     ///
   442     double cUserTime() const
   443     {
   444       return operator TimeStamp().cUserTime();
   445     }
   446     ///Gives back the ellapsed user time of the process' children
   447 
   448     ///\note On <tt>WIN32</tt> platform this value is not calculated. 
   449     ///
   450     double cSystemTime() const
   451     {
   452       return operator TimeStamp().cSystemTime();
   453     }
   454     ///Gives back the ellapsed real time
   455     double realTime() const
   456     {
   457       return operator TimeStamp().realTime();
   458     }
   459     ///Computes the ellapsed time
   460 
   461     ///This conversion computes the ellapsed time, therefore you can print
   462     ///the ellapsed time like this.
   463     ///\code
   464     ///  Timer t;
   465     ///  doSomething();
   466     ///  std::cout << t << '\n';
   467     ///\endcode
   468     operator TimeStamp () const
   469     {
   470       TimeStamp t;
   471       t.stamp();
   472       return _running?t-start_time:start_time;
   473     }
   474 
   475 
   476     ///@}
   477   };
   478 
   479   ///Same as \ref Timer but prints a report on destruction.
   480 
   481   ///Same as \ref Timer but prints a report on destruction.
   482   ///This example shows its usage.
   483   ///\code
   484   ///  void myAlg(ListGraph &g,int n)
   485   ///  {
   486   ///    TimeReport tr("Running time of myAlg: ");
   487   ///    ... //Here comes the algorithm
   488   ///  }
   489   ///\endcode
   490   ///
   491   ///\sa Timer
   492   ///\sa NoTimeReport
   493   ///\todo There is no test case for this
   494   class TimeReport : public Timer 
   495   {
   496     std::string _title;
   497     std::ostream &_os;
   498   public:
   499     ///\e
   500 
   501     ///\param title This text will be printed before the ellapsed time.
   502     ///\param os The stream to print the report to.
   503     ///\param run Sets whether the timer should start immediately.
   504 
   505     TimeReport(std::string title,std::ostream &os=std::cerr,bool run=true) 
   506       : Timer(run), _title(title), _os(os){}
   507     ///\e Prints the ellapsed time on destruction.
   508     ~TimeReport() 
   509     {
   510       _os << _title << *this << std::endl;
   511     }
   512   };
   513       
   514   ///'Do nothing' version of \ref TimeReport
   515 
   516   ///\sa TimeReport
   517   ///
   518   class NoTimeReport
   519   {
   520   public:
   521     ///\e
   522     NoTimeReport(std::string,std::ostream &,bool) {}
   523     ///\e
   524     NoTimeReport(std::string,std::ostream &) {}
   525     ///\e
   526     NoTimeReport(std::string) {}
   527     ///\e Do nothing.
   528     ~NoTimeReport() {}
   529 
   530     operator TimeStamp () const { return TimeStamp(); }
   531     void reset() {}
   532     void start() {}
   533     void stop() {}
   534     void halt() {} 
   535     int running() { return 0; }
   536     void restart() {}
   537     double userTime() const { return 0; }
   538     double systemTime() const { return 0; }
   539     double cUserTime() const { return 0; }
   540     double cSystemTime() const { return 0; }
   541     double realTime() const { return 0; }
   542   };
   543       
   544   ///Tool to measure the running time more exactly.
   545   
   546   ///This function calls \c f several times and returns the average
   547   ///running time. The number of the executions will be choosen in such a way
   548   ///that the full real running time will be roughly between \c min_time
   549   ///and <tt>2*min_time</tt>.
   550   ///\param f the function object to be measured.
   551   ///\param min_time the minimum total running time.
   552   ///\retval num if it is not \c NULL, then the actual
   553   ///        number of execution of \c f will be written into <tt>*num</tt>.
   554   ///\retval full_time if it is not \c NULL, then the actual
   555   ///        total running time will be written into <tt>*full_time</tt>.
   556   ///\return The average running time of \c f.
   557   
   558   template<class F>
   559   TimeStamp runningTimeTest(F f,double min_time=10,unsigned int *num = NULL,
   560                             TimeStamp *full_time=NULL)
   561   {
   562     TimeStamp full;
   563     unsigned int total=0;
   564     Timer t;
   565     for(unsigned int tn=1;tn <= 1U<<31 && full.realTime()<=min_time; tn*=2) {
   566       for(;total<tn;total++) f();
   567       full=t;
   568     }
   569     if(num) *num=total;
   570     if(full_time) *full_time=full;
   571     return full/total;
   572   }
   573   
   574   /// @}  
   575 
   576 
   577 } //namespace lemon
   578 
   579 #endif //LEMON_TIME_MEASURE_H