[C++] Template-Argument als Bedingung

[Goderion]

Hallo.

Ich möchte aufgrund von einem Template-Argument eine bestimmte Funktionalität erreichen.
Ich habe mal schnell etwas programmiert, um die eigentliche Problematik aufzuzeigen.

Code: Alles auswählen

enum EnumComponentType
{
	ComponentTypeNone,
	ComponentTypeStats,
	ComponentTypeWeapon,
	ComponentTypeArmor
};


class ClassComponent
{
public:
	ClassComponent(EnumComponentType ComponentType) : m_ComponentType(ComponentType) {}

	EnumComponentType GetComponentType(void) const
	{
		return m_ComponentType;
	}

private:
	EnumComponentType m_ComponentType;
};

class ClassComponentStats :
	public ClassComponent
{
public:
	ClassComponentStats(void) : ClassComponent(GetStaticComponentType()) {}

	static EnumComponentType GetStaticComponentType(void)
	{
		return ComponentTypeStats;
	}
};

class ClassComponentWeapon :
	public ClassComponent
{
public:
	ClassComponentWeapon(void) : ClassComponent(GetStaticComponentType()) {}

	static EnumComponentType GetStaticComponentType(void)
	{
		return ComponentTypeWeapon;
	}
};

class ClassComponentArmor :
	public ClassComponent
{
public:
	ClassComponentArmor(void) : ClassComponent(GetStaticComponentType()) {}

	static EnumComponentType GetStaticComponentType(void)
	{
		return ComponentTypeArmor;
	}
};

class ClassComponentArray
{
public:
	ClassComponentArray(void)
	{
		m_ppComponentArray[0] = new ClassComponentStats;
		m_ppComponentArray[1] = new ClassComponentWeapon;
		m_ppComponentArray[2] = new ClassComponentArmor;
	}

	~ClassComponentArray(void)
	{
		// delete ...
	}

	ClassComponentStats* FindComponentStats(void)
	{
		//return FindComponent_V1<ClassComponentStats>(ComponentTypeStats);
		return FindComponent_V3<ClassComponentStats>();
	}

	ClassComponent* FindComponent(EnumComponentType ComponentType)
	{
		for (int i = 0; i < 3; ++i)
		{
			if (m_ppComponentArray[i]->GetComponentType() == ComponentType)
			{
				return m_ppComponentArray[i];
			}
		}

		return nullptr;
	}

	template <class ComponentClassType> ComponentClassType* FindComponent_V1(EnumComponentType ComponentType)
	{
		return static_cast<ComponentClassType*>(FindComponent(ComponentType));
	}

	template <class ComponentClassType> ComponentClassType* FindComponent_V2(void)
	{
		// super lahm, hash scheint immer wieder neu generiert zu werden.

		size_t TypeHash = typeid(ComponentClassType).hash_code();

		if (typeid(ClassComponentStats).hash_code() == TypeHash)
		{
			return FindComponent_V1<ComponentClassType>(ComponentTypeStats);
		}
		else if (typeid(ClassComponentWeapon).hash_code() == TypeHash)
		{
			return FindComponent_V1<ComponentClassType>(ComponentTypeWeapon);
		}
		else if (typeid(ClassComponentArmor).hash_code() == TypeHash)
		{
			return FindComponent_V1<ComponentClassType>(ComponentTypeArmor);
		}

		return nullptr;
	}

	template <class ComponentClassType> ComponentClassType* FindComponent_V3(void)
	{
		// schnell, aber jeder Klasse benötigt für die Identifikation eine static function.

		return FindComponent_V1<ComponentClassType>(ComponentClassType::GetStaticComponentType());
	}

	void Test(void)
	{
		ClassComponentStats* pStats = FindComponentStats();
		ClassComponentArmor* pArmor = FindComponent_V3<ClassComponentArmor>();
		ClassComponentWeapon* pWeapon = FindComponent_V3<ClassComponentWeapon>();
	}

private:
	ClassComponent* m_ppComponentArray[3];
};

Ich hoffe man erkennt aufgrund vom Quellcode worum es geht.
Ich möchte rein durch die Angabe vom Template-Argument die richtige Klassen-Instanz zurückbekommen.
Die Funktionen FindComponent_V2 und FindComponent_V3 sind vom Aufruf/Parameter identisch, lösen das Problem aber auf unterschiedlicher Weise.
FindComponent_V3 gefällt mir bis jetzt am besten, nur die Notwendigkeit der statischen Funktion in jeder möglichen Klasse ist etwas "störend".

Gibt es einen besseren oder eleganteren Weg, dieses "Problem" zu lösen?

Ein wenig zum Hintergrund:
Es ist nicht möglich, die Architektur zu ändern. Es ist zwingend erforderlich, dass es eine Basisklasse gibt, im obigen Beispiel ClassComponent, und davon dann alle unterschiedlichen Arten von Komponenten erben, damit es eine Liste/Array geben kann, wo alle Komponenten zu finden sind. Ich habe lange rum experimentiert/recherchiert und mir fällt keine bessere Lösung für ein flexibles Objekt-Design ein. Mit dieser Architektur kann ich z.B. einem Tisch problemlos eine Container-Definition geben, oder einem Stuhl eine Waffen-Definition, oder jedem beliebigen Objekt eine Licht-Definition. (Es gibt keine Objektarten wie Tisch oder Stuhl, die Objekte definieren sich ausschließlich durch ihre Komponenten.)

[Helmut]

Ich bin immer ein Fan von einfachen Lösungen. Das hieße in deinem Fall, dass du in deiner Arrayklasse eine map/hashmap hast, die von enum auf Komponenteninstanz mappt. Und deiner GetComponent Methode übergibst du das entsprechende enum und bekommst die Instanz zurück. (Der Aufrufer castet dann).
Diese Variante benötigt keine Templates und keine lineare Suche und ist zudem sehr einfach. Wenn dich der Cast stört, könntest du über ein entsprechendes Makro nachdenken.

[Goderion]

Vielen Dank für die Hinweise!

Ich bin immer ein Fan von einfachen Lösungen.

Ich versuche die Sachen auch immer so simpel wie möglich zu gestalten, aber manchmal benötigt man Module/Klassen/Funktionen für viele verschiedene komplexe "Mechaniken", die einfach nicht mehr einfach sind. ;-)

Das hieße in deinem Fall, dass du in deiner Arrayklasse eine map/hashmap hast, die von enum auf Komponenteninstanz mappt.

