CH14 一些实用小技巧

14章 一些小技巧

14.1 使用查表(lookup tables)

如果这个表能被cache到的话，程序会很快的，所以使用查表最好这个表不是很大（一个chache line能装下最好）

• table 应该声明为const，这样方便constant propagation

• 如果可以向量化就不要用查表了

• 程序中static memory 是分布在内存的各个部分（非连续）， 这一样就不好cache了，如果程序是memory bound 的话那么最好把在static memory的表拷贝到static memory中，因为static memory是连续的一块空间。如何声明 为static memory呢：如下所示：

  void CriticalInnerFunction(){
      const int Table[13] = {1,1,2,6,24,120,...};
      int i, a, b;
      for(i = 0; i < 1000; i++){
        ...
        a = Table[b];
        ...
      }
  }
  

• 两个常量二选一的情况很适合查表

  a = (b==0) ? 1.0f : 2.5f
  

  像上述代码可以这么改：

  float a; int b;
  const float OneOrTwo[2] = {1.0f, 2.5f};
  a = OneOrTwo[b&1];
  

  b是double或者float的话 a = OneOrTwo[b!=0]; 和 a = OneOrTwo[(b!=0)?1:0] 是一样的效果；
  b是int的话 a = OneOrTwo[b!=0] 和 a = OneOrTwo[b&1]是有一个效果;
  所以不要在b是浮点数的时候使用上述代码。
  b是浮点数的话，a = 1.0f + b * 1.5f 更快，因为没有分支预测。 但是如果b是int的话这个方法就不好用了，因为b由int转为float是很耗时的。

• switch 特别适合查表
  当然，前提是case是int值。否则无法索引。

14.2 边界检查(Bounds checking)

像如下代码：

float list[size];

if( i < 0 || i >= size){
    cout << "error" <<endl;
}
else{
    list[i] += 1;
}

对于这种 需要确保i是属于[0,size]的边界检查，可以这么做：

if ( (unsigned int)i >= (unsigned int)size ){
    cout << "error" << endl;
}
else{
    list[i] += 1;
}

这样的做法少了一个检查条件，而且signed int 转化为unsigned int是不耗时的
并且，这个方法使用图检查任何闭区间[min, max]的检查：

if (unsigned int)(i-min) <= (unsigned int)(max - min){
    ...
 }

如果 size是2的倍数的话还有一个更高效的办法：

float list[16];
list[i & 15] += 1.0f;

i&15 ==> i & 0b0000...00001111,就是屏蔽了高位而已，效果相当于i % 16， 但是这样更快（快速取模操作学会了）
不过这种方法有点问题：如果超了的话比如i = 18，那么就是list[2] += 1.0f，这样的结果是不对的。如果不在乎这种错误，上述方法明显更快。

14.3 位操作

位操作可以进行很多骚操作：
一般int是32位，（int_64是64位），也就是可以存32个bool类型，或者说可以表示32种类型（相应位置是1）。如：

enum Weekdays { Sunday, Mon, Tues, Wed, Thur, Fri, Sat}
Weekdays day
if( Day==Tur || Day == Wed || Day == Fri ){
    ...
}

k可以用位操作改成：

enum Weekdays { Sunday = 1, Mon = 2, Tues = 4, Wed = 8,
    Thur = 0x10, Fri = 0x20, Sat = 0x40};
Weekdays day;
if( Day & (Tur | Wed | Fri ) ){
    ...
}

上述代码好在：

1. (Tur | Wed | Fri ) 可以在编译阶段算出来是0x2c == ob00101100；
2. 所以上述代码在运行时只执行了一个&操作；
3. 位操作要比bool操作快的多。

• 位操作的好处在于可以把int作为bool向量来计算，| & ^ 的组合可以实现各种功能
• 还记得李恒的位操作的骚操作吗？你值得拥有

14.4 乘法优化

