Optimizing Away the Use of Strings as Handles

Discussion area about developing or extending OGRE, adding plugins for it or building applications on it. No newbie questions please, use the Help forum for that.
User avatar
vitefalcon
Orc
Posts: 438
Joined: Tue Sep 18, 2007 5:28 pm
Location: Seattle, USA
x 13

Re: Optimizing Away the Use of Strings as Handles

Post by vitefalcon »

bstone wrote:vitefalcon, don't pay too much attention to that guy. I've seen the exact same pattern in another thread - posting stuff without any thought process behind it, then getting angry when pointed to that fact, then claiming how much more he knows, then never proving that.
Thanks for the support. I felt at a point that I had written something really wrong and I wasn't reading posts properly, so I had the urge to clear myself. I went through his other posts and saw the same pattern. Anyhoo, let's move on... :)
Image
TheSHEEEP
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 972
Joined: Mon Jun 02, 2008 6:52 pm
Location: Berlin
x 65

Re: Optimizing Away the Use of Strings as Handles

Post by TheSHEEEP »

masterfalcon wrote:Let's give the ResourceManager class, and therefore its subclasses, a StringVector of names for resources of the type that it manages. Resource types that contain other lists can do the same. For example, Technique has a list of Pass names, etc. But what about the unique ID? We already have an implied ID as the index in the StringVector and it's scoped to that particular resource type. Resources would know their ID but not their name but that could be queried through the manager as it is now.

To assign ID's we can find the first NULL object in the vector(not empty string) the index of which becomes the ID for that new resource. That way things can be deleted and their spaces(and ID's) reused without resizing the vector and keep it as packed as possible.
That sounds like a good idea. Is there any chance of a ressource being deleted without the user actively causing that?
I can't think of any, but if so, we'd need some kind of will-be-deleted-callback/event.
My site! - Have a look :)
Also on Twitter - extra fluffy
User avatar
vitefalcon
Orc
Posts: 438
Joined: Tue Sep 18, 2007 5:28 pm
Location: Seattle, USA
x 13

Re: Optimizing Away the Use of Strings as Handles

Post by vitefalcon »

TheSHEEEP wrote:Is there any chance of a ressource being deleted without the user actively causing that?
As long as an instance of ResourcePtr is being stored inside the respective ResourceManager, which it already does, there shouldn't be that scenario. Unless, just like you said, the user does something really nasty like 'delete resourcePtrInstance.get();', in which case, it's the user's fault anyway.
Image
Knotanalt
Halfling
Posts: 94
Joined: Sun Jul 01, 2012 2:58 pm
x 2

Re: Optimizing Away the Use of Strings as Handles

Post by Knotanalt »

vitefalcon wrote:
bstone wrote:vitefalcon, don't pay too much attention to that guy. I've seen the exact same pattern in another thread - posting stuff without any thought process behind it, then getting angry when pointed to that fact, then claiming how much more he knows, then never proving that.
Thanks for the support. I felt at a point that I had written something really wrong and I wasn't reading posts properly, so I had the urge to clear myself. I went through his other posts and saw the same pattern. Anyhoo, let's move on... :)
I asked where the performance improvement came from from using hashstring, I thought that ws pretty obvious but maybe not.

When you responded I assumed that you were addressing my question but reading back maybe you thought I was talking about something else. I am not too concerned with the performance of the lookup itself.

However it disturbs me a bit that simply changing the way that string works like tiffer did would make such big gains. Which is probably not the way to address things as it's a pretty classic optimization mistake, which is why I'd like to see more details about the profiling.

I don't mind disagreement but there's no need for you or for bstone to be rude about things. I don't assume you are liars or idiots and expect the same respect (if you think it privately I don't care at all but antagonism is a giant waste of time and energy). At any rate since it was tiffer who did the profiling (I assumed it was you since you responded) then there's no reason to go on with the misunderstanding.