Es geht hier um über 200.000 Objekte, die in der Regel über 2 Listen/Arrays verfügen, wo in jedem Fall (Liste/Array) die beschriebene Problematik auftritt. Das würde über 400.000 maps/hashmaps bedeutet, was meiner Meinung nach totaler Overkill ist. In den Listen/Arrays befinden sich auch meist nur wenige Objekte/Einträge.

Dazu kommt noch, dass ein Teil meiner Problematik bestehen bleibt, denn so müsste ich beim Hinzufügen einer Komponente zur Liste auch immer den Typ/Enum angeben, bzw. muss dieser irgendwie verfügbar sein.

Und deiner GetComponent Methode übergibst du das entsprechende enum und bekommst die Instanz zurück. (Der Aufrufer castet dann).

So ungefähr hatte ich es vorher, statt map/hashmap aber eine Liste/Array und jede Komponente kannte aufgrund einer Variable ihren Typ.

Diese Variante benötigt keine Templates und keine lineare Suche und ist zudem sehr einfach.

Die lineare Suche ist aufgrund der geringen Anzahl der Elemente (unter 10) in den Listen/Arrays eigentlich kein Problem.

Templates finde ich auch eigentlich Mist, aber ohne die, müsste ich zig Sachen mehrmals programmieren. Das Debuggen von Templates finde ich auch Käse. Warum erzeugt er zum Debuggen nicht die nötigen Quellcodes?! Das Kompilieren und Debuggen kommt mir auch immer langsamer vor, je mehr Templates ich nutze.


Ich bin ein Fan von langen Symbolen und daher habe ich viele Klassen, die z.B. so heißen: ClassEngineObjektDefinitionArmor2.

Meine ursprünglichen Version sah das so aus:

Code: Alles auswählen

ClassEngineObjektDefinitionArmor2* pDefinitionArmor = static_cast<ClassEngineObjektDefinitionArmor2*>(DefinitionList->FindDefinition(EngineObjektDefinitionTypeArmor));

Meine aktuelle Version sieht so aus:

Code: Alles auswählen

ClassEngineObjektDefinitionArmor2* pDefinitionArmor = DefinitionList->FindDefinition<ClassEngineObjektDefinitionArmor2>();

Die Wunsch-Version sieht so aus:

Code: Alles auswählen

ClassEngineObjektDefinitionArmor2* pDefinitionArmor = DefinitionList->FindDefinition();

Während ich nochmal über das Ganze nachgedacht und experimentiert habe, habe ich vielleicht einen Weg gefunden, die Wunsch-Version zu realisieren:

Code: Alles auswählen

enum EnumComponentType
{
	ComponentTypeNone,
	ComponentTypeStats,
	ComponentTypeWeapon,
	ComponentTypeArmor
};


class ClassComponent
{
public:
	ClassComponent(EnumComponentType ComponentType)
	{
		m_ComponentType = ComponentType;
	}

	EnumComponentType GetComponentType(void) const
	{
		return m_ComponentType;
	}

private:
	EnumComponentType m_ComponentType;
};


template <EnumComponentType ComponentType> class TemplateComponent :
	public ClassComponent
{
public:
	TemplateComponent(Void) : ClassComponent(ComponentType)
	{
	}

	static EnumComponentType GetComponentType(void)
	{
		return ComponentType;
	}
};


class ClassComponentStats : public TemplateComponent<ComponentTypeStats> {};
class ClassComponentWeapon : public TemplateComponent<ComponentTypeWeapon> {};
class ClassComponentArmor : public TemplateComponent<ComponentTypeArmor> {};


class ClassComponentArray;


class ClassComponentArrayCaster
{
public:
	template <class T> operator T*(Void)
	{
		return m_pArray->FindComponent<T>();
	}

	friend class ClassComponentArray;
private:
	ClassComponentArrayCaster(ClassComponentArray* pArray)
	{
		m_pArray = pArray;
	}

	ClassComponentArray* m_pArray;
};


class ClassComponentArray
{
public:
	ClassComponentArray(void)
	{
		m_ppComponentArray[0] = new ClassComponentStats;
		m_ppComponentArray[1] = new ClassComponentWeapon;
		m_ppComponentArray[2] = new ClassComponentArmor;
	}

	~ClassComponentArray(void)
	{
		delete (ClassComponentStats*)FindComponent();
		delete (ClassComponentWeapon*)FindComponent();
		delete (ClassComponentArmor*)FindComponent();
	}

	template <class T> operator T* (Void)
	{
		return FindComponent<T>();
	}

	ClassComponentArrayCaster FindComponent(Void)
	{
		return ClassComponentArrayCaster(this);
	}

	void Test(void)
	{
		ClassComponentArmor* pStats = FindComponent();
		ClassComponentArmor* pArmor = FindComponent();
		ClassComponentWeapon* pWeapon = FindComponent();
	}

	friend class ClassComponentArrayCaster;
private:
	template <class ComponentClassType> ComponentClassType* FindComponent(void)
	{
		return FindComponent<ComponentClassType>(ComponentClassType::GetComponentType());
	}

	template <class ComponentClassType> ComponentClassType* FindComponent(EnumComponentType ComponentType)
	{
		return static_cast<ComponentClassType*>(FindComponent(ComponentType));
	}

	ClassComponent* FindComponent(EnumComponentType ComponentType)
	{
		for (int i = 0; i < 3; ++i)
		{
			if (m_ppComponentArray[i]->GetComponentType() == ComponentType)
			{
				return m_ppComponentArray[i];
			}
		}

		return Null;
	}

	ClassComponent* m_ppComponentArray[3];
};

Das sieht zwar irgendwie cheesy aus, aber es funktioniert überraschend gut. Die static Funktion, die ich mit dieser Variante leider weiterhin brauche, konnte ich ähnlich wie hier in ein Template mit rein packen, welches in der Engine eh schon existiert.

Die Klasse ClassComponentArrayCaster ist eigentlich überflüssig, bzw. erzeugt sogar sinnlosen overhead, aber ich will den operator T* nicht direkt in der Liste haben. In der Release-Version erkennt der Compiler zum Glück diese Sinnlosigkeit und optimiert sie komplett weg, als würde ich den operator T* direkt in der Liste aufrufen, bzw. geht gleich zu FindComponent<T>.

