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