Sign in to follow this  
l0k0

Unity Component Entity Model Without RTTI

Recommended Posts

[quote name='Net Gnome' timestamp='1326584461' post='4902799']
I'm just curious as to why one would purposefully handicap themselves[/quote]

Handicap? I call it advantage.
One reason is simplicity. You have what you see. Not an unknown quantity which may be anything. It reduces the code size several fold. Also consider that C has no RTTI. On another end of scale is IoC and DI, both proven to scale to arbitrarily large projects by eschewing traditional typing.

[quote]by not taking advantage of even the most basic of OO techniques[/quote]
It's not necessary to abandon any OO techniques, it's about design. All of the above can be identically applied in any language.

Other reason is performance. You mentioned "1/1000th of a millisecond". That would be 1 microsecond, or on the order of several thousand CPU cycles. In that time, one can transform several thousand vertices or one model. In reality, the dynamic dispatch is considerably less (either no penalty due to branch prediction or only several cycles), but it adds up. Hence it's completely missing in GPU programming, where completely other techniques are used.

[quote]but its almost impossible to avoid OO in c# and therefore avoid RTTI.[/quote]
LINQ. Entity Framework. OO has been abandoned in .Net and just about any other framework. It simply doesn't scale management-wise.

Obivously, C# being designed on top of object-based VM means that syntax still uses Java-like constructs, but application design has moved completely away from OO. It's similar to how SOLID principles are commonly used in C applications despite language not supporting OO at all.


Performance plays a role here again, but in a different way. With emphasis being on web development, the latency of receiving data is simply too high. If dynamic dispatch costs only a cycle or two on CPU, equivalent design requires up to several seconds over internet. Hence the introduction of SPDY, the studies into async loading of assets in browsers, the preference of JSON vs. XML, the designs of web APIs. OO simply doesn't work over internet as Sun's falacies teach. One of biggest examples of such failures is CORBA.

Share this post


Link to post
Share on other sites
Oh, i completely agree with you on what you've said. I guess its just a difference in personal philosophy. I tend to favor flexibility over performance and it seems you're vice-versa. Don't take that to mean I'm against writing for performance, i just tend to go towards building a flexible framework first, then speed it up as needed.

Share this post


Link to post
Share on other sites
[quote name='Net Gnome' timestamp='1326634233' post='4902945']
I tend to favor flexibility over performance and it seems you're vice-versa.[/quote]

Not really. I find that I get considerably more flexibility and simplicity. Performance is not the crucial factor, but alternate designs are good fit for hardware realities.

Share this post


Link to post
Share on other sites
[quote name='l0k0' timestamp='1324411691' post='4895843']
However, RTTI (along with exceptions) is typically best left disabled in frameworks and engines if possible.
[/quote]

Sorry, I'm late to the discussion and the answer to my question may have already been provided. I'm also developing my own component entity system for my C++ Engine and I'm really curious as to where the above statement comes from. I use RTTI in my current system with essentially a base `Component` class and a one level of inheritance to derive Subsystem Components classes. I'm not using templates. Whats wrong with using RTTI?

Share this post


Link to post
Share on other sites
[quote name='T e c h l o r d' timestamp='1326690288' post='4903126']
Whats wrong with using RTTI?
[/quote]

The topic of the thread is
[b] Component Entity Model Without RTTI[/b]


I think thats all thats wrong with it.

Share this post


Link to post
Share on other sites
[quote name='T e c h l o r d' timestamp='1326690288' post='4903126']Whats wrong with using RTTI?[/quote]You can do better.

If you were to implement it yourself, would you do it like this?[code]struct TypeItem
{
const char* name;
TypeItem* parents;
TypeItem* next;
};
std::map<void*, TypeItem> g_types;

bool Match( TypeItem a, TypeItem b )
{
if( strcmp(a.name, b.name)==0 )//cache miss
return true;
else if( b.next && Match(a, *b.next) )//cache miss, recursive
return true;
else if( b.parents && Match(a, *b.parents) )//cache miss, recursive
return true;
else
return false;
}