• 整数的乘法一般耗时3-10个cycle， 编译器通常会将一些乘法转化成移位操作和加法操作。比如说a*16被转换成a<<4，a * 17转换成a<<4 + a

• 矩阵的数据访问和类的成员的调用也包含乘法，所以矩阵的列数最好是2的指数，类(包括struct)的大小最好是2的指数。
  例如：

  struct S1{
    int a;
    int b;
    int c;
    int UnusedFilter;
  } 
  S1 list[100];
  for(i=0; i < 100; i++){
    list[j].a = list[j].b + list[j].c;
  }
  

  在如上代码中，list[j].b的地址即：&list[j].b = &list[0] + 4 * sizeof(int) * j + sizeof(int);
  4 * sizeof(int) * j 中的4就是struct的大小，如果struct S只有abc三个int的话这个数就是3，也就不能用移位的操作来代替乘法，所以说添加一个UnusedFilter是有必要的。

• 在矩阵类型的访问中（上面的struct数组也算是矩阵类型的）如果访问是非线性的，那么上述技巧肯定是有意义的，因为
  可以用移位代替乘法操作；

• 但如果访问类型是线性的那么cache则起到了决定性的作用，即我们应该尽可能的使得cache miss尽可能的少。因此
  前面看过的矩阵的列数是2的大整数倍的情况所造成的cache疯狂替换（cache contention）造成的性能下降是我们应该极力避免的。

14.5 除法优化

整数除法操作要比整数的加减乘更耗时，32位int的除法大约是27-80个clock cycles。
一些优化过的编译器可能会将一些除法进行优化：如将a/b 改成 a*(2^n / b) >> n；2^n 会在编译阶段提前算好。

• 关于整数除法（取模），有这么三条原则可以借鉴：

  1. 确保除数在编译阶段可以确定，因为被常量除比变量除更快。
  2. 如果除数是2的指数那更快了。
  3. 如果被除数是unsigned int 那就更更快了。

• 对于i/a（i是loop counter，a是个小整数），可以使用循环展开来避免一些问题：

  int list[300];
  int i;
  for(i = 0; i < 300; i++){
    list[i] += 1/3;
  }
  

  像上面代码就可以改成：

  int list[300];
  int i i_div_3;
  for(i = i_div_3 = 0; i < 300; i+=3, i_div_3++){
    list[i]   += i_div_3;
    list[i+1] += i_div_3;
    list[i+2] += i_div_3;
  }
  

  这样写其实是利用了这么一个事情：i/3在i递增的过程总有三个相同的数(即i/3,(i+1)/3, (i+2)/3 的结果都是i_div_3), 多了几个加法操作但是消除了除法操作，不亏；
  取模操作也是同样道理。

14.6 浮点数除法

浮点数的除法大约要20-45个clock cycles。相对于乘法和加法这其实是个比较大的开销。所以能用乘法就用乘法。像a = b/1.2345可以写成a = b*(1/1.2345), 因为1/1.2345可以在编译时刻就算出来，不用等到执行的时候再算，所以能快一点。但是这种做法会损失一部分精度，而且如果你的编译选项选择了fast模式 ,编译器可能会自己就把这步给做了。

参考stack overflow上的高赞答案, 描述了gcc上添加-ffast-math之后主要做了什么优化；

-ffast-math does a lot more than just break strict IEEE compliance.
First of all, of course, it does break strict IEEE compliance, allowing e.g. the reordering of instructions to something which is mathematically the same (ideally) but not exactly the same in floating point.
Second, it disables setting errno after single-instruction math functions, which means avoiding a write to a thread-local variable (this can make a 100% difference for those functions on some architectures).
Third, it makes the assumption that all math is finite, which means that no checks for NaN (or zero) are made in place where they would have detrimental effects. It is simply assumed that this isn't going to happen.
Fourth, it enables reciprocal approximations for division and reciprocal square root.
Further, it disables signed zero (code assumes signed zero does not exist, even if the target supports it) and rounding math, which enables among other things constant folding at compile-time.
Last, it generates code that assumes that no hardware interrupts can happen due to signalling/trapping math (that is, if these cannot be disabled on the target architecture and consequently do happen, they will not be handled).

