COIN-OR::LEMON - Graph Library

Ticket #74: time_measure_port.hg

File time_measure_port.hg, 17.3 KB (added by Balazs Dezso, 12 years ago)
Line 
1# HG changeset patch
2# User Balazs Dezso <deba@inf.elte.hu>
3# Date 1207932268 -7200
4# Node ID 8bed93ad51f4d3c1d3d129002a12edc6518e1dc9
5# Parent  7b0ce9fb1169c533d2859b8d48bf8586d16fbc91
6Port time_measure.h from SVN -r 3489
7
8diff -r 7b0ce9fb1169 -r 8bed93ad51f4 lemon/Makefile.am
9--- a/lemon/Makefile.am Wed Apr 09 17:19:40 2008 +0100
10+++ b/lemon/Makefile.am Fri Apr 11 18:44:28 2008 +0200
11@@ -32,6 +32,7 @@ lemon_HEADERS += \
12        lemon/path.h \
13         lemon/random.h \
14        lemon/smart_graph.h \
15+       lemon/time_measure.h \
16         lemon/tolerance.h \
17        lemon/unionfind.h
18 
19diff -r 7b0ce9fb1169 -r 8bed93ad51f4 lemon/time_measure.h
20--- /dev/null   Thu Jan 01 00:00:00 1970 +0000
21+++ b/lemon/time_measure.h      Fri Apr 11 18:44:28 2008 +0200
22@@ -0,0 +1,570 @@
23+/* -*- C++ -*-
24+ *
25+ * This file is a part of LEMON, a generic C++ optimization library
26+ *
27+ * Copyright (C) 2003-2008
28+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
29+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
30+ *
31+ * Permission to use, modify and distribute this software is granted
32+ * provided that this copyright notice appears in all copies. For
33+ * precise terms see the accompanying LICENSE file.
34+ *
35+ * This software is provided "AS IS" with no warranty of any kind,
36+ * express or implied, and with no claim as to its suitability for any
37+ * purpose.
38+ *
39+ */
40+
41+#ifndef LEMON_TIME_MEASURE_H
42+#define LEMON_TIME_MEASURE_H
43+
44+///\ingroup timecount
45+///\file
46+///\brief Tools for measuring cpu usage
47+
48+
49+#ifdef WIN32
50+#include <windows.h>
51+#include <cmath>
52+#else
53+#include <sys/times.h>
54+#include <sys/time.h>
55+#endif
56+
57+#include <fstream>
58+#include <iostream>
59+
60+namespace lemon {
61+
62+  /// \addtogroup timecount
63+  /// @{
64+
65+  /// A class to store (cpu)time instances.
66+
67+  /// This class stores five time values.
68+  /// - a real time
69+  /// - a user cpu time
70+  /// - a system cpu time
71+  /// - a user cpu time of children
72+  /// - a system cpu time of children
73+  ///
74+  /// TimeStamp's can be added to or substracted from each other and
75+  /// they can be pushed to a stream.
76+  ///
77+  /// In most cases, perhaps the \ref Timer or the \ref TimeReport
78+  /// class is what you want to use instead.
79+  ///
80+  ///\author Alpar Juttner
81+
82+  class TimeStamp
83+  {
84+    double utime;
85+    double stime;
86+    double cutime;
87+    double cstime;
88+    double rtime;
89
90+    void _reset() {
91+      utime = stime = cutime = cstime = rtime = 0;
92+    }
93+
94+  public:
95+
96+
97+#ifndef WIN32
98+    ///Read the current time values of the process
99+    void stamp()
100+    {
101+      timeval tv;
102+      gettimeofday(&tv, 0);
103+      rtime=tv.tv_sec+double(tv.tv_usec)/1e6;
104+
105+      tms ts;
106+      double tck=sysconf(_SC_CLK_TCK);
107+      times(&ts);
108+      utime=ts.tms_utime/tck;
109+      stime=ts.tms_stime/tck;
110+      cutime=ts.tms_cutime/tck;
111+      cstime=ts.tms_cstime/tck;
112+    }
113+#else
114+    void stamp() {
115+      static const double ch = 4294967296.0e-7;
116+      static const double cl = 1.0e-7;
117+
118+      FILETIME system;
119+      GetSystemTimeAsFileTime(&system);
120+      rtime = ch * system.dwHighDateTime + cl * system.dwLowDateTime;
121+
122+      FILETIME create, exit, kernel, user;
123+      if (GetProcessTimes(GetCurrentProcess(),&create, &exit, &kernel, &user)) {
124+       utime = ch * user.dwHighDateTime + cl * user.dwLowDateTime;
125+       stime = ch * kernel.dwHighDateTime + cl * kernel.dwLowDateTime;
126+       cutime = 0;
127+       cstime = 0;
128+      } else {
129+       rtime = 0;
130+       utime = 0;
131+       stime = 0;
132+       cutime = 0;
133+       cstime = 0;
134+      }
135+    }
136+#endif     
137
138+    /// Constructor initializing with zero
139+    TimeStamp()
140+    { _reset(); }
141+
142+    ///Constructor initializing with the current time values of the process
143+    TimeStamp(void *) { stamp();}
144
145+    ///Set every time value to zero
146+    TimeStamp &reset() {_reset();return *this;}
147+
148+    ///\e
149+    TimeStamp &operator+=(const TimeStamp &b)
150+    {
151+      utime+=b.utime;
152+      stime+=b.stime;
153+      cutime+=b.cutime;
154+      cstime+=b.cstime;
155+      rtime+=b.rtime;
156+      return *this;
157+    }
158+    ///\e
159+    TimeStamp operator+(const TimeStamp &b) const
160+    {
161+      TimeStamp t(*this);
162+      return t+=b;
163+    }
164+    ///\e
165+    TimeStamp &operator-=(const TimeStamp &b)
166+    {
167+      utime-=b.utime;
168+      stime-=b.stime;
169+      cutime-=b.cutime;
170+      cstime-=b.cstime;
171+      rtime-=b.rtime;
172+      return *this;
173+    }
174+    ///\e
175+    TimeStamp operator-(const TimeStamp &b) const
176+    {
177+      TimeStamp t(*this);
178+      return t-=b;
179+    }
180+    ///\e
181+    TimeStamp &operator*=(double b)
182+    {
183+      utime*=b;
184+      stime*=b;
185+      cutime*=b;
186+      cstime*=b;
187+      rtime*=b;
188+      return *this;
189+    }
190+    ///\e
191+    TimeStamp operator*(double b) const
192+    {
193+      TimeStamp t(*this);
194+      return t*=b;
195+    }
196+    friend TimeStamp operator*(double b,const TimeStamp &t);
197+    ///\e
198+    TimeStamp &operator/=(double b)
199+    {
200+      utime/=b;
201+      stime/=b;
202+      cutime/=b;
203+      cstime/=b;
204+      rtime/=b;
205+      return *this;
206+    }
207+    ///\e
208+    TimeStamp operator/(double b) const
209+    {
210+      TimeStamp t(*this);
211+      return t/=b;
212+    }
213+    ///The time ellapsed since the last call of stamp()
214+    TimeStamp ellapsed() const
215+    {
216+      TimeStamp t(NULL);
217+      return t-*this;
218+    }
219
220+    friend std::ostream& operator<<(std::ostream& os,const TimeStamp &t);
221
222+    ///Gives back the user time of the process
223+    double userTime() const
224+    {
225+      return utime;
226+    }
227+    ///Gives back the system time of the process
228+    double systemTime() const
229+    {
230+      return stime;
231+    }
232+    ///Gives back the user time of the process' children
233+    double cUserTime() const
234+    {
235+      return cutime;
236+    }
237+    ///Gives back the user time of the process' children
238+    double cSystemTime() const
239+    {
240+      return cstime;
241+    }
242+    ///Gives back the real time
243+    double realTime() const {
244+      return rtime;
245+    }
246+  };
247+
248+  TimeStamp operator*(double b,const TimeStamp &t)
249+  {
250+    return t*b;
251+  }
252
253+  ///Prints the time counters
254+
255+  ///Prints the time counters in the following form:
256+  ///
257+  /// <tt>u: XX.XXs s: XX.XXs cu: XX.XXs cs: XX.XXs real: XX.XXs</tt>
258+  ///
259+  /// where the values are the
260+  /// \li \c u: user cpu time,
261+  /// \li \c s: system cpu time,
262+  /// \li \c cu: user cpu time of children,
263+  /// \li \c cs: system cpu time of children,
264+  /// \li \c real: real time.
265+  /// \relates TimeStamp
266+  inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t)
267+  {
268+    os << "u: " << t.userTime() <<
269+      "s, s: " << t.systemTime() <<
270+      "s, cu: " << t.cUserTime() <<
271+      "s, cs: " << t.cSystemTime() <<
272+      "s, real: " << t.realTime() << "s";
273+    return os;
274+  }
275+
276+  ///Class for measuring the cpu time and real time usage of the process
277+
278+  ///Class for measuring the cpu time and real time usage of the process.
279+  ///It is quite easy-to-use, here is a short example.
280+  ///\code
281+  /// #include<lemon/time_measure.h>
282+  /// #include<iostream>
283+  ///
284+  /// int main()
285+  /// {
286+  ///
287+  ///   ...
288+  ///
289+  ///   Timer t;
290+  ///   doSomething();
291+  ///   std::cout << t << '\n';
292+  ///   t.restart();
293+  ///   doSomethingElse();
294+  ///   std::cout << t << '\n';
295+  ///
296+  ///   ...
297+  ///
298+  /// }
299+  ///\endcode
300+  ///
301+  ///The \ref Timer can also be \ref stop() "stopped" and
302+  ///\ref start() "started" again, so it is possible to compute collected
303+  ///running times.
304+  ///
305+  ///\warning Depending on the operation system and its actual configuration
306+  ///the time counters have a certain (10ms on a typical Linux system)
307+  ///granularity.
308+  ///Therefore this tool is not appropriate to measure very short times.
309+  ///Also, if you start and stop the timer very frequently, it could lead to
310+  ///distorted results.
311+  ///
312+  ///\note If you want to measure the running time of the execution of a certain
313+  ///function, consider the usage of \ref TimeReport instead.
314+  ///
315+  ///\todo This shouldn't be Unix (Linux) specific.
316+  ///\sa TimeReport
317+  ///
318+  ///\author Alpar Juttner
319+  class Timer
320+  {
321+    int _running; //Timer is running iff _running>0; (_running>=0 always holds)
322+    TimeStamp start_time; //This is the relativ start-time if the timer
323+                          //is _running, the collected _running time otherwise.
324+   
325+    void _reset() {if(_running) start_time.stamp(); else start_time.reset();}
326
327+  public:
328+    ///Constructor.
329+
330+    ///\param run indicates whether or not the timer starts immediately.
331+    ///
332+    Timer(bool run=true) :_running(run) {_reset();}
333+
334+    ///\name Control the state of the timer
335+    ///Basically a Timer can be either running or stopped,
336+    ///but it provides a bit finer control on the execution.
337+    ///The \ref Timer also counts the number of \ref start()
338+    ///executions, and is stops only after the same amount (or more)
339+    ///\ref stop() "stop()"s. This can be useful e.g. to compute the running time
340+    ///of recursive functions.
341+    ///
342+
343+    ///@{
344+
345+    ///Reset and stop the time counters
346+
347+    ///This function resets and stops the time counters
348+    ///\sa restart()
349+    void reset()
350+    {
351+      _running=0;
352+      _reset();
353+    }
354+
355+    ///Start the time counters
356+   
357+    ///This function starts the time counters.
358+    ///
359+    ///If the timer is started more than ones, it will remain running
360+    ///until the same amount of \ref stop() is called.
361+    ///\sa stop()
362+    void start()
363+    {
364+      if(_running) _running++;
365+      else {
366+       _running=1;
367+       TimeStamp t;
368+       t.stamp();
369+       start_time=t-start_time;
370+      }
371+    }
372+
373+   
374+    ///Stop the time counters
375+
376+    ///This function stops the time counters. If start() was executed more than
377+    ///once, then the same number of stop() execution is necessary the really
378+    ///stop the timer.
379+    ///
380+    ///\sa halt()
381+    ///\sa start()
382+    ///\sa restart()
383+    ///\sa reset()
384+
385+    void stop()
386+    {
387+      if(_running && !--_running) {
388+       TimeStamp t;
389+       t.stamp();
390+       start_time=t-start_time;
391+      }
392+    }
393+
394+    ///Halt (i.e stop immediately) the time counters
395+
396+    ///This function stops immediately the time counters, i.e. <tt>t.stop()</tt>
397+    ///is a faster
398+    ///equivalent of the following.
399+    ///\code
400+    ///  while(t.running()) t.stop()
401+    ///\endcode
402+    ///
403+    ///
404+    ///\sa stop()
405+    ///\sa restart()
406+    ///\sa reset()
407+
408+    void halt()
409+    {
410+      if(_running) {
411+       _running=0;
412+       TimeStamp t;
413+       t.stamp();
414+       start_time=t-start_time;
415+      }
416+    }
417+
418+    ///Returns the running state of the timer
419+
420+    ///This function returns the number of stop() exections that is
421+    ///necessary to really stop the timer.
422+    ///For example the timer
423+    ///is running if and only if the return value is \c true
424+    ///(i.e. greater than
425+    ///zero).
426+    int running()  { return _running; }
427+   
428+   
429+    ///Restart the time counters
430+
431+    ///This function is a shorthand for
432+    ///a reset() and a start() calls.
433+    ///
434+    void restart()
435+    {
436+      reset();
437+      start();
438+    }
439+   
440+    ///@}
441+
442+    ///\name Query Functions for the ellapsed time
443+
444+    ///@{
445+
446+    ///Gives back the ellapsed user time of the process
447+    double userTime() const
448+    {
449+      return operator TimeStamp().userTime();
450+    }
451+    ///Gives back the ellapsed system time of the process
452+    double systemTime() const
453+    {
454+      return operator TimeStamp().systemTime();
455+    }
456+    ///Gives back the ellapsed user time of the process' children
457+    double cUserTime() const
458+    {
459+      return operator TimeStamp().cUserTime();
460+    }
461+    ///Gives back the ellapsed user time of the process' children
462+    double cSystemTime() const
463+    {
464+      return operator TimeStamp().cSystemTime();
465+    }
466+    ///Gives back the ellapsed real time
467+    double realTime() const
468+    {
469+      return operator TimeStamp().realTime();
470+    }
471+    ///Computes the ellapsed time
472+
473+    ///This conversion computes the ellapsed time, therefore you can print
474+    ///the ellapsed time like this.
475+    ///\code
476+    ///  Timer t;
477+    ///  doSomething();
478+    ///  std::cout << t << '\n';
479+    ///\endcode
480+    operator TimeStamp () const
481+    {
482+      TimeStamp t;
483+      t.stamp();
484+      return _running?t-start_time:start_time;
485+    }
486+
487+
488+    ///@}
489+  };
490+
491+  ///Same as \ref Timer but prints a report on destruction.
492+
493+  ///Same as \ref Timer but prints a report on destruction.
494+  ///This example shows its usage.
495+  ///\code
496+  ///  void myAlg(ListGraph &g,int n)
497+  ///  {
498+  ///    TimeReport tr("Running time of myAlg: ");
499+  ///    ... //Here comes the algorithm
500+  ///  }
501+  ///\endcode
502+  ///
503+  ///\sa Timer
504+  ///\sa NoTimeReport
505+  ///\todo There is no test case for this
506+  class TimeReport : public Timer
507+  {
508+    std::string _title;
509+    std::ostream &_os;
510+  public:
511+    ///\e
512+
513+    ///\param title This text will be printed before the ellapsed time.
514+    ///\param os The stream to print the report to.
515+    ///\param run Sets whether the timer should start immediately.
516+
517+    TimeReport(std::string title,std::ostream &os=std::cerr,bool run=true)
518+      : Timer(run), _title(title), _os(os){}
519+    ///\e Prints the ellapsed time on destruction.
520+    ~TimeReport()
521+    {
522+      _os << _title << *this << std::endl;
523+    }
524+  };
525+     
526+  ///'Do nothing' version of \ref TimeReport
527+
528+  ///\sa TimeReport
529+  ///
530+  class NoTimeReport
531+  {
532+  public:
533+    ///\e
534+    NoTimeReport(std::string,std::ostream &,bool) {}
535+    ///\e
536+    NoTimeReport(std::string,std::ostream &) {}
537+    ///\e
538+    NoTimeReport(std::string) {}
539+    ///\e Do nothing.
540+    ~NoTimeReport() {}
541+
542+    operator TimeStamp () const { return TimeStamp(); }
543+    void reset() {}
544+    void start() {}
545+    void stop() {}
546+    void halt() {}
547+    int running() { return 0; }
548+    void restart() {}
549+    double userTime() const { return 0; }
550+    double systemTime() const { return 0; }
551+    double cUserTime() const { return 0; }
552+    double cSystemTime() const { return 0; }
553+    double realTime() const { return 0; }
554+  };
555+     
556+  ///Tool to measure the running time more exactly.
557
558+  ///This function calls \c f several times and returns the average
559+  ///running time. The number of the executions will be choosen in such a way
560+  ///that the full real running time will be roughly between \c min_time
561+  ///and <tt>2*min_time</tt>.
562+  ///\param f the function object to be measured.
563+  ///\param min_time the minimum total running time.
564+  ///\retval num if it is not \c NULL, then the actual
565+  ///        number of execution of \c f will be written into <tt>*num</tt>.
566+  ///\retval full_time if it is not \c NULL, then the actual
567+  ///        total running time will be written into <tt>*full_time</tt>.
568+  ///\return The average running time of \c f.
569
570+  template<class F>
571+  TimeStamp runningTimeTest(F f,double min_time=10,unsigned int *num = NULL,
572+                            TimeStamp *full_time=NULL)
573+  {
574+    TimeStamp full;
575+    unsigned int total=0;
576+    Timer t;
577+    for(unsigned int tn=1;tn < 1U<<31 && full.realTime()<=min_time; tn*=2) {
578+      for(;total<tn;total++) f();
579+      full=t;
580+    }
581+    if(num) *num=total;
582+    if(full_time) *full_time=full;
583+    return full/total;
584+  }
585
586+  /// @} 
587+
588+
589+} //namespace lemon
590+
591+
592+#endif //LEMON_TIME_MEASURE_H
593diff -r 7b0ce9fb1169 -r 8bed93ad51f4 test/Makefile.am
594--- a/test/Makefile.am  Wed Apr 09 17:19:40 2008 +0100
595+++ b/test/Makefile.am  Fri Apr 11 18:44:28 2008 +0200
596@@ -20,6 +20,7 @@ check_PROGRAMS += \
597         test/path_test \
598         test/test_tools_fail \
599         test/test_tools_pass \
600+       test/time_measure_test \
601        test/unionfind_test
602 
603 TESTS += $(check_PROGRAMS)
604@@ -38,4 +39,5 @@ test_random_test_SOURCES = test/random_t
605 test_random_test_SOURCES = test/random_test.cc
606 test_test_tools_fail_SOURCES = test/test_tools_fail.cc
607 test_test_tools_pass_SOURCES = test/test_tools_pass.cc
608+test_time_measure_test_SOURCES = test/time_measure_test.cc
609 test_unionfind_test_SOURCES = test/unionfind_test.cc
610diff -r 7b0ce9fb1169 -r 8bed93ad51f4 test/time_measure_test.cc
611--- /dev/null   Thu Jan 01 00:00:00 1970 +0000
612+++ b/test/time_measure_test.cc Fri Apr 11 18:44:28 2008 +0200
613@@ -0,0 +1,63 @@
614+/* -*- C++ -*-
615+ *
616+ * This file is a part of LEMON, a generic C++ optimization library
617+ *
618+ * Copyright (C) 2003-2008
619+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
620+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
621+ *
622+ * Permission to use, modify and distribute this software is granted
623+ * provided that this copyright notice appears in all copies. For
624+ * precise terms see the accompanying LICENSE file.
625+ *
626+ * This software is provided "AS IS" with no warranty of any kind,
627+ * express or implied, and with no claim as to its suitability for any
628+ * purpose.
629+ *
630+ */
631+
632+#include <lemon/time_measure.h>
633+
634+///\file \brief Test cases for time_measure.h
635+///
636+///\todo To be extended
637+
638+
639+using namespace lemon;
640+
641+void f()
642+{
643+  double d=0;
644+  for(int i=0;i<1000;i++)
645+    d+=0.1;
646+}
647+
648+void g()
649+{
650+  static Timer T;
651
652+  for(int i=0;i<1000;i++)
653+    TimeStamp x(T);
654+}
655+
656+int main()
657+{
658+  Timer T;
659+  unsigned int n;
660+  for(n=0;T.realTime()<1.0;n++) ;
661+  std::cout << T << " (" << n << " time queries)\n";
662+  T.restart();
663+  while(T.realTime()<2.0) ;
664+  std::cout << T << '\n';
665+  TimeStamp full;
666+  TimeStamp t;
667+  t=runningTimeTest(f,1,&n,&full);
668+  std::cout << t << " (" << n << " tests)\n";
669+  std::cout << "Total: " << full << "\n";
670
671+  t=runningTimeTest(g,1,&n,&full);
672+  std::cout << t << " (" << n << " tests)\n";
673+  std::cout << "Total: " << full << "\n";
674
675+  return 0;
676+}