Fehler sollten damit eigentlich auch keine möglich sein. Sobald ich X = FindComponent() mache, wo X nicht die Funktion GetComponentType hat, gibt bereits der Compiler einen Fehler raus.

Na mal sehen, wie weit ich damit komme.

[dot]

Rein prinzipiell: Du hast deine Components in einem Array. Du hast einen Enum der die einzelnen Components kennzeichnet. Du willst aus dem Array die entsprechende Component bekommen, wieso nicht einfach deinen enum Wert als Array Index nehmen und fertig?

Abgesehen davon kommen mit bei deinem Code aber schon ein paar Fragen auf: Wieso ein Array von Pointern und dann aber immer fix die selben Components im C'tor per new anlegen und im D'tor deleten!? Können die einzelnen Components dann nicht einfach auch direkt Member sein!? Wieso musst du generell eigentlich ausgerechnet per enum auf die einzelnen Components zugreifen?

[Goderion]

Vielen Dank für die Antwort!

Rein prinzipiell: Du hast deine Components in einem Array. Du hast einen Enum der die einzelnen Components kennzeichnet.

Der hier von mir gezeigte Quellcode ist nur ein Test und dient ausschließlich zur Darstellung meines eigentlichen Problems.

Du willst aus dem Array die entsprechende Component bekommen, wieso nicht einfach deinen enum Wert als Array Index nehmen und fertig?

Aktuell gibt es 33 verschiedene Komponenten. Ein Array müsste immer 33 Einheiten groß sein, obwohl es in den meisten Fällen nur 3 bis 5 Komponenten hat.

Abgesehen davon kommen mit bei deinem Code aber schon ein paar Fragen auf: Wieso ein Array von Pointern und dann aber immer fix die selben Components im C'tor per new anlegen und im D'tor deleten!? Können die einzelnen Components dann nicht einfach auch direkt Member sein!?

Das habe ich nur zum Testen so aufgebaut. Im eigentlichen Programm sind es meist Listen, welche je nach Bedarf/Objekt mit Komponenten befüllt werden.

Wieso musst du generell eigentlich ausgerechnet per enum auf die einzelnen Components zugreifen?

Die Frage verstehe ich nicht ganz. Wie soll ich denn sonst ein Element in einer Liste/Array identifizieren?

Meine Engine basiert teilweise auf dem ECS-Konzept (Entity–component–system), daher diese Architektur.
https://en.wikipedia.org/wiki/Entity%E2 ... 0%93system

[xq]

Mal ganz blöd gefragt: Kommt sowas hier in Frage?

Code: Alles auswählen

class Entity
{
	std::vector<Component*> components;
public:
	template<typename T>
	T * GetComponent()
	{
		for(auto it : components)
		{
			auto * res = dynamic_cast<T*>(it);
			if(res)
				return res;
		}
		return nullptr;
	}
};

Oder möchtest du unbedingt O(1)-Zugriffszeiten?

[Goderion]

Vielen Dank für die Antwort.

Mal ganz blöd gefragt: Kommt sowas hier in Frage?

Es gibt keine blöden Fragen, nur blöde Antworten. ;-)

Die Idee finde ich eigentlich sehr gut, aber...

std::vector ist wohl furchtbar langsam.
Die Komponenten verfügen selber bereits über die nötigen Variablen (Prev/Next in der Basisklasse definiert), um in der Komponenten-Liste aufgenommen zu werden. Das Hinzufügen oder Entfernen benötigt daher keine weiteren Aktionen, Allocationen etc., nur die Variablen(Next/Prev) müssen gesetzt werden, was das Ganze sehr schnell macht.
Das Laden von Leveldaten dauert mit dem std::vector im Vergleich dazu gefühlt Ewigkeiten. Beim schnellen Debuggen meine ich sogar etwas von einer CriticalSection gesehen zu haben, was der totale Overkill wäre.

Noch viel schlimmer scheint es allerdings zu sein, dass ein dynamic_cast extrem langsam ist. Beim Testen messe ich folgende Zeiten:
dynamic_cast-Suche: 3469 ms
VariablenVergleich-Suche: 78 ms

Die Idee ist trotzdem interessant und vielleicht finde ich andere Stellen in meinem Programm, wo z.B. die Performance nicht so im Vordergrund steht, wo ich diese "Technik" einsetzen kann. Zum Prototypen ist das sicher auch sehr nützlich.

Oder möchtest du unbedingt O(1)-Zugriffszeiten?

Bei meiner alten und neuen Variante habe ich auch O(n)-Zugriffszeiten, was aber aufgrund der geringen Elementanzahl pro Liste kaum eine Rolle spielt. Ich vermute, dass sich eine O(1)-Technik oder Index(hashmap, binärbaum(rb/avl), usw.) erst ab 10 Elementen oder mehr lohnt.

[Chromanoid]

Du könntest pro Entity ein Bitset speichern, das angibt, welche Komponenten ein Entity besitzt. Du könntest dann eine zweidimensionale Struktur pflegen, die "Component-Type-ID" und "Component-Data-Index" verknüpft. Dann hast Du nur in dem Fall O(N), wenn das Entity die Komponente auch wirklich benutzt.

Component-Data-Index deswegen, weil Du vielleicht besser diesen Ansatz verfolgen willst, um die Daten der Komponenten pro Entity zu pflegen (Pointer geht natürlich auch, aber vielleicht will man die Indirektion absichtlich haben):

In other ECS architectures, every component type are stored in separate lists, so whatever systems operate on those type of components are only iterating over objects they care about by default. In this common ECS architecture, the described disadvantage actually becomes a major performance advantage, by more efficiently leveraging the CPU instruction and data caches.

Ich weiß nicht, wie das bei CPP ist, aber wenn Du wirklich ein dynamisches ECS-Framework entwickeln willst, solltest Du auf Enums und so verzichten und stattdessen eine Komponenten-Registry einführen, die "Component-Typ-IDs" dynamisch vergibt. Ansonsten musst Du an zentraler Stelle Code ändern, um neue Komponenten hinzuzufügen.

Edit: Ansonsten wäre ich übrigens wie Helmut für eine Hash-Map pro Entity. Das mag zwar mehr Speicher fressen, ist aber sehr flexibel und schön performant.
Noch ein edit: Eine Matrix aus allen Komponenten und allen Entities ist vielleicht auch nicht schlecht. So teuer ist das auch nicht, insbesondere wenn Du pro Zelle nur einen 24bit-Index speicherst, der auf die eigentliche Datenhaltung in den Komponenten verweist.

[xq]

dynamic_cast-Suche: 3469 ms
VariablenVergleich-Suche: 78 ms

Aua, dachte nicht, dass dynamic_cast SO lahm ist. Compiler-Optimierung ist auch sicher angeschaltet?

[Goderion]

Vielen Dank für die Antworten!

Du könntest pro Entity ein Bitset speichern, das angibt, welche Komponenten ein Entity besitzt. Du könntest dann eine zweidimensionale Struktur pflegen, die "Component-Type-ID" und "Component-Data-Index" verknüpft. Dann hast Du nur in dem Fall O(N), wenn das Entity die Komponente auch wirklich benutzt.

An so etwas ähnliches hatte ich auch schon gedacht, aber wenn ich das richtig verstanden habe, wie Du das meinst, muss das Bitset mindestens so viele Bits haben, wie es Komponenten gibt. Bei aktuell 33 Komponenten also eine 64 Bit Variable. Ich fürchte aber, dass ich über 64 Komponenten kommen werde, was die Sache dann verkompliziert. Ich hatte mir da überlegt, dass ich nur den 32 meist genutzten Komponenten so ein Such-Flag gebe und bei allen anderen Komponenten muss ich immer die Liste durchgehen.

Component-Data-Index deswegen, weil Du vielleicht besser diesen Ansatz verfolgen willst, um die Daten der Komponenten pro Entity zu pflegen (Pointer geht natürlich auch, aber vielleicht will man die Indirektion absichtlich haben):

In other ECS architectures, every component type are stored in separate lists, so whatever systems operate on those type of components are only iterating over objects they care about by default. In this common ECS architecture, the described disadvantage actually becomes a major performance advantage, by more efficiently leveraging the CPU instruction and data caches.

Die Verarbeitung der Objekte/Entities erfolgt über spezielle Strukturen. Solche Komponenten, wie z.B. für die KI, werden gesondert bei einem "Verarbeiter" registriert und dort behandelt. Im Prinzip hat der "Verarbeiter" auch nur eine Liste aller aktiven KI und geht diese pro Zyklus durch.

Ich weiß nicht, wie das bei CPP ist, aber wenn Du wirklich ein dynamisches ECS-Framework entwickeln willst, solltest Du auf Enums und so verzichten und stattdessen eine Komponenten-Registry einführen, die "Component-Typ-IDs" dynamisch vergibt. Ansonsten musst Du an zentraler Stelle Code ändern, um neue Komponenten hinzuzufügen.

So eine Dynamik wäre natürlich schön, aber das bringt auch andere Probleme mit sich. In meiner aktuellen Variante benötigt jede Komponente eine statische/static Funktion, die eine eindeutige Nummer zur Identifizierung der Komponentenart zurückgibt. Diese Nummer/Id muss ich aktuell leider zentral per Enum pflegen. Ohne diese satische Funktion, kann ich folgendes nicht mehr machen, bzw. weiß nicht wie:

Code: Alles auswählen

ClassComponentContainer* pContainer = pComponentList->Find();
ClassComponentLock* pLock = pComponentList->Find();

Ich muss darüber mehr nachdenken, wobei ich dieses eine zentrale Enum nicht so schlimm finde. Das Projekt muss ich so oder so oft komplett neu kompilieren, mehr Zeit für Youtube-Videos! ;-)

Edit: Ansonsten wäre ich übrigens wie Helmut für eine Hash-Map pro Entity. Das mag zwar mehr Speicher fressen, ist aber sehr flexibel und schön performant.

Ich habe das mal getestet anhand von einer Liste mit 5 Einträgen.
Listen-Suche: 312 ms
std::unordered_map: 734 ms

Bei std::hash_map meckert mein Compiler und verweist auf die std::unordered_map. Das Ergebnis überrascht mich jetzt aber, ich habe nur die Suche getestet, nicht das Hinzufügen. Muss ich bei der std::unordered_map noch was anderes machen? Die Elemente habe ich einfach per operator [] hinzugefügt und dann in der Suche find(X).

Code: Alles auswählen

std::unordered_map<keytype, valuetype> um;
um[1] = pC1;
um[2] = pC2;
...
pC1 = um.find(1);

STL zu debuggen ist immer die absolute Krätze! Für jeden Furz werden 1000 Codezeilen ausgeführt... Template-Hölle :?

Noch ein edit: Eine Matrix aus allen Komponenten und allen Entities ist vielleicht auch nicht schlecht. So teuer ist das auch nicht, insbesondere wenn Du pro Zelle nur einen 24bit-Index speicherst, der auf die eigentliche Datenhaltung in den Komponenten verweist.

Ich verstehe nicht genau, wie Du das meinst, bzw. fallen mir mehrere Konzepte ein, die zu deiner Matrix passen würden. Kannst Du das bitte genauer erläutern, bzw. ein Link, wo das genauer erklärt wird?

Aua, dachte nicht, dass dynamic_cast SO lahm ist.

Finde ich auch verdächtig komisch. Ich habe noch ein wenig rum experimentiert, kann die Zeit per dynamic_cast aber nicht reduzieren. Ich dachte, dass dies über die VTables geregelt wird, also sollte das eigentlich nicht so langsam sein.

Compiler-Optimierung ist auch sicher angeschaltet?

Ich habe in VS 2015 ein komplett neues Projekt erstellt (Win32-Konsolenanwendung) und die Zeit im Release-Modus gemessen.
Selbst wenn ich voll auf Codegeschwindigkeit optimieren lasse, wird es nicht schneller.

Vielleicht kann einer aufgrund folgender Assembler-Auszüge erkennen, warum die dynamic_cast-Version so lahm ist.

Listen-Suche:

Code: Alles auswählen

		ClassComponentArmor* pStats = FindComponent();
00281306  xor         edx,edx  
00281308  nop         dword ptr [eax+eax]  
00281310  mov         eax,dword ptr [ecx+edx*4]  
00281313  cmp         dword ptr [eax+4],3  
00281317  je          ClassComponentArray::TestDec+28h (0281328h)  
00281319  inc         edx  
0028131A  cmp         edx,5  
0028131D  jl          ClassComponentArray::TestDec+10h (0281310h)  
0028131F  mov         dword ptr [ebp-4],0  
00281326  jmp         ClassComponentArray::TestDec+2Bh (028132Bh)  
00281328  mov         dword ptr [ebp-4],eax  

