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:
- 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).
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 | |
TimeLimit & | operator= (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 ¶meters) |
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< TimeLimit > | Infinite () |
Creates a time limit object that uses infinite time for wall time, deterministic time and instruction count limit. More... | |
static std::unique_ptr< TimeLimit > | FromDeterministicTime (double deterministic_limit) |
Creates a time limit object that puts limit only on the deterministic time. More... | |
template<typename Parameters > | |
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() and max_deterministic_time(). More... | |
Static Public Attributes | |
static const double | kSafetyBufferSeconds |
static const int | kHistorySize |
Constructor & Destructor Documentation
◆ TimeLimit() [1/3]
|
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]
|
inline |
Definition at line 126 of file time_limit.h.
◆ TimeLimit() [3/3]
Member Function Documentation
◆ AdvanceDeterministicTime() [1/2]
|
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]
|
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()
|
inline |
Returns the current external Boolean limit.
Definition at line 280 of file time_limit.h.
◆ FromDeterministicTime()
|
inlinestatic |
Creates a time limit object that puts limit only on the deterministic time.
Definition at line 144 of file time_limit.h.
◆ FromParameters()
|
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()
|
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()
|
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()
|
inline |
Returns the time elapsed in seconds since the construction of this object.
Definition at line 251 of file time_limit.h.
◆ GetInstructionsLeft()
|
inline |
Returns the number of instructions left to reach the limit.
Definition at line 581 of file time_limit.h.
◆ GetTimeLeft()
|
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()
|
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()
|
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()
|
inline |
Definition at line 511 of file time_limit.h.
◆ operator=()
◆ ReadInstructionCounter()
|
inline |
Returns the number of instructions executed since the creation of this object.
Definition at line 522 of file time_limit.h.
◆ RegisterExternalBooleanAsLimit()
|
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()
|
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()
|
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
|
static |
Definition at line 108 of file time_limit.h.
◆ kSafetyBufferSeconds
|
static |
Definition at line 107 of file time_limit.h.
The documentation for this class was generated from the following file: