文档介绍：代码优化-之-优化条件分支
                   HouSisong@  
tag:代码优化,条件分支,饱和,MMX,CMOV,掩码
摘要: 条件分支是编程中经常使用的基本操作,然而在某些时候它确可能带来严重的性能问题.
当前的CPU都能对条件分支做预测(动用了庞大的晶体管资源),如果分支预测正确,那么条件
指令一般只需要花费一个CPU周期,而如果预测错误,那么将可能花费几十个CPU周期!
  本文将讨论条件分支的一些有效优化方法.
正文:
  文章为收集加经验编辑而成的文章,对优化条件分支做了较全面的阐述. 
文章假定的CPU为x86,示例代码为C/C++.
?
  分支是编程语言中的常见结构;分支可以分为条件分支和非条件分支;
  条件分支举例:
    条件判断: 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),...
  
  为了加快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工具可以采样分支预测错误率)
  比如前面的那个奇偶循环模式,假设CPU不能正确预测,那么可以尝试改写为两个
for循环,一个处理偶数,一个处理奇数;
  一些图像处理算法里(比如模板运算/卷积运算/形态学运算等),经常需要判断边
界像素点,进行特殊处理;可以考略的优化方案是把边界区域和内部区域分开处理;
或者条件允许的话,可以扩大原图像