dynamic_cast-Suche:

Code: Alles auswählen

		ClassComponentArmor* pStats = FindComponent();
00BE13BB  mov         esi,dword ptr [ebx+14h]  
00BE13BE  mov         edi,dword ptr [ebx+18h]  
00BE13C1  cmp         esi,edi  
00BE13C3  je          ClassComponentArray::TestDec+46h (0BE13F6h)  
00BE13C5  nop         word ptr [eax+eax]  
00BE13D0  push        0  
00BE13D2  push        offset ClassComponentArmor `RTTI Type Descriptor' (0BE617Ch)  
00BE13D7  push        offset ClassComponent `RTTI Type Descriptor' (0BE61A0h)  
00BE13DC  push        0  
00BE13DE  push        dword ptr [esi]  
00BE13E0  call        ___RTDynamicCast (0BE3094h)  
00BE13E5  add         esp,14h  
00BE13E8  mov         dword ptr [pStats],eax  
00BE13EB  test        eax,eax  
00BE13ED  jne         ClassComponentArray::TestDec+4Dh (0BE13FDh)  
00BE13EF  add         esi,4  
00BE13F2  cmp         esi,edi  
00BE13F4  jne         ClassComponentArray::TestDec+20h (0BE13D0h)  
00BE13F6  mov         dword ptr [pStats],0  

EDIT: Hier der Quellcode vom Testprogramm:

Win32Project4.cpp

(5.31 KiB) 309-mal heruntergeladen

[Chromanoid]

Zum Bitset: Ist die STD-Implementierung da so doof? http://en.cppreference.com/w/cpp/utility/bitset/bitset

Zu Map-Zugriff: Ich bin ja kein C++-Entwickler, aber die langen Zugriffszeiten bei der Map wundern mich ein bisschen. Gibt es einen Unterschied zwischen Zugriff über map.find und map[key]? Eigentlich sollte das ja eine Hashcode-Berechnung sein, dann ein Speicherzugriff und ggf. ein, zwei Vergleiche mit weiteren Speicherzugriffen.

Zur Matrix: ich meinte eine ziemlich billige Form der Implementierung, die mir so in den Sinn gekommen ist.
1. Ermittle die maximale Anzahl aller Komponenten.
2. Baue einen Array mit ANZAHL_ENTITIES*MAX_ANZAHL_KOMPONENTEN aus 24bit Ganzzahlen -> "Matrix".
3. Pro Komponente halte einen Array aus Stucts mit den komponmentenspezifischen Daten zu allen Entities, die diese Komponente nutzen. In der Struct befindet sich mindestens die Zeilennummer des Entity in der "Matrix". Pro Komponente führe weitere Datenstrukturen, um die Daten geschickt zu verwalten (Quadtree usw.). Komponenten recyclen ihre Entity-spezifischen Datenstrukturen.
4. Wenn ein neues Entitiy angelegt wird, reserviere eine Zeile in der "Matrix" und nutze den Index der Zeile zur Identifikation. Registriere das Entity bei allen gewünschten Komponenten und merke dir die Indizes zu jeder Komponente in der "Matrix" - der Rest der Zeile ist 2^24 oder was auch immer.

Zahlreiche Zugriffsmuster sind damit ziemlich optimal zu erledigen. Man kann in der Matrix und bei den Komponenten Chunking betreiben, um nicht von Anfang an Platz für die maximale Anzahl Entities machen zu müssen.

Edit: Nur zur Info :) wahrscheinlich ist es praktisch je Zeile statt einem simplen Array eine Struktur mit Kopfdaten vorzusehen. Je nach dem wie man recycled muss man natürlich schauen, ob man "zwischengespeicherte" Verweise auf Entities irgendwie extra verwalten muss. Vielleicht tut's bei Entitiy-Verweisen auch ne laufende Nummer, die neben dem Zeilenindex pro Entity gespeichert wird, damit man mitbekommt, dass das Entity, auf das man ursprünglich verwiesen hat, abgeräumt wurde.

[xq]

Gibt es einen Unterschied zwischen Zugriff über map.find und map[key]?

Jap, gibt es: map.find liefert einen Iterator zurück, welcher auch auf map.end zeigen kann (also: nicht element gefunden)
map[key] erzeugt im Falle einer nicht-existenz von key einen neuen eintrag mit key_t() als Wert, kann also im zweifel die komplette map umstrukturieren

[Krishty]

dynamic_cast-Suche: 3469 ms
VariablenVergleich-Suche: 78 ms

Aua, dachte nicht, dass dynamic_cast SO lahm ist. Compiler-Optimierung ist auch sicher angeschaltet?

dynamic_cast ist eine Suche durch verkettete Listen. Warum sollte sowas schnell sein?

Tut sowas nicht. Ich musste schon Programme warten, die 15 % ihrer Ausführungszeit in dynamic_cast verbracht haben.

- ambiguities (i.e multiple appearances of the same base in an object) need to produce a failure. That means that the entire class hierarchy must be traversed

- access control (conversion to private bases) needs to lead to failures. Therefore, private and protected inheritance must be available at run time as well.

[dot]

dynamic_cast ist lahm weil dynamic_cast lahm ist, daran lässt sich nix ändern. typeid() ist potentiell ein wenig schneller weil das nur den konkreten Typ returnen muss während dynamic_cast die Vererbungshierarchie traversiert...

Ich würde rein prinzipiell hier das Design hinterfragen; bei Anblick von dynamic_cast/typeid() sollten generell sofort immer erstmal die Alarmglocken läuten. Downcasts, egal in welcher Form, sind in der Regel Symptom eines grundlegenden Problems im Design. Ob du nun dynamic_cast, typeid oder irgendein selbst gebasteltes typeid (denn der Enum ist nix anderes) verwendest, spielt keine Rolle. Das grundlegende Problem ist, dass du Code hast, der nur ein abstraktes Interface kennt, der aber auf einmal wissen muss welche konkrete Implementierung hinter dem Interface steckt. So eine Situation zeigt in der Regel dass das Interface nicht zum Problem passt oder das Problem nicht zum Interface. Implementierungsabhängiges Verhalten sollte hinter einem Interface stecken und nicht davor, wofür bräuchte man sonst ein Interface!?

[Chromanoid]

