Basso rendimento da unordered_map quando si accede agli elementi nella funzione modello membro nella classe derivata

Question

Sto provando ad implementare un'architettura basata su componenti in un progetto di motore di gioco. Ogni GameObject ha uno unordered_map che contiene un puntatore alla classe base Component. A questo punto, ho solo una classe derivata da un componente, che è la classe Transform. Volevo implementare questa architettura basata su componenti simile alla convenzione di Unity: voglio ottenere un componente dell'oggetto di gioco chiamando la funzione template membro come GetComponent<Transform>().

Ecco le intestazioni:

Component.h

enum type{ 
    TRANSFORM // more will be added later 
}; 

class Component // base class 
{ 
public: 
    Component() : _owner(NULL) {} 
    virtual ~Component(){} 
    static type Type; 

protected: 
    GameObject* _owner; 
}; 

Transform.h

class Transform : public Component 
{ 
public: 
    Transform(); 
    ~Transform(); 
    static type Type; 

    void Rotate(float deg); 

    // to be encapsulated later on 
    Vector2D _position; 
    float _rotation; 
    Vector2D _scale; 
}; 

GameObject.h

class GameObject 
{ 
public: 
    GameObject(); 
    ~GameObject(); 

    void Update(); 
    //and more member functions 

    template<class T> 
    T* GetComponent(); 
private: 
    // some more private members 
    unordered_map<type, Component*> _componentList; // only 1 component of each type 
}; 

template<class T> 
T* GameObject::GetComponent() 
{  
    return static_cast<T*>(_componentList[T::Type]); 
} 

---

mio implementazione iniziale utilizzato std::vector per mantenere Component* e l'applicazione corse a 60 fps (ho anche un controllore frame rate, che limita solo la FPS a 60). Quando sono passato a unordered_map per accedere a quei puntatori di componenti, le prestazioni sono ridotte a 15 FPS.

I disegnare solo due quad e invito GetComponent<Transform>() solo 6 volte al telaio a questo punto, quindi non v'è molto movimento nella scena.

---

Cosa ho provato?

Ho cercato di usare const char*, std::string, type_info e infine enum type come valori fondamentali per il unordered_map ma niente aiuta davvero: tutte le implementazioni mi ha fatto 15-16 FPS.

Quali sono le cause di questo problema di prestazioni? Come posso isolare il problema?

_{spero che ho fornito sufficienti dettagli, non esitate a chiedere di più il codice, se necessario}

Answer 1

di responsabilità: mentre le informazioni qui di seguito dovrebbe tenere a prescindere, il primo test di integrità di base, dato una differenza così drastica delle prestazioni rispetto un caso così semplice è innanzitutto assicurarsi che le ottimizzazioni di build siano attive. Con quello fuori mano ...

unordered_map è progettato in definitiva come un contenitore abbastanza grande, preallocazione di un numero potenzialmente elevato di benne.

vedere qui: std::unordered_map very high memory usage

E qui: How does C++ STL unordered_map resolve collisions?

Mentre il calcolo di un indice di hash è banale, la quantità di memoria (e passi tra) a cui si accede per tale piccolo unordered_maps potrebbe facilmente trasformarsi in un collo di bottiglia mancante della cache con qualcosa a cui si accede frequentemente come il recupero di un'interfaccia componente da un'entità.

Per i sistemi di componenti di entità, in genere non si hanno molti componenti associati a un'entità, forse qualcosa come decine di piani superiori, e spesso solo alcuni. Di conseguenza, std::vector è in realtà una struttura molto più adatta e principalmente in termini di località di riferimento (piccoli array a cui è spesso possibile accedere ripetutamente ogni volta che si recupera un'interfaccia di un componente da un'entità). Mentre un punto minore, std::vector::operator[] è anche una funzione che è banalmente in-linea.

Se si desidera fare ancora meglio di std::vector qui (ma lo raccomando solo dopo averlo profilato e aver determinato che ne avete bisogno), a condizione che sia possibile dedurre un limite superiore del caso comune, N, per il numero di componenti tipicamente disponibili in un'entità, una cosa del genere può funzionare ancora meglio:

struct ComponentList 
{ 
    Component* components[N]; 
    Component** ptr; 
    int num; 
}; 

Iniziate impostando ptr per components e accedervi in ​​seguito attraverso ptr. L'inserimento di un nuovo componente aumenta num. Quando num >= 4 (raro caso), modificare ptr in modo che punti a un blocco assegnato dinamicamente con una dimensione maggiore. Quando si distrugge ComponentList, liberare la memoria allocata dinamicamente se ptr != components. Questo spreca un po 'di memoria se stai immagazzinando meno di N elementi (anche se lo std::vector lo fa anche con una capacità iniziale e il modo in cui cresce), ma trasforma la tua entità e l'elenco dei componenti forniti in una struttura completamente contigua a meno che non sia num > N. Di conseguenza, ottieni la migliore localizzazione di riferimento e risultati potenzialmente migliori rispetto a quello che hai iniziato (sto assumendo dal significativo calo dei frame rate che stavi recuperando i componenti da entità piuttosto frequentemente da loop che non è raro in ECS).

Data la frequenza con cui è possibile accedere alle interfacce dei componenti da un'entità e molto spesso in cicli molto stretti, ciò potrebbe valerne la pena.

Tuttavia, la scelta originale di std::vector in realtà era migliore rispetto alla scala tipica dei dati (numero di componenti disponibili in un'entità). Con insiemi di dati molto piccoli, le ricerche sequenziali di base in tempo lineare spesso sovraperformano strutture di dati più sofisticate e spesso si desidera concentrarsi maggiormente sull'efficienza della memoria/cache.

Ho cercato di usare const char *, std :: string, type_info e, infine, enum tipo come valori chiave per l'unordered_map ma niente aiuta davvero: tutte le implementazioni mi ha fatto 15-16 FPS.

Proprio su questa nota, per le chiavi si desidera qualcosa che può essere confrontato in un tempo costante come un valore integrale.Una possibilità che potrebbe essere utile in questo caso è una stringa interna che memorizza semplicemente un int per un equilibrio tra convenienza e prestazioni (consentendo ai clienti di costruirli tramite un string ma confrontarli tramite un componente int durante le ricerche del componente).