Sign in to follow this  

Speed up Property System

This topic is 3855 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been using a game-object property system for a while now, and it works very well. I call the properties 'facets' b/c 'properties' was already used in my engine for something else. Every game object in my engine has a std::map< wstring, Facet >, where each Facet contains a name, type enum, and a union of string, int, float, etc. It works well, and allows us to add new properties to game objects very quickly and without breaking saved games, etc. The bad news is that it's now showing up in the profile, and I want to fix ithe perf without losing the flexibility. I had a thought this morning on how to speed it up : - Move the most common properties from the facet system to member variables of the class, thus moving name-resolution from run-time to compile-time. - Do the above via a macro, so I can transparently switch between member variable and facet look-up, so once I switch client code to the macro, I won't have to change the client code again, even if I move things between members and facets. something like this :

#define GetFacetValue( name, value )
#ifdef facetcache.#name 
GetFromCache( facetcache.#name, value )
_GetFacetValue( ##name, value ) 
#endif
Designed to be used like so : pEntity->GetFacetValue( name, value ); Anyone done/seen something like this? I think this could be done through a template as well, but I'm not much of a meta-programming guru...

Share this post


Link to post
Share on other sites
Can you give us some more info? Where is the performance causing issues? Is it pulling the data out of the map? How are you using these (I'd call it a "property bag" by the way) in your game? Are you storing positional data, etc. this way?

I'm curious because we are working on something very similar in our rewrite of Crown and Cutlass. I have a Variant class (it's implemented using boost::variant). Then I have a PropertyBag class that is basically a map from a property name to a Variant. Our game objects are basically a property bag with a few predefined properties. Then in our scene graph, we have an entity node that references a game object. The idea is that the scene node contains the data that changes frequently (the positional info) while the game object holds the things that change infrequently (model name, etc) and basically whatever else the engine user wants for their needs. Anyway, we haven't gotten far enough to really try that yet, so I'm curious to hear more details about your system.

PS Some of the Doxygen docs may be out of date, you can find the most recent stuff in through the SVN repository links though if you are curious...

Share this post


Link to post
Share on other sites
I'm using a similar template based solution. While it has to deal with a lot more, the basic concept is sort of a typesafe dynamic memory allocation.


class base_key
{
// this class stores key id and implements map comparison
base_key( size_t uid ) : id(uid) {}
size_t id;
}

template < typename T >
class key : public base_key
{

// instance contains property name
// a unique id is generated for each key,
// that's used for comparison inside a map
key() : base_key( unique_id++ ) {}
};

typedef key<int> IntKey;
typedef key<std::string> StringKey;

const IntKey KHealth("health");
const StringKey KObjectName("object_name");

class Container
{
template < typename T >
void set( const key<T> &k, T value )
{
// find value in map, store pointer to it in *ptr
// if it exists we know its exact type
TypedVariable<T> *v = (TypedVariable<T> *)ptr;
v->set( value );
}

template < typename T >
T get( const key<T> &k )
{
// same as above, find pointer and put it in *ptr;
return ((TypedVariable<T> *)ptr)->get();
}

// examples of support for STL types
template < typename T >
void add( const key< std::list<T> > &k, T value);

template < typename T >
bool contains( const key< std::set<T> > &k, T value);

template < typename T >
T get( const key< std::vector<T> > &k, size_t index );


std::map< base_key, Variable * > m_storage;
};


// objects storing the values
// support serialization, custom allocation, etc.
class Variable;

template < typename T >
class TypedVariable;

tempalte < class T >
class ContainerVariable;

template < typename T >
class ListVariable : public ContainerVariable< std::list<T> >;

...

Container creature;
creature.set( KHealth, 17 );
creature.get( KObjectName );




Obviously, the real implementation supports all the STL containers, and is written in a slightly more robust way, but the general idea is to perform "volatile" memory allocation by using raw pointers, allowing arbitrary sizes, custom allocators, and all the usual low-level memory manipulation, while at the same time provide compile time safety.

The aproach is based after one of Game Programming Gems articles, and is used so that properties can be transparently inherited from other classes during run-time. So if a property is not found in a container, it will query the parent container, that one will do the same, and so on...

The profiling tests I've done on access to these values shows the system is pretty efficient, only about 5-8 times slower from a function call (non-inlined return of a value). Also important is that the performance degrades grafecully, going from 5 to 100 properties only decreases access times by a few percent.

In addition, the overhead of keys is nonexistant, since only one instance is used throughout the system.


My sugestion to you would be to find a way to use something else for key instead of a string. An int, or a way to represent a unique id. THat's probably where you lose most of the time compared to my experience with map based implementation.

Share this post


Link to post
Share on other sites
Ah, when you mentioned this originally I thought it might be a problem of sorts.

Unfortunately, I've got no better ideas. I wonder if you can access the map's buckets directly? In that case, you could probably save a hash operation by writing a quick macro to replace commonly accessed strings with a number.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ravuya
Ah, when you mentioned this originally I thought it might be a problem of sorts.

Unfortunately, I've got no better ideas. I wonder if you can access the map's buckets directly? In that case, you could probably save a hash operation by writing a quick macro to replace commonly accessed strings with a number.


Use OO. You only need to define one operator to support map lookups (IIRC).


class MapId
{
MapId( std::wstring s )
: hash( do_some_hashing_on_string(s) )
{}

// and add the comparison, forgot the exact syntax right now
int operator< ( const MapId &other );

int hash;
}




Then just pass the references to these keys around. Also much safer if they are only defined in one place.

You can make them singletons even. *One case where singletons aren't evil*.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ravuya
Singletons would be evil in this case if you were using a different hashing algorithm for one or more maps, no?


No. You only need comparison between the keys. As long as you stick with general purpose container you're not interested in how the hashes map into buckets, as long as they are unique and comparable.

If you want map-specific keys, then that particular container needs to generate them, and you can't have them global in the first place.

My proposal was for global key namespace, where internal hashes are unique, not instance/implementation specific. The keys in that case also hold invariant state.

Share this post


Link to post
Share on other sites
Quote:
Original post by SimmerD
The bad news is that it's now showing up in the profile, and I want to fix ithe perf without losing the flexibility.
Which part, exactly? I'm guessing it's the lookups that are showing up, but just to be clear.

Several options come to mind. The first is a hashtable, which built correctly might give a nice speed boost. You can do this fairly easily, at least for testing, by simply switching over to hash_map or whatever the VC version was called; it should switch over fairly transparently.

A more complex but very promising idea would be to replace the map with a splay tree based implementation. You can look up the details on wikipedia, but basically you'll end up with a map that is self optimizing to favor frequently accessed elements. And if you write it STLish, it won't require any particular changes in the rest of the codebase.

There's probably more intense metaprogrammed voodoo as an option, but simply switching out the base data structure is far less intrusive and could help a lot. I'd try those things before going to the obscure and arcane.

Share this post


Link to post
Share on other sites
Good points all.

Yes, the lookups seem to be the expensive part,

I am using a std::map with a custom string comparison function, one that considers string length for ordering first, and then uses std::wstring::operator< if the lengths are the same.

I will try a hash_map, and the splay tree may be a good idea down the line...

Share this post


Link to post
Share on other sites
Replacing the property names with property id numbers would definitely speed up the comparisons, at the cost of having to maintain the mapping between names and numbers. You could still support dynamic property lookup for supported names by maintaining a map from strings to ids. It would even still be possible to add names at run-time, by implementing a system to allocate these id numbers. In fact you could even do all the id allocation at run-time...

This idea is similiar to Antheus's key class, but less complicated in my opinion.

Share this post


Link to post
Share on other sites

This topic is 3855 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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