@dot Meinst Du wirklich das Vermeiden von Downcasts bzw. die Nutzung von Typ-IDs, ist bei der Implementierung von völlig beliebigen Spielregeln eine sinnvolle Einschränkung? Hier ein Beispiel: Gib mir alle Entities in Bereich R (Abfrage an Physik-Komponente o.Ä.). Füge allen Entities mit einer Health-Komponente 10 Schadenspunkte zu. Alle Entities, die zusätzlich eine "Eiswesen"-Komponente haben, bekommen die Komponente "Vergiftet" aufgedrückt. Wenn schon die Komponente "Vergiftet" vorliegt, wird der Vergiftungsfaktor verdoppelt. Wenn das Entity eine "Charakter"-Komponente hat und ihr Name mit Z anfängt, gibt's 5 Extraschadenspunkte.

[Goderion]

Vielen Dank für die Antworten!

Zum Bitset: Ist die STD-Implementierung da so doof? http://en.cppreference.com/w/cpp/utility/bitset/bitset

Ich weiß nicht, wie Du das meinst. Wenn ich 64 Bit brauche, muss die Variable/Speicher ja mindestens 64 Bit abbilden können, also auch mindestens 64 Bit groß sein. Sollte man die Bits auf mehre Variablen verteilen, ist eine weitere Logik notwendig, um die richtige Variable zu ermitteln. Ich werde mir das std::bitset mal genauer angucken, wie das intern arbeitet. Danke für den Link.

Zu Map-Zugriff: Ich bin ja kein C++-Entwickler, aber die langen Zugriffszeiten bei der Map wundern mich ein bisschen. Gibt es einen Unterschied zwischen Zugriff über map.find und map[key]? Eigentlich sollte das ja eine Hashcode-Berechnung sein, dann ein Speicherzugriff und ggf. ein, zwei Vergleiche mit weiteren Speicherzugriffen.

Ich denke solche Techniken/Algorithmen lohnen sich wie gesagt erst bei einer bestimmten Anzahl von Elementen. Ich habe nochmal einen Test mit 20 Elementen gemacht, und selbst da ist die std::unordererd_map etwas langsamer, als eine lineare Suche in einem Array oder Liste.
Hier meine Messergebnisse mit 20 Elementen:
Array -> 2031 ms
Liste -> 2594 ms
dynamic_cast ->102890 ms
std::unordered_map -> 2907 ms

Win32Project4_V2.cpp

(7.69 KiB) 305-mal heruntergeladen

Zur Matrix: ich meinte eine ziemlich billige Form der Implementierung, die mir so in den Sinn gekommen ist.
1. Ermittle die maximale Anzahl aller Komponenten.
2. Baue einen Array mit ANZAHL_ENTITIES*MAX_ANZAHL_KOMPONENTEN aus 24bit Ganzzahlen -> "Matrix".
3. Pro Komponente halte einen Array aus Stucts mit den komponmentenspezifischen Daten zu allen Entities, die diese Komponente nutzen. In der Struct befindet sich mindestens die Zeilennummer des Entity in der "Matrix". Pro Komponente führe weitere Datenstrukturen, um die Daten geschickt zu verwalten (Quadtree usw.). Komponenten recyclen ihre Entity-spezifischen Datenstrukturen.
4. Wenn ein neues Entitiy angelegt wird, reserviere eine Zeile in der "Matrix" und nutze den Index der Zeile zur Identifikation. Registriere das Entity bei allen gewünschten Komponenten und merke dir die Indizes zu jeder Komponente in der "Matrix" - der Rest der Zeile ist 2^24 oder was auch immer.

Zahlreiche Zugriffsmuster sind damit ziemlich optimal zu erledigen. Man kann in der Matrix und bei den Komponenten Chunking betreiben, um nicht von Anfang an Platz für die maximale Anzahl Entities machen zu müssen.

Ok, ich glaube ich habe es verstanden. Wenn ich jetzt auf einer Karte 240.000 Objekte habe und es gibt 33 verschiedene Komponenten, dann habe ich ein zweidimensionales Array mit der Größe [240.000][33], oder anders ausgedrückt, eine 240.000 * 33 Matrix. Ein Objekt kennt seine Zeile in dieser Matrix und in jeder Spalte steht der Index der Komponente. Also Spalte 0 ist z.B. für die Armor-Komponente, Spalte 1 für die Weapon-Komponente, usw.. Wenn ich jetzt bei einem Objekt wissen möchte, ob und welche Armor-Komponente es hat, gucke ich in der Zeile, die dem Objekt zugewiesen ist, in die betreffende Spalte, bei Armor also Spalte 0. Also KomponenteIndex = Matrix[Objektzeile][KomponentenSpalte]; Da steht dann z.B. -1, für keine Armor, oder halt der Index/Position für die Armor im ArmorArray.

Welche Vorteile sehe ich da?
1. Eine Komponente muss nicht mehr gesucht werden, entweder sie existiert oder nicht.
2. Ein Downcast ist nicht mehr Notwendig.
3. Ich kann eine Komponte, bzw. das Array, durchgehen, ohne dass ich auf andere Daten achten muss. Also z.B. alle Licht-Komponenten.

Punkt 1 und 2 kann ich auch erreichen, wenn ich die Komponentenliste komplett ändere, bzw. gegen eine Struktur mit Pointern zu allen Komponentenarten ersetze. Oder die Zeile pro Matrix direkt im Objekt gespeichert wird. Durch solche Lösungen wird natürlich Punkt 3 nichtig.

Punkt 3 klingt zwar interessant, aber ich habe bisher keine Situation, wo ich das sinnvoll nutzen könnte. Alle Mechaniken/Systeme, die aufgrund von einer Komponente etwas machen, haben so oder so ihre eigenen zusätzlichen Strukturen.

Ich würde rein prinzipiell hier das Design hinterfragen; bei Anblick von dynamic_cast/typeid() sollten generell sofort immer erstmal die Alarmglocken läuten. Downcasts, egal in welcher Form, sind in der Regel Symptom eines grundlegenden Problems im Design. Ob du nun dynamic_cast, typeid oder irgendein selbst gebasteltes typeid (denn der Enum ist nix anderes) verwendest, spielt keine Rolle. Das grundlegende Problem ist, dass du Code hast, der nur ein abstraktes Interface kennt, der aber auf einmal wissen muss welche konkrete Implementierung hinter dem Interface steckt. So eine Situation zeigt in der Regel dass das Interface nicht zum Problem passt oder das Problem nicht zum Interface. Implementierungsabhängiges Verhalten sollte hinter einem Interface stecken und nicht davor, wofür bräuchte man sonst ein Interface!?

