Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
stats.h
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// Helper classes to track statistics of a program component.
15//
16// Usage example:
17// // Suppose you have a class that contains a factorization of a matrix B and
18// // a Solve() function to solve the linear system B.x = a.
19//
20// // You will hold your stats in a Stats stats_ class member:
21// struct Stats : public StatsGroup {
22// Stats() : StatsGroup("BasisFactorization"),
23// solve_time("solve_time", this),
24// input_vector_density("input_vector_density", this),
25// estimated_accuracy("estimated_accuracy", this) {}
26//
27// TimeDistribution solve_time;
28// RatioDistribution input_vector_density;
29//
30// // Values of a few components of B.x - a, updated on each solve.
31// DoubleDistribution estimated_accuracy;
32// }
33//
34// // You then add a few lines to your Solve() function:
35// void Solve() {
36// stats_.solve_time.StartTimer();
37// stats_.input_vector_density.Add(ComputeDensity());
38// ... // Do the work.
39// stats_.estimated_accuracy.Add(EstimateAccuracy());
40// stats_.solve_time.StopTimerAndAddElapsedTime();
41// }
42//
43// // Now, calling stats_.StatString() will give you a summary of your stats:
44// BasisFactorization {
45// solve_time : num [min, max] average std_deviation total
46// input_vector_density : num [min, max] average std_deviation
47// estimated_accuracy : num [min, max] average std_deviation
48// }
49//
50// For measuring time, another alternative is to use the SCOPED_TIME_STAT macro.
51// In our example above, you don't need to define the solve_time distribution
52// and you can just do:
53//
54// void Solve() {
55// SCOPED_TIME_STAT(&stats_);
56// ...
57// }
58//
59// This automatically adds a TimeDistribution with name "Solve" to stats_ and
60// times your function calls!
61//
62// IMPORTANT: The SCOPED_TIME_STAT() macro only does something if OR_STATS is
63// defined, so you need to build your code with blaze build --copt='-DOR_STATS'.
64// The idea is that by default the instrumentation is off. You can also use the
65// macro IF_STATS_ENABLED() that does nothing if OR_STATS is not defined or just
66// translates to its argument otherwise.
67
68#ifndef OR_TOOLS_UTIL_STATS_H_
69#define OR_TOOLS_UTIL_STATS_H_
70
71#include <cstdint>
72#include <functional>
73#include <map>
74#include <memory>
75#include <string>
76#include <vector>
77
78#include "absl/container/flat_hash_map.h"
79#include "absl/strings/string_view.h"
80#include "absl/time/time.h"
81#include "ortools/base/timer.h"
82
83namespace operations_research {
84
85// Returns the current thread's total memory usage in an human-readable string.
86std::string MemoryUsage();
87
88// Forward declaration.
89class StatsGroup;
91
92// Base class for a statistic that can be pretty-printed.
93class Stat {
94 public:
95 explicit Stat(absl::string_view name) : name_(name) {}
96
97 // Also add this stat to the given group.
98 Stat(absl::string_view name, StatsGroup* group);
99 virtual ~Stat() {}
100
101 // Only used for display purposes.
102 std::string Name() const { return name_; }
103
104 // Returns a human-readable formatted line of the form "name:
105 // ValueAsString()".
106 std::string StatString() const;
107
108 // At display, stats are displayed by decreasing priority, then decreasing
109 // Sum(), then alphabetical order.
110 // Used to group the stats per category (timing, ratio, etc..,).
111 virtual int Priority() const { return 0; }
112
113 // By default return 0 for the sum. This makes it possible to sort stats by
114 // decreasing total time.
115 virtual double Sum() const { return 0; }
116
117 // Prints information about this statistic.
118 virtual std::string ValueAsString() const = 0;
119
120 // Is this stat worth printing? Usually false if nothing was measured.
121 virtual bool WorthPrinting() const = 0;
122
123 // Reset this statistic to the same state as if it was newly created.
124 virtual void Reset() = 0;
125
126 private:
127 const std::string name_;
128};
129
130// Base class to print a nice summary of a group of statistics.
132 public:
137
138 explicit StatsGroup(absl::string_view name)
139 : name_(name), stats_(), time_distributions_() {}
140
141 // This type is neither copyable nor movable.
142 StatsGroup(const StatsGroup&) = delete;
143 StatsGroup& operator=(const StatsGroup&) = delete;
144 ~StatsGroup() = default;
145
146 // Registers a Stat, which will appear in the string returned by StatString().
147 // The Stat object must live as long as this StatsGroup.
148 void Register(Stat* stat);
149
150 // Returns this group name, followed by one line per Stat registered with this
151 // group (this includes the ones created by LookupOrCreateTimeDistribution()).
152 // Note that only the stats WorthPrinting() are printed.
153 std::string StatString() const;
154
155 // Changes the print ordering (will affect the order in which the stats
156 // registered with this group are printed via StatString()).
157 void SetPrintOrder(PrintOrder print_order) { print_order_ = print_order; }
158
159 // Returns and if needed creates and registers a TimeDistribution with the
160 // given name. Note that this involve a hash map lookup and is thus slower
161 // than directly accessing a TimeDistribution variable.
162 TimeDistribution* LookupOrCreateTimeDistribution(absl::string_view name);
163
164 // Calls Reset() on all the statistics registered with this group.
165 void Reset();
166
167 private:
168 std::string name_;
170 std::vector<Stat*> stats_;
171 absl::flat_hash_map<std::string, std::unique_ptr<TimeDistribution>>
172 time_distributions_;
173};
174
175// Base class to track and compute statistics about the distribution of a
176// sequence of double. We provide a few sub-classes below that differ in the way
177// the values are added to the sequence and in the way the stats are printed.
178class DistributionStat : public Stat {
179 public:
180 explicit DistributionStat(absl::string_view name);
182 DistributionStat(absl::string_view name, StatsGroup* group);
183 ~DistributionStat() override {}
184 void Reset() override;
185 bool WorthPrinting() const override { return num_ != 0; }
186
187 // Implemented by the subclasses.
188 std::string ValueAsString() const override = 0;
189
190 // Trivial statistics on all the values added so far.
191 double Sum() const override { return sum_; }
192 double Max() const { return max_; }
193 double Min() const { return min_; }
194 int64_t Num() const { return num_; }
195
196 // Get the average of the distribution or 0.0 if empty.
197 double Average() const;
198
199 // Get the standard deviation of the distribution or 0.0 if empty.
200 // We use the on-line algorithm of Welford described at
201 // http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance
202 // TODO(user): We could also use on top the Kahan summation algorithm to be
203 // even more precise but a bit slower too.
204 double StdDeviation() const;
205
206 protected:
207 // Adds a value to this sequence and updates the stats.
208 void AddToDistribution(double value);
209 double sum_;
210 double average_;
212 double min_;
213 double max_;
214 int64_t num_;
215};
216
217// Statistic on the distribution of a sequence of running times.
218// Also provides some facility to measure such time with the CPU cycle counter.
219//
220// TODO(user): Since we inherit from DistributionStat, we currently store the
221// sum of CPU cycles as a double internally. A better option is to use int64_t
222// because with the 53 bits of precision of a double, we will run into an issue
223// if the sum of times reaches 52 days for a 2GHz processor.
225 public:
226 explicit TimeDistribution(absl::string_view name)
227 : DistributionStat(name), timer_() {}
229 TimeDistribution(absl::string_view name, StatsGroup* group)
230 : DistributionStat(name, group), timer_() {}
231 std::string ValueAsString() const override;
232
233 // Time distributions have a high priority to be displayed first.
234 int Priority() const override { return 100; }
235
236 // Internally the TimeDistribution stores CPU cycles (to do a bit less work
237 // on each StopTimerAndAddElapsedTime()). Use this function to convert
238 // all the statistics of DistributionStat into seconds.
239 static double CyclesToSeconds(double num_cycles);
240
241 // Adds a time in seconds to this distribution.
242 void AddTimeInSec(double seconds);
243 void AddTime(absl::Duration duration) {
244 AddTimeInSec(absl::ToDoubleSeconds(duration));
245 }
246
247 // Adds a time in CPU cycles to this distribution.
248 void AddTimeInCycles(double cycles);
249
250 // Starts the timer in preparation of a StopTimerAndAddElapsedTime().
251 inline void StartTimer() { timer_.Restart(); }
252
253 // Adds the elapsed time since the last StartTimer() to the distribution and
254 // returns this time in CPU cycles.
256 const double cycles = static_cast<double>(timer_.GetCycles());
257 AddToDistribution(cycles);
258 return cycles;
259 }
260
261 private:
262 // Converts and prints a number of cycles in an human readable way using the
263 // proper time unit depending on the value (ns, us, ms, s, m or h).
264 static std::string PrintCyclesAsTime(double cycles);
265 CycleTimer timer_;
266};
267
268// Statistic on the distribution of a sequence of ratios, displayed as %.
270 public:
271 explicit RatioDistribution(absl::string_view name) : DistributionStat(name) {}
273 RatioDistribution(absl::string_view name, StatsGroup* group)
274 : DistributionStat(name, group) {}
275 std::string ValueAsString() const override;
276 void Add(double value);
277};
278
279// Statistic on the distribution of a sequence of doubles.
281 public:
282 explicit DoubleDistribution(absl::string_view name)
283 : DistributionStat(name) {}
285 DoubleDistribution(absl::string_view name, StatsGroup* group)
286 : DistributionStat(name, group) {}
287 std::string ValueAsString() const override;
288 void Add(double value);
289};
290
291// Statistic on the distribution of a sequence of integers.
293 public:
294 explicit IntegerDistribution(absl::string_view name)
295 : DistributionStat(name) {}
297 IntegerDistribution(absl::string_view name, StatsGroup* group)
298 : DistributionStat(name, group) {}
299 std::string ValueAsString() const override;
300 void Add(int64_t value);
301};
302
303// Helper classes to time a block of code and add the result to a
304// TimeDistribution. Calls StartTimer() on creation and
305// StopTimerAndAddElapsedTime() on destruction.
306//
307// There are three classes with the same interface:
308// * EnabledScopedTimeDistributionUpdater always collects the time stats of the
309// scope in which it is defined. This class is used for stats that are always
310// collected.
311// * ScopedTimeDistributionUpdater collects the time stats only when OR_STATS is
312// defined. This symbol should be used for collecting stats in places where
313// the overhead of collecting the stats may hurt the performance of the
314// algorithm.
315// * DisabledScopedTimeDistributionUpdater is used to implement
316// ScopedTimeDistributionUpdater when OR_STATS is not defined.
318 public:
319 // Note that this does not take ownership of the given stat.
321 : stat_(stat), also_update_(nullptr) {
322 stat->StartTimer();
323 }
324
325 // This type is neither copyable nor movable.
331 const double cycles = stat_->StopTimerAndAddElapsedTime();
332 if (also_update_ != nullptr) {
333 also_update_->AddTimeInCycles(cycles);
334 }
335 }
336
337 // Updates another TimeDistribution on destruction. This is useful to split
338 // a total time measurement in different categories:
339 //
340 // EnabledScopedTimeDistributionUpdater timer(&total_timer);
341 // ...
342 // switch (type) {
343 // case TypeA : timer.AlsoUpdate(&typeA_timer); break;
344 // case TypeB : timer.AlsoUpdate(&typeB_timer); break;
345 // }
346 void AlsoUpdate(TimeDistribution* also_update) { also_update_ = also_update; }
347
348 private:
349 TimeDistribution* stat_;
350 TimeDistribution* also_update_;
351};
352
364
373
374// Measures the time from this macro line to the end of the scope and adds it
375// to the distribution (from the given StatsGroup) with the same name as the
376// enclosing function.
377//
378// Note(user): This adds more extra overhead around the measured code compared
379// to defining your own TimeDistribution stat in your StatsGroup. About 80ns
380// per measurement compared to about 20ns (as of 2012-06, on my workstation).
382 public:
384 absl::string_view function_name)
385 : scoped_time_stat_(
386 stats->LookupOrCreateTimeDistribution(function_name)) {}
391
392 private:
394};
395
396#ifdef OR_STATS
397
400
401// Simple macro to be used by a client that want to execute costly operations
402// only if OR_STATS is defined.
403#define IF_STATS_ENABLED(instructions) instructions
404
405#else // !OR_STATS
406// If OR_STATS is not defined, we remove some instructions that may be time
407// consuming.
408
411
412// Defining it that way makes sure that the compiler still sees the code and
413// checks that the syntax & types are valid.
414#define IF_STATS_ENABLED(instructions) \
415 if constexpr (false) { \
416 instructions; \
417 }
418
419#endif // OR_STATS
420
421#define SCOPED_TIME_STAT(stats) \
422 operations_research::ScopedTimeStats scoped_time_stat(stats, __FUNCTION__);
423
424#define SCOPED_INSTRUCTION_COUNT(time_limit)
425
426} // namespace operations_research
427
428#endif // OR_TOOLS_UTIL_STATS_H_
DisabledScopedTimeDistributionUpdater(const DisabledScopedTimeDistributionUpdater &)=delete
This type is neither copyable nor movable.
DisabledScopedTimeDistributionUpdater & operator=(const DisabledScopedTimeDistributionUpdater &)=delete
DisabledScopedTimeStats(StatsGroup *, const char *)
Definition stats.h:367
DisabledScopedTimeStats & operator=(DisabledScopedTimeStats &&)=delete
DisabledScopedTimeStats(const DisabledScopedTimeStats &)=delete
DisabledScopedTimeStats(DisabledScopedTimeStats &&)=delete
DisabledScopedTimeStats & operator=(const DisabledScopedTimeStats &)=delete
double Average() const
Get the average of the distribution or 0.0 if empty.
Definition stats.cc:175
bool WorthPrinting() const override
Is this stat worth printing? Usually false if nothing was measured.
Definition stats.h:185
double Sum() const override
Trivial statistics on all the values added so far.
Definition stats.h:191
void AddToDistribution(double value)
Adds a value to this sequence and updates the stats.
Definition stats.cc:157
std::string ValueAsString() const override=0
Implemented by the subclasses.
void Reset() override
Reset this statistic to the same state as if it was newly created.
Definition stats.cc:148
DistributionStat(absl::string_view name)
Definition stats.cc:130
std::string ValueAsString() const override
Implemented by the subclasses.
Definition stats.cc:231
DoubleDistribution(absl::string_view name, StatsGroup *group)
Definition stats.h:285
DoubleDistribution(absl::string_view name)
Definition stats.h:282
EnabledScopedTimeDistributionUpdater(TimeDistribution *stat)
Definition stats.h:320
EnabledScopedTimeDistributionUpdater(const EnabledScopedTimeDistributionUpdater &)=delete
This type is neither copyable nor movable.
void AlsoUpdate(TimeDistribution *also_update)
Definition stats.h:346
EnabledScopedTimeDistributionUpdater & operator=(const EnabledScopedTimeDistributionUpdater &)=delete
EnabledScopedTimeStats & operator=(const EnabledScopedTimeStats &)=delete
EnabledScopedTimeStats(StatsGroup *stats, absl::string_view function_name)
Definition stats.h:383
EnabledScopedTimeStats(const EnabledScopedTimeStats &)=delete
EnabledScopedTimeStats & operator=(EnabledScopedTimeStats &&)=delete
EnabledScopedTimeStats(EnabledScopedTimeStats &&)=delete
IntegerDistribution(absl::string_view name, StatsGroup *group)
Definition stats.h:297
std::string ValueAsString() const override
Implemented by the subclasses.
Definition stats.cc:240
IntegerDistribution(absl::string_view name)
Definition stats.h:294
std::string ValueAsString() const override
Implemented by the subclasses.
Definition stats.cc:223
RatioDistribution(absl::string_view name, StatsGroup *group)
Definition stats.h:273
RatioDistribution(absl::string_view name)
Definition stats.h:271
Base class for a statistic that can be pretty-printed.
Definition stats.h:93
std::string Name() const
Only used for display purposes.
Definition stats.h:102
virtual bool WorthPrinting() const =0
Is this stat worth printing? Usually false if nothing was measured.
virtual int Priority() const
Definition stats.h:111
virtual std::string ValueAsString() const =0
Prints information about this statistic.
Stat(absl::string_view name)
Definition stats.h:95
std::string StatString() const
Definition stats.cc:54
virtual double Sum() const
Definition stats.h:115
virtual void Reset()=0
Reset this statistic to the same state as if it was newly created.
Base class to print a nice summary of a group of statistics.
Definition stats.h:131
StatsGroup(const StatsGroup &)=delete
This type is neither copyable nor movable.
void SetPrintOrder(PrintOrder print_order)
Definition stats.h:157
StatsGroup & operator=(const StatsGroup &)=delete
TimeDistribution * LookupOrCreateTimeDistribution(absl::string_view name)
Definition stats.cc:120
StatsGroup(absl::string_view name)
Definition stats.h:138
std::string StatString() const
Definition stats.cc:77
void Reset()
Calls Reset() on all the statistics registered with this group.
Definition stats.cc:58
void Register(Stat *stat)
Definition stats.cc:56
std::string ValueAsString() const override
Implemented by the subclasses.
Definition stats.cc:211
void AddTimeInSec(double seconds)
Adds a time in seconds to this distribution.
Definition stats.cc:200
TimeDistribution(absl::string_view name)
Definition stats.h:226
TimeDistribution(absl::string_view name, StatsGroup *group)
Definition stats.h:229
static double CyclesToSeconds(double num_cycles)
Definition stats.cc:182
void StartTimer()
Starts the timer in preparation of a StopTimerAndAddElapsedTime().
Definition stats.h:251
void AddTime(absl::Duration duration)
Definition stats.h:243
int Priority() const override
Time distributions have a high priority to be displayed first.
Definition stats.h:234
void AddTimeInCycles(double cycles)
Adds a time in CPU cycles to this distribution.
Definition stats.cc:206
In SWIG mode, we don't want anything besides these top-level includes.
DisabledScopedTimeDistributionUpdater ScopedTimeDistributionUpdater
Definition stats.h:409
DisabledScopedTimeStats ScopedTimeStats
Definition stats.h:410
std::string MemoryUsage()
Returns the current thread's total memory usage in an human-readable string.
Definition stats.cc:33