#include <time_limit.h>

Public Member Functions
	TimeLimit (double limit_in_seconds, double deterministic_limit=std::numeric_limits< double >::infinity())
	################## Implementations below #####################

	TimeLimit ()

	TimeLimit (const TimeLimit &)=delete

TimeLimit &	operator= (const TimeLimit &)=delete

bool	LimitReached ()

double	GetTimeLeft () const

double	GetDeterministicTimeLeft () const

void	AdvanceDeterministicTime (double deterministic_duration)

void	AdvanceDeterministicTime (double deterministic_duration, const char *counter_name)

double	GetElapsedTime () const

double	GetElapsedDeterministicTime () const

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

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

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

template<typename Parameters >
void	ResetLimitFromParameters (const Parameters &parameters)

void	MergeWithGlobalTimeLimit (TimeLimit *other)

void	ChangeDeterministicLimit (double new_limit)

double	GetDeterministicLimit () const

std::string	DebugString () const

Static Public Member Functions
static std::unique_ptr< TimeLimit >	Infinite ()

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

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

Static Public Attributes
static const double	kSafetyBufferSeconds = 1e-4
	static constants.

static const int	kHistorySize = 100

Friends
class	NestedTimeLimit

class	ParallelTimeLimit

Detailed Description

A simple class to enforce both an elapsed time limit and a deterministic time limit in the same thread as a program. The idea is to call LimitReached() as often as possible, until it returns false. The program should then abort as fast as possible.

The deterministic limit is used to ensure reproductibility. As a consequence the deterministic time has to be advanced manually using the method AdvanceDeterministicTime().

The call itself is as fast as CycleClock::Now() + a few trivial instructions.

The limit is very conservative: it returns true (i.e. the limit is reached) when current_time + max(T, ε) >= limit_time, where ε is a small constant (see TimeLimit::kSafetyBufferSeconds), and T is the maximum measured time interval between two consecutive calls to LimitReached() over the last kHistorySize calls (so that we only consider "recent" history). This is made so that the probability of actually exceeding the time limit is small, without aborting too early.

The deterministic time limit can be logged at a more granular level: the method TimeLimit::AdvanceDeterministicTime takes an optional string argument: the name of a counter. In debug mode, the time limit object computes also the elapsed time for each named counter separately, and these values can be used to determine the coefficients for computing the deterministic duration from the number of operations. The values of the counters can be printed using TimeLimit::DebugString(). There is no API to access the values of the counters directly, because they do not exist in optimized mode.

The basic steps for determining coefficients for the deterministic time are:

Run the code in debug mode to collect the values of the deterministic time counters. Unless the algorithm is different in optimized mode, the values of the deterministic counters in debug mode will be the same as in optimized mode.
Run the code in optimized mode to measure the real (CPU) time of the whole benchmark.
Determine the coefficients for deterministic time from the real time and the values of the deterministic counters, e. g. by solving the equations C_1*c_1 + C_2*c_2 + ... + C_N*c_N + Err = T where C_1 is the unknown coefficient for counter c_1, Err is the random measurement error and T is the measured real time. The equation can be solved e.g. using the least squares method.

Note that in optimized mode, the counters are disabled for performance reasons, and calling AdvanceDeterministicTime(duration, counter_name) is equivalent to calling AdvanceDeterministicTime(duration).

Todo: (user): The expression "deterministic time" should be replaced with "number of operations" to avoid confusion with "real" time.

Definition at line 94 of file time_limit.h.

Constructor & Destructor Documentation

◆ TimeLimit() [1/3]

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

inlineexplicit

################## Implementations below #####################

Sets the elapsed and the deterministic time. The elapsed time is based on the wall time and the counter starts 'now'. The deterministic time has to be manually advanced using the method AdvanceDeterministicTime().

Use an infinite limit value to ignore a limit.

Definition at line 458 of file time_limit.h.

◆ TimeLimit() [2/3]

operations_research::TimeLimit::TimeLimit ( )

