我可以在这里使用奇怪的重复模板模式(C++)吗？

Question

我有一个C++应用程序,可以简化为这样的东西:

class AbstractWidget {
 public:
  virtual ~AbstractWidget() {}
  virtual void foo() {}
  virtual void bar() {}
  // (other virtual methods)
};

class WidgetCollection {
 private:
  vector<AbstractWidget*> widgets;

 public:
  void addWidget(AbstractWidget* widget) {
    widgets.push_back(widget);
  }

  void fooAll() {
    for (unsigned int i = 0; i < widgets.size(); i++) {
      widgets[i]->foo();
    }
  }

  void barAll() {
    for (unsigned int i = 0; i < widgets.size(); i++) {
      widgets[i]->bar();
    }
  }

  // (other *All() methods)
};

我的应用程序对性能至关重要.集合中通常有数千个小部件.从AbstractWidget(其中有几十个)派生的类通常会使许多虚函数不被覆盖.被覆盖的通常具有非常快的实现.

鉴于此,我觉得我可以通过一些聪明的元编程来优化我的系统.目标是利用函数内联并避免虚函数调用,同时保持代码可管理.我查看了奇怪的重复模板模式(请参阅此处的说明).这似乎几乎可以做我想要的,但并不完全.

有什么方法可以让CRTP在这里工作吗？或者,还有其他任何人都能想到的聪明解决方案吗？

Answer 1

模拟动态绑定(CRTP的其他用途)适用于基类认为自身是多态的,但客户端实际上只关心一个特定的派生类.因此,例如,您可能拥有表示某些特定于平台的功能的接口的类,并且任何给定的平台将只需要一个实现.模式的要点是对基类进行模板化,这样即使有多个派生类,基类也会在编译时知道哪一个正在使用.

当你真正需要运行时多态时,它没有帮助,例如当你有一个容器时AbstractWidget*,每个元素可以是几个派生类之一,你必须迭代它们.在CRTP(或任何模板代码),base<derived1>并且base<derived2>是不相关的类.因此,这样的derived1和derived2.它们之间没有动态多态,除非它们有另一个公共基类,但是你回到了虚拟调用的起点.

您可以通过使用几个向量替换向量来获得一些加速:一个用于您知道的每个派生类,另一个用于稍后添加新派生类并且不更新容器的泛型.然后,addWidget会对typeid窗口小部件执行一些(慢速)检查或虚拟调用,将窗口小部件添加到正确的容器中,并且可能在调用者知道运行时类时有一些重载.注意不要意外WidgetIKnowAbout地向WidgetIKnowAbout*向量添加子类.fooAll和barAll过依次在每个容器制造(快)可循环调用非虚拟fooImpl和barImpl功能然后,将被内联.然后,他们遍历希望小得多的AbstractWidget*向量,调用虚拟foo或bar函数.

它有点乱,而不是纯粹的OO,但如果几乎所有的小部件都属于容器所知的类,那么你可能会看到性能提升.

请注意,如果大多数小部件属于您的容器无法知道的类(例如,因为它们位于不同的库中),那么您不可能具有内联(除非您的动态链接器可以内联.我的不能).您可以通过弄乱成员函数指针来降低虚拟调用开销,但增益几乎肯定可以忽略不计甚至是负数.虚拟调用的大部分开销都在调用本身,而不是虚拟查找,并且不会内联通过函数指针调用.

换句话说:如果要内联代码,这意味着不同类型的实际机器代码必须不同.这意味着您需要多个循环或带有开关的循环,因为根据从集合中拉出的某个指针的类型,机器代码在每次通过循环时都无法在ROM中更改.

好吧,我想这个对象可能包含一些asm代码,循环复制到RAM中,标记可执行文件,然后跳转到.但那不是C++成员函数.它不能轻松完成.它可能甚至不会很快,复制和ic​​ache失效的东西.这就是虚拟通话存在的原因......

Answer 2

CRTP或编译时多态性适用于在编译时知道所有类型的情况.只要你使用addWidget在运行时,只要收集小部件列表fooAll,并barAll随后在运行时需要处理的小部件是同质列表中的成员,你必须要能够在运行时处理不同类型.因此,对于您提出的问题,我认为您使用运行时多态性.

当然,标准答案是在尝试避免运行时多态性之前验证运行时多态性的性能是否...

如果您确实需要避免运行时多态性,则可以使用以下解决方案之一.

选项1:使用编译时小部件集合

如果您的WidgetCollection成员在编译时已知,那么您可以非常轻松地使用模板.

template<typename F>
void WidgetCollection(F functor)
{
  functor(widgetA);
  functor(widgetB);
  functor(widgetC);
}

// Make Foo a functor that's specialized as needed, then...

void FooAll()
{
  WidgetCollection(Foo);
}

选项2:使用自由函数替换运行时多态性

class AbstractWidget {
 public:
  virtual AbstractWidget() {}
  // (other virtual methods)
};

class WidgetCollection {
 private:
  vector<AbstractWidget*> defaultFooableWidgets;
  vector<AbstractWidget*> customFooableWidgets1;
  vector<AbstractWidget*> customFooableWidgets2;      

 public:
  void addWidget(AbstractWidget* widget) {
    // decide which FooableWidgets list to push widget onto
  }

  void fooAll() {
    for (unsigned int i = 0; i < defaultFooableWidgets.size(); i++) {
      defaultFoo(defaultFooableWidgets[i]);
    }
    for (unsigned int i = 0; i < customFooableWidgets1.size(); i++) {
      customFoo1(customFooableWidgets1[i]);
    }
    for (unsigned int i = 0; i < customFooableWidgets2.size(); i++) {
      customFoo2(customFooableWidgets2[i]);
    }
  }
};

丑陋,真的不是OO.模板可以通过减少列出每个特殊情况的需要来帮助解决这个问题; 尝试类似下面的内容(完全未经测试),但在这种情况下你回到没有内联.

class AbstractWidget {
 public:
  virtual AbstractWidget() {}
};

class WidgetCollection {
 private:
  map<void(AbstractWidget*), vector<AbstractWidget*> > fooWidgets;

 public:
  template<typename T>
  void addWidget(T* widget) {
    fooWidgets[TemplateSpecializationFunctionGivingWhichFooToUse<widget>()].push_back(widget);
  }

  void fooAll() {
    for (map<void(AbstractWidget*), vector<AbstractWidget*> >::const_iterator i = fooWidgets.begin(); i != fooWidgets.end(); i++) {
      for (unsigned int j = 0; j < i->second.size(); j++) {
        (*i->first)(i->second[j]);
      }
    }
  }
};

方案3:消除OO

OO很有用,因为它有助于管理复杂性,因为它有助于在面对变化时保持稳定性.对于您似乎在描述的情况 - 成千上万的小部件,其行为通常不会改变,并且其成员方法非常简单 - 您可能没有太多的复杂性或更改来管理.如果是这种情况,那么您可能不需要OO.

此解决方案与运行时多态性相同,只是它要求您维护"虚拟"方法和已知子类(不是OO)的静态列表,并且它允许您使用跳转表将虚拟函数调用替换为内联函数.

class AbstractWidget {
 public:
  enum WidgetType { CONCRETE_1, CONCRETE_2 };
  WidgetType type;
};

class WidgetCollection {
 private:
  vector<AbstractWidget*> mWidgets;

 public:
  void addWidget(AbstractWidget* widget) {
    widgets.push_back(widget);
  }

  void fooAll() {
    for (unsigned int i = 0; i < widgets.size(); i++) {
      switch(widgets[i]->type) {
        // insert handling (such as calls to inline free functions) here
      }
    }
  }
};