Optimizing Away the Use of Strings as Handles

[Tiffer]

You will need hashing functions or add an operator to convert implicitely to the uint because names are mostly used in (hash)maps.
Or at least a < operator.

Yeah I just found that out, trying to find out while tr1::unordered_map won't take my hash function (which merely send out the uint uid). Technically we don't need a hashing function, the == operator should suffix, right? I'm a bit out of my element with templates, I tend to avoid them.

May I also minor suggestions:
- add a to_string() free function (like the new to_string() standard functions) that convert the id value to a String, either via it's member, or by searching in the name "database" or something;

Yeah, I already added a toString() method had to do it so that exceptions could print the id.

- change the name to something shorter as it will be used in a lot of interfaces;

Sure thing, Ogre::Id? EDIT: Or Ogre:Uid? I think Ogre::Id is more correct, since the class itself doesn't guarantee uniqueness, that's enforced by the users of the class, but w/e you like.

It's not clear to me how you intend to store the strings exactly? Have a Singleton id->name table?

The idea here is that the strings are optional and not used for comparison, a convenience to not lose the functionality. Personally I couldn't be less interested in using strings for any purpose since I prefer Ogre to be a thin layer, but since apparently some folks here like the functionality I'm trying to keep it somehow.

So the idea is simply that the Ogre::Id object holds a pointer to a string, and that pointer will be NULL by default, which means that if you are not interested in strings you are only wasting a 4 bytes in memory per id and no performance overhead at all.

[Klaim]

You will need hashing functions or add an operator to convert implicitely to the uint because names are mostly used in (hash)maps.
Or at least a < operator.

Yeah I just found that out, trying to find out while tr1::unordered_map won't take my hash function (which merely send out the uint uid). Technically we don't need a hashing function, the == operator should suffix, right? I'm a bit out of my element with templates, I tend to avoid them.

No, std::(tr1::)unordered_map is a hash-map so it needs hashing implementation for the type. Read this to see how to define one: http://en.cppreference.com/w/cpp/utility/hash
std::map requires the < operator or a custom comparison object.

The simplest way to do it is:
- define a < operator that compares the ids;
- define a hash type to work with standard containers, by simply returning the standard hash function for the value type (you can change it later when performance is needed);

- change the name to something shorter as it will be used in a lot of interfaces;

Sure thing, Ogre::Id?

Fine to me, but I'm not a team member.

It's not clear to me how you intend to store the strings exactly? Have a Singleton id->name table?

The idea here is that the strings are optional and not used for comparison, a convenience to not lose the functionality. Personally I couldn't be less interested in using strings for any purpose since I prefer Ogre to be a thin layer, but since apparently some folks here like the functionality I'm trying to keep it somehow.

So the idea is simply that the Ogre::Id object hold a pointer to a string, and that pointer will be NULL by default, which means that if you are not interested in strings you are only wasting a 4 bytes in memory per id and no performance overhead at all.

What I meant is: in case you do have a pointer to the string, how do you intend to store the string? You use a raw pointer here, which suggests it's not the id object that hold the string but just point to it. So I suppose you have a store of strings.

[Tiffer]

What I meant is: in case you do have a pointer to the string, how do you intend to store the string? You use a raw pointer here, which suggests it's not the id object that hold the string but just point to it. So I suppose you have a store of strings.

Ah don't pay attention to the fact that it was a raw pointer, it was just a prototype, I was gonna check Ogre's memory management practices later. The string would be indeed managed by the Id class.

I'm not sure about any of this of course, it's just an idea, right now I just wanna migrate Ogre::Node and see if there's any improvement. A change like this would break every plugin and application, there are ways to do it that are less radical (but Ogre would still be slower than it needs to be.)

[Tiffer]

Ok, got some results.

In the end I've merely changed the identifier from Ogre::Node from a String to a typedef Identifier that maps to an "unsigned int". This involved changes in dozens of OgreMain classes and also to the OctreeSceneManager, but it was rather straightforward.

My testbed is 900 animated characters on a screen, the testbed is totally Ogre-bound, I do nothing between renders. With the change from String to uint I get an increase in FPS of 3.6%. (From 16.4 to 17.00) I've tested over long periods of times and the FPS remains stable, the difference is clear. The only possible caveat is that I'm comparing my version against the stock Ogre binaries but I don't change any settings from the defaults that cmake-gui makes, so I'm pretty sure the configurations are identical.

And remember this is just Ogre::Node, there's other 20 classes that use string as identifiers, but the most important ones (I guess) are Node and MovableObject.