It looks like the situation is indeed what I expected, big suprise boy what an idiot I feel like. I just didn't know the exact location or numbers.
User avatar
vitefalcon
Orc
Posts: 438
Joined: Tue Sep 18, 2007 5:28 pm
Location: Seattle, USA
x 13

Re: Optimizing Away the Use of Strings as Handles

Post by vitefalcon »

vitefalcon wrote:I guess the resources, as it is now, already know their ID. Checking out the Resource.h, you'll see a private member called mHandle, which is of type ResourceHandle, which is a typedef of unsigned long long as per the documentation. I haven't dug deep enough to state this with absolute certainty, but it seems that Ogre currently assigns a Resource ID, but it's not being used efficiently.
The ResourceHandle values are generated in a thread-safe manner and there is a map to hold the mapping between ResourceHandle and the ResourcePtr in ResourceManager class. So I guess the changes should be towards changing the API to encourage users to use this ResourceHandle than using strings to access existing Resources. The other change that would be good to have is to use an atomic integer as the variable that is used to retrieve the next ResourceHandle value. We need to cater to both pre-C++11 and C++11+ users.

Use-cases where the ResourceHandle will not do:
  • Loading a resource by name that is already not loaded by the respective ResourceManager
  • Searching for a resource by name
Does anyone else have more scenarios?
Image
User avatar
Klaim
Old One
Posts: 2565
Joined: Sun Sep 11, 2005 1:04 am
Location: Paris, France
x 56
Contact:

Re: Optimizing Away the Use of Strings as Handles

Post by Klaim »

Is there a cheap way to avoid that lock?
User avatar
vitefalcon
Orc
Posts: 438
Joined: Tue Sep 18, 2007 5:28 pm
Location: Seattle, USA
x 13

Re: Optimizing Away the Use of Strings as Handles

Post by vitefalcon »

Klaim wrote:Is there a cheap way to avoid that lock?
Use an atomic data-type (long). Increments or decrements to these types are guaranteed to be thread-safe and doesn't need a mutex lock, which will cause (depending on the implementation of the mutex) the code to go into kernel mode causing a hit in performance.

EDIT:
References:
Image
User avatar
masterfalcon
OGRE Team Member
OGRE Team Member
Posts: 4270
Joined: Sun Feb 25, 2007 4:56 am
Location: Bloomington, MN
x 126
Contact:

Re: Optimizing Away the Use of Strings as Handles

Post by masterfalcon »

I'll ask again. Would anyone be able to commit their changes to a public repository for review?
User avatar
vitefalcon
Orc
Posts: 438
Joined: Tue Sep 18, 2007 5:28 pm
Location: Seattle, USA
x 13

Re: Optimizing Away the Use of Strings as Handles

Post by vitefalcon »

masterfalcon wrote:I'll ask again. Would anyone be able to commit their changes to a public repository for review?
I can work on the atomic integer for ResourceHandle and make sure that getNextHandle() doesn't require a lock. This includes creating a cross-platform version of atomic long integer and making sure it's compatible with C++11. If the compiler is C++11 compatible, then I will make sure to use the std::atomic<long>. Does that sound good for one commit change?
Image
User avatar
masterfalcon
OGRE Team Member
OGRE Team Member
Posts: 4270
Joined: Sun Feb 25, 2007 4:56 am
Location: Bloomington, MN
x 126
Contact:

Re: Optimizing Away the Use of Strings as Handles

Post by masterfalcon »

Are you going to make sure that there is also code compatible for compilers without c++11? If so then yes.
User avatar
vitefalcon
Orc
Posts: 438
Joined: Tue Sep 18, 2007 5:28 pm
Location: Seattle, USA
x 13

Re: Optimizing Away the Use of Strings as Handles

Post by vitefalcon »

masterfalcon wrote:Are you going to make sure that there is also code compatible for compilers without c++11? If so then yes.
Yes. That's the plan.
Image
User avatar
vitefalcon
Orc
Posts: 438
Joined: Tue Sep 18, 2007 5:28 pm
Location: Seattle, USA
x 13

