Optimizing Away the Use of Strings as Handles

[dark_sylinc]

I'm strongly against ptrs instead of handles.

Reasons:

• It's not unique. The same object can be referenced through multiple addresses. This is perfectly valid.
• Determinism goes to hell. Games relying on determinism no longer are guaranteed to be processed in the same order on each run. Edit: If combined with ordered sets.
• Correctness: Using a pointer once it has been freed is undefined behavior in C++. Even something innocent-looking as "if( freedPtr != otherValidPtr )" is undefined behavior (not just "*accessing" to it)
• Safety: We're forcing the user to store ptrs instead of handles. While this isn't a problem for advanced users, rookie users have a high chance of still having a ptr copy somewhere in his code after destroying the entity. Having a handle instead is safe and trying to find the entity it is linked to will return null ptr (instead of having a dangling one). Remember, someone has to deal with rookie users in the forum. Granted, they can still make this mistake, but at least we're not encouraging them to.

Uniqueness, Guaranteed determinism & Correctness while using ptrs would require an extra layer of memory management (which btw. could be a good idea, i.e. Havok does this* very well) while trading the safety for the small overhead (4 bytes) of the handle.
*The difference with Havok is that they can, to certain degree, assume it's users are experts. The original full license was waaay expensive and they have a thousand page manual.

Btw. int handles have small overhead (4-8 bytes, preallocated) while the problem here is that name handles have a huge overhead (minimum 12 bytes + dynamically allocated string without max limit)

And no, using a handle doesn't mean we need an std::map<int, Entity> at all. We can either:

• Use std::find( vector.begin(), vector.end(), HandleCmp() ); for linear search
• Use vector.insert( std::lower_bound( vector.begin(), vector.end(), HandleCmp() ) ); for having std::set like O(log(n)) search by keeping the vector ordered

Of course, HandleCmp is just a function that compares "arg1->m_id == arg2->m_id"

[bstone]

Thanks dark_sylinc. I'm glad you've found some time to share your concerns and those are some strong points, but let's look at them one by one.

It's not unique. The same object can be referenced through multiple addresses. This is perfectly valid.

That's only true when virtual inheritance is involved. In other cases it is guaranteed that the object accessed via a typed pointer will always have the same address, e.g. if the scene manager operates on Ogre::Entity* then the one and the same entity will always have the same address even if you have, say, MyEntity that inhertis from Ogre::Entity and MyCoolStuff at the same time. MyCoolStuff* and Entity* values for the same instance of MyEntity will have different values but from the perspective of the scene manager and its clients the Ogre::Entity* values will be unique and consistent.

Virtual inheritance would be problematic but let's be reasonable - the current Ogre's architecture doesn't even allow users to inject Ogre::Entity derivatives of their own. This is strictly controlled by the Ogre::SceneManager implementations. I don't think I will ever see a scene manager with entities or moveables or anything else using virtual inheritance, that's too much overhead even by the modest OOP standards and then there's the movement towards the data oriented design in 2.0! So having this minor restriction on Ogre's internals should be sensible. We're after performance here after all.

Casting pointers to void* and back will be problematic, but that a very bad idea no matter what.

Determinism goes to hell. Games relying on determinism no longer are guaranteed to be processed in the same order on each run. Edit: If combined with ordered sets.

That would have been a very good point if Ogre had been a game engine with responsibilities covering managing game objects and their state. Relying on the rendering engine to keep and maintain a deterministic something is rather questionable. Even now it's not really deterministic in some aspects.

Correctness: Using a pointer once it has been freed is undefined behavior in C++. Even something innocent-looking as "if( freedPtr != otherValidPtr )" is undefined behavior (not just "*accessing" to it)

Doesn't differ a single bit from a uint handle: "if( freedHandle != otherValidHandle )" is undefined just as well if you like to call it that way.

Safety: We're forcing the user to store ptrs instead of handles. While this isn't a problem for advanced users, rookie users have a high chance of still having a ptr copy somewhere in his code after destroying the entity. Having a handle instead is safe and trying to find the entity it is linked to will return null ptr (instead of having a dangling one). Remember, someone has to deal with rookie users in the forum. Granted, they can still make this mistake, but at least we're not encouraging them to.

