Posso usar a configuração padrão Curiosamente recorrente aqui (C ++)?

Question

Eu tenho um aplicativo C ++ que pode ser simplificada para algo como isto:

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

A minha aplicação é de desempenho crítico. Há tipicamente milhares de widgets na coleção. As classes derivadas de AbstractWidget (dos quais existem dezenas) deixar tipicamente muitas das funções virtuais não substituídas. Os que são substituídas geralmente têm implementações muito rápidas.

Diante disso, eu sinto que posso otimizar meu sistema com alguma meta-programação inteligente. O objetivo é função de alavanca inlining e para evitar chamadas de funções virtuais, mantendo o managable código. Eu olhei para o Recorrente Pattern Template Curiosamente (ver aqui para descrição). Este parece quase fazer o que quero, mas não completamente.

Existe alguma maneira de fazer o trabalho CRTP para mim aqui? Ou há alguma outra inteligente solução ninguém pode pensar?

Answer 1

CRTP ou tempo de compilação polimorfismo é para quando você sabe todos os seus tipos em tempo de compilação. Enquanto você estiver usando addWidget para coletar uma lista de widgets em tempo de execução e, enquanto fooAll e barAll então tem que lidar com os membros dessa lista homogênea de widgets em tempo de execução, você tem que ser capaz de lidar com diferentes tipos em tempo de execução. Assim, para o problema que você apresentou, eu acho que você está preso usando polimorfismo em tempo de execução.

A resposta padrão, é claro, é para verificar se o desempenho do polimorfismo em tempo de execução é um problema antes de tentar evitá-lo ...

Se você realmente precisa polimorfismo evitar a execução, em seguida, uma das seguintes soluções pode funcionar.

Opção 1: Use uma coleção de tempo de compilação de widgets

Se os membros do seu WidgetCollection são conhecidos em tempo de compilação, então você pode facilmente usar modelos.

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

Opção 2: Substitua o polimorfismo em tempo de execução com funções gratuitos

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

Feio, e realmente não OO. Modelos poderia ajudar com isso, reduzindo a necessidade de listar cada caso especial; tentar algo como o seguinte (completamente não testado), mas você está de volta para não inlining neste caso.

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

Opção 3: Eliminar OO

OO é útil porque ajuda a gerenciar a complexidade e porque ajuda a manter a estabilidade em face da mudança. Para as circunstâncias você parece estar descrevendo - milhares de widgets, cujo comportamento geralmente não muda, e cujo membro métodos são muito simples - você não pode ter muita complexidade ou mudança de gerir. Se for esse o caso, então você pode não precisar de OO.

Esta solução é o mesmo que o polimorfismo em tempo de execução, exceto que ele requer que você mantenha uma lista estática de métodos "virtuais" e subclasses conhecidas (que não é OO) e permite que você substituir chamadas de função virtuais com uma mesa de salto para inlined funções.

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

Simulado de ligação dinâmica (existem outros usos da CRTP) é para quando a classe base pensa de si mesmo como sendo polimórfico, mas clientes única realmente se preocupam com um especial derivado classe. Assim, por exemplo, você pode ter aulas representando uma interface para algumas funcionalidades específicas da plataforma, e qualquer plataforma só vai precisar de uma implementação. O ponto do padrão é templatize a classe base, de modo que, apesar de existirem várias classes derivadas, a classe base sabe em tempo de compilação que está em uso.

Não ajudá-lo quando você precisa realmente polimorfismo em tempo de execução, como por exemplo, quando você tem um recipiente de AbstractWidget*, cada elemento pode ser uma das várias classes derivadas, e você tem que interagir sobre eles. Em CRTP (ou qualquer código do modelo), base<derived1> e base<derived2> são classes não relacionadas. Daí por isso são derived1 e derived2. Não há polimorfismo dinâmico entre eles a menos que tenham uma outra classe base comum, mas, em seguida, você está de volta onde você começou com chamadas virtuais.

Você pode obter alguma aceleração, substituindo seu vetor com vários vetores: um para cada uma das classes derivadas que você sabe sobre, e um genérico para quando você adicionar novas classes derivadas mais tarde e não atualizar o recipiente. Então addWidget faz algum (lento) a verificação typeid ou uma chamada virtual para o widget, para adicionar o widget para o recipiente correto, e talvez tem algumas sobrecargas para quando o chamador sabe a classe de tempo de execução. Tenha cuidado para não adicionar acidentalmente uma subclasse de WidgetIKnowAbout ao vetor WidgetIKnowAbout*. fooAll e barAll lata loop sobre cada recipiente na tomada de turno (rápido) chamadas para funções fooImpl e barImpl não-virtuais que irá então ser embutido. Eles, então, varrer o vector AbstractWidget* espero muito menor, chamando as funções foo ou bar virtuais.

