for 循环中的 1 句话为什么写 8 次

[zhyoulun]

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;
}

[cnlinjie]

懒得写双循环吧。复制粘贴复制粘贴。~2333333

[kaneg]

为了最大可能性的提高性能，所以尽量减少循环语句。
按一般人的思路，这里应该写一个 8 次的循环，但写引擎的人会尽力压榨性能。

[R18]

跟 8bit 有关系吗？

[rogerchen]

两点
1. loop unrolling
2. 手动触发编译器向量化 heuristic

第一点是一定的，第二点是有可能的。

[sujin190]

其实是和 cpu 缓存有关，对齐缓存，提高效率

[rogerchen]

多说一点， unrolling 是很常见的优化技巧，而且是无视架构的，能够大幅缩减控制流中累加和尾后测试的开销，特别是循环体比较简单的时候优化系数很高。

Ref: https://en.wikipedia.org/wiki/Loop_unrolling

[zhyoulun]

@rogerchen 看了下 loop unrolling ，很靠谱

[zhyoulun]

@rogerchen 注意到程序的注释中也写到了这是 unrolled 过的变体， variant with the hash unrolled eight times

[cute]

@rogerchen
原来如此，
之前看 leveldb 的代码还纳闷这么写呢
https://github.com/google/leveldb/blob/3080a45b626f8ddb474bc5e860796a48b51b3cf0/util/hash.cc#L18

[undeflife]

不懂 php 但是 c 的循环展开是可以由编译器完成的

[phrack]

觉得是不必要的手动优化。

写一个循环，编译器检查到这样的循环会自动展开的。

[Yourshell]

好像 Duff's device

[xavierskip]

不懂，不过最近听别人抱怨写 swift ，某些语句拆开写能大幅度缩短编译时间。

[Shura]

csapp 中好像提到过这种优化方式，远古时候能够加速循环，现在的编译器已经能自动进行这种优化了。

[roychan]

现在编译器也能 unroll 了吧。。。

[Quaintjade]

我只知道 VBA 里 a^n 写开成 a*a*a*...*a 能大幅提高效率

[Contextualist]

这是 loop unrolling 中的 Duff's device 的抽离出 switch 的写法，而原版 Duff's device 是对于 C 语言中 switch 最精妙的利用 (误用，把 switch 当 goto 用
https://zh.wikipedia.org/wiki/达夫设备

[zhidian]

OpenMP 示例代码里也有看到用 loop unrolling 把不可并行的循环变得可以并行。

[bigpigeon]

@xavierskip 可能要考虑历史因素和环境因素把，可能那个年代 c 编译器没这种优化，可能某些 cpu 架构下的 c 编译器没做这种优化

[IgniteWhite]

为啥都要像汇编一样考虑循环展开。。。

[billwsy]

@sujin190 另一方面 unrolling 有时会导致指令不能全部存入高级的 Cache ，从而带来性能的损失

[firebroo]

我能说我使用的时候就是直接扣了这个函数吗？ https://github.com/firebroo/UnixTools/blob/master/uniq/hashtable.c （逃

[gjc9620]

DUFF 装置吗？