Re: Optimizing Away the Use of Strings as Handles

Post by vitefalcon »

The more I look at Ogre's code the more pleasantly surprised I am. Seems like there already is an implementation of atomic values in OgreAtomicWrappers.h. Although this doesn't use std::atomic in case of C++11, the implementation is good enough to work across all platforms and on C++11. I've just made the changes and created a pull-request into v2.0 for the change I made. It's quite a silly change though.

EDIT: Scratch that. Seems like I was working on default branch instead of v2-0. I'll make the changes into v2-0 and create another pull request.

EDIT2: Ok. Got it right this time. @masterfalcon: Can you take a look when you're free?
Image
User avatar
vitefalcon
Orc
Posts: 438
Joined: Tue Sep 18, 2007 5:28 pm
Location: Seattle, USA
x 13

Re: Optimizing Away the Use of Strings as Handles

Post by vitefalcon »

Once the change above is in place, the next plan should be about how to refactor resource managers to encourage the use of resource handles. This part will need more discussion before making any changes AFAICS.
Image
bstone
OGRE Expert User
OGRE Expert User
Posts: 1920
Joined: Sun Feb 19, 2012 9:24 pm
Location: Russia
x 201

Re: Optimizing Away the Use of Strings as Handles

Post by bstone »

So why would anybody use a "resource handle" instead of a pointer (smart) to the resource? I don't see any benefits - at the point where you resolve a resource name into its handle you can simply get the pointer to the resource instead and then use it afterwards, saving on handle<->resource lookups later in your code. Why then?
User avatar
vitefalcon
Orc
Posts: 438
Joined: Tue Sep 18, 2007 5:28 pm
Location: Seattle, USA
x 13

Re: Optimizing Away the Use of Strings as Handles

Post by vitefalcon »

bstone wrote:So why would anybody use a "resource handle" instead of a pointer (smart) to the resource? I don't see any benefits - at the point where you resolve a resource name into its handle you can simply get the pointer to the resource instead and then use it afterwards, saving on handle<->resource lookups later in your code. Why then?
Same thing I had asked before. :)
Image
User avatar
Xavyiy
OGRE Expert User
OGRE Expert User
Posts: 847
Joined: Tue Apr 12, 2005 2:35 pm
Location: Albacete - Spain
x 87

Re: Optimizing Away the Use of Strings as Handles

Post by Xavyiy »

Hi all!

Sorry if I'm saying something repeated or out of contest, this thread is quite big and I haven't followed it in detail. I'm writting these lines motivated by this twitter stream: https://twitter.com/davidjrogers/status ... 9357824000 (Almost all is in here, I'm just putting things in order in this post)

Well, let's start. The whole post is about how to identify objects in a smart, clean, easy and consistent way across the whole API.

I would like to suggest the approach I've been using since a while in the Paradise Engine: using a templated base class for identifiable objects, and then inheriting from it for objects which needs to be identify. Let's stop talking and see some code:

Code: Select all

/*
--------------------------------------------------------------------------------
This source file is part of Paradise Utils.
Visit ---

Copyright (C) 2009 Xavier Verguín González <xavierverguin@hotmail.com>
                                           <xavyiy@gmail.com>
--------------------------------------------------------------------------------
*/

#ifndef _PUtils_Identifiable_H_
#define _PUtils_Identifiable_H_

#include "Prerequisites.h"

namespace PUtils {

	/** Template base class for identifiable classes
	 */
	template <class T>
	class Identifiable
	{
	public:
		/** Default constructor
		 */
		inline Identifiable(){}

		/** Constructor
		    @param id Id
		 */
		inline Identifiable(const T& id)
			: mId(id) {}

		/** Set id
		    @param id New id
		 */
		inline void setId(const T& id)
		{
			mId = id;
		}

		/** Get id
		    @return Id
		 */
		inline const T& getId() const
		{
			return mId;
		}

	protected:
		/// Id
		T mId;

	};