I'll change MovableObject next and see if I get further improvements. If anybody wants the code as it is just let me know.

In the meantime I think we should start seriously discussing switching to integral ids altogether. Even Ogre itself didn't use the naming for anything! Sometimes Ogre would name something, i.e: "SkyDome" or "Ogre/SceneRoot", but it never used those literals again to retrieve them.

EDIT: Corrected numbers.

[AshMcConnell]

Hi Tiffer,

Impressive increase there kudos for the test! Can I check you are using release mode - there is so much jiggery pokery* with debug mode that it may not show realistic results.

All the best
Ash

*Technical Term

[Xavyiy]

The only possible caveat is that I'm comparing my version against the stock Ogre binaries but I don't change any settings from the defaults that cmake-gui makes, so I'm pretty sure the configurations are identical.

Try to compile the non-modified ogre version for your tests, 3.6% of gain is less than what you may get when enabling certain compiler optimizations, so for having more realiable results it's very convenient not to use the precompiled SDK (which AFAIK doesn't have threading enabled, etc) but a custom build with the same CMake options than the modified one.

Btw, increase the number of nodes to about 1000. Always use a release build and try to use less animated entities in order to get about 50-60 fps.

Xavier

[Tiffer]

Yeah, tomorrow I'll make sure I use the exact same config and double check everything. Right now I'm migrating all the MovableObjects, progress is 70%.When I'm done I'll also upload the tar somewhere so you guys can double check too. I'm also skeptic of the results, don't worry.

So you are suggesting I have at least 1000 non-animated nodes, with, say, 50 animated entities or something like that in order to get it down to 60? Will do.

[Tiffer]

Hello guys, good news

So I migrated both Node and MovableObject (and their dozens of children, ofc), to "typedef unsigned int Identifier;" instead of String for handlers. Component-wise, I've only migrated OgreMain and the Octree scene manager.

This time I'm 100% sure about the benchmarking methodology. I've generated and built both stock 1.8.1 and my modified version from scratch, starting from clean cmakefiles, using the same cmake-gui configuration, and I haven't touched any property in visual studio.

My testbed consists of 900 low poly animated characters on screen, using the D3D9 renderer. I didn't change the testbed as Xavier suggested because I moved to a faster pc, and I think this framerate is high enough to be conclusive.

Results:
Stock ogre: 35.0 fps.
uint-handler ogre: 37.8 fps (+8%)

I've tried many times and the results are stable, with a variability of +/-0.2 fps, mainly because the testbed is 100% ogre-bound. That's a stable 8% improvement. Considering that only a fraction of the time should be spent by Ogre on the CPU, this is pretty huge.

Note that there are still dozens of things in Ogre that use string as handlers but I tested these two classes because it seems like they would be the important ones. Maybe materials, textures, etc would also bring a noticeable improvement?

