Posso usare il modello di modello curiosamente ricorrente qui (C ++)?

Question

Ho un'applicazione C ++ che può essere semplificata in qualcosa del genere:

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

La mia applicazione è critica per le prestazioni. Di solito ci sono migliaia di widget nella raccolta. Le classi derivate da AbstractWidget (di cui ce ne sono dozzine) in genere lasciano molte funzioni virtuali non ignorate. Quelli che hanno la precedenza in genere hanno implementazioni molto veloci.

Detto questo, sento di poter ottimizzare il mio sistema con una metaprogrammazione intelligente. L'obiettivo è sfruttare la funzione inline ed evitare chiamate di funzione virtuali, mantenendo il codice gestibile. Ho esaminato il modello di modello curiosamente ricorrente (vedi qui per la descrizione). Questo sembra quasi fare quello che voglio, ma non del tutto.

C'è un modo per far funzionare il CRTP per me qui? Oppure, c'è qualche altra soluzione intelligente a cui qualcuno può pensare?

Answer 1

CRTP o polimorfismo in fase di compilazione è per quando conosci tutti i tuoi tipi in fase di compilazione. Finché si utilizza addWidget per raccogliere un elenco di widget in fase di esecuzione e fino a quando fooAll e barAll devono quindi gestire i membri di tale elenco omogeneo di widget in fase di esecuzione, è necessario essere in grado di gestire diversi tipi in fase di esecuzione. Quindi per il problema che hai presentato, penso che tu sia bloccato usando il polimorfismo di runtime.

Una risposta standard, ovviamente, è verificare che le prestazioni del polimorfismo di runtime siano un problema prima di provare ad evitarlo ...

Se hai davvero bisogno di evitare il polimorfismo di runtime, una delle seguenti soluzioni potrebbe funzionare.

Opzione 1: utilizza una raccolta di widget in fase di compilazione

Se i membri di WidgetCollection sono noti al momento della compilazione, è possibile utilizzare facilmente i modelli.

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

Opzione 2: sostituisci il polimorfismo di runtime con funzioni gratuite

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

Brutto e davvero non OO. I modelli potrebbero essere di aiuto in questo senso riducendo la necessità di elencare ogni caso speciale; prova qualcosa di simile al seguente (completamente non testato), ma in questo caso non sei tornato in linea.

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

Opzione 3: elimina OO

OO è utile perché aiuta a gestire la complessità e perché aiuta a mantenere la stabilità di fronte al cambiamento. Per le circostanze che sembri descrivere - migliaia di widget, il cui comportamento generalmente non cambia e i cui metodi membro sono molto semplici - potresti non avere molta complessità o modifiche da gestire. In tal caso, potrebbe non essere necessario OO.

Questa soluzione è la stessa del polimorfismo di runtime, tranne per il fatto che richiede di mantenere un elenco statico di " virtuale " metodi e sottoclassi note (che non sono OO) e consente di sostituire le chiamate di funzione virtuale con una tabella di salto con funzioni incorporate.

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

Il binding dinamico simulato (ci sono altri usi del CRTP) è quando la classe base si considera polimorfica, ma i client si preoccupano solo di un particolare derivato classe. Quindi, ad esempio, potresti avere classi che rappresentano un'interfaccia in alcune funzionalità specifiche della piattaforma e ogni piattaforma specifica avrà sempre bisogno di una sola implementazione. Il punto del modello è quello di modellare la classe base, in modo che anche se ci sono più classi derivate, la classe base conosce al momento della compilazione quale è in uso.

Non ti aiuta quando hai davvero bisogno del polimorfismo di runtime, come ad esempio quando hai un contenitore di AbstractWidget*, ogni elemento può essere una delle diverse classi derivate e devi iterare su di esse. In CRTP (o qualsiasi codice modello), base<derived1> e base<derived2> sono classi non correlate. Quindi anche derived1 e derived2. Non c'è polimorfismo dinamico tra loro a meno che non abbiano un'altra classe base comune, ma poi sei tornato da dove hai iniziato con le chiamate virtuali.

Potresti ottenere un po 'di velocità sostituendo il tuo vettore con diversi vettori: uno per ciascuna delle classi derivate che conosci e uno generico per quando aggiungi nuove classi derivate in seguito e non aggiorni il contenitore. Quindi addWidget esegue un controllo (lento) typeid o una chiamata virtuale al widget, per aggiungere il widget al contenitore corretto e forse presenta alcuni sovraccarichi per quando il chiamante conosce la classe di runtime. Fare attenzione a non aggiungere accidentalmente una sottoclasse di WidgetIKnowAbout al WidgetIKnowAbout* vettore. fooAll e barAll possono scorrere su ogni contenitore a sua volta effettuando chiamate (veloci) a funzioni fooImpl e barImpl non virtuali che verranno quindi incorporate. Quindi eseguono il ciclo sul vettore foo eventualmente molto più piccolo, chiamando le funzioni virtuali bar o <=>.

