Могу ли я использовать здесь шаблон Curily Recurring Template (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, но если почти все ваши виджеты принадлежат классам, о которых знает ваш контейнер, то вы можете увидеть увеличение производительности.

Обратите внимание, что если большинство виджетов принадлежат классам, о которых ваш контейнер не может знать (например, потому что они находятся в разных библиотеках), то у вас не может быть встроенного (если ваш динамический компоновщик не может быть встроенным. Мой может т). Вы могли бы отбросить накладные расходы на виртуальный вызов, возившись с указателями на функции-члены, но выигрыш почти наверняка будет незначительным или даже отрицательным. Большая часть накладных расходов на виртуальный вызов связана с самим вызовом, а не с виртуальным поиском, и вызовы через указатели функций не будут встроены.

Посмотрите на это по-другому: если код должен быть встроен, это означает, что фактический машинный код должен отличаться для разных типов. Это означает, что вам нужно либо несколько циклов, либо цикл с переключателем в нем, потому что машинный код явно не может изменяться в ПЗУ при каждом проходе цикла, в соответствии с типом некоторого указателя, извлеченного из коллекции.

Ну, я думаю, что, возможно, объект может содержать некоторый asm-код, который цикл копирует в RAM, отмечает исполняемый файл и переходит в него. Но это не функция-член C ++. И это нельзя сделать переносно. И это, вероятно, даже не будет быстрым, что с копированием и аннулированием icache. Вот почему существуют виртуальные звонки ...

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]);
    }
  }
};

Ужасно, и действительно не ОО. Шаблоны могут помочь с этим, уменьшая необходимость перечислять каждый особый случай; попробуйте что-то вроде следующего (полностью непроверенное), но в этом случае вы не вернетесь.

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.

Это решение аналогично полиморфизму времени выполнения, за исключением того, что оно требует ведения статического списка «виртуальных» методов и известных подклассов (который не является ОО) и позволяет заменять вызовы виртуальных функций таблицей перехода на встроенный функции.

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
      }
    }
  }
};

Answer 3

Короткий ответ - нет.

Длинный ответ (или все еще короткий ответ на некоторые другие ответы: -)

Вы динамически пытаетесь выяснить, какую функцию выполнять во время выполнения (то есть, что такое виртуальные функции). Если у вас есть вектор (чьи члены не могут быть определены во время компиляции), вы не сможете определить, как встроить функции независимо от того, что вы пытаетесь.

Единственный недостаток в том, что если векторы всегда содержат одни и те же элементы (т. Е. Вы можете отработать во время компиляции то, что будет выполняться во время выполнения). Затем вы могли бы переработать это, но для хранения элементов потребовалось бы нечто иное, чем вектор (вероятно, структура со всеми элементами в качестве членов).

Кроме того, вы действительно думаете, что виртуальная рассылка является узким местом?
Лично я в этом сильно сомневаюсь.

Answer 4

Нет, если вам нужен вектор из них. Контейнеры STL полностью однородны, что означает, что если вам нужно хранить widgetA и widgetB в одном контейнере, они должны быть унаследованы от общего родителя. И если widgetA :: bar () делает что-то отличное от widgetB :: bar (), вы должны сделать функции виртуальными.

Должны ли все виджеты быть в одном контейнере? Вы могли бы сделать что-то вроде

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

И тогда функции не должны быть виртуальными.

Answer 5

Проблема, с которой вы столкнетесь, связана с WidgetCollection::widgets. Вектор может содержать только элементы одного типа, и для использования CRTP требуется, чтобы каждый AbstractWidget имел свой тип, шаблонизированный требуемым производным типом. То есть вы AbstractWidget выглядели бы примерно так:

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

Это означает, что каждый AbstractWidget с другим типом Derived будет составлять свой тип AbstractWidget< Derived >. Хранить их все в одном векторе не получится. Похоже, в этом случае виртуальные функции - это путь.

Answer 6

Скорее всего, после того, как вы пройдете все эти усилия, вы не увидите никакой разницы в производительности.

Это абсолютно неправильный способ оптимизации. Вы бы не исправили логическую ошибку, изменяя случайные строки кода, не так ли? Нет, это глупо. Вы не «исправляете» код до тех пор, пока не обнаружите, какие строки действительно вызывают вашу проблему. Так почему же вы по-другому относитесь к производительности ошибок?

Вам нужно профилировать свою заявку и найти реальные узкие места. Затем ускорите этот код и снова запустите профилировщик. Повторяйте, пока ошибка производительности (слишком медленное выполнение) не исчезнет.