alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@119: * alpar@209: * This file is a part of LEMON, a generic C++ optimization library. alpar@119: * alpar@119: * Copyright (C) 2003-2008 alpar@119: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@119: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@119: * alpar@119: * Permission to use, modify and distribute this software is granted alpar@119: * provided that this copyright notice appears in all copies. For alpar@119: * precise terms see the accompanying LICENSE file. alpar@119: * alpar@119: * This software is provided "AS IS" with no warranty of any kind, alpar@119: * express or implied, and with no claim as to its suitability for any alpar@119: * purpose. alpar@119: * alpar@119: */ alpar@119: alpar@119: #ifndef LEMON_TIME_MEASURE_H alpar@119: #define LEMON_TIME_MEASURE_H alpar@119: alpar@119: ///\ingroup timecount alpar@119: ///\file alpar@119: ///\brief Tools for measuring cpu usage alpar@119: deba@126: #ifdef WIN32 alpar@368: #include deba@126: #else alpar@364: #include alpar@119: #include deba@126: #include deba@126: #endif alpar@119: alpar@143: #include alpar@119: #include alpar@119: #include alpar@119: alpar@119: namespace lemon { alpar@119: alpar@119: /// \addtogroup timecount alpar@119: /// @{ alpar@119: alpar@119: /// A class to store (cpu)time instances. alpar@119: alpar@119: /// This class stores five time values. alpar@119: /// - a real time alpar@119: /// - a user cpu time alpar@119: /// - a system cpu time alpar@119: /// - a user cpu time of children alpar@119: /// - a system cpu time of children alpar@119: /// alpar@119: /// TimeStamp's can be added to or substracted from each other and alpar@119: /// they can be pushed to a stream. alpar@119: /// alpar@119: /// In most cases, perhaps the \ref Timer or the \ref TimeReport alpar@119: /// class is what you want to use instead. alpar@119: alpar@119: class TimeStamp alpar@119: { deba@126: double utime; deba@126: double stime; deba@126: double cutime; deba@126: double cstime; deba@126: double rtime; alpar@209: alpar@209: void _reset() { deba@126: utime = stime = cutime = cstime = rtime = 0; alpar@119: } alpar@119: alpar@119: public: alpar@119: alpar@119: ///Read the current time values of the process alpar@119: void stamp() alpar@119: { deba@126: #ifndef WIN32 alpar@119: timeval tv; deba@126: gettimeofday(&tv, 0); deba@126: rtime=tv.tv_sec+double(tv.tv_usec)/1e6; deba@126: deba@126: tms ts; deba@126: double tck=sysconf(_SC_CLK_TCK); deba@126: times(&ts); deba@126: utime=ts.tms_utime/tck; deba@126: stime=ts.tms_stime/tck; deba@126: cutime=ts.tms_cutime/tck; deba@126: cstime=ts.tms_cstime/tck; deba@126: #else alpar@368: bits::getWinProcTimes(rtime, utime, stime, cutime, cstime); alpar@209: #endif alpar@119: } alpar@209: alpar@119: /// Constructor initializing with zero alpar@119: TimeStamp() alpar@119: { _reset(); } alpar@119: ///Constructor initializing with the current time values of the process alpar@119: TimeStamp(void *) { stamp();} alpar@209: alpar@119: ///Set every time value to zero alpar@119: TimeStamp &reset() {_reset();return *this;} alpar@119: alpar@119: ///\e alpar@119: TimeStamp &operator+=(const TimeStamp &b) alpar@119: { deba@126: utime+=b.utime; deba@126: stime+=b.stime; deba@126: cutime+=b.cutime; deba@126: cstime+=b.cstime; deba@126: rtime+=b.rtime; alpar@119: return *this; alpar@119: } alpar@119: ///\e alpar@119: TimeStamp operator+(const TimeStamp &b) const alpar@119: { alpar@119: TimeStamp t(*this); alpar@119: return t+=b; alpar@119: } alpar@119: ///\e alpar@119: TimeStamp &operator-=(const TimeStamp &b) alpar@119: { deba@126: utime-=b.utime; deba@126: stime-=b.stime; deba@126: cutime-=b.cutime; deba@126: cstime-=b.cstime; deba@126: rtime-=b.rtime; alpar@119: return *this; alpar@119: } alpar@119: ///\e alpar@119: TimeStamp operator-(const TimeStamp &b) const alpar@119: { alpar@119: TimeStamp t(*this); alpar@119: return t-=b; alpar@119: } alpar@119: ///\e alpar@119: TimeStamp &operator*=(double b) alpar@119: { deba@126: utime*=b; deba@126: stime*=b; deba@126: cutime*=b; deba@126: cstime*=b; deba@126: rtime*=b; alpar@119: return *this; alpar@119: } alpar@119: ///\e alpar@119: TimeStamp operator*(double b) const alpar@119: { alpar@119: TimeStamp t(*this); alpar@119: return t*=b; alpar@119: } alpar@119: friend TimeStamp operator*(double b,const TimeStamp &t); alpar@119: ///\e alpar@119: TimeStamp &operator/=(double b) alpar@119: { deba@126: utime/=b; deba@126: stime/=b; deba@126: cutime/=b; deba@126: cstime/=b; deba@126: rtime/=b; alpar@119: return *this; alpar@119: } alpar@119: ///\e alpar@119: TimeStamp operator/(double b) const alpar@119: { alpar@119: TimeStamp t(*this); alpar@119: return t/=b; alpar@119: } alpar@119: ///The time ellapsed since the last call of stamp() alpar@119: TimeStamp ellapsed() const alpar@119: { alpar@119: TimeStamp t(NULL); alpar@119: return t-*this; alpar@119: } alpar@209: alpar@119: friend std::ostream& operator<<(std::ostream& os,const TimeStamp &t); alpar@209: alpar@119: ///Gives back the user time of the process alpar@119: double userTime() const alpar@119: { deba@126: return utime; alpar@119: } alpar@119: ///Gives back the system time of the process alpar@119: double systemTime() const alpar@119: { deba@126: return stime; alpar@119: } alpar@119: ///Gives back the user time of the process' children deba@126: alpar@209: ///\note On WIN32 platform this value is not calculated. deba@126: /// alpar@119: double cUserTime() const alpar@119: { deba@126: return cutime; alpar@119: } alpar@119: ///Gives back the user time of the process' children deba@126: alpar@209: ///\note On WIN32 platform this value is not calculated. deba@126: /// alpar@119: double cSystemTime() const alpar@119: { deba@126: return cstime; alpar@119: } alpar@119: ///Gives back the real time deba@126: double realTime() const {return rtime;} alpar@119: }; alpar@119: alpar@209: TimeStamp operator*(double b,const TimeStamp &t) alpar@119: { alpar@119: return t*b; alpar@119: } alpar@209: alpar@119: ///Prints the time counters alpar@119: alpar@119: ///Prints the time counters in the following form: alpar@119: /// alpar@119: /// u: XX.XXs s: XX.XXs cu: XX.XXs cs: XX.XXs real: XX.XXs alpar@119: /// alpar@119: /// where the values are the alpar@119: /// \li \c u: user cpu time, alpar@119: /// \li \c s: system cpu time, alpar@119: /// \li \c cu: user cpu time of children, alpar@119: /// \li \c cs: system cpu time of children, alpar@119: /// \li \c real: real time. alpar@119: /// \relates TimeStamp deba@126: /// \note On WIN32 platform the cummulative values are not deba@126: /// calculated. alpar@119: inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t) alpar@119: { deba@126: os << "u: " << t.userTime() << deba@126: "s, s: " << t.systemTime() << deba@126: "s, cu: " << t.cUserTime() << deba@126: "s, cs: " << t.cSystemTime() << alpar@119: "s, real: " << t.realTime() << "s"; alpar@119: return os; alpar@119: } alpar@119: alpar@119: ///Class for measuring the cpu time and real time usage of the process alpar@119: alpar@119: ///Class for measuring the cpu time and real time usage of the process. alpar@119: ///It is quite easy-to-use, here is a short example. alpar@119: ///\code alpar@119: /// #include alpar@119: /// #include alpar@119: /// alpar@119: /// int main() alpar@119: /// { alpar@119: /// alpar@119: /// ... alpar@119: /// alpar@119: /// Timer t; alpar@119: /// doSomething(); alpar@119: /// std::cout << t << '\n'; alpar@119: /// t.restart(); alpar@119: /// doSomethingElse(); alpar@119: /// std::cout << t << '\n'; alpar@119: /// alpar@119: /// ... alpar@119: /// alpar@119: /// } alpar@119: ///\endcode alpar@119: /// alpar@119: ///The \ref Timer can also be \ref stop() "stopped" and alpar@119: ///\ref start() "started" again, so it is possible to compute collected alpar@119: ///running times. alpar@119: /// alpar@119: ///\warning Depending on the operation system and its actual configuration alpar@119: ///the time counters have a certain (10ms on a typical Linux system) alpar@119: ///granularity. alpar@119: ///Therefore this tool is not appropriate to measure very short times. alpar@119: ///Also, if you start and stop the timer very frequently, it could lead to alpar@119: ///distorted results. alpar@119: /// alpar@119: ///\note If you want to measure the running time of the execution of a certain alpar@119: ///function, consider the usage of \ref TimeReport instead. alpar@119: /// alpar@119: ///\sa TimeReport alpar@119: class Timer alpar@119: { alpar@119: int _running; //Timer is running iff _running>0; (_running>=0 always holds) alpar@119: TimeStamp start_time; //This is the relativ start-time if the timer alpar@119: //is _running, the collected _running time otherwise. alpar@209: alpar@119: void _reset() {if(_running) start_time.stamp(); else start_time.reset();} alpar@209: alpar@209: public: alpar@119: ///Constructor. alpar@119: alpar@119: ///\param run indicates whether or not the timer starts immediately. alpar@119: /// alpar@119: Timer(bool run=true) :_running(run) {_reset();} alpar@119: alpar@119: ///\name Control the state of the timer alpar@119: ///Basically a Timer can be either running or stopped, alpar@119: ///but it provides a bit finer control on the execution. kpeter@318: ///The \ref lemon::Timer "Timer" also counts the number of kpeter@318: ///\ref lemon::Timer::start() "start()" executions, and it stops kpeter@317: ///only after the same amount (or more) \ref lemon::Timer::stop() kpeter@317: ///"stop()"s. This can be useful e.g. to compute the running time alpar@119: ///of recursive functions. alpar@119: alpar@119: ///@{ alpar@119: alpar@119: ///Reset and stop the time counters alpar@119: alpar@119: ///This function resets and stops the time counters alpar@119: ///\sa restart() alpar@119: void reset() alpar@119: { alpar@119: _running=0; alpar@119: _reset(); alpar@119: } alpar@119: alpar@119: ///Start the time counters alpar@209: alpar@119: ///This function starts the time counters. alpar@119: /// alpar@119: ///If the timer is started more than ones, it will remain running alpar@119: ///until the same amount of \ref stop() is called. alpar@119: ///\sa stop() alpar@209: void start() alpar@119: { alpar@119: if(_running) _running++; alpar@119: else { alpar@209: _running=1; alpar@209: TimeStamp t; alpar@209: t.stamp(); alpar@209: start_time=t-start_time; alpar@119: } alpar@119: } alpar@119: alpar@209: alpar@119: ///Stop the time counters alpar@119: alpar@119: ///This function stops the time counters. If start() was executed more than alpar@119: ///once, then the same number of stop() execution is necessary the really alpar@119: ///stop the timer. alpar@209: /// alpar@119: ///\sa halt() alpar@119: ///\sa start() alpar@119: ///\sa restart() alpar@119: ///\sa reset() alpar@119: alpar@209: void stop() alpar@119: { alpar@119: if(_running && !--_running) { alpar@209: TimeStamp t; alpar@209: t.stamp(); alpar@209: start_time=t-start_time; alpar@119: } alpar@119: } alpar@119: alpar@119: ///Halt (i.e stop immediately) the time counters alpar@119: alpar@120: ///This function stops immediately the time counters, i.e. t.halt() alpar@119: ///is a faster alpar@119: ///equivalent of the following. alpar@119: ///\code alpar@119: /// while(t.running()) t.stop() alpar@119: ///\endcode alpar@119: /// alpar@119: /// alpar@119: ///\sa stop() alpar@119: ///\sa restart() alpar@119: ///\sa reset() alpar@119: alpar@209: void halt() alpar@119: { alpar@119: if(_running) { alpar@209: _running=0; alpar@209: TimeStamp t; alpar@209: t.stamp(); alpar@209: start_time=t-start_time; alpar@119: } alpar@119: } alpar@119: alpar@119: ///Returns the running state of the timer alpar@119: alpar@119: ///This function returns the number of stop() exections that is alpar@119: ///necessary to really stop the timer. alpar@119: ///For example the timer alpar@119: ///is running if and only if the return value is \c true alpar@119: ///(i.e. greater than alpar@119: ///zero). alpar@119: int running() { return _running; } alpar@209: alpar@209: alpar@119: ///Restart the time counters alpar@119: alpar@119: ///This function is a shorthand for alpar@119: ///a reset() and a start() calls. alpar@119: /// alpar@209: void restart() alpar@119: { alpar@119: reset(); alpar@119: start(); alpar@119: } alpar@209: alpar@119: ///@} alpar@119: alpar@119: ///\name Query Functions for the ellapsed time alpar@119: alpar@119: ///@{ alpar@119: alpar@119: ///Gives back the ellapsed user time of the process alpar@119: double userTime() const alpar@119: { alpar@119: return operator TimeStamp().userTime(); alpar@119: } alpar@119: ///Gives back the ellapsed system time of the process alpar@119: double systemTime() const alpar@119: { alpar@119: return operator TimeStamp().systemTime(); alpar@119: } alpar@119: ///Gives back the ellapsed user time of the process' children deba@126: alpar@209: ///\note On WIN32 platform this value is not calculated. deba@126: /// alpar@119: double cUserTime() const alpar@119: { alpar@119: return operator TimeStamp().cUserTime(); alpar@119: } alpar@119: ///Gives back the ellapsed user time of the process' children deba@126: alpar@209: ///\note On WIN32 platform this value is not calculated. deba@126: /// alpar@119: double cSystemTime() const alpar@119: { alpar@119: return operator TimeStamp().cSystemTime(); alpar@119: } alpar@119: ///Gives back the ellapsed real time alpar@119: double realTime() const alpar@119: { alpar@119: return operator TimeStamp().realTime(); alpar@119: } alpar@119: ///Computes the ellapsed time alpar@119: alpar@119: ///This conversion computes the ellapsed time, therefore you can print alpar@119: ///the ellapsed time like this. alpar@119: ///\code alpar@119: /// Timer t; alpar@119: /// doSomething(); alpar@119: /// std::cout << t << '\n'; alpar@119: ///\endcode alpar@119: operator TimeStamp () const alpar@119: { alpar@119: TimeStamp t; alpar@119: t.stamp(); alpar@119: return _running?t-start_time:start_time; alpar@119: } alpar@119: alpar@119: alpar@119: ///@} alpar@119: }; alpar@119: kpeter@317: ///Same as Timer but prints a report on destruction. alpar@119: alpar@119: ///Same as \ref Timer but prints a report on destruction. alpar@119: ///This example shows its usage. alpar@119: ///\code alpar@119: /// void myAlg(ListGraph &g,int n) alpar@119: /// { alpar@119: /// TimeReport tr("Running time of myAlg: "); alpar@119: /// ... //Here comes the algorithm alpar@119: /// } alpar@119: ///\endcode alpar@119: /// alpar@119: ///\sa Timer alpar@119: ///\sa NoTimeReport alpar@209: class TimeReport : public Timer alpar@119: { alpar@119: std::string _title; alpar@119: std::ostream &_os; alpar@119: public: kpeter@317: ///Constructor alpar@119: kpeter@317: ///Constructor. alpar@119: ///\param title This text will be printed before the ellapsed time. alpar@119: ///\param os The stream to print the report to. alpar@119: ///\param run Sets whether the timer should start immediately. alpar@209: TimeReport(std::string title,std::ostream &os=std::cerr,bool run=true) alpar@119: : Timer(run), _title(title), _os(os){} kpeter@317: ///Destructor that prints the ellapsed time alpar@209: ~TimeReport() alpar@119: { alpar@119: _os << _title << *this << std::endl; alpar@119: } alpar@119: }; alpar@209: kpeter@317: ///'Do nothing' version of TimeReport alpar@119: alpar@119: ///\sa TimeReport alpar@119: /// alpar@119: class NoTimeReport alpar@119: { alpar@119: public: alpar@119: ///\e alpar@119: NoTimeReport(std::string,std::ostream &,bool) {} alpar@119: ///\e alpar@119: NoTimeReport(std::string,std::ostream &) {} alpar@119: ///\e alpar@119: NoTimeReport(std::string) {} alpar@119: ///\e Do nothing. alpar@119: ~NoTimeReport() {} alpar@119: alpar@119: operator TimeStamp () const { return TimeStamp(); } alpar@119: void reset() {} alpar@119: void start() {} alpar@119: void stop() {} alpar@209: void halt() {} alpar@119: int running() { return 0; } alpar@119: void restart() {} alpar@119: double userTime() const { return 0; } alpar@119: double systemTime() const { return 0; } alpar@119: double cUserTime() const { return 0; } alpar@119: double cSystemTime() const { return 0; } alpar@119: double realTime() const { return 0; } alpar@119: }; alpar@209: alpar@119: ///Tool to measure the running time more exactly. alpar@209: alpar@119: ///This function calls \c f several times and returns the average alpar@119: ///running time. The number of the executions will be choosen in such a way alpar@119: ///that the full real running time will be roughly between \c min_time alpar@119: ///and 2*min_time. alpar@119: ///\param f the function object to be measured. alpar@119: ///\param min_time the minimum total running time. alpar@119: ///\retval num if it is not \c NULL, then the actual alpar@119: /// number of execution of \c f will be written into *num. alpar@119: ///\retval full_time if it is not \c NULL, then the actual alpar@119: /// total running time will be written into *full_time. alpar@119: ///\return The average running time of \c f. alpar@209: alpar@119: template alpar@119: TimeStamp runningTimeTest(F f,double min_time=10,unsigned int *num = NULL, alpar@119: TimeStamp *full_time=NULL) alpar@119: { alpar@119: TimeStamp full; alpar@119: unsigned int total=0; alpar@119: Timer t; alpar@119: for(unsigned int tn=1;tn <= 1U<<31 && full.realTime()<=min_time; tn*=2) { alpar@119: for(;total