È un po 'disordinato e non puro-OO, ma se quasi tutti i tuoi widget appartengono a classi che il tuo contenitore conosce, allora potresti vedere un aumento delle prestazioni.

Tieni presente che se la maggior parte dei widget appartiene a classi che il tuo contenitore non è in grado di conoscere (perché si trovano in librerie diverse, ad esempio), allora non puoi avere allineamento (a meno che il tuo linker dinamico non possa essere in linea. Il mio può " t). È possibile eliminare l'overhead della chiamata virtuale scherzando con i puntatori della funzione membro, ma il guadagno sarebbe quasi sicuramente trascurabile o addirittura negativo. La maggior parte dell'overhead di una chiamata virtuale si trova nella chiamata stessa, non nella ricerca virtuale, e le chiamate tramite i puntatori a funzione non verranno incorporate.

Guardalo in un altro modo: se il codice deve essere integrato, significa che il codice macchina effettivo deve essere diverso per i diversi tipi. Ciò significa che sono necessari più loop o un loop con un interruttore al suo interno, poiché il codice macchina chiaramente non può cambiare nella ROM ad ogni passaggio attraverso il loop, in base al tipo di puntatore estratto da una raccolta.

Immagino che forse l'oggetto potrebbe contenere del codice asm che il loop copia nella RAM, contrassegna l'eseguibile e salta. Ma questa non è una funzione membro C ++. E non può essere fatto in modo portabile. E probabilmente non sarebbe nemmeno veloce, per quanto riguarda la copia e l'invalidazione di Icache. Ecco perché esistono chiamate virtuali ...

Answer 3

La risposta breve è no.

La risposta lunga (o ancora corta rispetto ad altre risposte :-)

Stai cercando in modo dinamico di capire quale funzione eseguire in fase di esecuzione (ovvero quali sono le funzioni virtuali). Se hai un vettore (i cui membri non possono essere determinati al momento della compilazione), non puoi capire come incorporare le funzioni indipendentemente da ciò che provi.

L'unica caviat a questo è che se i vettori contengono sempre gli stessi elementi (cioè potresti calcolare in tempo di compilazione cosa verrà eseguito in fase di esecuzione). Potresti quindi rielaborarlo, ma richiederebbe qualcosa di diverso da un vettore per contenere gli elementi (probabilmente una struttura con tutti gli elementi come membri).

Inoltre, pensi davvero che la spedizione virtuale sia un collo di bottiglia?
Personalmente ne dubito fortemente.

Answer 4

Il problema che avrai qui è con WidgetCollection::widgets. Un vettore può contenere solo elementi di un tipo e l'utilizzo del CRTP richiede che ogni AbstractWidget abbia un tipo diverso, modellato dal tipo derivato desiderato. Cioè, Derived sembreresti qualcosa del genere:

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

Il che significa che ogni AbstractWidget< Derived > con un diverso <=> tipo costituirebbe un diverso tipo <=>. Memorizzarli tutti in un singolo vettore non funzionerà. Quindi sembra che, in questo caso, le funzioni virtuali siano la strada da percorrere.

Answer 5

Non se ne hai bisogno di un vettore. I contenitori STL sono completamente omogenei, il che significa che se è necessario memorizzare un widgetA e un widgetB nello stesso contenitore, devono essere ereditati da un genitore comune. E, se widgetA :: bar () fa qualcosa di diverso da widgetB :: bar (), devi rendere virtuali le funzioni.

Tutti i widget devono trovarsi nello stesso contenitore? Potresti fare qualcosa del genere

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

E quindi le funzioni non dovrebbero essere virtuali.

Answer 6

Le probabilità sono che dopo aver fatto tutto questo sforzo, non vedrai alcuna differenza di prestazioni.

Questo è assolutamente il modo sbagliato per ottimizzare. Non correggeresti un bug logico modificando le righe casuali di codice, vero? No, è sciocco. Non & Quot; fix & Quot; codice fino a quando non trovi per la prima volta quali righe causano effettivamente il tuo problema. Quindi perché dovresti trattare gli performance in modo diverso?

Devi profilare la tua applicazione e trovare dove si trovano i veri colli di bottiglia. Quindi velocizza quel codice ed esegui nuovamente il profiler. Ripetere l'operazione fino a quando il bug di prestazione (esecuzione troppo lenta) non scompare.