【ortools源码系列】 time_limit h头文件功能和源码分析
TimeLimit
功能
TimeLimit
类是一个简单的时间限制工具,用于在同一线程中强制执行已过时间限制和确定性时间限制。它可以根据实际运行时间、确定性时间和指令计数来控制程序的运行。该类的主要功能包括:
-
构造函数:可以设置wall time、确定性时间和指令计数限制。
-
LimitReached()方法:检查是否达到了时间限制,如果超过了限制则返回true。
-
GetTimeLeft()方法:返回剩余的时间限制。
-
AdvanceDeterministicTime()方法:提前确定性时间。
-
RegisterExternalBooleanAsLimit()方法:注册一个外部布尔值,当该布尔值为true时,LimitReached()方法将返回true。
-
DebugString()方法:以人类可读的形式返回有关时间限制对象的信息。
SharedTimeLimit
类是对
TimeLimit
类的封装,使其线程安全,并添加了Stop()方法来停止计时。它还可以更新本地时间限制和获取剩余时间。
NestedTimeLimit
类是基于
TimeLimit
类的嵌套时间限制工具,用于对算法中的特定部分设置更严格的时间限制。它接受一个基本的时间限制对象和一个特定部分的时间限制,并创建一个新的时间限制对象,该对象将在整体时间限制或特定部分的时间限制到期时终止。
总之,
TimeLimit
类及其相关类提供了一组工具来控制程序的运行时间,并可以根据实际运行时间、确定性时间和指令计数来设置时间限制。这对于需要对算法的不同部分设置不同时间限制的情况非常有用。
TimeLimit
源码
#ifndef OR_TOOLS_UTIL_TIME_LIMIT_H_
#define OR_TOOLS_UTIL_TIME_LIMIT_H_
#include <algorithm>
#include <atomic>
#include <cstdlib>
#include <limits>
#include <memory>
#include <string>
#include <vector>
#include "absl/base/port.h"
#include "absl/container/flat_hash_map.h"
#include "absl/memory/memory.h"
#include "absl/synchronization/mutex.h"
#include "absl/time/clock.h"
#include "ortools/base/commandlineflags.h"
#include "ortools/base/logging.h"
#include "ortools/base/macros.h"
#include "ortools/base/timer.h"
#include "ortools/util/running_stat.h"
#ifdef HAS_PERF_SUBSYSTEM
#include "exegesis/exegesis/itineraries/perf_subsystem.h"
#endif // HAS_PERF_SUBSYSTEM
// 启用更改TimeLimit类的行为,使用-b usertime而不是walltime。这对于基准测试非常有用。
ABSL_DECLARE_FLAG(bool, time_limit_use_usertime);
// 在TimeLimit类中添加支持测量执行的指令数。
ABSL_DECLARE_FLAG(bool, time_limit_use_instruction_count);
namespace operations_research {
// TimeLimit类是一个简单的类,用于在同一线程中强制执行已过时间限制和确定性时间限制。
// 其思想是尽可能频繁地调用LimitReached()方法,直到它返回false。然后程序应该尽快终止。
//
// 确定性限制用于确保可再现性。因此,必须手动使用AdvanceDeterministicTime()方法来提前确定性时间。
//
// 指令计数器用于跟踪执行的CPU指令数。它使用性能监控单元(PMU)计数器来跟踪指令计数。
//
// 该调用本身很快,只需CycleClock::Now()加上几个简单的指令,除非设置了time_limit_use_instruction_count标志。
//
// 限制非常保守:当current_time + max(T, ε) >= limit_time时,返回true(即达到限制),
// 其中ε是一个小常数(参见TimeLimit::kSafetyBufferSeconds),T是最后kHistorySize次调用LimitReached()之间的最大测量时间间隔(以便我们只考虑“最近”的历史记录)。
// 这样做是为了使实际超过时间限制的概率很小,而不会太早终止。
//
// 可以在更精细的级别上记录确定性时间限制:AdvanceDeterministicTime方法接受一个可选的字符串参数:计数器的名称。
// 在调试模式下,TimeLimit对象还会分别计算每个命名计数器的经过时间,并且可以使用这些值来从操作数计算确定性持续时间的系数。
// 计数器的值可以使用TimeLimit::DebugString()方法打印出来。由于在优化模式下不存在这些计数器,因此没有API直接访问计数器的值。
//
// 确定性时间的基本步骤是:
// 1. 在调试模式下运行代码,以收集确定性时间计数器的值。除非在优化模式下算法不同,否则在调试模式下的确定性计数器的值将与优化模式下的值相同。
// 2. 在优化模式下运行代码,以测量整个基准测试的实际(CPU)时间。
// 3. 根据实际时间和确定性计数器的值确定确定性时间的系数,例如通过解决方程
// C_1*c_1 + C_2*c_2 + ... + C_N*c_N + Err = T
// 其中C_1是计数器c_1的未知系数,Err是随机测量误差,T是测得的实际时间。可以使用最小二乘法等方法解决该方程。
//
// 注意,在优化模式下,出于性能原因,禁用了计数器,并且调用AdvanceDeterministicTime(duration, counter_name)等效于调用AdvanceDeterministicTime(duration)。
class TimeLimit {
public:
static const double kSafetyBufferSeconds;
static const int kHistorySize;
explicit TimeLimit(
double limit_in_seconds,
double deterministic_limit = std::numeric_limits<double>::infinity(),
double instruction_limit = std::numeric_limits<double>::infinity());
TimeLimit() : TimeLimit(std::