14章 一些小技巧

14.1 使用查表(lookup tables)

如果這個表能被cache到的話掐场，程序會很快的飞苇，所以使用查表最好這個表不是很大（一個chache line能裝下最好）

• table 應(yīng)該聲明為const，這樣方便constant propagation

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

• 程序中static memory 是分布在內(nèi)存的各個部分（非連續(xù)）收夸， 這一樣就不好cache了坑匠，如果程序是memory bound 的話那么最好把在static memory的表拷貝到static memory中，因為static memory是連續(xù)的一塊空間卧惜。如何聲明 為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是浮點數(shù)的時候使用上述代碼。
  b是浮點數(shù)的話咽瓷，a = 1.0f + b * 1.5f 更快设凹，因為沒有分支預(yù)測。 但是如果b是int的話這個方法就不好用了忱详，因為b由int轉(zhuǎn)為float是很耗時的围来。

• switch 特別適合查表
  當(dāng)然，前提是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 轉(zhuǎn)化為unsigned int是不耗時的
并且胀蛮，這個方法使用圖檢查任何閉區(qū)間[min, max]的檢查：

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

如果 size是2的倍數(shù)的話還有一個更高效的辦法：

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

i&15 ==> i & 0b0000...00001111,就是屏蔽了高位而已，效果相當(dāng)于i % 16糯钙， 但是這樣更快（快速取模操作學(xué)會了）
不過這種方法有點問題：如果超了的話比如i = 18粪狼，那么就是list[2] += 1.0f，這樣的結(jié)果是不對的任岸。如果不在乎這種錯誤再榄，上述方法明顯更快。

14.3 位操作

位操作可以進(jìn)行很多騷操作：
一般int是32位享潜，（int_64是64位）困鸥，也就是可以存32個bool類型，或者說可以表示32種類型（相應(yīng)位置是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. 所以上述代碼在運行時只執(zhí)行了一個&操作澜术；
3. 位操作要比bool操作快的多。

• 位操作的好處在于可以把int作為bool向量來計算猬腰，| & ^ 的組合可以實現(xiàn)各種功能
• 還記得李恒的位操作的騷操作嗎鸟废？你值得擁有

14.4 乘法優(yōu)化

• 整數(shù)的乘法一般耗時3-10個cycle， 編譯器通常會將一些乘法轉(zhuǎn)化成移位操作和加法操作姑荷。比如說a*16被轉(zhuǎn)換成a<<4盒延，a * 17轉(zhuǎn)換成a<<4 + a

• 矩陣的數(shù)據(jù)訪問和類的成員的調(diào)用也包含乘法，所以矩陣的列數(shù)最好是2的指數(shù)厢拭，類(包括struct)的大小最好是2的指數(shù)兰英。
  例如：

  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的話這個數(shù)就是3，也就不能用移位的操作來代替乘法陨闹，所以說添加一個UnusedFilter是有必要的楞捂。

• 在矩陣類型的訪問中（上面的struct數(shù)組也算是矩陣類型的）如果訪問是非線性的，那么上述技巧肯定是有意義的趋厉，因為
  可以用移位代替乘法操作寨闹；

• 但如果訪問類型是線性的那么cache則起到了決定性的作用，即我們應(yīng)該盡可能的使得cache miss盡可能的少君账。因此
  前面看過的矩陣的列數(shù)是2的大整數(shù)倍的情況所造成的cache瘋狂替換（cache contention）造成的性能下降是我們應(yīng)該極力避免的繁堡。

14.5 除法優(yōu)化

整數(shù)除法操作要比整數(shù)的加減乘更耗時，32位int的除法大約是27-80個clock cycles乡数。
一些優(yōu)化過的編譯器可能會將一些除法進(jìn)行優(yōu)化：如將a/b 改成 a*(2^n / b) >> n椭蹄；2^n 會在編譯階段提前算好。

• 關(guān)于整數(shù)除法（取模）净赴，有這么三條原則可以借鑒：

  1. 確保除數(shù)在編譯階段可以確定绳矩，因為被常量除比變量除更快。
  2. 如果除數(shù)是2的指數(shù)那更快了玖翅。
  3. 如果被除數(shù)是unsigned int 那就更更快了翼馆。