Well, that's debatable to some extent. The rookie users certainly feel better with named objects and strings, yet the performance hit is severe and we've seen a good deal of support for the idea of switching to something else. Why would you want to impose another hit for requiring the client code too look an entity up instead of using a direct pointer then?

Furthermore, having seen quite a few posts from the rookie users who bumped into that kind of issues I can tell that in 99% cases there will be no big difference, i.e.

Code: Select all

    // somewhere deep in the rookie's code

    Entity* m_player; // dangling or being other garbage
    m_player->setMaterial( m_glowingFire );

a related forum post would be:

Help, I tried a tutorial with a few changes and I've got "Error: ACCESS_VIOLATION 0xC0000005". What could be the problem?

Now the same scenario with handles:

Code: Select all

    // somewhere deep in the rookie's code

    Handle m_player; // dangling or being other garbage
    m_sceneManager->getEntity( m_player )->setMaterial( m_glowingFire );

a related forum post would be:

Help, I tried a tutorial with a few changes and I've got "Error: ACCESS_VIOLATION 0xC0000005". What could be the problem?

And having handles would make it super easy for a rookie to pass a handle to a material instead of an entity to the scene manager, unless we have more sophisticated handle types to fight that. That possibility alone would blow up the support forums for good

But even without all that let's keep in mind that v1.7 of Ogre already exposed many methods for dealing with pointers instead of names and then v1.8 pushed that even further. So that tendency was underway already, and for a good reason.

Uniqueness, Guaranteed determinism & Correctness while using ptrs would require an extra layer of memory management

I believe I've addressed Uniqueness. It's still not clear what Guaranteed Determinism in the render pipeline pointers could affect negatively if at all. If you have examples please share. I personally question your approach to Correctness but others might not of course. Yet handles are subject to the same flaws in that regard as those you brought up for the pointers.

And no, using a handle doesn't mean we need an std::map<int, Entity> at all. We can either:

• Use std::find( vector.begin(), vector.end(), HandleCmp() ); for linear search
• Use vector.insert( std::lower_bound( vector.begin(), vector.end(), HandleCmp() ) ); for having std::set like O(log(n)) search by keeping the vector ordered

Of course, HandleCmp is just a function that compares "arg1->m_id == arg2->m_id"

That would be perfectly legit if the ordered vector were static. But let's consider a scene with entities being added, then temporarily removed, then added back (it's the recommended way to hide entities from the scene btw). How large would the cost of maintaining the ordered vector be then? It would be even larger than for a map! And vectors would suffer from reallocating and copying large amounts of data when the reserved size gets exhausted anyway.

That's not even a tad closer to the performance of an intrusive list if you ask me.

[Wolfmanfx]

I think most people talk about different things here:

1) Handle could be defined as an index into a non-relocatable table(Jason Gregory)
And could be used as a reliable way to reference objects. But which kinds of objects are not reliable reference able? Think of an data structure which gets fragmented over time and you need to defragment (relocate) it than every pointer you hold into this data-structure can or gets invalid and you could point to a garbage address but a handle will still keep valid after such an operation.
Or another example is when you serialize a complex data-structure like a graph and want to deserialize it in way that all pointers point to an valid node (internally) then handles are the way to go. (Usually such deserialization is done in two passes)
A last one is also scripting where you can expose your objects easily via handles instead of ptr's.
No invalid or stale pointers.

2) Topic are string hashes (which are also great!)
I think this makes a lot sense to minimize runtime overhead in areas like the script compiler / material system where we can use compiletime hashing for const strings and runtime hashing when we do the actual comparison - I mean we pass a string into a function that gets then hashed when a comparison is made (and at best the calculated hash could be cached until the content changed).

3) Keep string id's intact but go and hash them as int64 hashes and minimize the comparison overhead inside the library .

I think i missed a few hybrid's of them but anyway that does not matter

