Google OR-Tools: ortools/util/time

Google OR-Tools: ortools/util/time_limit.h Source File

14#ifndef ORTOOLS_UTIL_TIME_LIMIT_H_

15#define ORTOOLS_UTIL_TIME_LIMIT_H_

17#include <algorithm>

18#include <atomic>

19#include <cstdint>

20#include <limits>

21#include <memory>

22#include <string>

23#include <vector>

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"

38#ifndef SWIG

44#endif

98 public:

101

111 double limit_in_seconds,

112 double deterministic_limit = std::numeric_limits<double>::infinity());

113

117

122 static std::unique_ptr<TimeLimit> Infinite() {

123 return std::make_unique<TimeLimit>(std::numeric_limits<double>::infinity(),

124 std::numeric_limits<double>::infinity());

125 }

126

131 double deterministic_limit) {

132 return std::make_unique<TimeLimit>(std::numeric_limits<double>::infinity(),

133 deterministic_limit);

134 }

135

142 template <typename Parameters>

144 const Parameters& parameters) {

145 return std::make_unique<TimeLimit>(parameters.max_time_in_seconds(),

146 parameters.max_deterministic_time());

147 }

148

155 bool LimitReached();

156

169 double GetTimeLeft() const;

170

178 return std::max(0.0, deterministic_limit_ - elapsed_deterministic_time_);

179 }

180

187 DCHECK_LE(0.0, deterministic_duration);

188 elapsed_deterministic_time_ += deterministic_duration;

189 }

190

201 const char* counter_name) {

203#ifndef NDEBUG

204 deterministic_counters_[counter_name] += deterministic_duration;

205#endif

206 }

207

212 return 1e-9 * (absl::GetCurrentTimeNanos() - start_ns_);

213 }

214

221 return elapsed_deterministic_time_;

222 }

223

234 std::atomic<bool>* external_boolean_as_limit) {

235 external_boolean_as_limit_ = external_boolean_as_limit;

236 }

237

247 std::atomic<bool>* external_boolean_as_limit) {

248 secondary_external_boolean_as_limit_ = external_boolean_as_limit;

249 }

250

255 return external_boolean_as_limit_;

256 }

257

262 template <typename Parameters>

263 void ResetLimitFromParameters(const Parameters& parameters);

264

270 void MergeWithGlobalTimeLimit(const TimeLimit* other);

271

276 deterministic_limit_ = new_limit;

277 }

278

283

291

295 std::string DebugString() const;

296

297 private:

298 void ResetTimers(double limit_in_seconds, double deterministic_limit);

299

300 mutable int64_t start_ns_;

301

302 int64_t last_ns_;

303 int64_t limit_ns_;

304 const int64_t safety_buffer_ns_;

306

307

309 double limit_in_seconds_;

310

311 double deterministic_limit_;

312 double elapsed_deterministic_time_;

313

314 std::atomic<bool>* external_boolean_as_limit_ = nullptr;

315 std::atomic<bool>* secondary_external_boolean_as_limit_ = nullptr;

316

317#ifndef NDEBUG

318

319 absl::flat_hash_map<std::string, double> deterministic_counters_;

320#endif

321

324};

325

326

328 public:

330 : time_limit_(time_limit), stopped_boolean_(false) {

331

333 if (stopped_ == nullptr) {

334 stopped_ = &stopped_boolean_;

336 }

337 }

338

340 if (stopped_ == &stopped_boolean_) {

341 time_limit_->RegisterExternalBooleanAsLimit(nullptr);

342 }

343 }

344

346

347

348 absl::MutexLock lock(mutex_);

349 return time_limit_->LimitReached();

350 }

351

353 absl::MutexLock lock(mutex_);

354 *stopped_ = true;

355 }

356

358 absl::MutexLock lock(mutex_);

360 }

361

363 absl::MutexLock lock(mutex_);

364 time_limit_->AdvanceDeterministicTime(deterministic_duration);

365 }

366

368 absl::ReaderMutexLock lock(mutex_);

369 return time_limit_->GetTimeLeft();

370 }

371

373 absl::ReaderMutexLock lock(mutex_);

374 return time_limit_->GetElapsedDeterministicTime();

375 }

376

378 absl::ReaderMutexLock lock(mutex_);

379

380

381 return time_limit_->ExternalBooleanAsLimit();

382 }

383

384 private:

385 mutable absl::Mutex mutex_;

386 TimeLimit* time_limit_ ABSL_GUARDED_BY(mutex_);

387 std::atomic<bool> stopped_boolean_ ABSL_GUARDED_BY(mutex_);

388 std::atomic<bool>* stopped_ ABSL_GUARDED_BY(mutex_);

389};

390

422 public:

428 double deterministic_limit);

429

430

433

438

446 template <typename Parameters>

448 TimeLimit* time_limit, const Parameters& parameters) {

449 return std::make_unique<NestedTimeLimit>(

450 time_limit, parameters.max_time_in_seconds(),

451 parameters.max_deterministic_time());

452 }

453

461

462 private:

463 TimeLimit* const base_time_limit_;

465};

466

468 public:

470 : time_limit_(time_limit), frequency_(N) {}

471

473 if (count_++ == frequency_) {

474 if (time_limit_->LimitReached()) {

475 stopped_ = true;

476 return true;

477 }

478 count_ = 0;

479 }

480 return stopped_;

481 }

482

483 private:

485 bool stopped_ = false;

486 int count_ = 0;