inline

Definition at line 111 of file time_limit.h.

◆ TimeLimit() [3/3]

operations_research::TimeLimit::TimeLimit ( const TimeLimit & )

delete

Member Function Documentation

◆ AdvanceDeterministicTime() [1/2]

void operations_research::TimeLimit::AdvanceDeterministicTime ( double deterministic_duration )

inline

Advances the deterministic time. For reproducibility reasons, the deterministic time doesn't advance automatically as the regular elapsed time does.

Definition at line 183 of file time_limit.h.

◆ AdvanceDeterministicTime() [2/2]

void operations_research::TimeLimit::AdvanceDeterministicTime	(	double	deterministic_duration,
		const char *	counter_name )

inline

Advances the deterministic time. For reproducibility reasons, the deterministic time doesn't advance automatically as the regular elapsed time does.

In debug mode, this method also updates the deterministic time counter with the given name. In optimized mode, this method is equivalent to AdvanceDeterministicTime(double).

Definition at line 197 of file time_limit.h.

◆ ChangeDeterministicLimit()

void operations_research::TimeLimit::ChangeDeterministicLimit ( double new_limit )

inline

Overwrites the deterministic time limit with the new value.

Definition at line 272 of file time_limit.h.

◆ DebugString()

std::string operations_research::TimeLimit::DebugString ( ) const

Returns information about the time limit object in a human-readable form.

Definition at line 34 of file time_limit.cc.

◆ ExternalBooleanAsLimit()

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

inline

Returns the current external Boolean limit.

Definition at line 251 of file time_limit.h.

◆ FromDeterministicTime()

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

inlinestatic

Creates a time limit object that puts limit only on the deterministic time.

Definition at line 127 of file time_limit.h.

◆ FromParameters()

template<typename Parameters >

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

inlinestatic

Creates a time limit object initialized from an object that provides methods max_time_in_seconds() and max_deterministic_time(). This method is designed specifically to work with solver parameter protos, e.g. BopParameters, MipParameters and SatParameters.

Definition at line 140 of file time_limit.h.

◆ GetDeterministicLimit()

double operations_research::TimeLimit::GetDeterministicLimit ( ) const

inline

Queries the deterministic time limit.

Definition at line 279 of file time_limit.h.

◆ GetDeterministicTimeLeft()

double operations_research::TimeLimit::GetDeterministicTimeLeft ( ) const

inline

Returns the remaining deterministic time before LimitReached() returns true due to the deterministic limit. If the TimeLimit was constructed with infinity as the deterministic limit (default value), this will always return infinity.

Definition at line 174 of file time_limit.h.

◆ GetElapsedDeterministicTime()

double operations_research::TimeLimit::GetElapsedDeterministicTime ( ) const

inline

Returns the elapsed deterministic time since the construction of this object. That corresponds to the sum of all deterministic durations passed as an argument to AdvanceDeterministicTime() calls.

Definition at line 217 of file time_limit.h.

◆ GetElapsedTime()

double operations_research::TimeLimit::GetElapsedTime ( ) const

inline

Returns the time elapsed in seconds since the construction of this object.

Definition at line 208 of file time_limit.h.

◆ GetTimeLeft()

double operations_research::TimeLimit::GetTimeLeft ( ) const

inline

Returns the time left on this limit, or 0 if the limit was reached (it never returns a negative value). Note that it might return a positive value even though LimitReached() would return true; because the latter is conservative (see toplevel comment). If LimitReached() was actually called and did return true, though, this will always return 0.

If the TimeLimit was constructed with infinity as the limit, this will always return infinity.

Note that this function is not optimized for speed as LimitReached() is.

Definition at line 533 of file time_limit.h.

◆ Infinite()

static std::unique_ptr< TimeLimit > operations_research::TimeLimit::Infinite ( )

inlinestatic

Creates a time limit object that uses infinite time for wall time and deterministic time.

Definition at line 119 of file time_limit.h.

◆ LimitReached()

