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.
blah
Sunday, November 8, 2009
With duplicate literal merging performed by the linker, maybe you could just use the pointer itself as a unique hash?
Humus
Sunday, November 8, 2009
I thought about that idea, but I still need to match the string against run-time generated values that come out of the shader. I'm not sure if there are any reasonable way to look up the corresponding pointer in run-time out of a run-time string. I guess you could search the whole global variable memory area, but that sounds like a shaky approach.
fjasdf
Sunday, November 8, 2009
Did you measure how much time you actually win with this?
Humus
Sunday, November 8, 2009
I did a quick test with a short list of 8 typical resource names and random lookups in it, and made 100 million lookups in it. Using the strcmp() method it took 2.45s, and using the StringHash method it took 0.95s.
Kristine
Monday, November 9, 2009
Very interesting stuff! But what about collisions?
Humus
Monday, November 9, 2009
I assume they don't happen.
For the paranoid it should be easy enough to verify on shader load that no two resource names collide.
chris green
Sunday, November 22, 2009
This post was helpful - I didn't realize that the compiler would successfully evaluate arbitrarily long sequences of assignments involving constant expressions at run-time.
What I ended up doing was writing a perl script to generate a case-insensitive murmurhash for various string constant lengths, and I got it to successfully compile them as just loads of simple integer constants. I'm using it for something similar to your application.
Tisten
Wednesday, November 25, 2009
context->SetTexture("Happy", m_Birthday);
More pages: 1 2
3 4