bool Match( void* objectA, void* objectB )
{
void* vtableA = *(void**)objectA;
void* vtableB = *(void**)objectB;
return Match( g_types[vtableA], g_types[vtableB] );
}[/code]...because you shouldn't be surprised if your compiler implements RTTI in such a horribly-performant manner.

And if you knew that type-comparisons involved calling a function this ugly, would you think twice about calling this type-comparison function?


Also, as discussed earlier, there's no [i]need[/i] to have a [font=courier new,courier,monospace]entity->GetComponent<T>()[/font] function in the first place...

Share this post


Link to post
Share on other sites
[quote name='Hodgman' timestamp='1326691929' post='4903133']
[quote name='T e c h l o r d' timestamp='1326690288' post='4903126']Whats wrong with using RTTI?[/quote]You can do better.

If you were to implement it yourself, would you do it like this?[code]struct TypeItem
{
const char* name;
TypeItem* parents;
TypeItem* next;
};
std::map<void*, TypeItem> g_types;

bool Match( TypeItem a, TypeItem b )
{
if( strcmp(a.name, b.name)==0 )//cache miss
return true;
else if( b.next && Match(a, *b.next) )//cache miss, recursive
return true;
else if( b.parents && Match(a, *b.parents) )//cache miss, recursive
return true;
else
return false;
}

bool Match( void* objectA, void* objectB )
{
void* vtableA = *(void**)objectA;
void* vtableB = *(void**)objectB;
return Match( g_types[vtableA], g_types[vtableB] );
}[/code]...because you shouldn't be surprised if your compiler implements RTTI in such a horribly-performant manner.

And if you knew that type-comparisons involved calling a function this ugly, would you think twice about calling this type-comparison function?


Also, as discussed earlier, there's no [i]need[/i] to have a [font=courier new,courier,monospace]entity->GetComponent<T>()[/font] function in the first place...
[/quote]
I don't know how the compiler implements RTTI and I honestly don't think my implementation would out perform it. I would like to believe that the compiler scientists identified weak RTTI performance and implemented an optimization, after all one would have to go thru the compiler to compile a home grown implementation. I also don't use templates but, I can rationalize why there's no [i]need[/i] to have a [font=courier new,courier,monospace]entity->GetComponent<T>()[/font]. I'm still in the process of refactoring and haven't fully worked out how the communication between components.

I use RTTI in my current system with a base `Component` class and a one level of inheritance to derive Subsystem Components classes. I'm personally not a big fan of the extra typing involved with using [i]static_cast<derived*>(base[/i][i]) [/i]and [i]dynamic_cast<derived*>(base) [/i]keywords. Which is my only grief. Other than that I still have seen any data validating the claim RTTI is `bad` for performance. Can someone please point me to some documentation that supports this claim? If necessary, I rather change the implementation now than later. Thanks in advance.

Share this post


Link to post
Share on other sites
[quote name='T e c h l o r d' timestamp='1326697224' post='4903153']I don't know how the compiler implements RTTI and I honestly don't think my implementation would out perform it. I would like to believe that the compiler scientists identified weak RTTI performance and implemented an optimization, after all one would have to go thru the compiler to compile a home grown implementation.[/quote]Just think about the feature that it's implementing -- it's mighty complex.
Try and think about how you might implement such a general system so that this kind of magic is possible:[code]struct A {};
struct B {};
struct C : public A, public B {};
struct D : public C {};

D data;
B* ptrBase = &data;
D* ptrDerived = dynamic_cast<D*>( ptr );[/code]No matter how much you optimise it, it's still going to be mighty complicated. You can't optimise out that complexity, because the complexity of working in every inheritance hierarchy is the core feature that it provides. Also, yes, it is often implemented using string-comparisons and linked-lists, because the compiler authors know that no-one who cares about performance is going to use [font=courier new,courier,monospace]dynamic_cast[/font] and then complain when it's slow...

