PHP 源码中 hash 的计算函数如下,想知道为什么 for 循环中把 1 句话写 8 次。
static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength)
{
register ulong hash = 5381;
/* variant with the hash unrolled eight times */
for (; nKeyLength >= 8; nKeyLength -= 8) {
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
}
switch (nKeyLength) {
case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 1: hash = ((hash << 5) + hash) + *arKey++; break;
case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
}
return hash;
}
1
cnlinjie 2017-03-07 18:01:45 +08:00
懒得写双循环吧。复制粘贴复制粘贴。~2333333
|
2
kaneg 2017-03-07 18:03:05 +08:00 via iPhone
为了最大可能性的提高性能,所以尽量减少循环语句。
按一般人的思路,这里应该写一个 8 次的循环,但写引擎的人会尽力压榨性能。 |
3
R18 2017-03-07 18:04:07 +08:00 via Android
跟 8bit 有关系吗?
|
4
rogerchen 2017-03-07 18:04:54 +08:00 4
两点
1. loop unrolling 2. 手动触发编译器向量化 heuristic 第一点是一定的,第二点是有可能的。 |
5
sujin190 2017-03-07 18:06:53 +08:00
其实是和 cpu 缓存有关,对齐缓存,提高效率
|
6
rogerchen 2017-03-07 18:08:23 +08:00 1
多说一点, unrolling 是很常见的优化技巧,而且是无视架构的,能够大幅缩减控制流中累加和尾后测试的开销,特别是循环体比较简单的时候优化系数很高。
Ref: https://en.wikipedia.org/wiki/Loop_unrolling |
8
zhyoulun OP @rogerchen 注意到程序的注释中也写到了这是 unrolled 过的变体, variant with the hash unrolled eight times
|
9
cute 2017-03-07 18:33:32 +08:00
@rogerchen
原来如此, 之前看 leveldb 的代码还纳闷这么写呢 https://github.com/google/leveldb/blob/3080a45b626f8ddb474bc5e860796a48b51b3cf0/util/hash.cc#L18 |
10
undeflife 2017-03-07 18:36:22 +08:00
不懂 php 但是 c 的循环展开是可以由编译器完成的
|
11
phrack 2017-03-07 18:51:29 +08:00 via Android
觉得是不必要的手动优化。
写一个循环,编译器检查到这样的循环会自动展开的。 |
12
Yourshell 2017-03-07 19:19:07 +08:00
好像 Duff's device
|
13
xavierskip 2017-03-07 19:23:14 +08:00
不懂,不过最近听别人抱怨写 swift ,某些语句拆开写能大幅度缩短编译时间。
|
14
Shura 2017-03-07 19:48:52 +08:00 via Android
csapp 中好像提到过这种优化方式,远古时候能够加速循环,现在的编译器已经能自动进行这种优化了。
|
15
roychan 2017-03-07 20:03:40 +08:00
现在编译器也能 unroll 了吧。。。
|
16
Quaintjade 2017-03-07 20:16:12 +08:00 via Android
我只知道 VBA 里 a^n 写开成 a*a*a*...*a 能大幅提高效率
|
17
Contextualist 2017-03-07 20:25:01 +08:00 via iPad
这是 loop unrolling 中的 Duff's device 的抽离出 switch 的写法,而原版 Duff's device 是对于 C 语言中 switch 最精妙的利用 (误用,把 switch 当 goto 用
https://zh.wikipedia.org/wiki/达夫设备 |
18
zhidian 2017-03-07 20:27:56 +08:00
OpenMP 示例代码里也有看到用 loop unrolling 把不可并行的循环变得可以并行。
|
19
bigpigeon 2017-03-07 20:47:11 +08:00
@xavierskip 可能要考虑历史因素和环境因素把,可能那个年代 c 编译器没这种优化,可能某些 cpu 架构下的 c 编译器没做这种优化
|
20
IgniteWhite 2017-03-07 22:59:58 +08:00
为啥都要像汇编一样考虑循环展开。。。
|
21
billwsy 2017-03-07 23:20:18 +08:00 via iPhone
@sujin190 另一方面 unrolling 有时会导致指令不能全部存入高级的 Cache ,从而带来性能的损失
|
22
firebroo 2017-03-08 10:42:14 +08:00
我能说我使用的时候就是直接扣了这个函数吗? https://github.com/firebroo/UnixTools/blob/master/uniq/hashtable.c (逃
|
23
gjc9620 2017-03-08 13:45:02 +08:00
DUFF 装置吗?
|