Here are just my thoughts / opinions:
* Ogre should remove the complete naming from Node/SceneNode/MovableObject/Entity/Bone
* For the scene graph itself we could rely on simple pointers (as long we do not do any defragmentation stuff)
* For entities / bones /... and stuff like that i would create a HandleClass which is responsible for holding the id's and making the lookups ->
think of a cheap smart pointer where it acts like a proxy so the user can call the entities method's as before (but its not)
* For gods sake we need our own string impl which enable us good runtime hashing + compile time hashing (macro magic) this could be used to replace the actual string comparison's and after that we can still take a look if we need it at all.

[bstone]

Think of an data structure which gets fragmented over time and you need to defragment (relocate) it than every pointer you hold into this data-structure can or gets invalid and you could point to a garbage address but a handle will still keep valid after such an operation.

Yep, that's what I expected to hear initially as that's the classic problem solved by handles. But you won't find anything like that in Ogre now and I wouldn't expect to find anything like that in the future because of the nature of a rendering pipeline and related performance hits.

Or another example is when you serialize a complex data-structure like a graph and want to deserialize it in way that all pointers point to an valid node (internally) then handles are the way to go. (Usually such deserialization is done in two passes)

I don't buy that one I have a one-pass serialization protocol working with pointers and saving/restoring complex graphs with cycles without any issues, Boost has a very capable implementation too.

A last one is also scripting where you can expose your objects easily via handles instead of ptr's. No invalid or stale pointers.

I don't see any difference here. Unreferencing an invalid handle would kill it equally bad as using an invalid pointer unless you pepper the entire code base with run-time checks against invalid handles. But most importantly, is that really a consideration for a rendering engine?

I think this makes a lot sense to minimize runtime overhead in areas like the script compiler / material system where we can use compiletime hashing for const strings and runtime hashing when we do the actual comparison - I mean we pass a string into a function that gets then hashed when a comparison is made (and at best the calculated hash could be cached until the content changed).

I haven't dig into the compile time hashing but from what I've heard so far it doesn't preserve the original string values which makes collisions fatal. That could be an interesting area to explore otherwise.

[Wolfmanfx]

As usual this needs to be profiled if a real gain happens.

Scripting - if your handle acts like a smart pointer you could ask if its null for example.

Regarding serialzation i did back in 2004 in C++ without boost (for the automotive industry) also 2 years ago in c# there is the problem where the language offers methods to setup correct pointers / references.
But anyway give it a thought how it could work when you implment it your self - again thats just my experiance

[Wolfmanfx]

Just thought if we get the ogre lib smaller when we get rid of all static strings inside the core.

[dark_sylinc]

It's not unique. The same object can be referenced through multiple addresses. This is perfectly valid.

That's only true when virtual inheritance is involved. In other cases it is guaranteed that the object accessed via a typed pointer will always have the same address, e.g. if the scene manager operates on Ogre::Entity* then the one and the same entity will always have the same address even if you have, say, MyEntity that inhertis from Ogre::Entity and MyCoolStuff at the same time. MyCoolStuff* and Entity* values for the same instance of MyEntity will have different values but from the perspective of the scene manager and its clients the Ogre::Entity* values will be unique and consistent.

**Sigh** I wasn't talking about virtual inheritance, but rather virtual address mapping. Two virtual addresses mapping to the same physical address.

Determinism goes to hell. Games relying on determinism no longer are guaranteed to be processed in the same order on each run. Edit: If combined with ordered sets.

That would have been a very good point if Ogre had been a game engine with responsibilities covering managing game objects and their state. Relying on the rendering engine to keep and maintain a deterministic something is rather questionable. Even now it's not really deterministic in some aspects.

It's still important, and helps narrowing bugs A LOT.
Furthermore, there are certain components that may be important for the game engine using Ogre, for example the Game engine depending on the results of the skeletal animation.

Correctness: Using a pointer once it has been freed is undefined behavior in C++. Even something innocent-looking as "if( freedPtr != otherValidPtr )" is undefined behavior (not just "*accessing" to it)

Doesn't differ a single bit from a uint handle: "if( freedHandle != otherValidHandle )" is undefined just as well if you like to call it that way.

