计算机组成原理-基于硬件原理的程序优化

1. 对于一些简单的函数，用内联函数替换。即：将代码中调用函数的步骤用函数体填充。这样就减少了调用函数的开销。

2. 消除循环的低效率。循环中可能存在需要执行多次，但是每次的计算结果都不变的表达式。此时可以把这一表达式移动到循环体之外。例如循环体的结束条件中，有时是以一个字符串的大小作为判据的。如果字符串的大小不变，那么不必每次调用strlen()函数，只需要在开始的时候调用一次即可。

3. 消除不必要的内存引用。例如求一个数组A所有元素的累加和，并将结果写入到一个储存在内存的变量中（如调用函数时，通过指针*dest来读取一个存储在内存中的变量）。如果将表达式写为*dest=*dest+A[i]，那么对于每一个i值，表达式的每一步都要读取一次内存并写入一次内存。此时可以用一个临时变量acc来保存结果，直接将最后结果写入到*dest中，由于临时变量acc被储存在寄存器中，此时就避免了内存的频繁读写。

4. 尽量用乘法代替除法，尽量用移位与加法运算代替乘除法。因为乘除法的在CPU计算时的延迟要大于加法，而除法的延迟又大于乘法且不是完全流水线化的。

5. 循环展开。增加每一次迭代时的操作数，从而减小循环的迭代次数。在使用优化等级3及以上（即编译时加上-O3），编译器会自动进行循环展开。

6. 提高并行性。由于CPU可以在每个时钟周期内执行多个操作（超标量），同时指令执行的顺序不一定与它们在机器级程序中的顺序一致，而且CPU的功能单元是流水线化的，因此可以使用一些办法来提高程序的并行性：

   1. 使用多个累积变量。 对于可结合和可交换的合并运算（如整数的累加累积，浮点数在相差不大情况下的累加和累积），可以将运算拆分成若干部分，并在最后合并结果。例如将一个n个数的累加拆分成2组n/2个数的累加，并在最后合并。对于延迟为L，容量为C的操作而言，循环展开因子至少为C*L时可以达到吞吐量界限。但是也并不意味着展开因子越多越好，由于寄存器的数量有限，如果临时变量过多，则会被保存到栈上去。

      例：同时使用循环展开与累积变量

      /* 2 x 2 loop unrolling */
         void combine6(vec_ptr v, data_t *dest)
         {
         	long i;
         	long length = vec_length(v);
         	long limit = length-1;
         	data_t *data = get_vec_start(v);
         	data_t acc0 = IDENT;
         	data_t acc1 = IDENT;
         	/* Combine 2 elements at a time */
         	for (i = 0; i < limit; i+=2) {
         		acc0 = acc0 OP data[i];
         		acc1 = acc1 OP data[i+1];
         	}
         	/* Finish any remaining elements */
         	for (; i < length; i++) {
         		acc0 = acc0 OP data[i];
         	}
         	*dest = acc0 OP acc1;
         }

   2. 重新结合变换。表达式acc=(acc*data[i])*data[i+1]与acc=acc*(data[i]*data[i+1])的运算所需时间是不同的。对于前者而言，需要等待括号内的值执行完之后才能执行下一步；而对于后者而言，由于CPU的流水线特性，计算括号内部分的时候，可以和acc的乘法运算同时进行。这样，就减少了计算数据流中关键路径上面操作的数量。

      又例：对于计算多项式的值，虽然第一段代码所需的乘法次数多于第二个，但是由于第一段代码中的两个乘法可以同时执行，因此反而第一段代码的速度更快

      double poly(double a[], double x, long degree)
      {
      	long i;
      	double result = a[0];
      	double xpwr = x; /* Equals x^i at start of loop */
      	for (i = 1; i <= degree; i++) {
      		result += a[i] * xpwr;
      		xpwr = x * xpwr;
      	}
      	return result;
      }
      
      double polyh(double a[], double x, long degree)
      {
      	long i;
      	double result = a[degree];
      	for (i = degree-1; i >= 0; i--)
      		result = a[i] + x*result;
      	return result;
      }

7. 将条件语句修改为功能式的风格。由于处理器具有投机执行的特性，因此对于一些结果不可预知的条件语句(如循环语句属于可以预知的)，这样修改可以提高函数的效率。例如一个将数组a和b中较小的元素保存在a中，较大的元素保存在b中的函数（只写主体部分）：

   for(i=0;i<n;i++){
       if(a[i]>b[i]){
           swap(a[i],b[i]);
       }
   }

   这一语句可修改为：

   for(i=0;i<n;i++){
       if(a[i]>b[i]){
           min=a[i]<b[i]?a[i]:b[i];
           max=a[i]<b[i]?b[i]:a[i];	
           a[i]=min;
           b[i]=max;
       }
   }

8. 选择合适的算法与数据结构，充分使用硬件性能。

9. 编写高速缓存友好的代码，即编写时间与空间局部性较好的代码。尽量增加对局部变量的反复引用；由于数据是以连续的块存储，因此在引用的时候尽量减小步长，例如引用数组的时候尽量由内到外引用，引用一个结构体的时候按照结构体中变量存储的顺序引用。

   例1：优化矩阵乘法

   for(k=0;k<n;k++){
   	for(i=0;i<n;i++){
   		r=A[i][k];
   		for(j=0;j<n;j++){
   			C[i][j]+=r*B[k][j];
   		}
   	}
   }

   例2：转置矩阵的时候，对矩阵分块进行操作

   #define B chunkdatas_length_of_side 
   void faster_transpose(int *dst, int *src, int dim) {    
       long limit = dim * dim;    
       for (int i = 0; i < dim; i += B) {        
           for (int j = 0; j < dim; j += B) {            
           /* Using blocking to improve temporal locality */             
               for (int k = i; k < i+B; ++k) {                
                   for (int l = j; l < j+B; ++l) {                    
                   /* independent calculations */                    
                       int d = l*dim + k;                    
                       int s = k*dim + l;                    
                       if (s < limit && d < limit) {                        
                           dst[d] = src[s]                    
                       }       
                   }
               }            
           }         
       }    
   }