• 對于i/a（i是loop counter，a是個小整數(shù)）金度，可以使用循環(huán)展開來避免一些問題：

  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遞增的過程總有三個相同的數(shù)(即i/3,(i+1)/3, (i+2)/3 的結(jié)果都是i_div_3), 多了幾個加法操作但是消除了除法操作应媚，不虧；
  取模操作也是同樣道理猜极。

14.6 浮點數(shù)除法

浮點數(shù)的除法大約要20-45個clock cycles中姜。相對于乘法和加法這其實是個比較大的開銷。所以能用乘法就用乘法魔吐。像a = b/1.2345可以寫成a = b*(1/1.2345), 因為1/1.2345可以在編譯時刻就算出來扎筒，不用等到執(zhí)行的時候再算莱找，所以能快一點。但是這種做法會損失一部分精度嗜桌，而且如果你的編譯選項選擇了fast模式 ,編譯器可能會自己就把這步給做了奥溺。

參考stack overflow上的高贊答案, 描述了gcc上添加-ffast-math之后主要做了什么優(yōu)化；

-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

• 還有一些可以自己手動優(yōu)化的東西像 a>b/c 改成 a * b > c ; y = a/b + c/d 改成 y = (a * d + c * b)/(bd) 這樣的簡單數(shù)學(xué)化簡
  一個比較好的例子：

  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，具體原因下小節(jié)解釋
  y1 = a1 * b2 * reciprocal_divisor;
  y2 = a2 * b1 * reciprocal_divisor;
  

14.7 不要將float和double 混著用

64位處理器處理double和float的時候通常耗時是一樣叔锐，但是你如果把float和double混著用就會產(chǎn)生額外的類型轉(zhuǎn)換的時間金踪。
如：

float a, b;
a = b * 1.2;

c/c++ 默認(rèn)認(rèn)為你的浮點數(shù)常數(shù)是double類型，所以1.2 在上面代碼中是double類型的浮點數(shù)蒋困，這樣在進(jìn)行計算的過程就會因數(shù)據(jù)轉(zhuǎn)換而降低計算效率，所以應(yīng)該把1.2聲明為float或者把a、b聲明為double：

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

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

14.8 浮點數(shù)與整數(shù)之間的轉(zhuǎn)換

1. floating -> int

   1. 在32系統(tǒng)中方灾，如果沒有使用SSE2指令集的話，浮點數(shù)到整數(shù)的轉(zhuǎn)換大約是40個clock cycle碌更。而且轉(zhuǎn)化方法使用的是truncation而不是rounding裕偿。
      truncation指的是截斷，就是只保留浮點數(shù)的整數(shù)部分痛单；
      rounding指的是四舍五入嘿棘，就是1.2是1，1.6是2那種旭绒，如果是.5的話就取偶數(shù)值鸟妙。即1.5是2，2.5還是2挥吵。
      而且rounding要比truncation快很多（在32位非sse2的情況下）重父， 64位情況下默認(rèn)使用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

整數(shù)轉(zhuǎn)成浮點數(shù)的速度比浮點數(shù)轉(zhuǎn)換成整數(shù)要快，大概是5-20 clock cycle脉幢。

• unsigned int 轉(zhuǎn)換為浮點數(shù)比signed int更慢歪沃，所以在確定int值是正數(shù)且小于2^31的情況下，可以先將usigned int 轉(zhuǎn)化為signed int嫌松，然后再轉(zhuǎn)換為floating沪曙。
  而且usigned int轉(zhuǎn)化為int 是沒有額外消耗的。

14.9 使用整數(shù)的操作來操作浮點數(shù)

在c/c++中浮點數(shù)表示如下：

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
};

• 使用整數(shù)操作浮點數(shù)的原理很簡單萎羔，就是利用union結(jié)構(gòu)的特性液走，因為int和float都是32位，所以一些操作可以直接進(jìn)行位操作，比如求絕對值缘眶、判斷是否等于0等等嘱根。
  具體操作看146頁各種實例。
• 有一點需要注意：union會強制讓數(shù)據(jù)保存在內(nèi)存中而不是放在寄存器里面巷懈，所以如果說float變量可以作為寄存器變量的話最好不用使用上述方法來計算该抒，因為得不償失