V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zhyoulun
V2EX  ›  C

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

  •  1
     
  •   zhyoulun · 2017-03-07 17:55:58 +08:00 · 3844 次点击
    这是一个创建于 2820 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    写一个循环,编译器检查到这样的循环会自动展开的。
    Yourshell
        12
    Yourshell  
       2017-03-07 19:19:07 +08:00
    好像 Duff's device
    xavierskip
        13
    xavierskip  
       2017-03-07 19:23:14 +08:00
    不懂,不过最近听别人抱怨写 swift ,某些语句拆开写能大幅度缩短编译时间。
    Shura
        14
    Shura  
       2017-03-07 19:48:52 +08:00 via Android
    csapp 中好像提到过这种优化方式,远古时候能够加速循环,现在的编译器已经能自动进行这种优化了。
    roychan
        15
    roychan  
       2017-03-07 20:03:40 +08:00
    现在编译器也能 unroll 了吧。。。
    Quaintjade
        16
    Quaintjade  
       2017-03-07 20:16:12 +08:00 via Android
    我只知道 VBA 里 a^n 写开成 a*a*a*...*a 能大幅提高效率
    Contextualist
        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/达夫设备
    zhidian
        18
    zhidian  
       2017-03-07 20:27:56 +08:00
    OpenMP 示例代码里也有看到用 loop unrolling 把不可并行的循环变得可以并行。
    bigpigeon
        19
    bigpigeon  
       2017-03-07 20:47:11 +08:00
    @xavierskip 可能要考虑历史因素和环境因素把,可能那个年代 c 编译器没这种优化,可能某些 cpu 架构下的 c 编译器没做这种优化
    IgniteWhite
        20
    IgniteWhite  
       2017-03-07 22:59:58 +08:00
    为啥都要像汇编一样考虑循环展开。。。
    billwsy
        21
    billwsy  
       2017-03-07 23:20:18 +08:00 via iPhone
    @sujin190 另一方面 unrolling 有时会导致指令不能全部存入高级的 Cache ,从而带来性能的损失
    firebroo
        22
    firebroo  
       2017-03-08 10:42:14 +08:00
    我能说我使用的时候就是直接扣了这个函数吗? https://github.com/firebroo/UnixTools/blob/master/uniq/hashtable.c (逃
    gjc9620
        23
    gjc9620  
       2017-03-08 13:45:02 +08:00
    DUFF 装置吗?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1500 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 17:09 · PVG 01:09 · LAX 09:09 · JFK 12:09
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.