Niedrige Leistung von unordered_map beim Zugriff auf Elemente in Member Template-Funktion in abgeleiteten Klasse

Question

Ich versuche, eine komponentenbasierte Architektur in einem Game-Engine-Projekt zu implementieren. Jedes GameObject hat einen unordered_map, der einen Zeiger auf die Basisklasse Component enthält. An diesem Punkt habe ich nur eine Komponente abgeleitet Klasse, die Transform Klasse ist. Ich wollte diese komponentenbasierte Architektur ähnlich der Unity-Konvention implementieren: Ich möchte eine Komponente des Spielobjekts erhalten, indem ich die Elementvorlagenfunktion wie GetComponent<Transform>() aufruft.

Hier sind die Header:

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

---

Meine anfängliche Implementierung verwendete std::vector für Component* zu halten und die Anwendung lief bei 60 fps (Ich habe auch einen Frame-Rate-Controller, der nur die FPS auf 60 begrenzt). Als ich zum Zugriff auf diese Komponentenzeiger auf unordered_map wechselte, ging die Leistung auf 15 FPS herunter.

Ich zeichne nur zwei Quads und ich rufe GetComponent<Transform>() nur 6-mal pro Rahmen an dieser Stelle, so ist es nicht viel in der Szene geht.

---

Was habe ich versucht?

Ich habe versucht, für die unordered_mapconst char*, std::string, type_info und schließlich enum type als Schlüsselwerte zu verwenden, aber nichts wirklich hilft: alle Implementierungen hat mich 15-16 FPS.

Was verursacht dieses Leistungsproblem? Wie kann ich das Problem isolieren?

_{Ich hoffe, dass ich genug Detail zur Verfügung gestellt, können Sie für mehr Code zu fragen, wenn nötig}

Answer 1

Haftungsausschluss: Während die unten angegebenen Informationen, unabhängig halten sollen, die erste grundlegende Plausibilitätsprüfung einen so drastischen Unterschied in der Leistung übergab Ein solcher einfacher Fall besteht darin, zuerst sicherzustellen, dass Build-Optimierungen aktiviert sind. Mit diesem aus dem Weg ...

unordered_map ist letztlich als ein ziemlich großen Container konzipiert, eine potenziell große Anzahl von Buckets Vorbelegung.

Siehe hier: std::unordered_map very high memory usage

Und hier: How does C++ STL unordered_map resolve collisions?

Während Berechnen einer Hash-Index trivial ist, die Größe des Speichers (und schreitet zwischen) für solche kleinen unordered_maps zugegriffen wird, könnte sehr leicht in ein Cachespeicher-fehlender Flaschenhals, auf den häufig zugegriffen wird, als wenn eine Komponentenschnittstelle aus einer Entität abgerufen wird.

Für Entity-Komponenten-Systeme haben Sie normalerweise nicht so viele Komponenten, die einer Entität zugeordnet sind - vielleicht so etwas wie Dutzende Tops und oft nur ein paar. Als Ergebnis ist std::vector tatsächlich eine viel geeignetere Struktur und in erster Linie in Bezug auf die Lokalität der Referenz (kleine Arrays, auf die oft wiederholt zugegriffen werden kann, wenn Sie eine Komponentenschnittstelle aus einer Entität holen). Während ein geringerer Punkt, std::vector::operator[] ist auch eine Funktion, die trivial-inline ist.

Wenn Sie noch besser als std::vector hier tun wollen (aber ich empfehle diese erst nach Profilierung und Bestimmen Sie es brauchen), vorausgesetzt, dass Sie einigen gemeinsamen Fall ableiten können obere Schranke, N, für die Anzahl der Komponenten, die typischerweise in ein Unternehmen, so etwas wie dies vielleicht sogar besser funktionieren:

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

starten, indem sie ptr auf components und greifen sie anschließend durch ptr ab. Das Einfügen einer neuen Komponente erhöht sich um num. Wenn num >= 4 (seltener Fall), ändern Sie ptr, um auf einen dynamisch zugewiesenen Block mit einer größeren Größe zu zeigen. Wenn Sie ComponentList löschen, geben Sie den dynamisch zugewiesenen Speicher frei, wenn ptr != components. Dies verschwendet ein wenig Speicher, wenn Sie weniger als N Elemente speichern (obwohl std::vector dies auch typischerweise mit einer Anfangskapazität und der Art, wie es wächst), aber es verwandelt Ihre Entität und die Komponentenliste in eine vollständig zusammenhängende Struktur, es sei denn num > N. Als Ergebnis erhalten Sie die beste Lokalität der Referenz und potenziell sogar bessere Ergebnisse als das, womit Sie begonnen haben (ich nehme an, dass die Frameraten erheblich häufiger aus Loops geholt wurden, was nicht ungewöhnlich ist) in ECS).

Angesichts wie häufig Komponenten-Schnittstellen von einer Entität zugegriffen werden können, und sehr oft in sehr engen Schleifen, könnte dies die Mühe wert sein.

Nichtsdestotrotz war Ihre ursprüngliche Wahl std::vector tatsächlich eine bessere angesichts der typischen Skala der Daten (Anzahl der verfügbaren Komponenten in einer Entität). Mit sehr kleinen Datensätzen übertreffen die grundlegenden sequenziellen Suchvorgänge in der linearen Zeit häufig komplexere Datenstrukturen, und Sie möchten sich stattdessen häufig viel mehr auf die Speicher-/Cache-Effizienz konzentrieren.

Ich habe versucht, const char *, std :: string, type_info und schließlich Typ als Schlüsselwerte für die unordered_map der ENUM zu nutzen, aber nichts wirklich hilft: alle Implementierungen hat mich 15-16 FPS.

Nur auf diesen Hinweis, für Schlüssel wollen Sie etwas, das in konstanter Zeit wie ein integraler Wert verglichen werden kann.Eine Möglichkeit, die in diesem Fall nützlich sein könnte, ist eine interne Zeichenkette, die nur ein int für ein Gleichgewicht zwischen Bequemlichkeit und Leistung speichert (Clients können sie durch eine string konstruieren aber vergleichen sie durch eine int während der Komponentensuche).