Die gute alte Downcast-Diskussion... ;-)
Die Frage ist, wie löse ich das anders? Die einfachste Lösung wäre, dass jedes Objekt einen Pointer oder Index zu jeder Komponente hat (geht in die Richtung der Matrix-Idee von Chromanoid). Ich rechne aber damit, das ich am Ende über 60 verschiedene Komponenten haben werde. Das bedeutet, jedes Objekt hat 60 Pointer/Indexwerte, von denen dann in der Regel 3 bis 5 genutzt werden, vielleicht auch mal 10, aber 50 werden meist total nutzlos leer sein. Ziemliche Speicherverschwendung aber best Performance und kein Downcast.... wahrscheinlich werde ich das, wenn das Prototypen der Komponenten abgeschlossen ist, mal ausprobieren.

@dot Meinst Du wirklich das Vermeiden von Downcasts bzw. die Nutzung von Typ-IDs, ist bei der Implementierung von völlig beliebigen Spielregeln eine sinnvolle Einschränkung? Hier ein Beispiel: Gib mir alle Entities in Bereich R (Abfrage an Physik-Komponente o.Ä.). Füge allen Entities mit einer Health-Komponente 10 Schadenspunkte zu. Alle Entities, die zusätzlich eine "Eiswesen"-Komponente haben, bekommen die Komponente "Vergiftet" aufgedrückt. Wenn schon die Komponente "Vergiftet" vorliegt, wird der Vergiftungsfaktor verdoppelt. Wenn das Entity eine "Charakter"-Komponente hat und ihr Name mit Z anfängt, gibt's 5 Extraschadenspunkte.

Schönes Beispiel, so ähnlich soll das am Ende ablaufen. :)

Nochmal Danke für die Antworten, über das Alles werde ich jetzt erstmal in Ruhe nachdenken.

[Goderion]

Gibt es eine Möglichkeit, folgenden Quellcode eleganter zu lösen?

Code: Alles auswählen

inline EnumValueType _GetValueType(const int* pValue) { return 1; }
inline EnumValueType _GetValueType(const bool* pValue) { return 2; }
inline EnumValueType _GetValueType(const float* pValue) { return 3; }
inline EnumValueType _GetValueType(const double* pValue) { return 4; }

template <class T> int GetValueType(const T& Value)
{
	return _GetValueType(&Value);
}

Anwendungsbeispiel:

Code: Alles auswählen

int Value;
int ValueType = GetValueType(Value); // ValueType = 1

[Schrompf]

Du willst den Typen eines Parameters in einem Enum umwandeln. Da das theoretisch zur Compile Time feststeht, könntest Du Type Traits aufziehen. Die sind allerdings nicht eleganter oder hübscher. Finde ich jedenfalls.

Code: Alles auswählen

template <typename T> struct ValueType { constexpr EnumValueType type = Invalid; };
template <> struct ValueType<int> { constexpr EnumValueType type = Integer; };

template <typename T> 
constexpr EnumValueType GetValueType(T) { return ValueType<T>::type; }

Oder Du machst Deine Funktionen constexpr und belässt es, wie es ist.

[dot]

1) das Undefined Behavior fixen indem du statt dem reservierten Namen _GetValueType etwas verwendest was erlaubt ist... ;)


Abgesehen davon dass ich selbstverständlich wieder das Design hinterfragen würde ( ;) ), könntest du hier einfach explizit spezialisieren:

Code: Alles auswählen

template <class T> int GetValueType(const T& Value) = delete;

template <> inline int GetValueType<int>(const int&)
{
        return 1;
}

template <> inline int GetValueType<bool>(const bool&)
{
        return 2;
}

template <> inline int GetValueType<float>(const float&)
{
        return 3;
}

template <> inline int GetValueType<double>(const double&)
{
        return 4;
}

[Goderion]

Vielen Dank für die Antworten!

Du willst den Typen eines Parameters in einem Enum umwandeln. Da das theoretisch zur Compile Time feststeht, könntest Du Type Traits aufziehen. Die sind allerdings nicht eleganter oder hübscher. Finde ich jedenfalls.

Bei mir (VS 2017) muss ich ein static vor constexpr setzten, sonst meckert er. (siehe unten V2)

Oder Du machst Deine Funktionen constexpr und belässt es, wie es ist.

Mmmmh.... (siehe unten V1)

1) das Undefined Behavior fixen indem du statt dem reservierten Namen _GetValueType etwas verwendest was erlaubt ist... ;)

_GetValueType ist reserviert? Im Link finde ich nix zu _GetValueType. Wie ist das gemeint?
Die _GetValueType-Funktionen bekommen aber so oder so noch einen anderen Namen, die sollen ja nicht direkt aufgerufen werden.

Abgesehen davon dass ich selbstverständlich wieder das Design hinterfragen würde ( ;) ), ...

:) Zum Generieren der Datenbanktabellen muss ich die Datentypen der Membervariablen bestimmen. Keine Ahnung wie ich das anders machen soll.

Code: Alles auswählen

// Alte Version
AddColumn(m_Variable, ValueTypeX);
// Neue Version
AddColumn(m_Variable);

... könntest du hier einfach explizit spezialisieren:

(siehe unten V3 und V4)

Ich habe jetzt 4 Versionen zur Auswahl:

Code: Alles auswählen

namespace GVT
{
	namespace V1
	{
		constexpr int _GetValueType(const int*) { return 1; }
		constexpr int _GetValueType(const bool*) { return 2; }
		constexpr int _GetValueType(const float*) { return 3; }
		constexpr int _GetValueType(const double*) { return 4; }

		template <class T> constexpr int GetValueType(const T& Value)
		{
			return _GetValueType(&Value);
		}
	}

	namespace V2
	{
		template <class T> struct ValueType { static constexpr int type = 0; };
		template <> struct ValueType<int> { static constexpr int type = 1; };
		template <> struct ValueType<bool> { static constexpr int type = 2; };
		template <> struct ValueType<float> { static constexpr int type = 3; };
		template <> struct ValueType<double> { static constexpr int type = 4; };

		template <class T> constexpr int GetValueType(const T&) { return ValueType<T>::type; }
	}

