Optimize（程序优化）

十大优化法则

1.更快（本课程重点！）

2.更省（存储空间、运行空间）

3.更美（UI 交互）

4.更正确（本课程重点！各种条件下）

5.更可靠

6.可移植

7.更强大（功能）

8.更方便（使用）

9.更范（格式符合编程规范、接口规范 ）

10.更易懂（能读明白、有注释、模块化）

优化概述

十五种优化思路的名称，原理，实现方案

  1. 面向存储器的优化：cache无处不在

    1. 消除循环的低效率

      比如二维数组遍历运算中，按列枚举改为按行枚举，这是因为二维数组在内存的存储顺序是按行顺序存储的。

    2. 重新排列提高空间局部性：尽量优先使用连续空间内的值，因为cache line 载入值时会将其附近的值一同载入分块，提高每个cache块的利用率，将反复多次调用的值先运算完再更新cache line，减少cache miss的次数，提高cache利用率。
    3. 时间局部性：如果一个存储器位置被引用了一次，那么程序很可能在不远的将来重复引用它。
    4. 空间局部性：如果一个存储器位置被引用了一次，那么程序很可能在不远的将来引用附近的一个存储器位置。
  2. 减少过程调用

    1. 过程调用会带来开销，而且妨碍大多数形式的的程序优化。
    2. 程序行为中严重依赖执行环境的方面，程序员要编写容易优化的代码，以帮助编译器。
    3. 比如在字符串遍历中，每次获取字符串长度：

      for(int i = 0; i
    4. 将体量小的函数使用inline内联优化，比如min函数，max函数。
  3. 消除不必要的内存引用

    1. 原因：存在内存别名的情况。编译器保守的方法是不断的读和写内存，即使这样效率不高。
    2. 引入局部变量，用局部变量计算后，再写入内存。
  4. 循环展开

    1. 理解现代处理器：流水线。
    2. 指令集并行：硬件可以并行执行多个指令。
    3. 超标量处理器：一个周期执行多条指令， 这些指令是从一个连续的指令流获取的，通常被动态调度的。
    4. 循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。
  5. 提高并行性

    1. 硬件具有更高速率执行乘法和加法的潜力，但是代码不能利用这种能力。所以在一些计算中，我们可以将结果值拆为几个累计变量，提高并行性。或者，重新组合变换，减少结果值的更新次数。
    2. 多个累计变量

      在计算(P_n=prod_{i=0}^{n - 1}a_i)时，可以写为(P_n = PE_n * PO_n)

      (PO_n=prod_{i=0}^{n/2 - 1}a_{2i + 1}) (PE_n=prod_{i=0}^{n/2 - 1}a_{2i})

      /* 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
    3. 重新结合变换

      /*2 * 1a loop unrolling*/
/*运用2×1a循环展开，重新结合合并操作。这种方法增加了可以并行执行的操作数量*/
void combine7(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 acc = IDENT;

    /* Combine 2 elements at a time */
    for (i = 0; i
  6. COMVxx指令

    1. 原理：代替test/cmp+jxx，减少条件的判断，直接实现功能
    2. 实现方案：利用指令CMOVxx代替test/cmp + jxx
  7. 使用编译器的优化模式，-O:0 1 2 3

    1. 面向编译器的优化。
    2. 期望编译器能提高速度或者能够节省内存，对程序进行有偏向性的编译。
  8. 多线程优化

    1. 面向CPU的优化，利用CPU多核的性质，将任务分为多个线程
    2. 多线程与多进程的区别：

      1. 线程是进程的子集，一个进程可能由多个线程组成
      2. 多进程的数据是分开的，共享复杂。比如你可以一边听歌，一边玩游戏，实际上CPU在不断切换地工作，只是太快感觉不出来。
      3. 多线程共享进程数据，共享简单。
  9. 嵌入式汇编

    1. 原理：通过汇编语言更接近底层，通过对底层直接操作，防止编译器编译出一些冗繁的操作，省去一些不必要的判断
    2. 实现方案：利用嵌入汇编的方法，人为的对底层进行优化
  10. 减少除法等一些计算量大的运算的使用

    1. 用移位代替乘除法。
    2. 能用乘法就不用除法：

      //test1
while(a > b / c)// 1.1
while(a * c > b)// 1.2
//test2 取模运算
a = a % b       //2.1
while(a >= b)    //2.2
{
    a -= b;
}
  11. GPU编程

    1. 原理：利用GPU多核的特点，拥有更强的算力，可以更快的完成任务
    2. 实现方案：利用GPU运行程序
  12. 多进程优化

    1. 使用Linux C语言fork函数

    2. 一个进程，包括代码、数据和分配给进程的资源。fork ( )函数通过系统调用创建一个与原来进程几乎完全相同的进程，也就是两个进程可以做完全相同的事，但如果初始参数或者传入的变量不同，两个进程也可以做不同的事。

      一个进程调用 fork( )函数后，系统先给新的进程分配资源，例如存储数据和代码的空间。然后把原来的进程的所有值都复制到新的新进程中，只有少数值与原来的进程的值不同。相当于克隆了一个自己。

    3. fork函数参考链接：fork函数

优化实验

实验任务

​ 一个图像处理程序实现图像的平滑，其图像分辨率为1920*1080，每一点颜色值为64b，用long img [1920] [1080]存储屏幕上的所有点颜色值,颜色值可从0依行列递增，或真实图像。

平滑算法为：任一点的颜色值为其上下左右4个点颜色的平均值，即：

​ img[i] [j] = (img [i-1] [j] +img[i+1] [j]+img[i] [j-1] +img[i] [j+1] ) / 4。

请面向你的CPU与cache，利用本课程学过的优化技术，编写程序，并说明你所采用的优化方法。

前言

关于本次的平滑算法： 不考虑四周，不考虑前后变量改变带来的正确性问题，只作为优化的任务。

但如果考虑其正确性，用一个 dst [1920]] [1080] 存储平滑后的图像值也是可以的。

测量性能

使用C语言 time.h 库， 获取运行前后时间钟，算出运行时间。

void Test(void (*function)()) 
{
    clock_t t1 = clock();
    int t = 100;
    while(t--) 
    {
        function();
    }
    clock_t t2 = clock();
    printf("COST %ldmsn",(t2 - t1) * 1000 / CLOCKS_PER_SEC);
}

原始版本

先要写为可优化的版本，所以先枚举列再枚举行。

int i, j;
for(j = 1; j

面向cache优化

改为先枚举行，再枚举列。

int i, j;
for(i = 1; i

循环展开

减少迭代次数。但是实验结果是性能并没有优化（相比较上一个）。

原因应该是：前后变量有运算依赖关系。

int block = 4;
int i, j;

for(i = 1; i

并发优化

既然前后变量有运算依赖关系，那我们就不让有依赖关系，并保持循环展开的形式。

但实验结果是：没有优化多少，这个原因仍没搞懂，或许需要查看汇编代码。

int i, j;
//为什么是14：14|1918 
for(i = 1; i

分块优化

分块，使每次运算的数据恰好填满cache line，从而减少cache miss。

register int i, j;
register int i_, j_;
register int i__, j__;
int block = 8;// 8 * 8 = 64 = cache line
for(i = 1; i

多线程优化

利用CPU多核的特点，将任务分为多个子任务。

这里使用C语言pthread库。优化效果显著！

点击查看代码 
#include 
#include 
#include 
#include 

#define PTHREAD_NUM 6//线程总数
#define RECNUM 100 

typedef struct 
{
    int l;
    int r;
}PTH_ARGV;//线程参数结构体

typedef struct 
{
    int a;
}PTH_RETURN;//线程返回值结构体

#define HEIGHT 1080
#define WIDTH 1920

long img[HEIGHT][WIDTH];
int maxn(int x, int y)
{
    if(x >= y)
    {
        return x;
    }else
    {
        return y;
    }
}
int minn(int x, int y)
{
    if(x >= y)
    {
        return y;
    }else
    {
        return x;
    }
}

void *func(void *argv)//线程函数体
{
    PTH_ARGV *pth_argv;
    PTH_RETURN *pth_return = malloc(sizeof(PTH_RETURN));//为返回值申请空间
    pth_argv = (PTH_ARGV*)argv;//将参数强转为参数结构体

    {//线程要做的事情
        register int i, j;
        register int i_, j_;
        register int i__, j__;
        int block = 8;// 8 * 8 = 64 = cache line
        for(i = pth_argv->l; i r; i += block)
        {
            for(j = 1; j r, i + block);
                j__ = minn(WIDTH - 1, j + block);

                for(i_ = i; i_ l = maxn(1, i * HEIGHT / PTHREAD_NUM);
                pth_argv->r = minn(HEIGHT - 1, (i + 1) * HEIGHT / PTHREAD_NUM);
            }
            /*
        int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg);

        描述：创建一个线程。
        返回值：成功返回0，失败返回一个错误编号。
        参数：
        thread -- 回填创建的线程的PID。
        attr -- 特殊要求。默认为NULL.
        start_routine --  被创建的线程所执行的函数。
                void *(*start_routine) (void *)
        arg -- start_routine函数的传参。
        */
            pthread_create(pd + i,NULL,func,pth_argv);//创建线程
        }

        for(i = 0;i

多进程优化

也是没有明显的优化效果。

register int i, j;
register int i_, j_;
register int i__, j__;
int block = 8;
int id = fork();

if(id == 0) 
{
    for(i = 1; i

后记

  1. 当把除法改为移位：无明显优化。
  2. 内联函数：无明显优化。
  3. 多线程优化在96核的泰山服务器上运行反而性能拖慢了很多，查阅资料得知，这应该是Windows和Linux系统对线程不同的管理造成的， Linux和windows下多线程的区别，Linux下多线程反而造成Cache互相扰乱，从而极大拖慢了程序。
  4. 关于并发优化未实现优化仍未搞明白。

文章来源于互联网：Optimize（程序优化）

THE END
分享
二维码