Fix wrong iteration in ListGraph snapshot, part II. (#598)
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2013
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_TIME_MEASURE_H
20 #define LEMON_TIME_MEASURE_H
24 ///\brief Tools for measuring cpu usage
26 #include <lemon/config.h>
29 #include <lemon/bits/windows.h>
32 #include <sys/times.h>
39 #include <lemon/math.h>
43 /// \addtogroup timecount
46 /// A class to store (cpu)time instances.
48 /// This class stores five time values.
51 /// - a system cpu time
52 /// - a user cpu time of children
53 /// - a system cpu time of children
55 /// TimeStamp's can be added to or substracted from each other and
56 /// they can be pushed to a stream.
58 /// In most cases, perhaps the \ref Timer or the \ref TimeReport
59 /// class is what you want to use instead.
70 ///Display format specifier
75 /// Reports all measured values
77 /// Only real time and an error indicator is displayed
82 static Format _format;
85 utime = stime = cutime = cstime = rtime = 0;
94 ///The output format is global for all timestamp instances.
95 static void format(Format f) { _format = f; }
96 ///Retrieve the current output format
98 ///Retrieve the current output format
100 ///The output format is global for all timestamp instances.
101 static Format format() { return _format; }
104 ///Read the current time values of the process
109 gettimeofday(&tv, 0);
110 rtime=tv.tv_sec+double(tv.tv_usec)/1e6;
113 double tck=sysconf(_SC_CLK_TCK);
115 utime=ts.tms_utime/tck;
116 stime=ts.tms_stime/tck;
117 cutime=ts.tms_cutime/tck;
118 cstime=ts.tms_cstime/tck;
120 bits::getWinProcTimes(rtime, utime, stime, cutime, cstime);
124 /// Constructor initializing with zero
127 ///Constructor initializing with the current time values of the process
128 TimeStamp(void *) { stamp();}
130 ///Set every time value to zero
131 TimeStamp &reset() {_reset();return *this;}
134 TimeStamp &operator+=(const TimeStamp &b)
144 TimeStamp operator+(const TimeStamp &b) const
150 TimeStamp &operator-=(const TimeStamp &b)
160 TimeStamp operator-(const TimeStamp &b) const
166 TimeStamp &operator*=(double b)
176 TimeStamp operator*(double b) const
181 friend TimeStamp operator*(double b,const TimeStamp &t);
183 TimeStamp &operator/=(double b)
193 TimeStamp operator/(double b) const
198 ///The time ellapsed since the last call of stamp()
199 TimeStamp ellapsed() const
205 friend std::ostream& operator<<(std::ostream& os,const TimeStamp &t);
207 ///Gives back the user time of the process
208 double userTime() const
212 ///Gives back the system time of the process
213 double systemTime() const
217 ///Gives back the user time of the process' children
219 ///\note On <tt>WIN32</tt> platform this value is not calculated.
221 double cUserTime() const
225 ///Gives back the user time of the process' children
227 ///\note On <tt>WIN32</tt> platform this value is not calculated.
229 double cSystemTime() const
233 ///Gives back the real time
234 double realTime() const {return rtime;}
237 inline TimeStamp operator*(double b,const TimeStamp &t)
242 ///Prints the time counters
244 ///Prints the time counters in the following form:
246 /// <tt>u: XX.XXs s: XX.XXs cu: XX.XXs cs: XX.XXs real: XX.XXs</tt>
248 /// where the values are the
249 /// \li \c u: user cpu time,
250 /// \li \c s: system cpu time,
251 /// \li \c cu: user cpu time of children,
252 /// \li \c cs: system cpu time of children,
253 /// \li \c real: real time.
254 /// \relates TimeStamp
255 /// \note On <tt>WIN32</tt> platform the cummulative values are not
257 inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t)
261 case TimeStamp::NORMAL:
262 os << "u: " << t.userTime() <<
263 "s, s: " << t.systemTime() <<
264 "s, cu: " << t.cUserTime() <<
265 "s, cs: " << t.cSystemTime() <<
266 "s, real: " << t.realTime() << "s";
268 case TimeStamp::SHORT:
269 double total = t.userTime()+t.systemTime()+
270 t.cUserTime()+t.cSystemTime();
272 << "s (err: " << round((t.realTime()-total)/
273 t.realTime()*10000)/100
280 ///Class for measuring the cpu time and real time usage of the process
282 ///Class for measuring the cpu time and real time usage of the process.
283 ///It is quite easy-to-use, here is a short example.
285 /// #include<lemon/time_measure.h>
286 /// #include<iostream>
295 /// std::cout << t << '\n';
297 /// doSomethingElse();
298 /// std::cout << t << '\n';
305 ///The \ref Timer can also be \ref stop() "stopped" and
306 ///\ref start() "started" again, so it is possible to compute collected
309 ///\warning Depending on the operation system and its actual configuration
310 ///the time counters have a certain (10ms on a typical Linux system)
312 ///Therefore this tool is not appropriate to measure very short times.
313 ///Also, if you start and stop the timer very frequently, it could lead to
314 ///distorted results.
316 ///\note If you want to measure the running time of the execution of a certain
317 ///function, consider the usage of \ref TimeReport instead.
322 int _running; //Timer is running iff _running>0; (_running>=0 always holds)
323 TimeStamp start_time; //This is the relativ start-time if the timer
324 //is _running, the collected _running time otherwise.
326 void _reset() {if(_running) start_time.stamp(); else start_time.reset();}
331 ///\param run indicates whether or not the timer starts immediately.
333 Timer(bool run=true) :_running(run) {_reset();}
335 ///\name Control the State of the Timer
336 ///Basically a Timer can be either running or stopped,
337 ///but it provides a bit finer control on the execution.
338 ///The \ref lemon::Timer "Timer" also counts the number of
339 ///\ref lemon::Timer::start() "start()" executions, and it stops
340 ///only after the same amount (or more) \ref lemon::Timer::stop()
341 ///"stop()"s. This can be useful e.g. to compute the running time
342 ///of recursive functions.
346 ///Reset and stop the time counters
348 ///This function resets and stops the time counters
356 ///Start the time counters
358 ///This function starts the time counters.
360 ///If the timer is started more than ones, it will remain running
361 ///until the same amount of \ref stop() is called.
365 if(_running) _running++;
370 start_time=t-start_time;
375 ///Stop the time counters
377 ///This function stops the time counters. If start() was executed more than
378 ///once, then the same number of stop() execution is necessary the really
388 if(_running && !--_running) {
391 start_time=t-start_time;
395 ///Halt (i.e stop immediately) the time counters
397 ///This function stops immediately the time counters, i.e. <tt>t.halt()</tt>
399 ///equivalent of the following.
401 /// while(t.running()) t.stop()
415 start_time=t-start_time;
419 ///Returns the running state of the timer
421 ///This function returns the number of stop() exections that is
422 ///necessary to really stop the timer.
423 ///For example, the timer
424 ///is running if and only if the return value is \c true
425 ///(i.e. greater than
427 int running() { return _running; }
430 ///Restart the time counters
432 ///This function is a shorthand for
433 ///a reset() and a start() calls.
443 ///\name Query Functions for the Ellapsed Time
447 ///Gives back the ellapsed user time of the process
448 double userTime() const
450 return operator TimeStamp().userTime();
452 ///Gives back the ellapsed system time of the process
453 double systemTime() const
455 return operator TimeStamp().systemTime();
457 ///Gives back the ellapsed user time of the process' children
459 ///\note On <tt>WIN32</tt> platform this value is not calculated.
461 double cUserTime() const
463 return operator TimeStamp().cUserTime();
465 ///Gives back the ellapsed user time of the process' children
467 ///\note On <tt>WIN32</tt> platform this value is not calculated.
469 double cSystemTime() const
471 return operator TimeStamp().cSystemTime();
473 ///Gives back the ellapsed real time
474 double realTime() const
476 return operator TimeStamp().realTime();
478 ///Computes the ellapsed time
480 ///This conversion computes the ellapsed time, therefore you can print
481 ///the ellapsed time like this.
485 /// std::cout << t << '\n';
487 operator TimeStamp () const
491 return _running?t-start_time:start_time;
498 ///Same as Timer but prints a report on destruction.
500 ///Same as \ref Timer but prints a report on destruction.
501 ///This example shows its usage.
503 /// void myAlg(ListGraph &g,int n)
505 /// TimeReport tr("Running time of myAlg: ");
506 /// ... //Here comes the algorithm
512 class TimeReport : public Timer
521 ///\param title This text will be printed before the ellapsed time.
522 ///\param os The stream to print the report to.
523 ///\param run Sets whether the timer should start immediately.
524 ///\param active Sets whether the report should actually be printed
526 TimeReport(std::string title,std::ostream &os=std::cerr,bool run=true,
528 : Timer(run), _title(title), _os(os), _active(active) {}
529 ///Destructor that prints the ellapsed time
532 if(_active) _os << _title << *this << std::endl;
535 ///Retrieve the activity status
539 bool active() const { return _active; }
540 ///Set the activity status
542 /// This function set whether the time report should actually be printed
544 void active(bool a) { _active=a; }
547 ///'Do nothing' version of TimeReport
555 NoTimeReport(std::string,std::ostream &,bool) {}
557 NoTimeReport(std::string,std::ostream &) {}
559 NoTimeReport(std::string) {}
563 operator TimeStamp () const { return TimeStamp(); }
568 int running() { return 0; }
570 double userTime() const { return 0; }
571 double systemTime() const { return 0; }
572 double cUserTime() const { return 0; }
573 double cSystemTime() const { return 0; }
574 double realTime() const { return 0; }
577 ///Tool to measure the running time more exactly.
579 ///This function calls \c f several times and returns the average
580 ///running time. The number of the executions will be choosen in such a way
581 ///that the full real running time will be roughly between \c min_time
582 ///and <tt>2*min_time</tt>.
583 ///\param f the function object to be measured.
584 ///\param min_time the minimum total running time.
585 ///\retval num if it is not \c NULL, then the actual
586 /// number of execution of \c f will be written into <tt>*num</tt>.
587 ///\retval full_time if it is not \c NULL, then the actual
588 /// total running time will be written into <tt>*full_time</tt>.
589 ///\return The average running time of \c f.
592 TimeStamp runningTimeTest(F f,double min_time=10,unsigned int *num = NULL,
593 TimeStamp *full_time=NULL)
596 unsigned int total=0;
598 for(unsigned int tn=1;tn <= 1U<<31 && full.realTime()<=min_time; tn*=2) {
599 for(;total<tn;total++) f();
603 if(full_time) *full_time=full;
612 #endif //LEMON_TIME_MEASURE_H