Here's a patch, keep in mind this was just in experiment to see if it was something worth bothering about, things are done in a hackish way, I didn't even change the identifiers (uids are still called name) and the identifiers are still Const& even though they are uint (assuming that won't affect performance much for the sake of testing). If the maintainers would be interested in a serious patch, let's discuss. This is just provided in case somebody wants to try bench-marking too.

http://pastebin.com/9ed56ZkX (Apply to stock 1.8.1 source package)

EDIT: If I don't animate the characters, the improvement is only 1% (56.3 to 56.8 ) which suggests that mostly animation is affected by this.

[TheSHEEEP]

A huge thanks to you!



Such numbers and test-code are exactly what one needs for well-founded decisions.
btw. could you also upload the code you used as your test-scene?
Maybe we could also use the instancing Sample as a good testing ground for that.

[Tiffer]

btw. could you also upload the code you used as your test-scene?
Maybe we could also use the instancing Sample as a good testing ground for that.

I'm afraid it would be too complicated since it has a lot of dependencies on my code. There's nothing special about it, though, it's a lot like the instancing sample actually, just lots of characters in an array.

Also keep in mind that this breaks compatibility from current animated meshes, since the serialized skeletons contain node ids (cause bones are nodes), that now are integer instead of string, so the format changes. It's one of the things that need to be discussed. I used my own models generated with my own toolset. You may need to adapt the mesh tools to use existing meshes.

A way around it would be to change skeleton serialization to convert integer ids to/from string. Then you'd just need to make sure the nodes are numeric. Obviously long term you don't want that limitation, which means identifiers/handlers must be decoupled somehow.

EDIT: Ok, to make old skeletons compatible, undo my changes in SkeletonSerializer::writeBone and SkeletonSerializer::readBone, and instead of changing from string to int, keep using a string but convert the identifier with atoi()/itoa(), for example, or the c++ way too. But remember, your bone ids will have to be integral numbers now. Alternatively just re-generate new skeletons (recompile your export tools with the new ogre).

There are a lot of things to be done, and I could create a fork in bitbucket, but I need to know if the maintainers are open to it, and what branch to fork, etc. I would love to have a solution to get rid of strings for 1.8.2 but I know that's not the Ogre way, can we have it for 1.9?

[Tiffer]

Any interest for this from the maintainers? I'm not gonna do a pull request without knowing if a serious patch for this would be considered, I don't use mercurial currently so setting up is a bit of work. I also would like to know what branch I could use.

[CABAListic]

Considered, definitely, though I can't promise it would be applied. The general consensus is to rework Ogre's use of string handles, but there may be more than one way to do that, and we haven't settled on a particular approach.
Given that you've already done your work, it would be a waste not to present it

The most appropriate branch would be v2-0. I'm afraid it's a little too late for v1-9, given the impact of the changes.

[Tiffer]

Ok, that's all I wanted to know

May clean it up a little and make a fork of the 2-0 branch then.

If any of the Ogre experts reading this has suggestions of other things that are slow in Ogre I would love to hear them to potentially trying changing them and adding them to this patch.

[vitefalcon]

I have a TMP implementation of, what I call, HashString. In fact, the name comes from this article. The code is given below. Maybe it could be of some help.

HashString.h

Code: Select all

#pragma once
#ifndef _HASH_STRING_H
#define _HASH_STRING_H

#include <string>

#define _HASHSTRING_STORE_STRING 1

#define _HASHSTRING_FNV_OFFSET  2166136261u
#define _HASHSTRING_FNV_PRIME   16777619u

template <size_t N, size_t I>
struct FnvHash
{
    inline static size_t Hash(const char (&str)[N])
    {
        return (FnvHash<N, I-1>::Hash(str) ^ str[I-1])*_HASHSTRING_FNV_PRIME;
    }
};

template <size_t N>
struct FnvHash<N, 0>
{
    inline static size_t Hash(const char (&str)[N])
    {
        (void)str;
        return _HASHSTRING_FNV_OFFSET;
    }
};

/**
  * A class that stores strings as a hash.
 **/
class HashString
{
public:
    struct ConstCharWrapper
    {
        inline ConstCharWrapper(const char* str)
            :str(str){}

        const char* str;
    };

    HashString()
        : mHash(FnvHash<1,0>::Hash(""))
    {
    }

    template <size_t N>
    inline HashString(const char (&str)[N])
        : mHash(FnvHash<N,N-1>::Hash(str))
#if _HASHSTRING_STORE_STRING
        , mString(str)
#endif
    {
    }

    // Run-time hashing
    explicit HashString(ConstCharWrapper str);

    ~HashString();

#if _HASHSTRING_STORE_STRING
    inline const std::string& str() const
    {
        return mString;
    }
#endif // _DEBUG

    inline bool empty() const
    {
        return _HASHSTRING_FNV_OFFSET == mHash;
    }

    inline void swap(HashString& other)
    {
        std::swap(mHash, other.mHash);
#if _HASHSTRING_STORE_STRING
        mString.swap(other.mString);
#endif //_DEBUG
    }

    inline bool equals(const HashString& rhs) const
    {
        return mHash == rhs.mHash;
    }

    inline bool operator == (const HashString& rhs) const
    {
        return equals(rhs);
    }

    inline bool operator != (const HashString& rhs) const
    {
        return !equals(rhs);
    }

    inline HashString& operator = (const HashString& rhs)
    {
        HashString(rhs).swap(*this);
        return *this;
    }

    inline size_t hash() const
    {
        return mHash;
    }

    inline bool operator < (const HashString& rhs) const
    {
        return mHash < rhs.mHash;
    }

    friend std::ostream& operator << (std::ostream& stream, const HashString& str)
    {
#if _HASHSTRING_STORE_STRING
        return stream << str.mString;
#else
        return stream << "#" << str.mHash;
#endif // _DEBUG
    }

private:
    size_t mHash;
#if _HASHSTRING_STORE_STRING
    std::string mString;
#endif // _HASHSTRING_STORE_STRING
};

#define _H(str) HashString(str)

namespace boost{
    inline size_t hash_value(const HashString& str)
    {
        return str.hash();
    }
}

#endif // _HASH_STRING_H

HashString.cpp

Code: Select all

#include "HashString.h"
//------------------------------------------------------------------------------
namespace{
    static size_t CalculateFNV(const char* str)
    {
        size_t hash = _HASHSTRING_FNV_OFFSET;
        while (*str != 0)
        {
            hash = (hash ^ *str++) * _HASHSTRING_FNV_PRIME;
        }
        return hash;
    }
}
//------------------------------------------------------------------------------
HashString::HashString(ConstCharWrapper str)
    :mHash(CalculateFNV(str.str))
#if _HASHSTRING_STORE_STRING
    ,mString(str.str)
#endif // _HASHSTRING_STORE_STRING
{
}
//------------------------------------------------------------------------------
HashString::~HashString()
{
}

A quick summary of how it's used:

Constant strings gets computed to hash at compile time:

Code: Select all

HashString textureName = "ogre_head.png"; // This gets compiled to hash at compile time by TMP

Strings have to be explicitly converted to HashString:

Code: Select all

HashString textureName = _H(textureNameInStdString.c_str()); // The hash gets computed at runtime

You can opt to have the string stored or save on loading by disabling to store strings. The macro that defines this is _HASHSTRING_STORE_STRING. The best approach would be define that to 1 to debug and set it to 0 otherwise.

Word of Caution: I have renamed stuff in code to make it 'friendlier' for others to read as my project has a different naming and coding convention. So I could've got this code to break if compiled. If you could let me know if something is wrong. I'll update this code accordingly.

[Knotanalt]

So does it traverse the scene graph by node name then? Where exactly is the savings coming from?

[vitefalcon]

It is not for scenegraph traversing. Every resource is currently identified by a string. If you have N resources you would have to do N string comparisons where each string comparison takes another M comparisons, where M is the length of the string. Dont forget the number of bytes it has to fetch from memory for each string.

With a HashString, to the programmer that looks and feels like a string but is represented as a number instead. So the number of comparisons is stil N, however we wil get a huge performance gain with the comparison.

[Knotanalt]

Thanks for responding. Maybe we can make it so that there's also a reference to the material, that gets filled in the first time it's dereferenced. It's got to be quite costly to look that up over and over, though the hash idea will make it faster.

[madmarx]

The only downside I can think of (aside from the work required to implement this!) is that debugging OGRE code in a debugger will be a little harder

I suggest that with a #define for debug mode; it should be possible to store the original string near the hashcode inside the stringhandle ?

[vitefalcon]

I suggest that with a #define for debug mode; it should be possible to store the original string near the hashcode inside the stringhandle ?

There is one catch though, when archives need to search for resources, you still need the full string. Like when you do ResourceGroupManager::findFileInfos("*.png");, if you use a hash-string, there no way to check for matches.

[Zonder]

I suggest that with a #define for debug mode; it should be possible to store the original string near the hashcode inside the stringhandle ?

There is one catch though, when archives need to search for resources, you still need the full string. Like when you do ResourceGroupManager::findFileInfos("*.png");, if you use a hash-string, there no way to check for matches.

I wouldn't expect the resource system to lose strings its a requirement for it. Everything after a resource is loaded should lose the string though

[Transporter]

This topic sounds interesting. Maybe it's possible to get rid of a second string problem (http://www.ogre3d.org/forums/viewtopic.php?f=2&t=76191) at the same time.

I suggest StringHandles already introduce in a version 1.9.5. It's too late for 1.9.0 but it would be nice to have it in an update. Why waiting two years on such a performance step? The Unicode problem should be solved also as fast as possible.

[Klaim]

I suggest StringHandles already introduce in a version 1.9.5. It's too late for 1.9.0 but it would be nice to have it in an update. Why waiting two years on such a performance step? The Unicode problem should be solved also as fast as possible.

Isn't this feature interface breaking?
It would be 1.10 then.

[bstone]

Isn't this feature interface breaking?
It would be 1.10 then.

The way it's originally described won't break compatibility - that was the whole point. It won't ever make into 1.10 though, too late for that

[masterfalcon]

@vitefalcon Would you be able to do a pull request on this? I'd like to check it out and see what we can do. Actually, make a fork of Ogre on bitbucket. Then others can check it out and play too.

Give me an hour or two. I'm going to merge 1.9 into 2.0 so that it's up to date.

[vitefalcon]

@vitefalcon Would you be able to do a pull request on this? I'd like to check it out and see what we can do. Actually, make a fork of Ogre on bitbucket. Then others can check it out and play too.

Give me an hour or two. I'm going to merge 1.9 into 2.0 so that it's up to date.

No problem. I will work on this tonight when I get home. I'll let you know when it's done.