zhyoulun
V2EX  ›  C

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

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

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

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

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