"We could change the world, if God gave us the source code."
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



Rory
Thursday, November 5, 2009

That's pretty cool. I have the same thing in my home engine with setting textures and shader constants by const char* lookup. I was looking for a nice way to get compile-time constants without needing to run a preprocessor over the file, so thanks!

castano
Friday, November 6, 2009

Interesting trick. I tried to achieve that in gcc a while ago using pure functions, but they didn't get inlined. Unrolling the loop might to the trick, though.

Sopyer
Friday, November 6, 2009

Have you tried to do this trick with C++ templates?

template <size_t N>
StringHash(const char (&str)[N])

Does compiler also unroll this? And how do you resolve hash collisions?

Rohit
Friday, November 6, 2009

Cool, is this framework4 available somewhere?

sqrt[-1]
Friday, November 6, 2009

Arr so this is why you were asking on the Beyond3D forum for this.

I am eagerly awaiting FrameWork4 as I find your framework interfaces really nice for distilling the raw functionality. (I have a habit of thinking - " but what if I want to..." when I make interfaces)

MaciejS
Friday, November 6, 2009

GCC is actually even smarter: http://www.gamedev.net/community/forums/topic.asp?topic_id=550505

Kayru
Friday, November 6, 2009

to Sopyer:
Visual C++ 2005 expands template version only if string is shorter than certain length:
http://www.everfall.com/paste/id.php?3ebi39jmnir0

Humus
Friday, November 6, 2009

castano: Yeah, it's the manual unrolling that does the trick. Without it, compilers appear to stop trying to pre-compute it after a certain length. I found it to be 10 chars in MSVC 2008, which was a bit too short for me. With manual unroll it appears to work regardless of the length of the string (although I haven't tried super long strings).

Sopyer: I was recommended to use templates first like this using the solution in MaciejS's link. However, I wanted to keep my syntax, so after I found that the template trick worked I tried doing the same with constructors, and that worked fine too.

Rohit: No, it's not available yet.

Kayru: That's without unrolling though, isn't it?

More pages: 1 2 3 4