我需要优化这个非常微小但却令人讨厌的功能.
unsigned umod(int a, unsigned b)
{
while(a < 0)
a += b;
return a % b;
}
在你喊出"你不需要优化它"之前,请记住,这个函数被称为整个程序生命周期的50%,因为它被称为最小测试用例基准测试的21495808次.
该函数已由编译器内联,因此请不要添加inline关键字.
难道保证(-x) % m,在这里x和m在C++中积极标准(C++ 0x中)为负,等于-(x % m)？
我知道它在我知道的所有机器上都是正确的.
我有一个存储四叉树条目的哈希表.
哈希函数如下所示:
四叉树哈希
#define node_hash(a,b,c,d) \
(((int)(d))+3*(((int)(c))+3*(((int)(b))+3*((int)(a))+3)))
请注意,此操作的结果始终使用模数素数进行分块,如下所示:
h = node_hash(p->nw, p->ne, p->sw, p->se) ;
h %= hashprime ;
...
与最佳散列的比较
一些统计分析表明,这种散列在减少碰撞方面是最佳的.
给出带有b桶和n条目的哈希表.使用完美散列的碰撞风险是:
(n - b * (1 - power((b-1)/b,n)))) * 100 / n
当n = b时,这意味着碰撞风险为37%.
一些测试表明,上面的哈希与标准非常吻合(对于哈希表的所有填充级别).
运行时运行时间
在很大程度上取决于值hashprime
计时(1000次运行中最好的)是:
hashprime CPU-cycles per run
--------------------------------
4049 56
16217 68
64871 127 <-- whoooh
有没有办法改善这一点,同时仍然保持最佳的碰撞风险？
通过优化模数运算(在循环外使用'魔术'数字计算机替换它).
用其他哈希函数替换哈希函数.
背景
产生以下组件:
//--------h = node_hash(p->nw, p->ne, p->sw, p->se) ;
mov eax,[rcx+node.nw] <<+
lea eax,[eax+eax*2+3] |
add eax,[rcx+node.ne] | …我需要生成大约N = 1亿个密钥的哈希密钥.从我的研究看来,murmur3(MurmurHash3_x86_32,见murmur3 hash)将是最快的散列函数,具有最佳延迟和足够小的碰撞率.我面临的问题是该函数返回键为 void *.更具体地说,模板是:
void MurmurHash3_x86_32 (const void *key, int len, uint32_t seed, void *out);
由于我的哈希表大小将小于它可以生成的最大哈希,我需要将它放入表范围[0,N-1].最简单的解决方案似乎是使用%运算符.但由于众所周知这是一个缓慢的操作员,我想知道是否有更快的方法来解决问题.
我发现一个有趣的建议是否有替代在C/C++中使用%(模数)？在StackOverflow本身.它暗示了"两个人的力量,以下作品(假设两个补语表示)":
return i & (n-1);
我的问题是,在较新的CPU上,它有时(或者大部分时间都是这样？),由于多路缓存线,性能会在大约2 ^ n,IIRC附近降低.(此链接提供有关插入大内存的说明,第3.5部分:Google sparsehash!).
目前,murmur3的优势似乎因硬件相关问题和%运营商的低效率而无效.由于性能是一个约束,我要求低延迟和更快的解决方案,即使它不是MurmurHash3_x86_32.