lemon/time_measure.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 19 Feb 2010 14:08:32 +0100
changeset 844 a6eb9698c321
parent 584 33c6b6e755cd
child 1054 c40a9d94442d
permissions -rw-r--r--
Support tolerance technique for BellmanFord (#51)

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