bool operations_research::TimeLimit::LimitReached ( )

inline

Returns true when the external limit is true, or the deterministic time is over the deterministic limit or if the next time LimitReached() is called is likely to be over the time limit. See toplevel comment. Once it has returned true, it is guaranteed to always return true.

To avoid making many system calls, we only check the user time when the "absolute" time limit has been reached. Note that the user time should advance more slowly, so this is correct.

To ensure that future calls to LimitReached() will return true.

Definition at line 497 of file time_limit.h.

◆ MergeWithGlobalTimeLimit()

void operations_research::TimeLimit::MergeWithGlobalTimeLimit ( TimeLimit * other )

inline

Sets time limits equal to the min of the current one and the passed limit. If the passed limit contain an external Boolean, replace the current one with it. Not that this does not change the secondary Boolean.

Definition at line 487 of file time_limit.h.

◆ operator=()

TimeLimit & operations_research::TimeLimit::operator= ( const TimeLimit & )

delete

◆ RegisterExternalBooleanAsLimit()

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

inline

Registers the external Boolean to check when LimitReached() is called. This is used to mark the limit as reached through an external Boolean, i.e. LimitReached() returns true when the value of external_boolean_as_limit is true whatever the time limits are.

Note that users of the TimeLimit can modify the provided atomic for their own internal logic (see SharedTimeLimit::Stop() for example).

Definition at line 230 of file time_limit.h.

◆ RegisterSecondaryExternalBooleanAsLimit()

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

inline

Same as RegisterExternalBooleanAsLimit() but register a second Boolean. We have seen that in some situation two Booleans are required, but we haven't needed more than two yet.

Note(user): It was also easier to just add a second one rather to refactor all clients to use a vector for instance.

Definition at line 243 of file time_limit.h.

◆ ResetLimitFromParameters()

template<typename Parameters >

void operations_research::TimeLimit::ResetLimitFromParameters ( const Parameters & parameters )

inline

Sets new time limits. Note that this does not reset the running max nor any registered external Boolean.

Definition at line 482 of file time_limit.h.

Friends And Related Symbol Documentation

◆ NestedTimeLimit

friend class NestedTimeLimit

friend

Definition at line 311 of file time_limit.h.

◆ ParallelTimeLimit

friend class ParallelTimeLimit

friend

Definition at line 312 of file time_limit.h.

Member Data Documentation

◆ kHistorySize

const int operations_research::TimeLimit::kHistorySize = 100

static

Definition at line 97 of file time_limit.h.

◆ kSafetyBufferSeconds

const double operations_research::TimeLimit::kSafetyBufferSeconds = 1e-4

static

static constants.

Definition at line 96 of file time_limit.h.

The documentation for this class was generated from the following files:

ortools/util/time_limit.h
ortools/util/time_limit.cc

Public Member Functions

Static Public Member Functions

Static Public Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ TimeLimit() [1/3]

◆ TimeLimit() [2/3]

◆ TimeLimit() [3/3]

Member Function Documentation

◆ AdvanceDeterministicTime() [1/2]

◆ AdvanceDeterministicTime() [2/2]

◆ ChangeDeterministicLimit()

◆ DebugString()

◆ ExternalBooleanAsLimit()

◆ FromDeterministicTime()

◆ FromParameters()

◆ GetDeterministicLimit()

◆ GetDeterministicTimeLeft()

◆ GetElapsedDeterministicTime()

◆ GetElapsedTime()

◆ GetTimeLeft()

◆ Infinite()

◆ LimitReached()

◆ MergeWithGlobalTimeLimit()

◆ operator=()

◆ RegisterExternalBooleanAsLimit()

◆ RegisterSecondaryExternalBooleanAsLimit()

◆ ResetLimitFromParameters()

Friends And Related Symbol Documentation

◆ NestedTimeLimit

◆ ParallelTimeLimit

Member Data Documentation

◆ kHistorySize

◆ kSafetyBufferSeconds