编译期字符串Hash

Jan 14

转载请注明出处为KlayGE游戏引擎，本文的永久链接为http://www.klayge.org/?p=647

老早就想写这篇了，但一直没空，现在抽个空写写吧。

Motivation

编译期字符串Hash的想法源于一个常见做法，字符串比较。比如在KlayGE的effect系统中，有很多if (“cull_mode” == state_name)这样的比较。加速这个操作的方法之一就是hash。但是如果改成if (0x8F1E5E5F == state_name_hash)又非常不直观。如果能有一个编译期的hash方法，先称之为CT_HASH，就可以if(CT_HASH(“cull_mode”) == state_name_hash)，既保证直观，又保证开发效率。

尝试

要在编译期做事情首先都会想到template，但是C++的template没法提供字符串的操作，就算boost::mpl::string，也必须把一个一个字符分开塞给它才行，就像这样：

boost::mpl::string<‘c’, ‘u’, ‘l’, ‘l’, ‘_’, ‘m’, ‘o’, ‘d’, ‘e’>

仍然不直观，所以template这条路走不通。

剩下的就是宏了。

inline size_t HASH_FUNCTION(size_t seed, char ch)
{
return seed ^ (ch + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}

#define HASH_RECURSE_00(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_01(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_01(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_02(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_02(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_03(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_03(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_04(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_04(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_05(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_05(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_06(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_06(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_07(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_07(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_08(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_08(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_09(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_09(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_10(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_10(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_11(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_11(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_12(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_12(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_13(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_13(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_14(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_14(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_15(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_15(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_16(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_16(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_17(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_17(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_18(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_18(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_19(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_19(seed, str) HASH_FUNCTION((seed), *(str))

#define CT_HASH(str) HASH_RECURSE_00(0, (str))

这里的HASH_FUNCTION来自于boost，其本身是否出现冲突的情况不属于本片讨论的范围。值得注意的是，如果HASH_FUNCTION用宏的方式来写，那么HASH_RECURSE到9个之后就会造成编译器heap溢出，必须写成函数的形式。

编译期？

这样的CT_HASH是编译期的吗？是也不是。在Release下，看汇编的结果可以发现

cout << CT_HASH(“cull_mode”) << endl;

被编译成了

00DC1103 mov         eax,dword ptr [__imp_std::endl (0DC2054h)]
00DC1108 mov         ecx,dword ptr [__imp_std::cout (0DC2058h)]
00DC110E push        eax
00DC110F push        8F1E5E5Fh
00DC1114 mov         dword ptr [ebp-18h],0Fh
00DC111B mov         dword ptr [ebp-1Ch],ebx
00DC111E mov         byte ptr [ebp-2Ch],bl
00DC1121 call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (0DC2048h)]
00DC1127 mov         ecx,eax
00DC1129 call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (0DC2044h)]

也就是说CT_HASH(“cull_mode”)被编译成了常量8F1E5E5Fh。看似成功了，但是对于另一个更严格的常量测试

switch (state_name_hash)
{
case CT_HASH(“cull_mode”):
…
}

却失败了。也就是说CT_HASH(“cull_mode”)其实并不是编译期常量，而是优化器产生的。

结论

想要做一个编译期字符串Hash的尝试HLL地失败了:(，只能做到“优化期”常量的效果。如果各位看客有何高见的话不妨讨论讨论！

A good Explosion Texture Generator[ZZ]发现一个不错的爆炸纹理生成器

KlayGE中的延迟渲染（二）

hash

Comments

Huang Donghai

January 14th, 2011 at 6:15 PM

用FixedString, 给“不变字符串”给个整数id。

GONG Minmin

January 15th, 2011 at 4:19 PM

这也不能在编译期生成吧，hash还是到了运行期

Huang Donghai

January 15th, 2011 at 9:42 PM

确实不能编译器生成。如果是Parse Effect File的时候，用普通的strcmp也没关系，这个不是经常跑的。运行时的时候，就是FixedString比较FixedString，只是比较整数是否相等而已。HashFunction直接返回id即可，不需要rehash string。
Huang Donghai

January 15th, 2011 at 9:53 PM

何况，用hashstring值来比较字符串原则上也是不对的,hash也可能会碰撞（多个string可能会hash到同一个值）啊。hash只能绝对判断不等于，不能绝对判断等于。

godzza

November 25th, 2012 at 12:37 AM

在Debug 模式下再加断言吧。

Taiwanese programmer

January 14th, 2011 at 9:32 PM

目前使用一個國外遊戲引擎，產生字符串hash的做法是製作一個獨立的工具，
在程式碼編譯前，會先以這個工具掃描程式碼的macro字串，填入hash值，
如CT_HASH(“cull_mode”)經過工具處理後，會變成CT_HASH(“cull_mode”, 0x8F1E5E5F)。
這個方法也可以處理所有遊戲asset資料的字串符，
配合網路功能，也可以處理hash值collision的問題。
目前這個方式運作相當良好，更感謝您提供的想法~ 🙂

GONG Minmin

January 15th, 2011 at 4:18 PM

这种方法不少地方用过，但因为我不想引入一层预编译，尝试在编译期解决，所以成了现在这样的情况

Taiwanese programmer

January 14th, 2011 at 10:02 PM

下面這個網址的做法是以四個char為單位，可以稍微美化您原來template一個一個char的做法，
http://arcticinteractive.com/2009/04/18/compile-time-string-hashing-boost-mpl/

GONG Minmin

January 15th, 2011 at 4:20 PM

谢谢你提供的建议，这个方法我在尝试mpl的时候也实现过

mtlung

January 15th, 2011 at 1:07 AM

你好! 小弟也曾作這方面的嘗試,也看過很多其他的實作, 相信 boost 的作法已是真實编译期常量中最直觀的了. 因為 “” 字串內容本身就沒有编译期常量的資格.

另外還有一種不用 macro 的”偽”编译期常量方法:

template struct Str { typedef const char (&Type)[N]; };
template FORCE_INLINE int sdbm(typename Str::Type str) {
return sdbm((typename Str::Type)str) * 65599 + str[N-2];
}

// “1” = char[2]
// NOTE: Template specialization have to be preformed in namespace scope.
template FORCE_INLINE int sdbm(Str::Type str) {
return str[0];
}

FORCE_INLINE int stringHash(const char (&str)[2]){
retrun sdbm(str);
}

FORCE_INLINE int stringHash(const char (&str)[3]){
retrun sdbm(str);
}

…

GONG Minmin

January 15th, 2011 at 4:22 PM

似乎这个问题在C++98层面无法解决了，C++0x的const_expr可能可以尝试一下

liuzhi

January 17th, 2011 at 9:26 PM

gpref性能非常好
虽然大家都喜欢发明轮子。。。

GONG Minmin

January 18th, 2011 at 9:15 AM

gperf性能再好也不是编译期的啊

再探编译期字符串Hash - KlayGE游戏引擎

December 28th, 2012 at 1:29 PM

[…] 时间过得真快，离上一次讨论编译期字符串Hash已经差不多2年了。上次的尝试失败了，只能产生优化期常量，没有做到编译期常量的效果。现在有了C++11，情况会不会有所改变呢？ […]

KlayGE游戏引擎