C++ Reference

C++ Reference: CP-SAT

time_limit.h
Go to the documentation of this file.
1// Copyright 2010-2018 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#ifndef OR_TOOLS_UTIL_TIME_LIMIT_H_
15#define OR_TOOLS_UTIL_TIME_LIMIT_H_
16
17#include <algorithm>
18#include <atomic>
19#include <cstdlib>
20#include <limits>
21#include <memory>
22#include <string>
23
24#include "absl/container/flat_hash_map.h"
25#include "absl/memory/memory.h"
26#include "absl/synchronization/mutex.h"
27#include "absl/time/clock.h"
28#include "ortools/base/commandlineflags.h"
29#include "ortools/base/logging.h"
30#include "ortools/base/macros.h"
31#include "ortools/base/timer.h"
32#include "ortools/util/running_stat.h"
33#ifdef HAS_PERF_SUBSYSTEM
34#include "exegesis/exegesis/itineraries/perf_subsystem.h"
35#endif // HAS_PERF_SUBSYSTEM
36
41ABSL_DECLARE_FLAG(bool, time_limit_use_usertime);
42
47ABSL_DECLARE_FLAG(bool, time_limit_use_instruction_count);
48
49namespace operations_research {
50
103// TODO(user): The expression "deterministic time" should be replaced with
104// "number of operations" to avoid confusion with "real" time.
106 public:
107 static const double kSafetyBufferSeconds; // See the .cc for the value.
108 static const int kHistorySize;
109
121 explicit TimeLimit(
122 double limit_in_seconds,
123 double deterministic_limit = std::numeric_limits<double>::infinity(),
124 double instruction_limit = std::numeric_limits<double>::infinity());
125
126 TimeLimit() : TimeLimit(std::numeric_limits<double>::infinity()) {}
127 TimeLimit(const TimeLimit&) = delete;
128 TimeLimit& operator=(const TimeLimit&) = delete;
129
134 static std::unique_ptr<TimeLimit> Infinite() {
135 return absl::make_unique<TimeLimit>(
136 std::numeric_limits<double>::infinity(),
137 std::numeric_limits<double>::infinity(),
138 std::numeric_limits<double>::infinity());
139 }
140
144 static std::unique_ptr<TimeLimit> FromDeterministicTime(
145 double deterministic_limit) {
146 return absl::make_unique<TimeLimit>(
147 std::numeric_limits<double>::infinity(), deterministic_limit,
148 std::numeric_limits<double>::infinity());
149 }
150
157 // TODO(user): Support adding instruction count limit from parameters.
158 template <typename Parameters>
159 static std::unique_ptr<TimeLimit> FromParameters(
160 const Parameters& parameters) {
161 return absl::make_unique<TimeLimit>(
162 parameters.max_time_in_seconds(), parameters.max_deterministic_time(),
163 std::numeric_limits<double>::infinity());
164 }
165
171 void SetInstructionLimit(double instruction_limit) {
172 instruction_limit_ = instruction_limit;
173 }
174
179 // TODO(user): Use an exact counter for counting instructions. The
180 // PMU counter returns the instruction count value as double since there may
181 // be sampling issues.
182 double ReadInstructionCounter();
183
190 bool LimitReached();
191
204 double GetTimeLeft() const;
205
213 return std::max(0.0, deterministic_limit_ - elapsed_deterministic_time_);
214 }
215
219 double GetInstructionsLeft();
220
226 inline void AdvanceDeterministicTime(double deterministic_duration) {
227 DCHECK_LE(0.0, deterministic_duration);
228 elapsed_deterministic_time_ += deterministic_duration;
229 }
230
240 inline void AdvanceDeterministicTime(double deterministic_duration,
241 const char* counter_name) {
242 AdvanceDeterministicTime(deterministic_duration);
243#ifndef NDEBUG
244 deterministic_counters_[counter_name] += deterministic_duration;
245#endif
246 }
247
251 double GetElapsedTime() const {
252 return 1e-9 * (absl::GetCurrentTimeNanos() - start_ns_);
253 }
254
261 return elapsed_deterministic_time_;
262 }
263
273 std::atomic<bool>* external_boolean_as_limit) {
274 external_boolean_as_limit_ = external_boolean_as_limit;
275 }
276
280 std::atomic<bool>* ExternalBooleanAsLimit() const {
281 return external_boolean_as_limit_;
282 }
283
288 template <typename Parameters>
289 void ResetLimitFromParameters(const Parameters& parameters);
291
295 std::string DebugString() const;
296
297 private:
298 void ResetTimers(double limit_in_seconds, double deterministic_limit,
299 double instruction_limit);
300
301 std::string GetInstructionRetiredEventName() const {
302 return "inst_retired:any_p:u";
303 }
304
305 mutable int64 start_ns_; // Not const! this is initialized after instruction
306 // counter initialization.
307 int64 last_ns_;
308 int64 limit_ns_; // Not const! See the code of LimitReached().
309 const int64 safety_buffer_ns_;
310 RunningMax<int64> running_max_;
311
312 // Only used when FLAGS_time_limit_use_usertime is true.
313 UserTimer user_timer_;
314 double limit_in_seconds_;
315
316 double deterministic_limit_;
317 double elapsed_deterministic_time_;
318
319 std::atomic<bool>* external_boolean_as_limit_;
320
321#ifdef HAS_PERF_SUBSYSTEM
322 // PMU counter to help count the instructions.
323 exegesis::PerfSubsystem perf_subsystem_;
324#endif // HAS_PERF_SUBSYSTEM
325 // Given limit in terms of number of instructions.
326 double instruction_limit_;
327
328#ifndef NDEBUG
329 // Contains the values of the deterministic time counters.
330 absl::flat_hash_map<std::string, double> deterministic_counters_;
331#endif
332
333 friend class NestedTimeLimit;
334 friend class ParallelTimeLimit;
335};
336
337// Wrapper around TimeLimit to make it thread safe and add Stop() support.
339 public:
340 explicit SharedTimeLimit(TimeLimit* time_limit)
341 : time_limit_(time_limit), stopped_boolean_(false) {
342 // We use the one already registered if present or ours otherwise.
343 stopped_ = time_limit->ExternalBooleanAsLimit();
344 if (stopped_ == nullptr) {
345 stopped_ = &stopped_boolean_;
346 time_limit->RegisterExternalBooleanAsLimit(stopped_);
347 }
348 }
349
351 if (stopped_ == &stopped_boolean_) {
352 time_limit_->RegisterExternalBooleanAsLimit(nullptr);
353 }
354 }
355
356 bool LimitReached() const {
357 // Note, time_limit_->LimitReached() is not const, and changes internal
358 // state of time_limit_, hence we need a writer's lock.
359 absl::MutexLock lock(&mutex_);
360 return time_limit_->LimitReached();
361 }
362
363 void Stop() {
364 absl::MutexLock lock(&mutex_);
365 *stopped_ = true;
366 }
367
368 void UpdateLocalLimit(TimeLimit* local_limit) {
369 absl::MutexLock lock(&mutex_);
370 local_limit->MergeWithGlobalTimeLimit(time_limit_);
371 }
372
373 void AdvanceDeterministicTime(double deterministic_duration) {
374 absl::MutexLock lock(&mutex_);
375 time_limit_->AdvanceDeterministicTime(deterministic_duration);
376 }
377
378 double GetTimeLeft() const {
379 absl::ReaderMutexLock lock(&mutex_);
380 return time_limit_->GetTimeLeft();
381 }
382
384 absl::ReaderMutexLock lock(&mutex_);
385 return time_limit_->GetElapsedDeterministicTime();
386 }
387
388 private:
389 mutable absl::Mutex mutex_;
390 TimeLimit* time_limit_ ABSL_GUARDED_BY(mutex_);
391 std::atomic<bool> stopped_boolean_ ABSL_GUARDED_BY(mutex_);
392 std::atomic<bool>* stopped_ ABSL_GUARDED_BY(mutex_);
393};
394
426 public:
431 NestedTimeLimit(TimeLimit* base_time_limit, double limit_in_seconds,
432 double deterministic_limit);
433
438
446 template <typename Parameters>
447 static std::unique_ptr<NestedTimeLimit> FromBaseTimeLimitAndParameters(
448 TimeLimit* time_limit, const Parameters& parameters) {
449 return absl::make_unique<NestedTimeLimit>(
450 time_limit, parameters.max_time_in_seconds(),
451 parameters.max_deterministic_time());
452 }
453
460 TimeLimit* GetTimeLimit() { return &time_limit_; }
461
462 private:
463 TimeLimit* const base_time_limit_;
464 TimeLimit time_limit_;
465
466 DISALLOW_COPY_AND_ASSIGN(NestedTimeLimit);
467};
468
469// ################## Implementations below #####################
470
471inline TimeLimit::TimeLimit(double limit_in_seconds, double deterministic_limit,
472 double instruction_limit)
473 : safety_buffer_ns_(static_cast<int64>(kSafetyBufferSeconds * 1e9)),
474 running_max_(kHistorySize),
475 external_boolean_as_limit_(nullptr) {
476 ResetTimers(limit_in_seconds, deterministic_limit, instruction_limit);
477}
478
479inline void TimeLimit::ResetTimers(double limit_in_seconds,
480 double deterministic_limit,
481 double instruction_limit) {
482 elapsed_deterministic_time_ = 0.0;
483 deterministic_limit_ = deterministic_limit;
484 instruction_limit_ = instruction_limit;
485
486 if (absl::GetFlag(FLAGS_time_limit_use_usertime)) {
487 user_timer_.Start();
488 limit_in_seconds_ = limit_in_seconds;
489 }
490#ifdef HAS_PERF_SUBSYSTEM
491 if (absl::GetFlag(FLAGS_time_limit_use_instruction_count)) {
492 perf_subsystem_.CleanUp();
493 perf_subsystem_.AddEvent(GetInstructionRetiredEventName());
494 perf_subsystem_.StartCollecting();
495 }
496#endif // HAS_PERF_SUBSYSTEM
497 start_ns_ = absl::GetCurrentTimeNanos();
498 last_ns_ = start_ns_;
499 limit_ns_ = limit_in_seconds >= 1e-9 * (kint64max - start_ns_)
500 ? kint64max
501 : static_cast<int64>(limit_in_seconds * 1e9) + start_ns_;
502}
503
504template <typename Parameters>
505inline void TimeLimit::ResetLimitFromParameters(const Parameters& parameters) {
506 ResetTimers(parameters.max_time_in_seconds(),
507 parameters.max_deterministic_time(),
508 std::numeric_limits<double>::infinity());
509}
510
512 if (other == nullptr) return;
513 ResetTimers(
514 std::min(GetTimeLeft(), other->GetTimeLeft()),
516 std::numeric_limits<double>::infinity());
517 if (other->ExternalBooleanAsLimit() != nullptr) {
519 }
520}
521
523#ifdef HAS_PERF_SUBSYSTEM
524 if (absl::GetFlag(FLAGS_time_limit_use_instruction_count)) {
525 return perf_subsystem_.ReadCounters().GetScaledOrDie(
526 GetInstructionRetiredEventName());
527 }
528#endif // HAS_PERF_SUBSYSTEM
529 return 0;
530}
531
533 if (external_boolean_as_limit_ != nullptr &&
534 external_boolean_as_limit_->load()) {
535 return true;
536 }
537
538 if (GetDeterministicTimeLeft() <= 0.0) {
539 return true;
540 }
541
542#ifdef HAS_PERF_SUBSYSTEM
543 if (ReadInstructionCounter() >= instruction_limit_) {
544 return true;
545 }
546#endif // HAS_PERF_SUBSYSTEM
547
548 const int64 current_ns = absl::GetCurrentTimeNanos();
549 running_max_.Add(std::max(safety_buffer_ns_, current_ns - last_ns_));
550 last_ns_ = current_ns;
551 if (current_ns + running_max_.GetCurrentMax() >= limit_ns_) {
552 if (absl::GetFlag(FLAGS_time_limit_use_usertime)) {
553 // To avoid making many system calls, we only check the user time when
554 // the "absolute" time limit has been reached. Note that the user time
555 // should advance more slowly, so this is correct.
556 const double time_left_s = limit_in_seconds_ - user_timer_.Get();
557 if (time_left_s > kSafetyBufferSeconds) {
558 limit_ns_ = static_cast<int64>(time_left_s * 1e9) + last_ns_;
559 return false;
560 }
561 }
562
563 // To ensure that future calls to LimitReached() will return true.
564 limit_ns_ = 0;
565 return true;
566 }
567 return false;
568}
569
570inline double TimeLimit::GetTimeLeft() const {
571 if (limit_ns_ == kint64max) return std::numeric_limits<double>::infinity();
572 const int64 delta_ns = limit_ns_ - absl::GetCurrentTimeNanos();
573 if (delta_ns < 0) return 0.0;
574 if (absl::GetFlag(FLAGS_time_limit_use_usertime)) {
575 return std::max(limit_in_seconds_ - user_timer_.Get(), 0.0);
576 } else {
577 return delta_ns * 1e-9;
578 }
579}
580
582 return std::max(instruction_limit_ - ReadInstructionCounter(), 0.0);
583}
584
585} // namespace operations_research
586
587#endif // OR_TOOLS_UTIL_TIME_LIMIT_H_
Provides a way to nest time limits for algorithms where a certain part of the computation is bounded ...
Definition: time_limit.h:425
static std::unique_ptr< NestedTimeLimit > FromBaseTimeLimitAndParameters(TimeLimit *time_limit, const Parameters &parameters)
Creates a time limit object initialized from a base time limit and an object that provides methods ma...
Definition: time_limit.h:447
TimeLimit * GetTimeLimit()
Returns a time limit object that represents the combination of the overall time limit and the part-sp...
Definition: time_limit.h:460
~NestedTimeLimit()
Updates elapsed deterministic time in the base time limit object.
NestedTimeLimit(TimeLimit *base_time_limit, double limit_in_seconds, double deterministic_limit)
Creates the nested time limit.
void UpdateLocalLimit(TimeLimit *local_limit)
Definition: time_limit.h:368
SharedTimeLimit(TimeLimit *time_limit)
Definition: time_limit.h:340
double GetElapsedDeterministicTime() const
Definition: time_limit.h:383
void AdvanceDeterministicTime(double deterministic_duration)
Definition: time_limit.h:373
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
double GetInstructionsLeft()
Returns the number of instructions left to reach the limit.
Definition: time_limit.h:581
static std::unique_ptr< TimeLimit > FromParameters(const Parameters &parameters)
Creates a time limit object initialized from an object that provides methods max_time_in_seconds() an...
Definition: time_limit.h:159
static const double kSafetyBufferSeconds
Definition: time_limit.h:107
void ResetLimitFromParameters(const Parameters &parameters)
Sets new time limits.
Definition: time_limit.h:505
double GetDeterministicTimeLeft() const
Returns the remaining deterministic time before LimitReached() returns true due to the deterministic ...
Definition: time_limit.h:212
double GetTimeLeft() const
Returns the time left on this limit, or 0 if the limit was reached (it never returns a negative value...
Definition: time_limit.h:570
void SetInstructionLimit(double instruction_limit)
Sets the instruction limit.
Definition: time_limit.h:171
std::atomic< bool > * ExternalBooleanAsLimit() const
Returns the current external Boolean limit.
Definition: time_limit.h:280
double ReadInstructionCounter()
Returns the number of instructions executed since the creation of this object.
Definition: time_limit.h:522
void RegisterExternalBooleanAsLimit(std::atomic< bool > *external_boolean_as_limit)
Registers the external Boolean to check when LimitReached() is called.
Definition: time_limit.h:272
std::string DebugString() const
Returns information about the time limit object in a human-readable form.
bool LimitReached()
Returns true when the external limit is true, or the deterministic time is over the deterministic lim...
Definition: time_limit.h:532
static std::unique_ptr< TimeLimit > Infinite()
Creates a time limit object that uses infinite time for wall time, deterministic time and instruction...
Definition: time_limit.h:134
static std::unique_ptr< TimeLimit > FromDeterministicTime(double deterministic_limit)
Creates a time limit object that puts limit only on the deterministic time.
Definition: time_limit.h:144
TimeLimit(const TimeLimit &)=delete
static const int kHistorySize
Definition: time_limit.h:108
double GetElapsedDeterministicTime() const
Returns the elapsed deterministic time since the construction of this object.
Definition: time_limit.h:260
void AdvanceDeterministicTime(double deterministic_duration, const char *counter_name)
Advances the deterministic time.
Definition: time_limit.h:240
void MergeWithGlobalTimeLimit(TimeLimit *other)
Definition: time_limit.h:511
TimeLimit & operator=(const TimeLimit &)=delete
double GetElapsedTime() const
Returns the time elapsed in seconds since the construction of this object.
Definition: time_limit.h:251
void AdvanceDeterministicTime(double deterministic_duration)
Advances the deterministic time.
Definition: time_limit.h:226
ABSL_DECLARE_FLAG(bool, time_limit_use_usertime)
Enables changing the behavior of the TimeLimit class to use -b usertime instead of walltime.