The reason that you can easily beat this, is because you don't need that much complexity! If you only need to be able to perform exact type comparisons (no hierarchy testing) on a specific, small set of types, then you can roll an ID system in two lines:[code]struct TypeIdBase { protected: static int NextId() { static int i = 0; return i++; } };
template<class T> struct Type : TypeIdBase { public: static int Id() { static int id = NextId(); return id; } };[/code]and implement type-comparisons in one line, with the ability to store type-id's in [font=courier new,courier,monospace]int[/font] members if needs be:[code]if( Type<int>::Id() == Type<float>::Id() )
printf("what?");[/code]
However, it's extremely rare to find a use for [font=courier new,courier,monospace]dynamic_cast[/font]ing that's justifiable in the first place. There's usually a simpler, cleaner, more maintainable way of doing things.
In what situations do you use [font=courier new,courier,monospace]dynamic_cast[/font]?

Share this post


Link to post
Share on other sites
I use pointers to the base component class to work with derived component classes. I only use [i]RTTI casting [/i]when a base class pointer needs to access a member of the derived class. My initial reason for this approach was make my life easier wrapping objects from 3rd Party libraries like Ogre::Mesh into a Component. A Derived Component inherits from both the Base Component and Ogre::Mesh Classes or contains members to work Ogre::Meshes directly. I'm relatively new to C++ and still trying to wrap my head around a components implementation.

Share this post


Link to post
Share on other sites
For my assignment of entities to components i use an array of arrays to contain components by type. When a component is added to the framework, a type Id is established. This is nothing more than assigning an incrementing integer to a static int in the component. Since its static, each and every component of that type will report the same exact type Id (i also perform an early registry when a system is established to ensure a type id is created as well). so when i need to retrieve component x from entity y i use x.id to index into the array of arrays to pull out the applicable component array, then use the y.id (entity) to retrieve the relevant component. (i.e., no type comparisons are ever required other than checking for index safety).

now of course this also adds some memory overhead, but the trade-off is access performance. of course my implementation uses RTTI to access the type id, as its generally accessed through an interface. Now if i could get a way to do that without having to go through an interface but still remain agnostic in implementation thats faster than an assembly table lookup (from my digging around, that is approximately how interfaces are implemented by the compiler), i'm all ears [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] Or will i need to loose the agnostic approach?

Share this post


Link to post
Share on other sites
Well, hrm... now that i think of it, i could make the component be a mapping container, where it holds a type id and then another mapping id which would say which index I would want in a dedicated array for that data type. The component manager and mapper would just use another layer of lookup to get/set the data needed. I would need to use something like a switch to direct it to the correct retrieval mechanisms, but would this be faster than an interface?

The component would be something like this:

[CODE]
class Component
{
int entityId;
int componentType;
int componentId;
}
[/CODE]

though, the componentId and entityId could be merged to do the indexing if you dont mind an entity only able to own one component of any type. If you did that, you could remove the need for a class entirely as long as you knew the entity id and component type desired.

But with that approach, you would need a unique retrieval mechanisms for each and every component type to be defined in a component manager/mapper, even if you reduced that class down to a global constant...

At that point you no longer have an agnostic framework though =/

Share this post


Link to post
Share on other sites
[quote name='Net Gnome' timestamp='1326719422' post='4903215']
Well, hrm... now that i think of it, i could make the component be a mapping container, where it holds a type id and then another mapping id which would say which index I would want in a dedicated array for that data type. The component manager and mapper would just use another layer of lookup to get/set the data needed. I would need to use something like a switch to direct it to the correct retrieval mechanisms, but would this be faster than an interface?[/quote]

Speed is not primary concern, at least not when it comes to design.

