14#ifndef OR_TOOLS_UTIL_TIME_LIMIT_H_
15#define OR_TOOLS_UTIL_TIME_LIMIT_H_
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"
33#ifdef HAS_PERF_SUBSYSTEM
34#include "exegesis/exegesis/itineraries/perf_subsystem.h"
122 double limit_in_seconds,
123 double deterministic_limit = std::numeric_limits<double>::infinity(),
124 double instruction_limit = std::numeric_limits<double>::infinity());
135 return absl::make_unique<TimeLimit>(
136 std::numeric_limits<double>::infinity(),
137 std::numeric_limits<double>::infinity(),
138 std::numeric_limits<double>::infinity());
145 double deterministic_limit) {
146 return absl::make_unique<TimeLimit>(
147 std::numeric_limits<double>::infinity(), deterministic_limit,
148 std::numeric_limits<double>::infinity());
158 template <
typename Parameters>
161 return absl::make_unique<TimeLimit>(
163 std::numeric_limits<double>::infinity());
172 instruction_limit_ = instruction_limit;
213 return std::max(0.0, deterministic_limit_ - elapsed_deterministic_time_);
228 elapsed_deterministic_time_ += deterministic_duration;
241 const char* counter_name) {
244 deterministic_counters_[counter_name] += deterministic_duration;
252 return 1e-9 * (absl::GetCurrentTimeNanos() - start_ns_);
261 return elapsed_deterministic_time_;
273 std::atomic<bool>* external_boolean_as_limit) {
274 external_boolean_as_limit_ = external_boolean_as_limit;
281 return external_boolean_as_limit_;
288 template <
typename Parameters>
298 void ResetTimers(
double limit_in_seconds,
double deterministic_limit,
299 double instruction_limit);
301 std::string GetInstructionRetiredEventName()
const {
302 return "inst_retired:any_p:u";
305 mutable int64 start_ns_;
309 const int64 safety_buffer_ns_;
310 RunningMax<int64> running_max_;
314 double limit_in_seconds_;
316 double deterministic_limit_;
317 double elapsed_deterministic_time_;
319 std::atomic<bool>* external_boolean_as_limit_;
321#ifdef HAS_PERF_SUBSYSTEM
323 exegesis::PerfSubsystem perf_subsystem_;
326 double instruction_limit_;
330 absl::flat_hash_map<std::string, double> deterministic_counters_;
341 : time_limit_(
time_limit), stopped_boolean_(false) {
343 stopped_ =
time_limit->ExternalBooleanAsLimit();
344 if (stopped_ ==
nullptr) {
345 stopped_ = &stopped_boolean_;
346 time_limit->RegisterExternalBooleanAsLimit(stopped_);
351 if (stopped_ == &stopped_boolean_) {
352 time_limit_->RegisterExternalBooleanAsLimit(
nullptr);
359 absl::MutexLock lock(&mutex_);
360 return time_limit_->LimitReached();
364 absl::MutexLock lock(&mutex_);
369 absl::MutexLock lock(&mutex_);
374 absl::MutexLock lock(&mutex_);
375 time_limit_->AdvanceDeterministicTime(deterministic_duration);
379 absl::ReaderMutexLock lock(&mutex_);
380 return time_limit_->GetTimeLeft();
384 absl::ReaderMutexLock lock(&mutex_);
385 return time_limit_->GetElapsedDeterministicTime();
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_);
432 double deterministic_limit);
446 template <
typename Parameters>
449 return absl::make_unique<NestedTimeLimit>(
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);
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;
486 if (absl::GetFlag(FLAGS_time_limit_use_usertime)) {
488 limit_in_seconds_ = limit_in_seconds;
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();
497 start_ns_ = absl::GetCurrentTimeNanos();
498 last_ns_ = start_ns_;
499 limit_ns_ = limit_in_seconds >= 1e-9 * (
kint64max - start_ns_)
501 :
static_cast<int64>(limit_in_seconds * 1e9) + start_ns_;
504template <
typename Parameters>
508 std::numeric_limits<double>::infinity());
512 if (other ==
nullptr)
return;
516 std::numeric_limits<double>::infinity());
523#ifdef HAS_PERF_SUBSYSTEM
524 if (absl::GetFlag(FLAGS_time_limit_use_instruction_count)) {
525 return perf_subsystem_.ReadCounters().GetScaledOrDie(
526 GetInstructionRetiredEventName());
533 if (external_boolean_as_limit_ !=
nullptr &&
534 external_boolean_as_limit_->load()) {
542#ifdef HAS_PERF_SUBSYSTEM
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)) {
556 const double time_left_s = limit_in_seconds_ - user_timer_.
Get();
558 limit_ns_ =
static_cast<int64>(time_left_s * 1e9) + last_ns_;
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);
577 return delta_ns * 1e-9;
#define DCHECK_LE(val1, val2)
Provides a way to nest time limits for algorithms where a certain part of the computation is bounded ...
static std::unique_ptr< NestedTimeLimit > FromBaseTimeLimitAndParameters(TimeLimit *time_limit, const Parameters ¶meters)
Creates a time limit object initialized from a base time limit and an object that provides methods ma...
TimeLimit * GetTimeLimit()
Returns a time limit object that represents the combination of the overall time limit and the part-sp...
~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)
double GetTimeLeft() const
SharedTimeLimit(TimeLimit *time_limit)
double GetElapsedDeterministicTime() const
bool LimitReached() const
void AdvanceDeterministicTime(double deterministic_duration)
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
double GetInstructionsLeft()
Returns the number of instructions left to reach the limit.
static std::unique_ptr< TimeLimit > FromParameters(const Parameters ¶meters)
Creates a time limit object initialized from an object that provides methods max_time_in_seconds() an...
static const double kSafetyBufferSeconds
void ResetLimitFromParameters(const Parameters ¶meters)
Sets new time limits.
double GetDeterministicTimeLeft() const
Returns the remaining deterministic time before LimitReached() returns true due to the deterministic ...
double GetTimeLeft() const
Returns the time left on this limit, or 0 if the limit was reached (it never returns a negative value...
void SetInstructionLimit(double instruction_limit)
Sets the instruction limit.
std::atomic< bool > * ExternalBooleanAsLimit() const
Returns the current external Boolean limit.
friend class ParallelTimeLimit
double ReadInstructionCounter()
Returns the number of instructions executed since the creation of this object.
void RegisterExternalBooleanAsLimit(std::atomic< bool > *external_boolean_as_limit)
Registers the external Boolean to check when LimitReached() is called.
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...
static std::unique_ptr< TimeLimit > Infinite()
Creates a time limit object that uses infinite time for wall time, deterministic time and instruction...
static std::unique_ptr< TimeLimit > FromDeterministicTime(double deterministic_limit)
Creates a time limit object that puts limit only on the deterministic time.
TimeLimit(const TimeLimit &)=delete
static const int kHistorySize
double GetElapsedDeterministicTime() const
Returns the elapsed deterministic time since the construction of this object.
void AdvanceDeterministicTime(double deterministic_duration, const char *counter_name)
Advances the deterministic time.
void MergeWithGlobalTimeLimit(TimeLimit *other)
TimeLimit & operator=(const TimeLimit &)=delete
double GetElapsedTime() const
Returns the time elapsed in seconds since the construction of this object.
void AdvanceDeterministicTime(double deterministic_duration)
Advances the deterministic time.
SharedTimeLimit * time_limit
static const int64 kint64max
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
ABSL_DECLARE_FLAG(bool, time_limit_use_usertime)
Enables changing the behavior of the TimeLimit class to use -b usertime instead of walltime.