gcc -ffast-math

• 还有一些可以自己手动优化的东西像 a>b/c 改成 a * b > c ; y = a/b + c/d 改成 y = (a * d + c * b)/(bd) 这样的简单数学化简
  一个比较好的例子：

  double a1, a2, b1, b2, y1, y2;
  y1 = a1 / b1;
  y2 = a2 / b2;
  

  更快的版本：

  double a1, a2, b1, b2, y1, y2, reciprocal_divisor;
  reciprocal_divisor = 1.0/(b1 * b2); //注意，如果a b 类型是float的话1.0 写成1.0f，具体原因下小节解释
  y1 = a1 * b2 * reciprocal_divisor;
  y2 = a2 * b1 * reciprocal_divisor;
  

14.7 不要将float和double 混着用

64位处理器处理double和float的时候通常耗时是一样，但是你如果把float和double混着用就会产生额外的类型转换的时间。
如：

float a, b;
a = b * 1.2;

c/c++ 默认认为你的浮点数常数是double类型，所以1.2 在上面代码中是double类型的浮点数，这样在进行计算的过程就会因数据转换而降低计算效率，所以应该把1.2声明为float或者把a、b声明为double：

//1
float a, b;
a = b * 1.2f;

//2
double a, b;
a = b * 1.2;

14.8 浮点数与整数之间的转换

1. floating -> int

   1. 在32系统中，如果没有使用SSE2指令集的话，浮点数到整数的转换大约是40个clock cycle。而且转化方法使用的是truncation而不是rounding。
      truncation指的是截断，就是只保留浮点数的整数部分；
      rounding指的是四舍五入，就是1.2是1，1.6是2那种，如果是.5的话就取偶数值。即1.5是2，2.5还是2。
      而且rounding要比truncation快很多（在32位非sse2的情况下）， 64位情况下默认使用SSE2指令集，truncation和rounding没有效率上的差别。
   2. 如果你想使用rounding的话，下面代码更快：（但是不比truncation快）

   //float to int truncation
   static inline lrintf(float cont x){
       return _mm_cvtss_si32(_mm_load_ss(&x));
   }
   double to int truncation
   static inline int lrint(double const x){
       return _mm_cvtsd_si32(_mm_load_sd(&x));
   }
   

2. int -> floating

整数转成浮点数的速度比浮点数转换成整数要快，大概是5-20 clock cycle。

• unsigned int 转换为浮点数比signed int更慢，所以在确定int值是正数且小于2^31的情况下，可以先将usigned int 转化为signed int，然后再转换为floating。
  而且usigned int转化为int 是没有额外消耗的。

14.9 使用整数的操作来操作浮点数

在c/c++中浮点数表示如下：

struct Sfloat {
    unsigned int fraction : 23; // fractional part
    unsigned int exponent : 8; // exponent + 0x7F
    unsigned int sign : 1; // sign bit
};

struct Sdouble {
    unsigned int fraction : 52; // fractional part
    unsigned int exponent : 11; // exponent + 0x3FF
    unsigned int sign : 1; // sign bit
};

struct Slongdouble {
    unsigned int fraction : 63; // fractional part
    unsigned int one : 1; // always 1 if nonzero and normal
    unsigned int exponent : 15; // exponent + 0x3FFF
    unsigned int sign : 1; // sign bit
};

• 使用整数操作浮点数的原理很简单，就是利用union结构的特性，因为int和float都是32位，所以一些操作可以直接进行位操作，比如求绝对值、判断是否等于0等等。
  具体操作看146页各种实例。
• 有一点需要注意：union会强制让数据保存在内存中而不是放在寄存器里面，所以如果说float变量可以作为寄存器变量的话最好不用使用上述方法来计算，因为得不偿失