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