	/// Identifiable types
	typedef Identifiable<int16> int16Identifiable;
	typedef Identifiable<int32> int32Identifiable;

	typedef Identifiable<uint16> uint16Identifiable;
	typedef Identifiable<uint32> uint32Identifiable;

	typedef Identifiable<STDString> strIdentifiable;

}

#endif
One time you've and idea of what the base class looks like, let's continue, then SceneNodes (maybe Nodes) and MovableObjects should inherit from them (and all identifiable objects: materials, gpu programs, etc), something like this:

Code: Select all

namespace PEngine {

	/** Node class
	 */
	class PEngineDllExport Node : public PUtils::Serializable, public PUtils::uint32Identifiable
	{
	public:
Depending of the nature of the resource, we'll be using uint32Identifiable or strIdentifiable classes (or ever a uint64Identifiable, if we want to warrant MMORPGs compatibility, just kidding, 2^32 is more than enough :P). The point is only using strIdentifiable for resources which really needs unique names (since the final goal is improving performance!), maybe physical resources like textures, materials and GPU programs. For nodes and movable objects uint32 ids are perfect.

How to generate/assign the id? easy: in the creator class, SceneManager for nodes and in factories for movable objects. Some important reflexions:
  • Ids are generated by an auto-incremental var stored in the creator class: object->setId(mNextId++);
  • Use unique ids at movable object level: even if entities and billboard sets (for example) could have the same ids since them are from different factories, it could be quite confusing having movable object ptrs and having duplicated ids for different movable objects. I suggest one unique id at movable object level, maybe stored (the mNextId var) as a static var in the MovableObject class (although I'm not very friend of static vars, hehe)
  • Movable objects and nodes would continue having a name variable, but just optional and for lookup operations: if we've two nodes with the same name, we just return the first reference. Internally all is stored in maps (or whatever) based on the unique id.
Some code regarding this last point:

Code: Select all

/** Create node
		    @param name Node name
			@return Node
			@remarks For properly remove the created node, use WorldSystem::destroyNode(...).
					 Use Scene::createNode(...) to create a Node with an unique associated PUtils::uint32Identifiable id.
		 */
		Node* createNode(const PUtils::STDString& name = "");

		/** Get node by name
		    @param name Node name
			@return The node pointer or NULL if the node is not found
			@remarks Multiple nodes are allowed to have the same name. The returned node will 
					 be the first result
		 */
		Node* getNode(const PUtils::STDString& name);

...

/** Create light
		    @param lt Light type
		    @param name Light name
			@return Light
			@remarks For properly remove the created light, use WorldSystem::destroyLight(...).
					 Use Scene::createLight(...) to create a Light with an unique associated PUtils::uint32Identifiable id.
		 */
		Light* createLight(const Light::LightType& lt, const PUtils::STDString& name = "");

		/** Get light by name
		    @param name Light name
			@return The light pointer or NULL if the light is not found
			@remarks Multiple lights are allowed to have the same name. The returned light will 
					 be the first result
		 */
		Light* getLight(const PUtils::STDString& name);

...etc
What are the advantages of using a base class for identifiable objects?
  • Consistent interface across the whole API: smart, clean, easy
  • Being able to store ptrs to identifiables, useful in some cases!
  • Since the base class is a templated one, we can still to use the same interface even for different type of ids: uint32, String, ... easily.
Hope this helps!

Xavier
bstone
OGRE Expert User
OGRE Expert User
Posts: 1920
Joined: Sun Feb 19, 2012 9:24 pm
Location: Russia
x 201

Re: Optimizing Away the Use of Strings as Handles

Post by bstone »

That still doesn't answer the main question: why would I want to deal with uint32 identifiers if I can simply use pointers to the objects I need and bypass costly map lookups or extra memory wasted for vectorized object lists (just for the sake of mapping IDs to objects) altogether? Don't forget that handles/IDs will also cut off the type information down to the base class (as exposed by the container you would query an object from by handle/ID). That will force unnecessary static casts (i.e. type errors delayed till the run time, nasty) in places where storing a properly typed pointer would do the justice.

I only buy the whole idea of handles as long as the main goal is to keep the string based client code compatible with the update API that would also let the users deal with faster ID types (but even that would still negatively affect performance because even simpler IDs would need to be mapped back to pointers, albeit faster than strings). From what has been said already in this and related threads the general consensus is that trading strings for better performance is the way to go.

Xavyiy, can you share your experience in that respect? What made you develop your Identifiable<T> in the first place? I guess it wasn't scene management you've been tackling but rather serialization or interfacing with plugins, was it?
User avatar
syedhs
Silver Sponsor
Silver Sponsor
Posts: 2703
Joined: Mon Aug 29, 2005 3:24 pm
Location: Kuala Lumpur, Malaysia
x 51

Re: Optimizing Away the Use of Strings as Handles

Post by syedhs »

bstone wrote:That still doesn't answer the main question: why would I want to deal with uint32 identifiers if I can simply use pointers to the objects I need and bypass costly map lookups or extra memory wasted for vectorized object lists (just for the sake of mapping IDs to objects) altogether? Don't forget that handles/IDs will also cut off the type information down to the base class (as exposed by the container you would query an object from by handle/ID). That will force unnecessary static casts (i.e. type errors delayed till the run time, nasty) in places where storing a properly typed pointer would do the justice.
You are correct. In fact, when I first encountered Ogre, I noticed 'name' being used quite everywhere and I first thought, why not just assign the pointer to a variable (and it is guaranteed unique!) in 'init' for an example, and then use the variable everywhere else? If the reason for maintaining id/name is convenience, then it shoudn't come with performance cost. It is just a little convenience - so I vote to just remove name or any id altogether. It makes things simpler and faster.

And another, if you still need the name for identification purpose, then create your own implementation - application level that is not Ogre level. It is suffice to probably create your own function myCreateEntity and in it, you simply call SceneManager::createEntity and use the map<Strring, pointer) to store the name association.
A willow deeply scarred, somebody's broken heart
And a washed-out dream
They follow the pattern of the wind, ya' see
Cause they got no place to be
That's why I'm starting with me
bstone
OGRE Expert User
OGRE Expert User
Posts: 1920
Joined: Sun Feb 19, 2012 9:24 pm
Location: Russia
x 201

Re: Optimizing Away the Use of Strings as Handles

Post by bstone »

syedhs wrote:And another, if you still need the name for identification purpose, then create your own implementation - application level that is not Ogre level. It is suffice to probably create your own function myCreateEntity and in it, you simply call SceneManager::createEntity and use the map<Strring, pointer) to store the name association.
Exactly, that's why I mentioned the same thing earlier in this thread.

My understanding is that the name based API was either influenced by some other engine of the days when Ogre was born or was deemed more convenient (e.g. if you now a name of the mesh you can spawn entities with that mesh anywhere in your code without bothering too much about where the mesh pointer is, etc.). The funny thing though is that any experienced coder will keep a constant/variable with the name of the mesh anyway to avoid issues with mistyping that name in different places. And that's basically your pointer variable if Ogre had used pointers. I can see the slight benefit of a constant over a variable (stateless, easier to access) but it's certainly not worth losing that associated bit of performance.
User avatar
Klaim
Old One
Posts: 2565
Joined: Sun Sep 11, 2005 1:04 am
Location: Paris, France
x 56
Contact:

Re: Optimizing Away the Use of Strings as Handles

Post by Klaim »

That would imply to separate the resource system from the resource script system, make the later optional and make it hold the strings of the loaded resources?
bstone
OGRE Expert User
OGRE Expert User
Posts: 1920
Joined: Sun Feb 19, 2012 9:24 pm
Location: Russia
x 201

Re: Optimizing Away the Use of Strings as Handles

Post by bstone »

Klaim wrote:That would imply to separate the resource system from the resource script system, make the later optional and make it hold the strings of the loaded resources?
1. It already holds the names of the loaded resources.

2. The resource system is not what's causing the ~8% performance loss and using strings to identify resources during the application loading/initialization stage totally makes sense.

The main point is that everything else can live without referencing the names after that. If you absolutely need the names (to expose them to your scripting engine maybe) then you can create a map< string, resource/entity/whatever> and use it, but it doesn't have to slow down the rendering engine right from the start.

I can't remember how the resource system popped up in this thread btw. It's not what was discussed initially under the proposed optimizations. Maybe that confused some people. So once again, there's no sense in removing strings from the resource system, submeshes, bones, etc. Let them provide a way to look the related objects up by name for convenience, but never use that internally in the engine except some basic initialization steps, but never every frame.
User avatar
Klaim
Old One
Posts: 2565
Joined: Sun Sep 11, 2005 1:04 am
Location: Paris, France
x 56
Contact:

Re: Optimizing Away the Use of Strings as Handles

Post by Klaim »

Sorry, just forgot about that. I think it's the way the resource system was written initially that incited using names in all systems (like, keeping the different system looking alike).

Anyway for entities and the rest, you're right. In my current code I only use the associated smart pointers.
bstone
OGRE Expert User
OGRE Expert User
Posts: 1920
Joined: Sun Feb 19, 2012 9:24 pm
Location: Russia
x 201

Re: Optimizing Away the Use of Strings as Handles

Post by bstone »

One other advantage of using pointers that I didn't mention earlier - you can use them directly in unordered sets (gaining faster search time compared to strings) to reduce object lists maintenance overhead, but even more important is the fact that with pointers Ogre could use an implementation of intrusive lists that would beat even unordered sets in add/insert/remove operations performance. If that is implemented then I expect the total performance gain being even greater. And you absolutely can't do anything like that with strings. You could sort of pull that off with handles wrapping the strings but that would mean one extra level of indirection and is meaningless if you can use pointers anyway.
User avatar
Xavyiy
OGRE Expert User
OGRE Expert User
Posts: 847
Joined: Tue Apr 12, 2005 2:35 pm
Location: Albacete - Spain
x 87

Re: Optimizing Away the Use of Strings as Handles

Post by Xavyiy »

Xavyiy, can you share your experience in that respect? What made you develop your Identifiable<T> in the first place? I guess it wasn't scene management you've been tackling but rather serialization or interfacing with plugins, was it?
Yes, your're right in the whole post: my final goal for the Idenfiable part is allow the -end- user to track nodes and spatials in the scripting part. From an Ogre point of view, it's not absolutely needed I think.

For debugging/identification, the user could always set the node/monableObject name property by hand and then watch it in the debugger or use it in its final app. Not as an unique identifier, just like any other object property! (or completely remove the name property and do it via setAny, but that would be more complicated for debugging purposes I guess).

On this last point, the end user always could create its own tracking implementation, like syedhs has said, and like I've done in my personal engine. But thinking it again: ogre could be totally agnostic to this, and just working with ptrs.

As the last posts claims, storing the ptrs in a vector or equivalent is enough from the Ogre point of view. About breaking or not the current string-id interface: I would vote for breaking it, it's time to change some obsolete parts of the Ogre API and this change looks like a good start, even more if it really saves the 8% of time!

That said, I would not remove the string-id interface for script/phisical resources: materials, textures, GPUPrograms, etc. Maybe we can enhance the internal part by doing the internal per-frame updates using hashes rather than string comparisons (if there is any kind of internal per-frame update in these kind of resources, I haven't checked that part of Ogre since a long time ago), but I think string-ids for resources are natural and more than correct.

Xavier
bstone
OGRE Expert User
OGRE Expert User
Posts: 1920
Joined: Sun Feb 19, 2012 9:24 pm
Location: Russia
x 201

Re: Optimizing Away the Use of Strings as Handles

Post by bstone »

Thanks for confirming my thoughts. I totally agree about resources here, see my previous post.
Post Reply