You're not getting what I meant.
Being a Handle an uint32, freedHandle is still an integer; and hence it is a well defined operation by the C++ standard. However freedPointer isn't, because pointers aren't integers (even though for x86 hw implementation in a flat memory model, pointers are integers; but this isn't guaranteed)

Furthermore, having seen quite a few posts from the rookie users who bumped into that kind of issues I can tell that in 99% cases there will be no big difference, i.e.

Code: Select all

    // somewhere deep in the rookie's code

    Entity* m_player; // dangling or being other garbage
    m_player->setMaterial( m_glowingFire );

No, that code WITH LUCK will get an access violation 0xC0000005. Because m_player is dangling.

Code: Select all

    Handle m_player; // dangling or being other garbage
    m_sceneManager->getEntity( m_player )->setMaterial( m_glowingFire );

No, that code will always produce a C++ exception, that resource associated with m_player couldn't be found, because m_glowingFire is just an int.
Or we can avoid raising a C++ exception, and get an access violation 0xC0000005 for trying to read a null ptr. But it is guaranteed to always fail; but your first example with pointers instead of handles is not guaranteed.

It's still not clear what Guaranteed Determinism in the render pipeline pointers could affect negatively if at all.

Guaranteed determinism is very important for some games (Often but not limited to RTS). It's also very useful to playback sessions in the hunt for bugs, as well as having a bug consistently behaving the same way every time you attempt to debug it.

I personally question your approach to Correctness but others might not of course. Yet handles are subject to the same flaws in that regard as those you brought up for the pointers.

I you understand what's wrong in the following code, you'll understand what I'm talking about:

Code: Select all

int *myPtr = new int[10];
std::vector<int*> myPointers;
for( int i=0; i<myPointers.size(); ++i )
   myPointers[i] = myPtr + i;

delete myPtr;
int *oldBase = myPtr;
int *newBase= new int[10];

//Update the new locations in memory
for( int i=0; i<myPointers.size(); ++i )
   myPointers[i] = (myPointers[i] - oldBase[i]) + newBase;

I just happened to write code similar to this (where an alternate correct solution wasn't as obvious as straightforward as it would be to fix this one).

And no, using a handle doesn't mean we need an std::map<int, Entity> at all. We can either:

• Use std::find( vector.begin(), vector.end(), HandleCmp() ); for linear search
• Use vector.insert( std::lower_bound( vector.begin(), vector.end(), HandleCmp() ) ); for having std::set like O(log(n)) search by keeping the vector ordered

Of course, HandleCmp is just a function that compares "arg1->m_id == arg2->m_id"

That would be perfectly legit if the ordered vector were static. But let's consider a scene with entities being added, then temporarily removed, then added back (it's the recommended way to hide entities from the scene btw). How large would the cost of maintaining the ordered vector be then? It would be even larger than for a map! And vectors would suffer from reallocating and copying large amounts of data when the reserved size gets exhausted anyway.

[/quote]
I'm considering addition & removal won't be too often now. Specially in that pattern (adding preexisting entities back). The cost of such maintainment is actually low, but this problem is 100% shared with ptrs anyway, because we will have to store the ptrs we've created in a vector or list of some sort. And removing the pointer from the list needs lookup, doesn't matter whether we lookup by ptr or by ptr->int.

[Knotanalt]

Here are just my thoughts / opinions:
* Ogre should remove the complete naming from Node/SceneNode/MovableObject/Entity/Bone
* For the scene graph itself we could rely on simple pointers (as long we do not do any defragmentation stuff)
* For entities / bones /... and stuff like that i would create a HandleClass which is responsible for holding the id's and making the lookups ->
think of a cheap smart pointer where it acts like a proxy so the user can call the entities method's as before (but its not)
* For gods sake we need our own string impl which enable us good runtime hashing + compile time hashing (macro magic) this could be used to replace the actual string comparison's and after that we can still take a look if we need it at all.

Yeah, pretty much all this summarizes my thoughts from the getgo.

Not to give an appeal to popularity but doesn't almost every other engine work like that?

Also you can't even just include ogre string in a file then use it in the contents, it won't compile. Pretty mindblowing when you realize at the core it's just using std string anyway. Maybe that doesn't need to be the case for every single file but at least simple stuff and certainly strings ought to work like that.

[saejox]

Here is my view as a user of Ogre on the subject.

Handles are used to ensure safety and uniqueness. Uniqueness i get, but safety?
I don't think anyone chooses C++ because it is safe to program in. Managed languages are for that not C++. Most of the C++ users feel dirty using even shared_ptr because it tries to lock a mutex and cache miss with reference count.
Even if i had unique and safe handles i would still use raw pointers. Why? because i know my data is just one indirection away. Thankfully Ogre doesn't move or delete my scenenodes/entities behind my back.
I know practically everyone uses ids/names for they their game objects, but that doesn't mean ogre should supply them.

Yeah, i know most of you wrote this already, but whatever i love Ogre and i couldn't help myself

[bstone]

**Sigh** I wasn't talking about virtual inheritance, but rather virtual address mapping. Two virtual addresses mapping to the same physical address.

I think it's a far stretch. Any real-life or even imaginary example where Ogre would have to deal with that? I admit that I'm not a guru when it comes to console/mobile development but does any of the non-Intel platforms supported by Ogre impose anything like that?

I certainly don't see that happening on an Intel platform. If it's something artificial like virtual paging, why should that affect Ogre? Would that be justified somehow if it does?

It's still important, and helps narrowing bugs A LOT.
Furthermore, there are certain components that may be important for the game engine using Ogre, for example the Game engine depending on the results of the skeletal animation.

Yes, I can relate to that but does it mean we should also drop all the ideas about threading Ogre's internals? Otherwise the precious determinism is definitely at stake.

You're not getting what I meant.
Being a Handle an uint32, freedHandle is still an integer; and hence it is a well defined operation by the C++ standard. However freedPointer isn't, because pointers aren't integers (even though for x86 hw implementation in a flat memory model, pointers are integers; but this isn't guaranteed)

First, I can't agree to that. The C++ standard is quite explicit about pointer equality and relational operations. They are well defined:

5.10.1. ... Two pointers of the same type compare equal if and only if they are both null, both point to the same function, or both represent the same address.

That clearly means that on platforms where freedPointer doesn't represent an address anymore the equality operation will return false. The operation is thus well defined for freed/invalid pointers. You can't count on its result for any practical purpose but it won't throw, cause a segfault, etc.

There's only one exception for the pointer equality operator where the result is unspecified by the standard:

5.10.2. ... Otherwise if either is a pointer to a virtual member function, the result is unspecified.

Second, comparing a freed pointer is a bug just like dereferencing it and it shouldn't happen in a correctly working software. So the whole argument seems a bit pointless to me.

No, that code will always produce a C++ exception, that resource associated with m_player couldn't be found, because m_glowingFire is just an int.
Or we can avoid raising a C++ exception, and get an access violation 0xC0000005 for trying to read a null ptr. But it is guaranteed to always fail; but your first example with pointers instead of handles is not guaranteed.

You have a point but for practical purposes where's no difference between the 99.999% chance to fail and 100% chance to fail. What about the platforms without branch prediction? Checking handles in every operation wouldn't be justified on those.

And finally I will agree with saejox. It's C++, not C# or visual basic. Guarding users from pointer related mistakes is very counter productive to me.

Guaranteed determinism is very important for some games (Often but not limited to RTS). It's also very useful to playback sessions in the hunt for bugs, as well as having a bug consistently behaving the same way every time you attempt to debug it.

Can't argue with that but see your Ogre 2.0 manifest. Threading kills it.

I you understand what's wrong in the following code, you'll understand what I'm talking about:

Code: Select all

int *myPtr = new int[10];
std::vector<int*> myPointers;
for( int i=0; i<myPointers.size(); ++i )
   myPointers[i] = myPtr + i;

delete myPtr;
int *oldBase = myPtr;
int *newBase= new int[10];

//Update the new locations in memory
for( int i=0; i<myPointers.size(); ++i )
   myPointers[i] = (myPointers[i] - oldBase[i]) + newBase;

I just happened to write code similar to this (where an alternate correct solution wasn't as obvious as straightforward as it would be to fix this one).

The code will do nothing because myPointers is always empty but I see your point. It's flawed logic - you can do all sort of awkward things with handles too, believe me (e.g. the type safety problem I mentioned).

I'm considering addition & removal won't be too often now. Specially in that pattern (adding preexisting entities back). The cost of such maintainment is actually low, but this problem is 100% shared with ptrs anyway, because we will have to store the ptrs we've created in a vector or list of some sort. And removing the pointer from the list needs lookup, doesn't matter whether we lookup by ptr or by ptr->int.

What about intrusive lists? They make both arguments irrelevant - no need to maintain vectors/lists, removing the pointer needs no lookups, saves the extra indirections too.

[bstone]

Just thought if we get the ogre lib smaller when we get rid of all static strings inside the core.

I believe getting rid of depending on RTTI in Ogre will gain much more in terms of ogre lib size. But removing static strings would certainly help a bit too.

[Knotanalt]

Threading shouldn't affect material/rendering task determinism which hopefully is what he's talking about. Not sure that is something to care about though. True determinism for whole program is impossible anyway, you can't be sure you always get exact same memory layout etc.

[bstone]

No the major concern was about things that could affect the game state, like animated skeletons, etc. Materials and other pure rendering stuff is out of question here.

If we think about animation then the problematic part is any code that subscribes to animation/frame events, i.e. if that code depends on the order of events between different animations. That's one thing I see that could require deterministic behavior between runs. But I'm not even convinced that pointers would do any harm here - animations would be processed in the order they are stored in (i.e. added to) animation lists. Pointers change nothing in that regard compared to handles.

But threading kills any determinism there for real. And animations are one of the things that could benefit from threading tremendously.

Furthermore, if we go for threading then animations event system will require an overhaul because we won't be able to trigger animation events from the animation worker threads anymore (w/o serious restrictions on the listening code).

So with threading we'll either have to deal with deterministic order of events here (e.g. by queuing them up and then applying a deterministic order to them before dispatching on the main thread) or drop that guarantee altogether.

[Kojack]

If you aren't enforcing a fixed render rate then animation is already non deterministic. Slight variations in performance will cause animations to end on different frames.
Deterministic render order can be controlled using render queue priorities. Deterministic order of animation updates or scene node updates... I don't see where that will make a difference. Animations don't have a dependency on each other. (Plus one of the plans for ogre 2.0 was to move the animation system to a higher level instead of being embedded in the core engine anyway). Scene node update order is still going to be based on the hierarchy depth, sibling nodes or nodes in other branches won't affect each other based on order.

While multiple addresses in virtual space might might to the same physical address, under which circumstances will the scene manager give us two different pointers that actually refer to the same scene node? How would a handle prevent this? If returning a pointer from the scene manager is unsafe then how is a handle stopping this from happening internally, and does that mean that ogre has been broken for years, since it provides pointer based access?


While I haven't spent much time thinking about it, my initial idea would be remove names from nodes, movableobjects and similar, use pointers to handle them internally, but provide a mapping of names to pointers inside of the scene manager for use by the user if desired. So a scene node with no name or handle takes no extra storage.

good runtime hashing + compile time hashing (macro magic)

If we were writing Ogre in D that would be easy, it's compile time processing is crazy powerful. I once wrote a brainf**k string parser to D source generator that worked at compile time.

[Klaim]

If we were writing Ogre in D that would be easy, it's compile time processing is crazy powerful. I once wrote a brainf**k string parser to D source generator that worked at compile time.

Actually it's easier with C++11 using constexpr but we can't rely C++11 for Ogre AFAIK (at least not for immediately coming versions).

[Kojack]

True, constexpr is pretty cool, but nowhere near the power of D's compile time processing. But that's getting a bit off topic.

[Klaim]

True, constexpr is pretty cool, but nowhere near the power of D's compile time processing. But that's getting a bit off topic.

Agreed twice.

[/offtopic]

[dark_sylinc]

I certainly don't see that happening on an Intel platform. If it's something artificial like virtual paging, why should that affect Ogre? Would that be justified somehow if it does?

Surprise!.

Yes, I can relate to that but does it mean we should also drop all the ideas about threading Ogre's internals? Otherwise the precious determinism is definitely at stake.

All the multithreading solutions I've proposed for Ogre 2.0 guarantee determinism. It's true that by nature single threaded solutions tend to be deterministic, while multi-threaded solutions tend to be chaotic. But this doesn't mean it's impossible, as long as certain precautions are made.

You're not getting what I meant.
Being a Handle an uint32, freedHandle is still an integer; and hence it is a well defined operation by the C++ standard. However freedPointer isn't, because pointers aren't integers (even though for x86 hw implementation in a flat memory model, pointers are integers; but this isn't guaranteed)

First, I can't agree to that. The C++ standard is quite explicit about pointer equality and relational operations. They are well defined:

5.10.1. ... Two pointers of the same type compare equal if and only if they are both null, both point to the same function, or both represent the same address.

I'm afraid there's more to it:

If the argument given to a deallocation function in the standard library is a pointer that is not the null pointer value (4.10),
the deallocation function shall deallocate the storage referenced by the pointer, rendering invalid all pointers referring
to any part of the deallocated storage. The effect of using an invalid pointer value (including passing it to a deallocation
function) is undefined.

Freed pointer == Invalid pointers. Invalid pointers -> can't be used. "Usage" covers dereferencing, as well as comparing with other pointers, or passing it through. This is because pointers are not integers, and integers are not pointers; and any conversions between them is implementation defined. In x86 architectures pointers are integers, which simplifies a lot (there is no "conversion" needed). But it's not a guarantee. An architecture is allowed to have special hardware & registers just to load pointers that reference to memory, and they could raise an exception if trying to use that HW with invalid pointers.
To my knowledge, all architectures I've known will behave nicely by using pointers & invalid pointers directly as integers; and this is mostly backwards compatibility with ancient tech from even before I was born. However we should aim for correctness, we don't know what will happen in the future, or even if there's an arch. detail we're unaware of. IE 6 is an extreme example of what happens when you don't aim for standard correctness.

I you understand what's wrong in the following code, you'll understand what I'm talking about:

Code: Select all

int *myPtr = new int[10];
std::vector<int*> myPointers;
for( int i=0; i<myPointers.size(); ++i )
   myPointers[i] = myPtr + i;

delete myPtr;
int *oldBase = myPtr;
int *newBase= new int[10];

//Update the new locations in memory
for( int i=0; i<myPointers.size(); ++i )
   myPointers[i] = (myPointers[i] - oldBase[i]) + newBase;

I just happened to write code similar to this (where an alternate correct solution wasn't as obvious as straightforward as it would be to fix this one).

The code will do nothing because myPointers is always empty but I see your point. It's flawed logic - you can do all sort of awkward things with handles too, believe me (e.g. the type safety problem I mentioned).

There was a bug in the code I wrote, it should've been: myPointers = (myPointers - oldBase) + newBase;
The point was that you can't use oldBase after it has been freed, not even to do (myPointers - oldBase). It will work fine on x86 hw, but it's undefined behavior per C++ standard.

I'm considering addition & removal won't be too often now. Specially in that pattern (adding preexisting entities back). The cost of such maintainment is actually low, but this problem is 100% shared with ptrs anyway, because we will have to store the ptrs we've created in a vector or list of some sort. And removing the pointer from the list needs lookup, doesn't matter whether we lookup by ptr or by ptr->int.

What about intrusive lists? They make both arguments irrelevant - no need to maintain vectors/lists, removing the pointer needs no lookups, saves the extra indirections too.

There are alternatives. Personally I would go for a vector because iteration is what's at stake here. But there are many alternative solutions too that could work better/worse. The discussion would be about what container to use (which C++ allows us to switch between them with a simple typedef change) rather than ptr vs handle discussion.
Understanding the Second-Generation of Behavior Trees, Alex J. Champandard, 2012, is an excellent example of cache-friendly trees (which can be used for, i.e. linked lists, etc).

[bstone]

Surprise!.

Nah, not a surprise at all. As I already said - on Intel platforms that won't happen unless you cause it artificially. And the question was why Ogre would want that and whether that would be justified. Not likely that Ogre will use anything like that due to cross-platform issues to start with and ending with the common sense. Making your life harder and losing performance just because there's a possibility to map virtual address space even though that will never be used by Ogre doesn't make much sense to me.

All the multithreading solutions I've proposed for Ogre 2.0 guarantee determinism.

Can't remember anything about deterministic animations there. Will have to look once again. Sorry if I missed it.

Freed pointer == Invalid pointers. Invalid pointers -> can't be used. "Usage" covers dereferencing, as well as comparing with other pointers, or passing it through. This is because pointers are not integers, and integers are not pointers; and any conversions between them is implementation defined.

That's another stretch. "Using pointers" is not defined strictly by the standard therefore you should refer to the context of that phrase. It clearly means dereferencing and passing to the deallocation functions to me. Furthermore, relational and equivalence operations between pointers are never defined in terms of conversions between pointers and integers. To move this even further I will once again appeal to the common sense: there will be no hardware checking whether the pointer points to a freed address range before comparing it to another pointer - that is slow and futile.

And wouldn't you agree that having code that relies on comparing freed pointers is a bad smell after all?

There was a bug in the code I wrote, it should've been: myPointers = (myPointers - oldBase) + newBase;
The point was that you can't use oldBase after it has been freed, not even to do (myPointers - oldBase). It will work fine on x86 hw, but it's undefined behavior per C++ standard.

First, as I said that was flawed logic. Second, that would raise access violation right away in a debug build. If your run-time doesn't provide debug versions of malloc/free then I would definitely recommend writing and using them, real time saver.

There are alternatives. Personally I would go for a vector because iteration is what's at stake here. But there are many alternative solutions too that could work better/worse. The discussion would be about what container to use (which C++ allows us to switch between them with a simple typedef change) rather than ptr vs handle discussion.
Understanding the Second-Generation of Behavior Trees, Alex J. Champandard, 2012, is an excellent example of cache-friendly trees (which can be used for, i.e. linked lists, etc).

Yeah, iterations could easily prevail but reallocations are very expensive. Ideally that would be controllable with a compile-time directive (the simple typedef you mentioned) at least. Then you could adapt it to specific use cases. Maybe even something dynamic to make it possible having multiple scenes with different optimal access/modification patterns. But that's thinking too far ahead already.

[Knotanalt]

I guess ultimately who cares. Theoretically you could have these issues but ONLY if you caused them yourself much like the magic ring issue. Not as a user but as the engine maker.

Important things will wind up deterministic anyway, because of linear dependencies. You also haven't shown a real world example that doesn't constitute an error where handles allow determinism but pointers don't. If you don't change something's location in memory, pointers remain valid. Changing locations in memory is not something you want happening anyway so...whatever. Especially if you are talking about debugging ease, then suggesting implementing something that changes what you're pointing to behind your back (and when exactly would it be safe to do this even if you did think it was a good idea). If anything you'd do it the other way around and traversal changes but the data stays the same.

I guess handles make some sense for some things, but they really should be for true system stuff not for a scene graph. Is it locked or system object that's somehow very limited or may move around? Then handles make sense, but there's no 256 limit compiled into the kernel on nodes.

And ultimately algorithms are deterministic, not data, threads. pointers, etc. You can always guarantee it if you want but like I said you don't truly have it anyway in the first place, and ultimately due to linear dependencies the parts we might care about to be deterministic are always going to be anyway.

And the threading, for efficiency's sake it should not be 100% deterministic or you are just creating bottlenecks or yourself. Lots of stuff, who really cares. If your sort is debugged then how could you possibly care if it's deterministic, especially if it's an in place sort. Your result at the end will be the same.

[Zonder]

I don't see the issue engine uses pointers if you need handles implement them on top in your own app?

[oiram]

please review this thread:
http://www.ogre3d.org/forums/viewtopic.php?f=4&t=76985