7

我有一个可以简化为这样的 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 在这里为我工作吗?或者,还有其他任何人能想到的聪明的解决方案吗?

4

6 回答 6

7

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

当您真正需要运行时多态性时,它对您没有帮助,例如当您有一个容器时AbstractWidget*,每个元素都可以是几个派生类之一,并且您必须遍历它们。在 CRTP(或任何模板代码)中,base<derived1>都是base<derived2>不相关的类。因此derived1和 也是如此derived2。除非它们有另一个公共基类,否则它们之间没有动态多态性,但是你又回到了从虚拟调用开始的地方。

您可以通过将向量替换为多个向量来获得一些加速:一个用于您知道的每个派生类,一个通用的用于稍后添加新派生类且不更新容器时。然后 addWidget 对小部件进行一些(缓慢的)typeid检查或虚拟调用,以将小部件添加到正确的容器中,并且当调用者知道运行时类时可能会有一些重载。小心不要意外地将 的子类添加WidgetIKnowAboutWidgetIKnowAbout*向量中。fooAll并且barAll可以循环遍历每个容器,依次对非虚拟fooImplbarImpl函数进行(快速)调用,然后将其内联。然后他们遍历希望小得多的AbstractWidget*向量,调用虚函数foobar函数。

这有点混乱而且不是纯 OO,但如果几乎所有小部件都属于容器知道的类,那么您可能会看到性能提升。

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

换个角度看:如果要内联代码,这意味着不同类型的实际机器代码必须不同。这意味着您需要多个循环,或者一个带有开关的循环,因为机器代码显然不能在每次通过循环时在 ROM 中更改,具体取决于从集合中拉出的某个指针的类型。

好吧,我猜这个对象可能包含一些 asm 代码,循环复制到 RAM 中,标记为可执行文件,然后跳转到。但这不是 C++ 成员函数。而且它不能便携。它甚至可能不会很快,复制和 icache 失效。这就是为什么存在虚拟呼叫...

于 2009-06-16T17:05:43.960 回答
5

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
      }
    }
  }
};
于 2009-06-16T17:00:28.037 回答
4

最简洁的答案是不。

长答案(或仍然短于其他一些答案:-)

您正在动态地尝试找出在运行时要执行的函数(即虚拟函数是什么)。如果您有一个向量(在编译时无法确定其成员),那么无论您尝试什么,您都无法弄清楚如何内联函数。

唯一需要注意的是,如果向量总是包含相同的元素(即,您可以计算出编译时间将在运行时执行什么)。然后您可以重新工作,但它需要除矢量以外的其他东西来保存元素(可能是一个所有元素作为成员的结构)。

另外,你真的认为虚拟调度是一个瓶颈吗?
我个人非常怀疑。

于 2009-06-16T17:39:44.267 回答
3

您将在这里遇到的问题是WidgetCollection::widgets. 一个向量只能包含一种类型的项,并且使用 CRTP 要求每个项AbstractWidget都具有不同的类型,并由所需的派生类型进行模板化。也就是说,你AbstractWidget看起来像这样:

template< class Derived >
class AbstractWidget {
    ...
    void foo() {
        static_cast< Derived* >( this )->foo_impl();
    }        
    ...
}

这意味着每个AbstractWidget具有不同Derived类型的都会构成不同的类型AbstractWidget< Derived >。将这些全部存储在一个向量中是行不通的。所以看起来,在这种情况下,虚拟功能是要走的路。

于 2009-06-16T16:56:13.563 回答
3

如果您需要它们的向量,则不需要。STL 容器是完全同构的,这意味着如果您需要将一个小部件A 和一个小部件B 存储在同一个容器中,它们必须从一个共同的父级继承。而且,如果widgetA::bar() 做的事情与widgetB::bar() 不同,则必须使函数虚拟化。

所有的小部件都需要在同一个容器中吗?你可以做类似的事情

vector<widgetA> widget_a_collection;
vector<widgetB> widget_b_collection;

然后这些功能就不需要是虚拟的了。

于 2009-06-16T16:57:38.023 回答
1

很可能,在您完成所有这些努力之后,您将看不到性能差异。

这绝对是错误的优化方式。您不会通过更改随机代码行来修复逻辑错误吗?不,这很愚蠢。在您首先找到哪些行实际上导致您的问题之前,您不会“修复”代码。那么为什么你会以不同的方式处理性能错误呢?

您需要分析您的应用程序并找出真正的瓶颈在哪里。然后加速该代码并重新运行分析器。重复直到性能错误(执行太慢)消失。

于 2009-06-16T17:48:04.300 回答