You talked about SQL-like mapping. Apply the same principle here. Take two systems, perhaps a physics one and perhaps a pickup trigger. We have this data:[code]Vector3 position[];
Vector3 orientation[];
Vector3 velocities[];
TriggerRadius triggers[];
ItemTemplate templates[];[/code]Physics requires position, orientation and velocities. Quest trigger requires position triggers and templates.

The logic that manipulates these would be akin to select statement (SELECT position, orientation, velocities ... and SELECT position, triggers, templates ...).

There is no presecribed way to express such relation or how items are connected. At most basic level, you could indeed to this:[code]class RigidBody {
Vector3 position, orientation, velocities;
};[/code]Then design listeners and whatnot to update these instances as they change. Then propagate them to pickup system, for example.

Alternatively, you can express all of these as pure code.[code]void stepPhysics() {
// do stuff with velocities, orientation, position
}

void checkForPickups() {
for every item that has a trigger
check for trigger radius
if in_range of trigger
use item based on template
}[/code]


How to map these things? Whatever is most convenient. One might use 1:1 indices. So that position[i], orientation[i] and velocity[i] belong to same entity. For triggers, there might be a a separate map that contains indices mapping between needed values.


Such approach lends itself well to cases where there is many things and there is expected to be many things. It's not worth complicating for one-off objects.

For UI, we know we'll have many buttons and frames. We also know that each button has associated action. So perhaps something like this:[code]Rect uiElements[];
delegate void UIAction(...); // note the abstract handler
UIAction actions[];

void onClick(int x, int y) {
find which element was clicked in uiElements, located at index i
invoke corresponding handler[i]
}[/code]

At each level, there's absolute minimum amount of data stored. An UI element doesn't need to know its type at first pass, it's just a rectangle that can be matched to a click. Later, we can differentiate between buttons, listboxes, .... Also notice the use of "complex" delegate. On each click, we'll invoke one element (or perhaps a few on multitouch).


Now consider that we end up with many UI elements and clicking is slow. No problem, all we have is a bunch of rectangles. Maybe build a quad tree over them and use that to query. Also, for simplicity, examples use arrays. These can be any container, List<>, Map<> whatever is most suitable. For performance sensitive work, they'd be either aligned arrays or in C# arrays/lists of structs.

Share this post


Link to post
Share on other sites
Figure i would write a minor test case, just to see how much performance i am loosing using the most basic of interface usage. i wrote this to test:


[CODE]
namespace InterfaceTest
{
class Program
{
static void Main(string[] args)
{
Test test = new Test();
test.runTest();
}
}

class Test
{
private IInterface interfaceClass = new ExtendedClass();
private NormalClass normalClass = new NormalClass();
private ExtendedClass extendedClass = new ExtendedClass();
private int test;
private long interfaceStart, interfaceFinish, normalStart, normalFinish, extendedStart, extendedFinish;

public void runTest()
{
interfaceStart = DateTime.Now.Ticks;
for (int i = 0; i < 100000000; i++)
{
test = interfaceClass.getInt();
}
interfaceFinish = DateTime.Now.Ticks;
normalStart = DateTime.Now.Ticks;
for (int i = 0; i < 100000000; i++)
{
test = normalClass.getInt();
}
normalFinish = DateTime.Now.Ticks;
extendedStart = DateTime.Now.Ticks;
for (int i = 0; i < 100000000; i++)
{
test = extendedClass.getInt();
}
extendedFinish = DateTime.Now.Ticks;
Console.WriteLine("interface duration: " + (interfaceFinish - interfaceStart));
Console.WriteLine("normal duration: " + (normalFinish - normalStart));
Console.WriteLine("extended duration: " + (extendedFinish - extendedStart));
Console.Read();
}
}
}
[/CODE]

inteface:


[CODE]
namespace InterfaceTest
{
interface IInterface
{
int getInt();
}
}
[/CODE]

extended:


[CODE]
namespace InterfaceTest
{
class ExtendedClass : IInterface
{
int i;
public int getInt()
{
return i;
}
}
}
[/CODE]

