高效编码的建议

注：本文内容来源于大话处理器，如有侵权，请联系删除

1. 减少指令数

• 使用更快的算法
  举例：等差求和公式要比直接累加要快
• 选择合适的指令
  有些专用的指令，SIMD等
• 降低数据的精度
  float 类型的数据要比double数据运算速度快
• 减少函数的调用
  函数的调用会产生跳转，入栈出栈等，可以考虑使用inline关键字
• 空间换时间
• 减少过度保护

2. 减少处理器不擅长的操作

• 减少乘法的使用
  可以将乘$2^N$的运算改为移位操作
• 少用除法、求余
  可以将除法操作转换为乘法，例如除5可以改为乘0.2
• 在精度允许的情况下，将浮点数定点化
  从1分1000步减小到0，改为从1000减小到0
• 尽量减少分支
  例如：

for(int i = 0;i<100;i++)
{
    if(i%2==0)
    {
        a[i] = x;
    }
    else
    {
        a[i] = y;
    }
}

改为：

for(int i = 0;i<100;i+=2)
{
    a[i] = x;
    a[i+1] = y;
}

• 将最可能进入的分支放入if中，而不是else中
  由于分支预测的情况，会导致处理器预测失败

优化内存访问

• 少用数组和指针
  例如下面的代码需要四次内存访问：

c = a[i] + b[i];
d = a[i] * b[i];

改为：

x = a[i];
y = b[i];
c = x + y;
d = x * y;

• 少用全局变量
  全局变量不会存放到寄存器上，减少全局变量的调用次数
  例如：

int x;
int fun_a()
{
    int y,z;
    y = x;
    z = x + 1;
}

改为下边的形式减小全局变量的调用次数

int x;
int fun_a()
{
    int y,z,temp;
    y = temp;
    z = temp + 1;
}

• 一次多访问一些数据
• 数据对齐访问
• 大数据结构时采用Cache line对齐
  Intel的处理器Cache line大多为64 byte，因此处理大数据时最好也要64Byte对齐
• 程序、数据访问符合Cache的时间、空间局部性
  例如以下程序，如果a[i][j] 在Cache中，那么a[i][j+1] 大概率也在Cache中，但是a[i+1][j] 就不一定。

for(j=0;j<500;j++)
{
    for(i=0;i<500;i++)
    {
        sum += a[i][j];
    }
}

应该改为：

for(i=0;i<500;i++)
{
    for(j=0;j<500;j++)
    {
        sum += a[i][j];
    }
}

• 多线程编程时，避免false sharing
  False sharing（伪共享）是指多个线程同时访问同一缓存行中的不同变量，由于缓存一致性协议的原因，即使这些变量在内存中是不相干的，也会导致缓存行的频繁无效化和更新，从而降低程序的性能。
• 尽量少共享数据
• 尽量少修改数据
• 尽量少频繁的修改数据
• 自己管理内存动态分配
• 隐藏数据搬移的时间

3. 充分利用编译器进行优化

编译器优化会带来程序空间的额增加，因此不要过度有优化

• 编译器会计算常量
• 简单的表达式化简
  例如：

int a,b,c;
b = (a+5) * (a+5)
c = (a+5)/4;

编译器会转换为：

int a,b,c,temp;
temp = a+5;
b = temp * temp;
c = temp>>2;

• 提取公共语句
  如下：

i = 100；
while(i<0)
{
    i+=x+y;
    *p=i;
}

编译器会分析出x+y是独立于while循环之外的，可以将x+y提取出去

i = 100；
temp = x+y;
while(i<0)
{
    i+=temp;
    *p=i;
}

• 展开循环、软件流水
• 自动向量化
• 高效的数据组织，减小Cache miss
• 指令并行化

4. 利用多核加速

• 并行计算
• 任务划分
• 数据划分
• 数据流划分
• 多线程编程
• OpenMP
  例子：

#pragma omp parallel num_threads(8) //设置8个线程数
#pargma omp parallel for //将下边的for循环分到8个线程中执行
for(i=0;i<1024;i++)
{
    c[i] = a[i] + b[i];
}

0\~127 的数据作为一个线程， 128\~255 的数据作为一个线程……