É uma bagunça pouco e não puro-OO, mas se quase todos os seus widgets pertencem a classes que seu recipiente conhece, então você pode ver um aumento de desempenho.

Note que, se a maioria dos widgets de pertencer a classes que o recipiente não pode saber sobre (porque eles estão em diferentes bibliotecas, por exemplo), então você não pode, eventualmente, ter inlining (a menos que o vinculador dinâmico pode inline. Mina pode' t). Você poderia deixar cair a sobrecarga chamada virtual por mexer com ponteiros de função de membro, mas o ganho seria quase certamente negativo insignificante ou mesmo. A maior parte da sobrecarga de uma chamada virtual está na própria chamada, não a pesquisa virtual, e chamadas através de ponteiros de função não vai ser embutido.

olhar para ele de outra forma: se o código é para ser embutido, isso significa que o código de máquina real tem que ser diferente para os diferentes tipos. Isto significa que você precisará de vários loops, ou um laço com um interruptor nela, porque o código de máquina claramente não pode mudar em ROM em cada passagem pelo loop, de acordo com o tipo de alguns ponteiro puxado para fora de uma coleção.

Bem, eu acho que talvez o objeto poderia conter algum código asm que o loop copia para RAM, marcas executável, e salta para. Mas isso não é uma função C ++ membro. E isso não pode ser feito portably. E provavelmente não iria mesmo ser rápido, o que com a cópia e a invalidação ICACHE. É por isso que as chamadas virtuais existem ...

Answer 3

A resposta curta não é.

A resposta longa (ou ainda curta campared a algumas outras respostas: -)

Você está dinamicamente tentando descobrir o que funciona para executar em tempo de execução (que é o que funções virtuais são). Se você tem um vetor (whoses membros não pode ser determinado em tempo de compilação), então você não pode trabalhar para fora como para inline as funções não importa o que você tente.

A única caviat para isso é que, se os vetores contêm sempre os mesmos elementos (ou seja, você poderia trabalhar para fora um tempo de compilação o que vai ser executado em tempo de execução). Você poderia, então, re-trabalho este mas isso exigiria somthing diferente de um vector para segurar os elementos (provavelmente uma estrutura com todos os elementos como membros).

Além disso, você realmente acha que o envio virtual é um gargalo?
Pessoalmente, eu duvido muito.

Answer 4

O problema que você terá aqui é com WidgetCollection::widgets. Um vector pode conter apenas um tipo de itens, e usando o CRTP requer que cada AbstractWidget tem um tipo diferente, por templatized o tipo derivado desejado. Ou seja, você está AbstractWidget seria algo parecido com isto:

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

O que significa que cada AbstractWidget com um tipo diferente Derived constituiria um tipo AbstractWidget< Derived > diferente. Armazenar estes todos em um único vector não vai funcionar. Portanto, parece que, neste caso, as funções virtuais são o caminho a percorrer.

Answer 5

Não, se você precisa de um vector deles. Os contêineres STL são completamente homogênea, o que significa que se você precisa armazenar um widgetA e uma widgetB no mesmo recipiente, devem ser herdadas de um pai comum. E, se widgetA :: bar () faz algo diferente do que widgetB :: bar (), você tem que fazer as funções virtual.

Será que todos os widgets precisam estar no mesmo recipiente? Você poderia fazer algo assim

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

E, em seguida, as funções que não precisa ser virtual.

Answer 6

As probabilidades são de que, depois de passar por todo esse esforço, você não verá nenhuma diferença de desempenho.

Este é absolutamente o errado forma de otimizar. Você não iria corrigir um erro de lógica, alterando linhas aleatórias de código não é? Não, isso é bobagem. Você não codificam "solução" até encontrar primeira quais linhas são realmente causando o problema. Então, por que você iria tratar desempenho erros de forma diferente?

Você precisa o perfil de seu aplicativo e descubra quais são os gargalos reais. Em seguida, acelerar esse código e execute novamente o profiler. Repita até que o bug desempenho (execução muito lenta) está desaparecido.