摘要: 条件分支是编程中经常使用的基本操作,然而在某些时候它确可能带来严重的性能问题.

当前的CPU都能对条件分支做预测(动用了庞大的晶体管资源),如果分支预测正确,那么条件指令一般只需要花费一个CPU周期,而如果预测错误,那么将可能花费几十个CPU周期!
本文将讨论条件分支的一些有效优化方法.

正文：
文章为收集加经验编辑而成的文章,对优化条件分支做了较全面的阐述.
文章假定的CPU为x86,示例代码为C\C++.

A.什么是分支?
分支是编程语言中的常见结构；分支可以分为条件分支和非条件分支；
条件分支举例:
    条件判断: if (a>255) a=255; else if (a<0) a=0;
    循环: for (i=0;i<1000;++i) { ...; }
          while(!bOk) { bOk=...; }
          ...
    对应汇编指令的jnz,jg等等
非条件分支举例:
    函数调用(call)，函数返回(return\ret)，软件中断(int 3)，直接跳转(jmp),...

B.CPU分支预测错误的惩罚由来
为了加快CPU的处理频率，现代CPU都设计了多级流水线，有的甚至有20级以上；当CPU遇到跳转指令的时候，会做一个预测，把预测的分支代码载入流水线，当发现预测错误的时候，需要清空流水线，重新载入正确的分支到流水线；那么预测错误的代价周期数至少应该和流水线长度相当；然而考虑到各级的缓存失效、指令解码等等，实际损失的周期数有可能是流水线长度的几倍!
   对于非条件分支，一般来说CPU都能得到相当高的预测准确率；我们主要来讨论一下条件分支的预测；
(有人可能会说，当CPU遇到条件分支时不做预测不就没有预测错误的惩罚了吗? 这种流水线空着的惩罚实质和每次都预测错误然后清空流水线的代价相当，退一步说就算每次随机选择一个分支来执行也有50%的收益)

C:需要优化的条件分支
当前的CPU对各种简单的条件分支模式都能做出很的预测，比如奇偶模式：
for (int i=0;i<1000;++i)
{
     if (a%2==0) do0();
     else do1();
}
而对于随机的分支模式，再好的预测器也不可能做出好的预测；我们要优化条件分支，这些分支代码应该满足：该分支处于时间热点上，并且分支预测错误率较高；这样我们才能得到优化的收益；
   (intel的VTune工具可以采样分支预测错误率)

D.把条件分支移动到热点外
比如前面的那个奇偶循环模式,假设CPU不能正确预测,那么可以尝试改写为两个for循环,一个处理偶数,一个处理奇数;一些图像处理算法里(比如模板运算\卷积运算\形态学运算等),经常需要判断边界像素点,进行特殊处理;可以考略的优化方案是把边界区域和内部区域分开处理;或者条件允许的话,可以扩大原图像的边界,形成"哨兵"数据,这样访问像素的时候就不用考虑越界的问题了;

E.合并多个条件来减少条件分支
比如: if ( (a0==0) && (a1==0) && (a2==0) ) ...
    编译器将生成3个条件跳转指令,而且使分支可预测性大大降低;
可以改写为: if ( (a0|a1|a2)==0 ) ...
    从而同时改进代码和分支预测率;

比如:if ( (b0>=64) || (b1>=64)) ... //b0,b1>=0
改写为: if ( (b0|b1)>=64 ) ...
(请尝试证明其等价性)

F.将出现几率高的分支优先处理,从而提高预测准确率

G.优化第一次执行的条件分支
当CPU第一次执行到一个条件分支的时候,默认的预测分支规则是不跳转的那个分支(也就是紧接着条件跳转指令之后的那些指令);

(下面的内容主要讨论完全替换掉分支的一些方法; 移除分支意味着代码的性能可以不受输入数据的影响,并可能能更好的使用SIMD类指令)

H.使用条件状态值生成掩码来移除条件分支
比如: if (color<0) color=0;
改写为: color &=-(color>=0);//求负是为了生成掩码,也可以减1来生成掩码

这里的思路是利用比较来产生0或1值,然后利用生成的值参与运算从而移除了分支;

比如: if (color>255) color=255;
改写为: color = (color | -(color>255) ) & 0xFF;

比如: if (a>=b) return a; else return b;
改写为: return a + ( (b-a) & -(b>a) );

(警告:这里利用了C\C++中比较的结果是0或1,在其他语言或编译器中可能定义不同)

