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