487 const int frequency_;

488};

489

490

491

492inline void TimeLimit::ResetTimers(double limit_in_seconds,

493 double deterministic_limit) {

494 elapsed_deterministic_time_ = 0.0;

495 deterministic_limit_ = deterministic_limit;

496

497 if (absl::GetFlag(FLAGS_time_limit_use_usertime)) {

498 user_timer_.Start();

499 limit_in_seconds_ = limit_in_seconds;

500 }

501 start_ns_ = absl::GetCurrentTimeNanos();

502 last_ns_ = start_ns_;

503

504 limit_ns_ = (absl::Seconds(limit_in_seconds) + absl::Nanoseconds(start_ns_)) /

505 absl::Nanoseconds(1);

506}

507

508template <typename Parameters>

510 ResetTimers(parameters.max_time_in_seconds(),

511 parameters.max_deterministic_time());

512}

513

515 if (other == nullptr) return;

516 ResetTimers(

521 }

522}

523

525 if (external_boolean_as_limit_ != nullptr &&

526 external_boolean_as_limit_->load()) {

527 return true;

528 }

529 if (secondary_external_boolean_as_limit_ != nullptr &&

530 secondary_external_boolean_as_limit_->load()) {

531 return true;

532 }

533

535 return true;

536 }

537

538 const int64_t current_ns = absl::GetCurrentTimeNanos();

539 running_max_.Add(std::max(safety_buffer_ns_, current_ns - last_ns_));

540 last_ns_ = current_ns;

541 if (current_ns + running_max_.GetCurrentMax() >= limit_ns_) {

542 if (absl::GetFlag(FLAGS_time_limit_use_usertime)) {

543

544

545

546 const double time_left_s = limit_in_seconds_ - user_timer_.Get();

548 limit_ns_ = static_cast<int64_t>(time_left_s * 1e9) + last_ns_;

549 return false;

550 }

551 }

552

553

554 limit_ns_ = 0;

555 return true;

556 }

557 return false;

558}

559

561 if (limit_ns_ == kint64max) return std::numeric_limits<double>::infinity();

562 const int64_t delta_ns = limit_ns_ - absl::GetCurrentTimeNanos();

563 if (delta_ns < 0) return 0.0;

564 if (absl::GetFlag(FLAGS_time_limit_use_usertime)) {

565 return std::max(limit_in_seconds_ - user_timer_.Get(), 0.0);

566 } else {

567 return delta_ns * 1e-9;

568 }

569}

570

571}

572

573#endif

static std::unique_ptr< NestedTimeLimit > FromBaseTimeLimitAndParameters(TimeLimit *time_limit, const Parameters &parameters)

Definition time_limit.h:447

NestedTimeLimit(const NestedTimeLimit &)=delete

NestedTimeLimit(TimeLimit *base_time_limit, double limit_in_seconds, double deterministic_limit)

TimeLimit * GetTimeLimit()

Definition time_limit.h:460

NestedTimeLimit & operator=(const NestedTimeLimit &)=delete

bool LimitReached()

Definition time_limit.h:472

TimeLimitCheckEveryNCalls(int N, TimeLimit *time_limit)

Definition time_limit.h:469

Definition time_limit.h:97

TimeLimit & operator=(const TimeLimit &)=delete

TimeLimit()

Definition time_limit.h:114

static std::unique_ptr< TimeLimit > FromParameters(const Parameters &parameters)

Definition time_limit.h:143

bool LimitReached()

Definition time_limit.h:524

double GetTimeLeft() const

Definition time_limit.h:560

TimeLimit(const TimeLimit &)=delete

TimeLimit(double limit_in_seconds, double deterministic_limit=std::numeric_limits< double >::infinity())

void MergeWithGlobalTimeLimit(const TimeLimit *other)

Definition time_limit.h:514

friend class ParallelTimeLimit

Definition time_limit.h:323

double GetDeterministicLimit() const

Definition time_limit.h:282

void ResetHistory()

Definition time_limit.h:290

void AdvanceDeterministicTime(double deterministic_duration)

Definition time_limit.h:186

friend class NestedTimeLimit

Definition time_limit.h:322

std::atomic< bool > * ExternalBooleanAsLimit() const

Definition time_limit.h:254

double GetElapsedDeterministicTime() const

Definition time_limit.h:220

static std::unique_ptr< TimeLimit > Infinite()

Definition time_limit.h:122

void AdvanceDeterministicTime(double deterministic_duration, const char *counter_name)

Definition time_limit.h:200

void RegisterExternalBooleanAsLimit(std::atomic< bool > *external_boolean_as_limit)

Definition time_limit.h:233

void RegisterSecondaryExternalBooleanAsLimit(std::atomic< bool > *external_boolean_as_limit)

Definition time_limit.h:246

double GetDeterministicTimeLeft() const

Definition time_limit.h:177

static const int kHistorySize

Definition time_limit.h:100

static std::unique_ptr< TimeLimit > FromDeterministicTime(double deterministic_limit)

Definition time_limit.h:130

static const double kSafetyBufferSeconds

Definition time_limit.h:99

void ResetLimitFromParameters(const Parameters &parameters)

Definition time_limit.h:509

void ChangeDeterministicLimit(double new_limit)

Definition time_limit.h:275

double GetElapsedTime() const

Definition time_limit.h:211

OR_DLL ABSL_DECLARE_FLAG(bool, time_limit_use_usertime)

static const int64_t kint64max