I.使用带符号的移位生成掩码来移除条件分支
(建议使用该方案替代上面的条件状态值方案)

比如: if (color<0) color=0; //color为long类型
改写为: color &=~(color>>31); //带符号移位从而生成需要的掩码

比如: if (color>255) color=255;
改写为: color = (color | ((255-color)>>31) ) & 0xFF;

比如: if (a>=b) return a; else return b;
改写为: return a + ( (b-a) & -(b>a) );

移除分支的一个更通用的思路: 针对不同类的数据生成不同的掩码数据,然后让原数据和掩码参与运算得到想要的结果,从而移除分支;

J: 查表法移除分支
比如: if (color<0) color=0;
        else if (color>255) color=255; //假设color属于[-256..512]
改写为: color=ColorTable[color];
      其中ColorTable的建立:
          _ColorTable[512+256+1]; ColorTable=&_ColorTable[256];
      for (i=-256;i<=512;++i)
      {
          if (i<0) ColorTable[i]=0;
          else if (i>255) ColorTable[i]=255;
          else ColorTable[i]=i;
      }

   比如: if (score>=90) //score属于[0..100]
            return 'A';
         else if (score>=75)
            return 'B';
         else if (score>=60)
            return 'C';
         else
            return 'D';
   改写为: return scTable[score];
      其中scTable应该预先存的值就不用再写了吧:)

K:使用CMOV条件传送指令来移除条件分支
(为了避免分支预测错误造成的性能损失,现代的CPU一般都提供了很多能够避免分支的指令,比如条件传送\掩码生成\最值等指令,请查阅指令说明和支持的CPU)

CMOV条件传送指令是很多条具体的指令,它们根据条件寄存器的值来决定是否赋值.
比如: if (x<0) x=-x;
用CMOV改写为(汇编):
       mov   edx, eax   //假设x的值在eax寄存器,该指令使edx=eax
       neg   eax        //eax=-eax   //该指令的结果将设置条件寄存器的状态
       cmovs eax,edx    //如果状态为负,将edx的值传递给eax
      
CMOV指令列表:
CMOVA/CMOVNBE CMOVAE/CMOVNB/CMOVNC CMOVB/CMOVC/CMOVNAE
CMOVBE/CMOVNA CMOVE/CMOVZ CMOVG/CMOVNLE CMOVGE/CMOVNL
CMOVL/CMOVNGE CMOVLE/CMOVNG CMOVNE/CMOVNZ CMOVNO
CMOVNP/CMOVPO CMOVNS CMOVO CMOVP/CMOVPE CMOVS

x87浮点CMOV指令列表:
FCMOVB FCMOVBE FCMOVE FCMOVNB FCMOVNBE FCMOVNE
FCMOVNU FCMOVU

L:使用MMX\SSE2中的饱和指令
对于颜色的饱和处理,比如:
      if (color<0) color=0;
        else if (color>255) color=255;
x86CPU从奔腾MMX开始,提供了MMX指令集(后来的SSE2也有类似指令);增加了对饱和处理的指令支持,在图像处理和声音处理中得到了广泛应用;

(我的blog的很多文章有使用MMX\SSE指令的例子)(MMX\SSE之类的SIMD指令还能够同时并行执行多路数据,从而加快执行速度)

M:使用CMP掩码生成指令来移除条件分支
比如:
    //r = (x < y) ? a : b
    // In: MM0 = a, MM1 = b, MM2 = x, MM3 = y
    // Out: MM0 = r
    pcmpgtd mm3, mm2 //比较y>x,生成掩码0xFFFFFFFF 或者 0
    pand mm0, mm3    //a 或者 0
    pandn mm3, mm1   //0 或者 b
    por mm0, mm3

CMP指令包括:
CMPPS,CMPSS,CMPPD,CMPS,CMPSB,CMPSW,CMPSD,, PCMPEQB, PCMPEQD, PCMPEQW, PCMPGTB, PCMPGTD, PCMPGTW, CMPXCHG,CMPXCHG8B 等

N:使用MIN\MAX指令来移除条件分支
MAXPS,MAXPD,MAXSS,MAXSD,MINPS,MINPD,MINSS,MINSD,PMAXSW, PMAXUB, PMINSW, PMINUB等

HouSisong@GMail.com   2007.10.05

tag:代码优化,条件分支,饱和,MMX,CMOV,掩码