Могу ли я использовать здесь шаблон 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 (из которых десятки) обычно оставляют многие виртуальные функции не переопределенными. Те, которые переопределяются, обычно имеют очень быстрые реализации.

Учитывая это, я чувствую, что могу оптимизировать свою систему с помощью некоторого умного метапрограммирования. Цель состоит в том, чтобы использовать встраивание функций и избежать вызовов виртуальных функций, сохраняя при этом код управляемым. Я заглянул в шаблон с любопытными повторяющимися шаблонами (см. Описание здесь ). Кажется, это почти делает то, что я хочу, но не совсем.

Есть ли способ заставить меня работать здесь? Или есть какое-нибудь другое умное решение, о котором можно подумать?

Answer 1

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.

Это решение аналогично полиморфизму во время выполнения, за исключением того, что оно требует ведения статического списка " virtual " методы и известные подклассы (которые не являются 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 2

Имитация динамического связывания (есть и другие применения CRTP) для случая, когда базовый класс считает себя полиморфным, а клиентов фактически заботится только об одном конкретном производном учебный класс. Так, например, у вас могут быть классы, представляющие интерфейс для некоторой функциональности, специфичной для платформы, и любой конкретной платформе потребуется только одна реализация. Смысл шаблона в том, чтобы шаблонизировать базовый класс, чтобы, несмотря на наличие нескольких производных классов, базовый класс знал во время компиляции, какой из них используется.

Это не поможет вам, когда вам действительно нужен полиморфизм во время выполнения, например, когда у вас есть контейнер AbstractWidget*, каждый элемент может быть одним из нескольких производных классов, и вам придется их перебирать. В CRTP (или любом коде шаблона) base<derived1> и base<derived2> не связаны между собой классами. Отсюда и derived1, и derived2. Между ними нет динамического полиморфизма, если только у них нет другого общего базового класса, но тогда вы вернулись к тому, с чего начали виртуальные вызовы.

Вы можете получить некоторое ускорение, заменив вектор на несколько векторов: по одному для каждого из производных классов, о которых вы знаете, и один для того, когда вы добавляете новые производные классы позже и не обновляете контейнер. Затем addWidget выполняет некоторую (медленную) typeid проверку или виртуальный вызов виджета, чтобы добавить виджет в правильный контейнер, и, возможно, имеет некоторые перегрузки, когда вызывающий объект знает класс времени выполнения. Будьте осторожны, чтобы случайно не добавить подкласс WidgetIKnowAbout в вектор WidgetIKnowAbout*. fooAll и barAll могут циклически перебирать каждый контейнер, делая (быстрые) вызовы не виртуальных функций fooImpl и barImpl, которые затем будут встроены. Затем они перебирают, мы надеемся, намного меньший вектор foo, вызывая виртуальные функции bar или <=>.

Это немного грязно и не чисто OO, но если почти все ваши виджеты принадлежат классам, о которых ваш контейнер знает, то вы можете увидеть увеличение производительности.

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

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

Answer 6

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

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

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