	namespace V3
	{
		template <class T> int GetValueType(const T&) = delete;

		template <> int GetValueType<int>(const int&) { return 1; }
		template <> int GetValueType<bool>(const bool&) { return 2; }
		template <> int GetValueType<float>(const float&) { return 3; }
		template <> int GetValueType<double>(const double&) { return 4; }
	}

	namespace V4
	{
		template <class T> constexpr int GetValueType(const T&) = delete;

		constexpr int GetValueType(const int&) { return 1; }
		constexpr int GetValueType(const bool&) { return 2; }
		constexpr int GetValueType(const float&) { return 3; }
		constexpr int GetValueType(const double&) { return 4; }
	}
}

V1: Übertrieben lange Fehlermeldung (alle Überladungen werden aufgezählt).
V2: Geht immer, egal was ich da übergebe. Sehe ich als Nachteil.
V3/V4: Gute Fehlermeldung und in der IDE wird der Funktionsaufruf rot unterstrichen.

Mein Favorit ist V4, wobei ich keine Ahnung habe, inwiefern sich V3 und V4 unterscheiden.

[dot]

1) das Undefined Behavior fixen indem du statt dem reservierten Namen _GetValueType etwas verwendest was erlaubt ist... ;)

_GetValueType ist reserviert? Im Link finde ich nix zu _GetValueType. Wie ist das gemeint?

Der Link führt zu der Stelle im C++ Standard, die besagt dass alle Identifier die doppelte Underscores enthalten oder mit einem Underscore gefolgt von einem Großbuchstaben beginnen reserviert sind. _GetValueType fällt in diese Kategorie. Ein Programm das ein Ding mit einem solchen Identifier als Namen deklariert hat streng genommen autom. Undefined Behavior.

Ich habe jetzt 4 Versionen zur Auswahl: [...]

Ich dachte irgendwie dass dein GetValueType() aus irgendeinem Grund ein Template sein muss. Ansonsten:

Code: Alles auswählen

namespace GVT
{
	namespace V5
	{
		constexpr int GetValueType(const int&) { return 1; }
		constexpr int GetValueType(const bool&) { return 2; }
		constexpr int GetValueType(const float&) { return 3; }
		constexpr int GetValueType(const double&) { return 4; }
	}
}

[Krishty]

V2: Geht immer, egal was ich da übergebe. Sehe ich als Nachteil.

Lass doch die Standard-Definition weg, dann gehen nur noch die Spezialisierungen.

[Goderion]

Vielen Dank für die Antworten!

Der Link führt zu der Stelle im C++ Standard, die besagt dass alle Identifier die doppelte Underscores enthalten oder mit einem Underscore gefolgt von einem Großbuchstaben beginnen reserviert sind. _GetValueType fällt in diese Kategorie. Ein Programm das ein Ding mit einem solchen Identifier als Namen deklariert hat streng genommen autom. Undefined Behavior.

Oha, danke für den Hinweis. Benutze öfter _ um Funktionen zu kennzeichnen, die nicht direkt aufgerufen werden sollen oder in Klassen als "interne" Funktionen dienen.

Ich dachte irgendwie dass dein GetValueType() aus irgendeinem Grund ein Template sein muss. Ansonsten:

Code: Alles auswählen

namespace GVT
{
	namespace V5
	{
		constexpr int GetValueType(const int&) { return 1; }
		constexpr int GetValueType(const bool&) { return 2; }
		constexpr int GetValueType(const float&) { return 3; }
		constexpr int GetValueType(const double&) { return 4; }
	}
}

Das geht leider nicht. short wird z.B. zu int konvertiert. Das const muss weg, dann explodiert aber leider die Fehlermeldung wie bei V1.

Lass doch die Standard-Definition weg, dann gehen nur noch die Spezialisierungen.

Das funktioniert, aber die Fehlermeldung finde ich unnötig lang.

V4 bleibt mein Favorit. Wenn nichts dagegen spricht, werde ich das so umsetzen.

[DerAlbi]

Benutze öfter _ um Funktionen zu kennzeichnen, die nicht direkt aufgerufen werden sollen oder in Klassen als "interne" Funktionen dienen.

Dafür gibts private:,protected: und public:. struct ist per default (also nach "{" ) public, class ist per default private.
Das funktioniert mit deinen namespace-Konstruken allerdings nicht. Da würde ich mich an die STL halten: die versteckt Hilfsfunktionen in einem weiteren unter-namespace detail oder was auch immer.

[Goderion]

Danke für die Antwort!

Dafür gibts private:,protected: und public:. struct ist per default (also nach "{" ) public, class ist per default private.

So meinte ich das nicht. Bei internen Funktionen meine ich Methoden, die private sind, aber deren Name aufgrund ihrer "Tätigkeit/Funktion" sonst z.B. doppelt wären. Ein kleines Beispiel:

Code: Alles auswählen

	void AddElement(ClassListElement* pElement)
	{
		BeforeAddElement(pElement);
		Impl_AddElement(pElement);
		AfterAddElement(pElement);
	}

	void RemoveElement(ClassListElement* pElement)
	{
		BeforeRemoveElement(pElement);
		Impl_RemoveElement(pElement);
		AfterRemoveElement(pElement);
	}

	void MoveElementBack(ClassListElement* pElement)
	{
		BeforeRemoveElement(pElement);
		Impl_RemoveElement(pElement);
		Impl_AddElement(pElement);
	}

In dem obigen Beispiel gibt es zwei Funktionen, die ein Element einer Liste hinzufügen. Die erste Funktion AddElement ist public und führt noch zusätzliche Funktionen aus, z.B. zur Validierung. Die zweite Funktion, hier jetzt Impl_AddElement genannt, fügt das Element tatsächlich zur Liste hinzu, ohne weitere Prüfungen usw..

Da mir nichts besseres eingefallen ist, habe ich vor allen Funktionen, die mit einem Unterstrich begonnen haben, ein Impl gesetzt. Falls ich eine bessere Lösung finde, kann ich das ja einfach ersetzen.

Das funktioniert mit deinen namespace-Konstruken allerdings nicht. Da würde ich mich an die STL halten: die versteckt Hilfsfunktionen in einem weiteren unter-namespace detail oder was auch immer.

Ich habe aktuell keine Funktionen, auf die man nicht zugreifen soll, die nicht private sind, aber eine gute Idee mit dem Namespace.