zhyoulun
V2EX  ›  C

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

  •  1
     
  •   zhyoulun · Mar 7, 2017 · 5063 views
    This topic created in 3530 days ago, the information mentioned may be changed or developed.

    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;
    }
    
    23 replies  •  2017-03-08 13:45:02 +08:00
    hrH5KaH2t49cVPy2
    hrH5KaH2t49cVPy2
    Mar 7, 2017
    1
    懒得写双循环吧。复制粘贴复制粘贴。~2333333
    kaneg
    kaneg
    Mar 7, 2017 via iPhone
    2
    为了最大可能性的提高性能,所以尽量减少循环语句。
    按一般人的思路,这里应该写一个 8 次的循环,但写引擎的人会尽力压榨性能。
    R18
    R18
    Mar 7, 2017 via Android
    3
    跟 8bit 有关系吗?
    rogerchen
    rogerchen
    Mar 7, 2017❤️4
    4
    两点
    1. loop unrolling
    2. 手动触发编译器向量化 heuristic

    第一点是一定的,第二点是有可能的。
    sujin190
    sujin190
    Mar 7, 2017
    5
    其实是和 cpu 缓存有关,对齐缓存,提高效率
    rogerchen
    rogerchen
    Mar 7, 2017❤️1
    6
    多说一点, unrolling 是很常见的优化技巧,而且是无视架构的,能够大幅缩减控制流中累加和尾后测试的开销,特别是循环体比较简单的时候优化系数很高。

    Ref: https://en.wikipedia.org/wiki/Loop_unrolling
    zhyoulun
    zhyoulun
    OP
    Mar 7, 2017
    7
    @rogerchen 看了下 loop unrolling ,很靠谱
    zhyoulun
    zhyoulun
    OP
    Mar 7, 2017
    8
    @rogerchen 注意到程序的注释中也写到了这是 unrolled 过的变体, variant with the hash unrolled eight times
    cute
    cute
    Mar 7, 2017
    9
    undeflife
    undeflife
    Mar 7, 2017
    10
    不懂 php 但是 c 的循环展开是可以由编译器完成的
    phrack
    phrack
    Mar 7, 2017 via Android
    11
    觉得是不必要的手动优化。

    写一个循环,编译器检查到这样的循环会自动展开的。
    Yourshell
    Yourshell
    Mar 7, 2017
    12
    好像 Duff's device
    C0VN
    C0VN
    Mar 7, 2017
    13
    不懂,不过最近听别人抱怨写 swift ,某些语句拆开写能大幅度缩短编译时间。
    Shura
    Shura
    Mar 7, 2017 via Android
    14
    csapp 中好像提到过这种优化方式,远古时候能够加速循环,现在的编译器已经能自动进行这种优化了。
    roychan
    roychan
    Mar 7, 2017
    15
    现在编译器也能 unroll 了吧。。。
    Quaintjade
    Quaintjade
    Mar 7, 2017 via Android
    16
    我只知道 VBA 里 a^n 写开成 a*a*a*...*a 能大幅提高效率
    Contextualist
    Contextualist
    Mar 7, 2017 via iPad
    17
    这是 loop unrolling 中的 Duff's device 的抽离出 switch 的写法,而原版 Duff's device 是对于 C 语言中 switch 最精妙的利用 (误用,把 switch 当 goto 用
    https://zh.wikipedia.org/wiki/达夫设备
    zhidian
    zhidian
    Mar 7, 2017
    18
    OpenMP 示例代码里也有看到用 loop unrolling 把不可并行的循环变得可以并行。
    bigpigeon
    bigpigeon
    Mar 7, 2017
    19
    @xavierskip 可能要考虑历史因素和环境因素把,可能那个年代 c 编译器没这种优化,可能某些 cpu 架构下的 c 编译器没做这种优化
    FurN1
    FurN1
    Mar 7, 2017
    20
    为啥都要像汇编一样考虑循环展开。。。
    billwsy
    billwsy
    Mar 7, 2017 via iPhone
    21
    @sujin190 另一方面 unrolling 有时会导致指令不能全部存入高级的 Cache ,从而带来性能的损失
    firebroo
    firebroo
    Mar 8, 2017
    22
    我能说我使用的时候就是直接扣了这个函数吗? https://github.com/firebroo/UnixTools/blob/master/uniq/hashtable.c (逃
    gjc9620
    gjc9620
    Mar 8, 2017
    23
    DUFF 装置吗?
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Privacy   ·   Solana   ·   1535 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 57ms · UTC 17:57 · PVG 01:57 · LAX 09:57 · JFK 12:57
    ♥ Do have faith in what you're doing.