"The point is ladies and gentlemen that greed, for lack of a better word, is good. Greed is right. Greed works. Greed clarifies, cuts through and captures the essence of the evolutionary spirit. Greed, in all of it's forms - greed for life, for money, knowledge - has marked the upward surge of mankind."
- Gordon Gekko
More pages: 1 2 3 4
Framework4 update
Thursday, November 5, 2009 | Permalink

I haven't mentioned the new framework I'm working on in a while, mostly because progress has been slow and I've been occupied with other things. Just wanted to give a brief mention of a neat trick I've implemented recently. In my framework I try to strike some kind of balance between ease of use and readability versus performance. Most of the time my demos are not very CPU heavy at all, so the CPU-side performance part isn't all that relevant, but it's always nice to have low overhead, just because it feels good. In Framework4 I've taken some steps to keep the overhead down. Something I usually do for readability is to set textures and other resources by name using strings, like so:

context->SetTexture("Tex", m_Texture);

This makes the code very readable and it's easy to see the mapping from the code to the shader. Unfortunately, lookups by a bunch of strcmp() is not the fastest way to find the corresponding texture unit index, even though it doesn't have to be terribly slow. A faster way is to use a precomputed hash value and do a lookup with that instead. I still want to use the same syntax though. What I ended up doing was changing const char * to StringHash, which is a class containing only a uint32 value, so for all practical purposes, it's a uint32 when compiled with optimizations. StringHash has loads of constructors. One for each length of the string I need, like so:

StringHash(const char (&str)[2]);
StringHash(const char (&str)[3]);
StringHash(const char (&str)[4]);
StringHash(const char (&str)[5]);
...
StringHash(const char (&str)[21]);

This covers all strings up to 20 characters, which should be enough for resource names. Each constructor contains the unrolled code for generating the hash, for instance:

StringHash(const char (&str)[4])
{
    m_Hash = 0;
    m_Hash = m_Hash * 65599 + str[0];
    m_Hash = m_Hash * 65599 + str[1];
    m_Hash = m_Hash * 65599 + str[2];
}

The hash function itself is not very important, I chose this one because it came up early on a google search. So when I make a SetTexture() call, I can call it with a constant string directly, which in C++ means it'll look for a way to convert the const char array to a StringHash, and finding a matching constructor it will use that to construct the StringHash object for me. Given the compile-time constant string and the simple unrolled code, any decent compiler will boil all this down to the resulting hash code when compiled with optimizations, and the runtime cost is essentially the same as if I would have written it like this:

context->SetTexture(0x29C22FA7, m_Texture);

A sneak peek at the assembly code we find the resulting hash inlined as an intermediate constant:

mov dword ptr [eax], 29C22FA7h
call Context::SetTexture

It will of course still be faster to just call SetTexture() with an index directly instead of the name, but this should narrow the gap somewhat.

Name

Comment

Enter the code below



Jackis
Wednesday, November 25, 2009

Gratulerer med fodelsdagen! 30 years - is pretty cool age

MarkW
Monday, November 30, 2009

We use a COMPILETIME_HASH("SomeString, 0) macro which gets parsed as a part of our pre-build / makefile process with a simple python script.
The 0 will be substituted with the correct hash, and a database is built up such that we can use our custom printf type functions using a %H which converts a hash to a string which is awfully useful for those missing asset messages or other such things!
As an aside, our asset system is being described by one of our guys at the Aussy GCAP conference on Monday Dec 7th.

Ming
Tuesday, January 12, 2010

Hi Humus,

The design of your Framework3 is great and I would like to take it as the reference of the rendering part of our company's 3d engine (under development).

I would like to ask what are the major features in Framework4 and when will it be released? Is there any big API changes between Framework3 and Framework4?

Thanks

imho
Thursday, March 4, 2010

Only problem with this approach i see if the inability for handling pointers passed in from strdup for example.

Adding a StringHash(const char* str) wouldn't solve the problem as the compiler wouldn't be able to resolve the ambiguity of calling which ctor as const char array and char pointer are schematically similar when passed as function parameters

Aslan Dzodzikov
Friday, May 14, 2010

It is possible to create just one templated constructor:

namespace StringHashHelper
{
template<size_t N>
unsigned _Hash(const char (&str)[N])
{
typedef const char (&truncated_str)[N-1];
return str[N] + 65599 * _Hash<N-1>((truncated_str)str);
}

template<>
unsigned _Hash<1>(const char (&str)[1])
{
return str[0];
}
};

class StringHash
{
unsigned m_val;

public:
template <size_t N>
StringHash(const char (&str)[N])
{
m_val = StringHashHelper::_Hash(str);
}

operator unsigned() { return m_val; }
};

StringHash a = "a", ab = "ab";

This implementation guaranties loop unrolling.

Aslan Dzodzikov
Friday, May 14, 2010

Sorry, the previous post contained 1 bug. Here is corrected code:

namespace StringHashHelper
{
template<size_t N>
inline unsigned _Hash(const char (&str)[N])
{
typedef const char (&truncated_str)[N-1];
return str[N-1] + 65599 * _Hash<N-1>((truncated_str)str);
}

template<>
inline unsigned _Hash<1>(const char (&str)[1])
{
return str[0];
}
};

class StringHash
{
unsigned m_val;

public:
template <size_t N>
StringHash(const char (&str)[N])
{
m_val = StringHashHelper::_Hash(str);
}

operator unsigned() { return m_val; }
};

StringHash a = "a", ab = "ab";

Aslan Dzodzikov
Friday, May 14, 2010

And now the final, more compact version:

class StringHash
{
unsigned m_val;

template<size_t N> unsigned _Hash(const char (&str)[N])
{
typedef const char (&truncated_str)[N-1];
return str[N-1] + 65599 * _Hash((truncated_str)str);
}
unsigned _Hash(const char (&str)[2]) { return str[1] + 65599 * str[0]; }

public:
template <size_t N> StringHash(const char (&str)[N]) { m_val = _Hash(str); }
operator unsigned() { return m_val; }
};

I apologize for multiple, redundant posts.

Aslan Dzodzikov
Monday, May 17, 2010

Just a test result for StringHash:

void PrintHash(const StringHash& _hash)
{
printf( "%x", (unsigned)_hash );
}

PrintHash("Creating Device! Just a test for StringHash";

compiles to:
lea eax, DWORD PTR $T107665[esp+684]
push edi
push eax
mov DWORD PTR $T107665[esp+692], 1584422291 ; 5e705d93H
call ?PrintHash@@YAXABVStringHash@@@Z ; PrintHash
add esp, 4

Under MSVC 2008 SP1

More pages: 1 2 3 4