and normal

[CODE]
namespace InterfaceTest
{
public class NormalClass
{
int i;

public int getInt()
{
return i;
}
}
}
[/CODE]

interface: 2964005
normal: 312000
extended: 312001

so, its roughly 9.5 times slower than a direct call. interesting.

edit: realized i had a type conversion from int to long in there, its fixed now.

Share this post


Link to post
Share on other sites
interestingly enough, using an abstract class vs an interface results in a about 1716003 ticks, or ~5.5x as long as a direct class call and an internal call costs the same as a direct class call. So when in doubt, go abstract over interface... Interesting things to ponder...

Share this post


Link to post
Share on other sites
[quote name='Net Gnome' timestamp='1326739063' post='4903311']
interestingly enough, using an abstract class vs an interface results in a about 1716003 ticks, or ~5.5x as long as a direct class call and an internal call costs the same as a direct class call. So when in doubt, go abstract over interface... Interesting things to ponder...
[/quote]

I don't really want this to be about synthetic microbenchmarking, it's more about showing what happens if you turn your world completely upside down and throw away all existing notions of how a solution should be structured.

There's also another test that is missing above:[code]
public class NormalClass
{
int i;

public void testInt(int n)
{
for (int i = 0; i < n; i++)
{
test = i;
}
}
}
[/code]
It's considerably more representative of real world difference. Original test is a NOP, so it's measuring the overhead of pointless assignment. The changed example moves the separation line from outside of interface into implementation itself.

Ironically, this version is better OO than other tests. Getters break encapsulation.

Share this post


Link to post
Share on other sites
[quote name='T e c h l o r d' timestamp='1326704427' post='4903169']
I use pointers to the base component class to work with derived component classes. I only use [i]RTTI casting [/i]when a base class pointer needs to access a member of the derived class. My initial reason for this approach was make my life easier wrapping objects from 3rd Party libraries like Ogre::Mesh into a Component. A Derived Component inherits from both the Base Component and Ogre::Mesh Classes or contains members to work Ogre::Meshes directly. I'm relatively new to C++ and still trying to wrap my head around a components implementation.
[/quote]

A cleaner solution would be to treat the ogre mesh as a property of your derived component and through an interface, keeps the Ogre API out of the ECS framework.

[CODE]
/* Base mesh object */
class IMeshObject {
};
/* Ogre mesh object */
class OgreMeshObject : public IMeshObject {
};
/* CryEngine mesh object */
class CryMeshObject : public IMeshObject {
};
/* Base component */
class IComponent {
};
/* Renderable Component */
class IRenderComponent : public IComponent {
};
/* Mesh component */
class MeshComponent : public IRenderComponent {
public:
void setMeshObject(IMeshObject* meshObject);
IMeshObject* getMeshObject();
};
[/CODE]

If you wanted to keep it simple and refactor later, you could avoid wrapping the ogre API if you wanted and simply use get/set methods for the Ogre::MeshPtr object; however, I certainly would not inherit from any render API classes when creating my ECS components.

Share this post


Link to post
Share on other sites
[quote name='Hodgman' timestamp='1326158891' post='4901151']
It also has the problem of enforcing the there can only be one philosophy onto the user -- each entity can only have one transform and one health component -- which may seem like a trivial burden at the time of writing, but at some point your users will find a reason for there to be two of something, and will be forced to construct ungracious work-arounds involving several entities cooperating to function as one "entity".
[/quote]

My current system uses said system without that restriction like so:

[CODE]
template<class T> void getComponents(T *components[], int32 &n) const {
n = 0;
uint32 i;
for (i = 0; i < componentList.size(); ++i) {
if (componentList[i]->asType<T>()) {
components[n++] = static_cast<T *>(componentList[i]);
}
}
}
[/CODE]

I think you make a great point about the hidden dependencies though. Accessing the pointers directly is also faster than a linear search/hash table look up when it matters too.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this