C++ Reference

C++ Reference: CP-SAT

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 instruction counter keeps track of number of executed cpu instructions. It uses Performance Monitoring Unit (PMU) counters to keep track of instruction count.

The call itself is as fast as CycleClock::Now() + a few trivial instructions, unless the time_limit_use_instruction_count flag is set.

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:

  1. 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.
  2. Run the code in optimized mode to measure the real (CPU) time of the whole benchmark.
  3. 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).

Definition at line 105 of file time_limit.h.

Public Member Functions

 TimeLimit (double limit_in_seconds, double deterministic_limit=std::numeric_limits< double >::infinity(), double instruction_limit=std::numeric_limits< double >::infinity())
 Sets the elapsed, the deterministic time and the instruction count limits. More...
 
 TimeLimit ()
 
 TimeLimit (const TimeLimit &)=delete
 
TimeLimitoperator= (const TimeLimit &)=delete
 
void SetInstructionLimit (double instruction_limit)
 Sets the instruction limit. More...
 
double ReadInstructionCounter ()
 Returns the number of instructions executed since the creation of this object. More...
 
bool LimitReached ()
 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. More...
 
double GetTimeLeft () const
 Returns the time left on this limit, or 0 if the limit was reached (it never returns a negative value). More...
 
double GetDeterministicTimeLeft () const
 Returns the remaining deterministic time before LimitReached() returns true due to the deterministic limit. More...
 
double GetInstructionsLeft ()
 Returns the number of instructions left to reach the limit. More...
 
void AdvanceDeterministicTime (double deterministic_duration)
 Advances the deterministic time. More...
 
void AdvanceDeterministicTime (double deterministic_duration, const char *counter_name)
 Advances the deterministic time. More...
 
double GetElapsedTime () const
 Returns the time elapsed in seconds since the construction of this object. More...
 
double GetElapsedDeterministicTime () const
 Returns the elapsed deterministic time since the construction of this object. More...
 
void RegisterExternalBooleanAsLimit (std::atomic< bool > *external_boolean_as_limit)
 Registers the external Boolean to check when LimitReached() is called. More...
 
std::atomic< bool > * ExternalBooleanAsLimit () const
 Returns the current external Boolean limit. More...
 
template<typename Parameters >
void ResetLimitFromParameters (const Parameters &parameters)
 Sets new time limits. More...
 
void MergeWithGlobalTimeLimit (TimeLimit *other)
 
std::string DebugString () const
 Returns information about the time limit object in a human-readable form. More...
 

Static Public Member Functions

static std::unique_ptr< TimeLimitInfinite ()
 Creates a time limit object that uses infinite time for wall time, deterministic time and instruction count limit. More...
 
static std::unique_ptr< TimeLimitFromDeterministicTime (double deterministic_limit)
 Creates a time limit object that puts limit only on the deterministic time. More...
 
template<typename Parameters >
static std::unique_ptr< TimeLimitFromParameters (const Parameters &parameters)
 Creates a time limit object initialized from an object that provides methods max_time_in_seconds() and max_deterministic_time(). More...
 

Static Public Attributes

static const double kSafetyBufferSeconds
 
static const int kHistorySize
 

Constructor & Destructor Documentation

◆ TimeLimit() [1/3]

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

Sets the elapsed, the deterministic time and the instruction count limits.

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().

Instruction count is the number of instructions executed. It is based on PMU counters and is not very acurate.

Use an infinite limit value to ignore a limit.

Definition at line 471 of file time_limit.h.

◆ TimeLimit() [2/3]

TimeLimit ( )
inline

Definition at line 126 of file time_limit.h.

◆ TimeLimit() [3/3]

TimeLimit ( const TimeLimit )
delete

Member Function Documentation

◆ AdvanceDeterministicTime() [1/2]

void 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 226 of file time_limit.h.

◆ AdvanceDeterministicTime() [2/2]

void 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 240 of file time_limit.h.

◆ DebugString()

std::string DebugString ( ) const

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

◆ ExternalBooleanAsLimit()

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

Returns the current external Boolean limit.

Definition at line 280 of file time_limit.h.

◆ FromDeterministicTime()

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

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

Definition at line 144 of file time_limit.h.

◆ FromParameters()

static std::unique_ptr<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 159 of file time_limit.h.

◆ GetDeterministicTimeLeft()

double 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 212 of file time_limit.h.

◆ GetElapsedDeterministicTime()

double 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 260 of file time_limit.h.

◆ GetElapsedTime()

double GetElapsedTime ( ) const
inline

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

Definition at line 251 of file time_limit.h.

◆ GetInstructionsLeft()

double GetInstructionsLeft ( )
inline

Returns the number of instructions left to reach the limit.

Definition at line 581 of file time_limit.h.

◆ GetTimeLeft()

double 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 570 of file time_limit.h.

◆ Infinite()

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

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

Definition at line 134 of file time_limit.h.

◆ LimitReached()

bool 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.

Definition at line 532 of file time_limit.h.

◆ MergeWithGlobalTimeLimit()

void MergeWithGlobalTimeLimit ( TimeLimit other)
inline

Definition at line 511 of file time_limit.h.

◆ operator=()

TimeLimit& operator= ( const TimeLimit )
delete

◆ ReadInstructionCounter()

double ReadInstructionCounter ( )
inline

Returns the number of instructions executed since the creation of this object.

Definition at line 522 of file time_limit.h.

◆ RegisterExternalBooleanAsLimit()

void 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 : The external_boolean_as_limit can be modified during solve.

Definition at line 272 of file time_limit.h.

◆ ResetLimitFromParameters()

void 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 505 of file time_limit.h.

◆ SetInstructionLimit()

void SetInstructionLimit ( double  instruction_limit)
inline

Sets the instruction limit.

We need this method since the static constructor to create time limit from parameters doesn't support setting instruction limit.

Definition at line 171 of file time_limit.h.

Member Data Documentation

◆ kHistorySize

const int kHistorySize
static

Definition at line 108 of file time_limit.h.

◆ kSafetyBufferSeconds

const double kSafetyBufferSeconds
static

Definition at line 107 of file time_limit.h.


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