多方法与双调度器详解

### 多方法与双调度器详解 #### 1. 恒定时间多方法：极致速度 在调度器的选择上，静态调度器耦合性高，基于映射的调度器速度慢。若追求绝对速度和可扩展性，就需要考虑恒定时间调度器。 双调度的本质是在二维空间中找到处理函数，其中一个轴是左操作数的类型，另一个轴是右操作数的类型，两者的交点即为对应的处理函数。例如，在形状（Shapes）和绘图设备（DrawingDevices）的双调度中，处理函数可以是在具体绘图设备上渲染具体形状对象的绘图函数。 为了在二维空间中实现恒定时间的搜索，可采用二维矩阵的索引访问。每个类需有唯一的整数值作为调度器矩阵中的索引，且该整数值能在恒定时间内被访问，可借助虚函数实现。当发出双调度调用时，调度器从两个对象获取索引，访问矩阵中的处理函数并执行，成本为两次虚调用、一次矩阵索引操作和一次函数指针调用，成本恒定。 不过，实现过程存在一些细节问题，如维护索引可能会很麻烦，每个类需分配唯一的整数值 ID，且要确保在编译时能检测到重复 ID，ID 需从 0 开始且无间隙，否则会浪费矩阵存储空间。 更好的解决方案是将索引管理移至调度器本身。每个类存储一个静态整数变量，初始值为 -1 表示未分配，虚函数返回该静态变量的引用，允许调度器在运行时更改其值。当向矩阵添加新处理函数时，调度器访问 ID，若为 -1，则为其分配矩阵中的下一个可用槽位。 以下是实现的关键宏： ```cpp #define IMPLEMENT_INDEXABLE_CLASS(SomeClass) static int& GetClassIndexStatic()\ {\ static int index = -1;\ return index;\ }\ virtual int& GetClassIndex()\ {\ assert(typeid(*this) == typeid(SomeClass));\ return GetClassIndexStatic();\ } ``` 需将此宏插入每个要支持多调度的类的公共部分。 `BasicFastDispatcher` 类模板与之前定义的 `BasicDispatcher` 功能相同，但使用不同的存储和检索机制： ```cpp template < class BaseLhs, class BaseRhs = BaseLhs, typename ResultType = void, typename CallbackType = ResultType (*)(BaseLhs&, BaseRhs&) > class BasicFastDispatcher { typedef std::vector<CallbackType> Row; typedef std::vector<Row> Matrix; Matrix callbacks_; int columns_; public: BasicFastDispatcher() : columns_(0) {} template <class SomeLhs, SomeRhs> void Add(CallbackType pFun) { int& idxLhs = SomeLhs::GetClassIndexStatic(); if (idxLhs < 0) { callbacks_.push_back(Row()); idxLhs = callbacks_.size() - 1; } else if (callbacks_.size() <= idxLhs) { callbacks_.resize(idxLhs + 1); } Row& thisRow = callbacks_[idxLhs]; int& idxRhs = SomeRhs::GetClassIndexStatic(); if (idxRhs < 0) { thisRow.resize(++columns_); idxRhs = thisRow.size() - 1; } else if (thisRow.size() <= idxRhs) { thisRow.resize(idxRhs + 1); } thisRow[idxRhs] = pFun; } }; ``` `BasicFastDispatcher::Add` 函数的操作步骤如下： 1. 调用 `GetClassIndexStatic` 获取每个类的 ID。 2. 若一个或两个索引未初始化，则进行初始化和调整，为未初始化的索引扩展矩阵以容纳额外元素。 3. 将回调插入矩阵的正确位置。 `columns_` 成员变量记录到目前为止添加的列数，虽严格来说是冗余的，但使用起来更方便。 `BasicFastDispatcher::Go` 函数的实现如下： ```cpp template <...> class BasicFastDispatcher { ... as above ... ResultType Go(BaseLhs& lhs, BaseRhs& rhs) { int& idxLhs = lhs.GetClassIndex(); int& idxRhs = rhs.GetClassIndex(); if (idxLhs < 0 || idxRhs < 0 || idxLhs >= callbacks_.size() || idxRhs >= callbacks_[idxLhs].size() || callbacks_[idxLhs][idxRhs] == 0) { ... error handling goes here ... } return callbacks_[idxLhs][idxRhs].callback_(lhs, rhs); } }; ``` 总结来说，基于矩阵的调度器通过为每个类分配整数值索引，能在恒定时间内访问回调对象，并自动初始化支持数据（类对应的索引）。使用 `BasicFastDispatcher` 的用户需在每个使用该调度器的类中添加 `IMPLEMENT_INDEXABLE_CLASS(YourClass)` 宏。 #### 2. 基本调度器和快速基本调度器作为策略 当速度是关键因素时，基于矩阵的 `BasicFastDispatcher` 优于基于映射的 `BasicDispatcher`。但高级类 `FnDispatcher` 和 `FunctorDispatcher` 是围绕 `BasicDispatcher` 构建的，是否需要开发使用 `BasicFastDispatcher` 作为后端的 `FnFastDispatcher` 和 `FunctorFastDispatcher` 呢？ 更好的方法是让 `FnDispatcher` 和 `FunctorDispatcher` 根据模板参数选择使用 `BasicDispatcher` 或 `BasicFastDispatcher`，即将调度器作为策略，就像处理类型转换策略一样。 由于 `BasicDispatcher` 和 `BasicFastDispatcher` 具有相同的调用接口，因此替换它们就像更改模板参数一样简单。以下是 `FnDispatcher` 的修订声明： ```cpp template < class BaseLhs, class BaseRhs = BaseLhs, typename ResultType = void, template <class, class> class CastingPolicy = Dyn ```