Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
time_limit.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#ifndef OR_TOOLS_UTIL_TIME_LIMIT_H_
15#define OR_TOOLS_UTIL_TIME_LIMIT_H_
16
17#include <algorithm>
18#include <atomic>
19#include <cstdint>
20#include <limits>
21#include <memory>
22#include <string>
23#include <vector>
24
25#include "absl/base/thread_annotations.h"
26#include "absl/container/flat_hash_map.h"
27#include "absl/flags/declare.h"
28#include "absl/flags/flag.h"
29#include "absl/log/check.h"
30#include "absl/synchronization/mutex.h"
31#include "absl/time/clock.h"
32#include "absl/time/time.h"
34#include "ortools/base/timer.h"
35#include "ortools/base/types.h"
37
42OR_DLL ABSL_DECLARE_FLAG(bool, time_limit_use_usertime);
43
44namespace operations_research {
45
93// TODO(user): The expression "deterministic time" should be replaced with
94// "number of operations" to avoid confusion with "real" time.
96 public:
97 static const double kSafetyBufferSeconds; // See the .cc for the value.
98 static const int kHistorySize;
99
108 explicit TimeLimit(
109 double limit_in_seconds,
110 double deterministic_limit = std::numeric_limits<double>::infinity());
111
112 TimeLimit() : TimeLimit(std::numeric_limits<double>::infinity()) {}
113 TimeLimit(const TimeLimit&) = delete;
114 TimeLimit& operator=(const TimeLimit&) = delete;
115
120 static std::unique_ptr<TimeLimit> Infinite() {
121 return std::make_unique<TimeLimit>(std::numeric_limits<double>::infinity(),
122 std::numeric_limits<double>::infinity());
123 }
124
128 static std::unique_ptr<TimeLimit> FromDeterministicTime(
129 double deterministic_limit) {
130 return std::make_unique<TimeLimit>(std::numeric_limits<double>::infinity(),
131 deterministic_limit);
132 }
133
140 template <typename Parameters>
141 static std::unique_ptr<TimeLimit> FromParameters(
142 const Parameters& parameters) {
143 return std::make_unique<TimeLimit>(parameters.max_time_in_seconds(),
144 parameters.max_deterministic_time());
145 }
146
153 bool LimitReached();
154
167 double GetTimeLeft() const;
168
176 return std::max(0.0, deterministic_limit_ - elapsed_deterministic_time_);
177 }
178
184 inline void AdvanceDeterministicTime(double deterministic_duration) {
185 DCHECK_LE(0.0, deterministic_duration);
186 elapsed_deterministic_time_ += deterministic_duration;
187 }
188
198 inline void AdvanceDeterministicTime(double deterministic_duration,
199 const char* counter_name) {
200 AdvanceDeterministicTime(deterministic_duration);
201#ifndef NDEBUG
202 deterministic_counters_[counter_name] += deterministic_duration;
203#endif
204 }
205
209 double GetElapsedTime() const {
210 return 1e-9 * (absl::GetCurrentTimeNanos() - start_ns_);
211 }
212
219 return elapsed_deterministic_time_;
220 }
221
232 std::atomic<bool>* external_boolean_as_limit) {
233 external_boolean_as_limit_ = external_boolean_as_limit;
234 }
235
245 std::atomic<bool>* external_boolean_as_limit) {
246 secondary_external_boolean_as_limit_ = external_boolean_as_limit;
247 }
248
252 std::atomic<bool>* ExternalBooleanAsLimit() const {
253 return external_boolean_as_limit_;
254 }
255
260 template <typename Parameters>
261 void ResetLimitFromParameters(const Parameters& parameters);
262
268 void MergeWithGlobalTimeLimit(const TimeLimit* other);
269
273 void ChangeDeterministicLimit(double new_limit) {
274 deterministic_limit_ = new_limit;
275 }
276
280 double GetDeterministicLimit() const { return deterministic_limit_; }
281
288 void ResetHistory() { running_max_.Reset(); }
289
293 std::string DebugString() const;
294
295 private:
296 void ResetTimers(double limit_in_seconds, double deterministic_limit);
297
298 mutable int64_t start_ns_; // Not const! this is initialized after
299 // instruction counter initialization.
300 int64_t last_ns_;
301 int64_t limit_ns_; // Not const! See the code of LimitReached().
302 const int64_t safety_buffer_ns_;
303 RunningMax<int64_t> running_max_;
304
305 // Only used when FLAGS_time_limit_use_usertime is true.
306 UserTimer user_timer_;
307 double limit_in_seconds_;
308
309 double deterministic_limit_;
310 double elapsed_deterministic_time_;
311
312 std::atomic<bool>* external_boolean_as_limit_ = nullptr;
313 std::atomic<bool>* secondary_external_boolean_as_limit_ = nullptr;
314
315#ifndef NDEBUG
316 // Contains the values of the deterministic time counters.
317 absl::flat_hash_map<std::string, double> deterministic_counters_;
318#endif
319
320 friend class NestedTimeLimit;
321 friend class ParallelTimeLimit;
322};
323
324// Wrapper around TimeLimit to make it thread safe and add Stop() support.
326 public:
328 : time_limit_(time_limit), stopped_boolean_(false) {
329 // We use the one already registered if present or ours otherwise.
330 stopped_ = time_limit->ExternalBooleanAsLimit();
331 if (stopped_ == nullptr) {
332 stopped_ = &stopped_boolean_;
333 time_limit->RegisterExternalBooleanAsLimit(stopped_);
334 }
335 }
336
338 if (stopped_ == &stopped_boolean_) {
339 time_limit_->RegisterExternalBooleanAsLimit(nullptr);
340 }
341 }
342
343 bool LimitReached() const {
344 // Note, time_limit_->LimitReached() is not const, and changes internal
345 // state of time_limit_, hence we need a writer's lock.
346 absl::MutexLock lock(&mutex_);
347 return time_limit_->LimitReached();
348 }
349
350 void Stop() {
351 absl::MutexLock lock(&mutex_);
352 *stopped_ = true;
353 }
354
355 void UpdateLocalLimit(TimeLimit* local_limit) {
356 absl::MutexLock lock(&mutex_);
357 local_limit->MergeWithGlobalTimeLimit(time_limit_);
358 }
359
360 void AdvanceDeterministicTime(double deterministic_duration) {
361 absl::MutexLock lock(&mutex_);
362 time_limit_->AdvanceDeterministicTime(deterministic_duration);
363 }
364
365 double GetTimeLeft() const {
366 absl::ReaderMutexLock lock(&mutex_);
367 return time_limit_->GetTimeLeft();
368 }
369
371 absl::ReaderMutexLock lock(&mutex_);
372 return time_limit_->GetElapsedDeterministicTime();
373 }
374
375 std::atomic<bool>* ExternalBooleanAsLimit() const {
376 absl::ReaderMutexLock lock(&mutex_);
377 // We can simply return the "external bool" and remain thread-safe because
378 // it's wrapped in std::atomic.
379 return time_limit_->ExternalBooleanAsLimit();
380 }
381
382 private:
383 mutable absl::Mutex mutex_;
384 TimeLimit* time_limit_ ABSL_GUARDED_BY(mutex_);
385 std::atomic<bool> stopped_boolean_ ABSL_GUARDED_BY(mutex_);
386 std::atomic<bool>* stopped_ ABSL_GUARDED_BY(mutex_);
387};
388
420 public:
425 NestedTimeLimit(TimeLimit* base_time_limit, double limit_in_seconds,
426 double deterministic_limit);
427
428 // This type is neither copyable nor movable.
431
436
444 template <typename Parameters>
445 static std::unique_ptr<NestedTimeLimit> FromBaseTimeLimitAndParameters(
446 TimeLimit* time_limit, const Parameters& parameters) {
447 return std::make_unique<NestedTimeLimit>(
448 time_limit, parameters.max_time_in_seconds(),
449 parameters.max_deterministic_time());
450 }
451
458 TimeLimit* GetTimeLimit() { return &time_limit_; }
459
460 private:
461 TimeLimit* const base_time_limit_;
462 TimeLimit time_limit_;
463};
464
466 public:
468 : time_limit_(time_limit), frequency_(N) {}
469
471 if (count_++ == frequency_) {
472 if (time_limit_->LimitReached()) {
473 stopped_ = true;
474 return true;
475 }
476 count_ = 0;
477 }
478 return stopped_;
479 }
480
481 private:
482 TimeLimit* time_limit_;
483 bool stopped_ = false;
484 int count_ = 0;
485 const int frequency_;
486};
487
488// ################## Implementations below #####################
489
490inline void TimeLimit::ResetTimers(double limit_in_seconds,
491 double deterministic_limit) {
492 elapsed_deterministic_time_ = 0.0;
493 deterministic_limit_ = deterministic_limit;
494
495 if (absl::GetFlag(FLAGS_time_limit_use_usertime)) {
496 user_timer_.Start();
497 limit_in_seconds_ = limit_in_seconds;
498 }
499 start_ns_ = absl::GetCurrentTimeNanos();
500 last_ns_ = start_ns_;
501 // Note that duration arithmetic is properly saturated.
502 limit_ns_ = (absl::Seconds(limit_in_seconds) + absl::Nanoseconds(start_ns_)) /
503 absl::Nanoseconds(1);
504}
505
506template <typename Parameters>
507inline void TimeLimit::ResetLimitFromParameters(const Parameters& parameters) {
508 ResetTimers(parameters.max_time_in_seconds(),
509 parameters.max_deterministic_time());
510}
511
513 if (other == nullptr) return;
514 ResetTimers(
515 std::min(GetTimeLeft(), other->GetTimeLeft()),
517 if (other->ExternalBooleanAsLimit() != nullptr) {
519 }
520}
521
523 if (external_boolean_as_limit_ != nullptr &&
524 external_boolean_as_limit_->load()) {
525 return true;
526 }
527 if (secondary_external_boolean_as_limit_ != nullptr &&
528 secondary_external_boolean_as_limit_->load()) {
529 return true;
530 }
531
532 if (GetDeterministicTimeLeft() <= 0.0) {
533 return true;
534 }
535
536 const int64_t current_ns = absl::GetCurrentTimeNanos();
537 running_max_.Add(std::max(safety_buffer_ns_, current_ns - last_ns_));
538 last_ns_ = current_ns;
539 if (current_ns + running_max_.GetCurrentMax() >= limit_ns_) {
540 if (absl::GetFlag(FLAGS_time_limit_use_usertime)) {
541 // To avoid making many system calls, we only check the user time when
542 // the "absolute" time limit has been reached. Note that the user time
543 // should advance more slowly, so this is correct.
544 const double time_left_s = limit_in_seconds_ - user_timer_.Get();
545 if (time_left_s > kSafetyBufferSeconds) {
546 limit_ns_ = static_cast<int64_t>(time_left_s * 1e9) + last_ns_;
547 return false;
548 }
549 }
550
551 // To ensure that future calls to LimitReached() will return true.
552 limit_ns_ = 0;
553 return true;
554 }
555 return false;
556}
557
558inline double TimeLimit::GetTimeLeft() const {
559 if (limit_ns_ == kint64max) return std::numeric_limits<double>::infinity();
560 const int64_t delta_ns = limit_ns_ - absl::GetCurrentTimeNanos();
561 if (delta_ns < 0) return 0.0;
562 if (absl::GetFlag(FLAGS_time_limit_use_usertime)) {
563 return std::max(limit_in_seconds_ - user_timer_.Get(), 0.0);
564 } else {
565 return delta_ns * 1e-9;
566 }
567}
568
569} // namespace operations_research
570
571#endif // OR_TOOLS_UTIL_TIME_LIMIT_H_
#define OR_DLL
Definition base_export.h:27
void Start()
When Start() is called multiple times, only the most recent is used.
Definition timer.h:30
static std::unique_ptr< NestedTimeLimit > FromBaseTimeLimitAndParameters(TimeLimit *time_limit, const Parameters &parameters)
Definition time_limit.h:445
NestedTimeLimit(const NestedTimeLimit &)=delete
This type is neither copyable nor movable.
NestedTimeLimit(TimeLimit *base_time_limit, double limit_in_seconds, double deterministic_limit)
Definition time_limit.cc:62
NestedTimeLimit & operator=(const NestedTimeLimit &)=delete
void UpdateLocalLimit(TimeLimit *local_limit)
Definition time_limit.h:355
void AdvanceDeterministicTime(double deterministic_duration)
Definition time_limit.h:360
std::atomic< bool > * ExternalBooleanAsLimit() const
Definition time_limit.h:375
SharedTimeLimit(TimeLimit *time_limit)
Definition time_limit.h:327
TimeLimitCheckEveryNCalls(int N, TimeLimit *time_limit)
Definition time_limit.h:467
TimeLimit & operator=(const TimeLimit &)=delete
static std::unique_ptr< TimeLimit > FromParameters(const Parameters &parameters)
Definition time_limit.h:141
TimeLimit(const TimeLimit &)=delete
TimeLimit(double limit_in_seconds, double deterministic_limit=std::numeric_limits< double >::infinity())
Definition time_limit.cc:39
void MergeWithGlobalTimeLimit(const TimeLimit *other)
Definition time_limit.h:512
double GetDeterministicLimit() const
Definition time_limit.h:280
void AdvanceDeterministicTime(double deterministic_duration)
Definition time_limit.h:184
std::atomic< bool > * ExternalBooleanAsLimit() const
Definition time_limit.h:252
double GetElapsedDeterministicTime() const
Definition time_limit.h:218
static std::unique_ptr< TimeLimit > Infinite()
Definition time_limit.h:120
void AdvanceDeterministicTime(double deterministic_duration, const char *counter_name)
Definition time_limit.h:198
void RegisterExternalBooleanAsLimit(std::atomic< bool > *external_boolean_as_limit)
Definition time_limit.h:231
void RegisterSecondaryExternalBooleanAsLimit(std::atomic< bool > *external_boolean_as_limit)
Definition time_limit.h:244
double GetDeterministicTimeLeft() const
Definition time_limit.h:175
static const int kHistorySize
Definition time_limit.h:98
static std::unique_ptr< TimeLimit > FromDeterministicTime(double deterministic_limit)
Definition time_limit.h:128
static const double kSafetyBufferSeconds
static constants.
Definition time_limit.h:97
void ResetLimitFromParameters(const Parameters &parameters)
Definition time_limit.h:507
void ChangeDeterministicLimit(double new_limit)
Definition time_limit.h:273
time_limit
Definition solve.cc:22
In SWIG mode, we don't want anything besides these top-level includes.
STL namespace.
OR_DLL ABSL_DECLARE_FLAG(bool, time_limit_use_usertime)
WallTimer UserTimer
Definition timer.h:65
static const int64_t kint64max
Definition types.h:32