十大优化法则

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

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

3.更美（UI 交互）

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

5.更可靠

6.可移植

7.更强大（功能）

8.更方便（使用）

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

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

优化概述

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

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

2. 减少过程调用

3. 消除不必要的内存引用

4. 循环展开

5. 提高并行性

6. COMVxx指令

7. 使用编译器的优化模式，-O:0 1 2 3

8. 多线程优化

9. 嵌入式汇编

10. 减少除法等一些计算量大的运算的使用

11. GPU编程

12. 多进程优化

优化实验

实验任务

​ 一个图像处理程序实现图像的平滑，其图像分辨率为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 %ldms\n",(t2 - t1) * 1000 / CLOCKS_PER_SEC);
}

原始版本

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

int i, j;
for(j = 1; j < WIDTH - 1; j ++ )
{
    for(i = 1; i < HEIGHT - 1; i ++ )
    {
        img[i][j] = (img[i - 1][j] + img[i + 1][j] + img[i][j + 1] + img[i][j - 1]) / 4;
    }
}

面向cache优化

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

int i, j;
for(i = 1; i < HEIGHT - 1; i ++ )
{
    for(j = 1; j < WIDTH - 1; j ++ )
    {
        img[i][j] = (img[i - 1][j] + img[i + 1][j] + img[i][j + 1] + img[i][j - 1]) / 4;
    }
}

循环展开

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

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

int block = 4;
int i, j;

for(i = 1; i < HEIGHT - 1; i ++ )
{
    for(j = 1; j < WIDTH - 4; j += block)
    {
        img[i][j] = (img[i - 1][j] + img[i + 1][j] + img[i][j + 1] + img[i][j - 1]) / 4;
        img[i][j + 1] = (img[i - 1][j + 1] + img[i + 1][j + 1] + img[i][j + 1 + 1] + img[i][j - 1 + 1]) / 4;
        img[i][j + 2] = (img[i - 1][j + 2] + img[i + 1][j + 2] + img[i][j + 1 + 2] + img[i][j - 1 + 2]) / 4;
        img[i][j + 3] = (img[i - 1][j + 3] + img[i + 1][j + 3] + img[i][j + 1 + 3] + img[i][j - 1 + 3]) / 4;
    }
    for(;j < WIDTH - 1; j ++ )
    {
        img[i][j] = (img[i - 1][j] + img[i + 1][j] + img[i][j + 1] + img[i][j - 1]) / 4;
    }
}

并发优化

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

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

int i, j;
//为什么是14：14|1918
for(i = 1; i < HEIGHT - 1; i ++ )
{
    for(j = 1; j < WIDTH - 1; j += 14)
    {
        img[i][j + 0] = (img[i - 1][j] + img[i + 1][j] + img[i][j + 1] + img[i][j - 1]) / 4;
        img[i][j + 2] = (img[i - 1][j + 2] + img[i + 1][j + 2] + img[i][j + 1 + 2] + img[i][j - 1 + 2]) / 4;
        img[i][j + 4] = (img[i - 1][j + 4] + img[i + 1][j + 4] + img[i][j + 1 + 4] + img[i][j - 1 + 4]) / 4;
        img[i][j + 6] = (img[i - 1][j + 6] + img[i + 1][j + 6] + img[i][j + 1 + 6] + img[i][j - 1 + 6]) / 4;
        img[i][j + 8] = (img[i - 1][j + 8] + img[i + 1][j + 8] + img[i][j + 1 + 8] + img[i][j - 1 + 8]) / 4;
        img[i][j + 10] = (img[i - 1][j + 10] + img[i + 1][j + 10] + img[i][j + 1 + 10] + img[i][j - 1 + 10]) / 4;
        img[i][j + 12] = (img[i - 1][j + 12] + img[i + 1][j + 12] + img[i][j + 1 + 12] + img[i][j - 1 + 12]) / 4;
    }
    for(j = 2; j < WIDTH - 1; j += 14)
    {
        img[i][j + 0] = (img[i - 1][j] + img[i + 1][j] + img[i][j + 1] + img[i][j - 1]) / 4;
        img[i][j + 2] = (img[i - 1][j + 2] + img[i + 1][j + 2] + img[i][j + 1 + 2] + img[i][j - 1 + 2]) / 4;
        img[i][j + 4] = (img[i - 1][j + 4] + img[i + 1][j + 4] + img[i][j + 1 + 4] + img[i][j - 1 + 4]) / 4;
        img[i][j + 6] = (img[i - 1][j + 6] + img[i + 1][j + 6] + img[i][j + 1 + 6] + img[i][j - 1 + 6]) / 4;
        img[i][j + 8] = (img[i - 1][j + 8] + img[i + 1][j + 8] + img[i][j + 1 + 8] + img[i][j - 1 + 8]) / 4;
        img[i][j + 10] = (img[i - 1][j + 10] + img[i + 1][j + 10] + img[i][j + 1 + 10] + img[i][j - 1 + 10]) / 4;
        img[i][j + 12] = (img[i - 1][j + 12] + img[i + 1][j + 12] + img[i][j + 1 + 12] + img[i][j - 1 + 12]) / 4;
    }
}

分块优化

分块，使每次运算的数据恰好填满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 < HEIGHT - 1; i += block)
{
    for(j = 1; j < WIDTH - 1; j += block)
    {
        i__ = minn(HEIGHT - 1, i + block);
        j__ = minn(WIDTH - 1, j + block);

        for(i_ = i; i_ < i__; i_ ++)
        {
            for(j_ = j; j_ < j__; j_ ++)
            {
                img[i_][j_] = (img[i_][j_ - 1] + img[i_][j_ + 1] + img[i_ - 1][j_] + img[i_ + 1][j_]) / 4;
            }
        }
    }
}

多线程优化

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

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

点击查看代码

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>

#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 < pth_argv->r; i += block)
        {
            for(j = 1; j < WIDTH - 1; j += block)
            {
                i__ = minn(pth_argv->r, i + block);
                j__ = minn(WIDTH - 1, j + block);

                for(i_ = i; i_ < i__; i_ ++)
                {
                    for(j_ = j; j_ < j__; j_ ++)
                    {
                        img[i_][j_] = (img[i_][j_ - 1] + img[i_][j_ + 1] + img[i_ - 1][j_] + img[i_ + 1][j_]) / 4;
                    }
                }
            }
        }

    }

    free(argv);//释放线程参数空间
    /*
    void pthread_exit(void *retval);
    描述：线程终止；类似于exit，exit是进程终止，两者差距在于结束的对象不同。
    参数：
    retval -- 要带回的值,可以为NULL，如果为NULL，则不需要线程返回值结构体，母线程也不会收到子线程的返回值
    */
    pthread_exit(pth_return);//线程结束，返回母线程需要的返回值，
}

int main()
{
    pthread_t pd[PTHREAD_NUM];//pid
    PTH_ARGV *pth_argv;//线程参数
    //PTH_RETURN *pth_return;//线程返回值

    int cnt = RECNUM;
    clock_t t1, t2;
    t1 = clock();
    while(cnt --)
    {
        int i;

        for(i = 0;i < PTHREAD_NUM;i ++)
        {
            //为线程参数申请空间（注：为什么要申请空间？因为不申请空间，所有线程公用同意参数空间，很可能发生线程间的抢占效果），此函数需要由子线程释放掉

            pth_argv = malloc(sizeof(PTH_ARGV));
              {//对线程参数结构体进行初始化
                pth_argv->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<PTHREAD_NUM;i++)
        {

            /*
            int pthread_join(pthread_t thread, void **retval);
            描述：给线程号为thread的线程收尸(线程结束后会变成僵尸线程（不占用空间，但占用线程号），父线程需要等待子线程结束，然后释放掉线程的线程号），
            一般是谁创建谁收尸（不是铁律，线程之间平等），可以起到阻塞非盲等的状态。
            返回值：成功时返回 0；出错时，它返回一个错误编号。
            参数：
            thread -- 线程ID
            retval -- 回填PID为thread的线程的的返回值，可以为NULL，为NULL时，父线程将不在接收到子线程回传的返回值。
            */
            //pthread_join(pd[i],(void **)&pth_return);//等待线程结束
            pthread_join(pd[i],NULL);//等待线程结束
            //free(pth_return);//释放掉线程返回值结构体
        }
    }

    t2 = clock();

    printf("COST %ldms\n",(t2 - t1) * 1000 / CLOCKS_PER_SEC);
    return 0;
} 

多进程优化

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

void Func6()
{
    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 < HEIGHT / 2; i += block)
        {
            for(j = 1; j < WIDTH - 1; j += block)
            {

                i__ = minn(HEIGHT / 2, i + block);
                j__ = minn(WIDTH - 1, j + block);
                for(i_ = i; i_ < i__; i_ ++)
                {
                    for(j_ = j; j_ < j__; j_ ++)
                    {
                        img[i_][j_] = (img[i_][j_ - 1] + img[i_][j_ + 1] + img[i_ - 1][j_] + img[i_ + 1][j_]) / 4;
                    }
                }
            }
        }
        exit(0);
    }
    else
    {
        for(i = HEIGHT / 2; i < HEIGHT - 1; i += block)
        {
            for(j = 1; j < WIDTH - 1; j += block)
            {
                i__ = minn(HEIGHT - 1, i + block);
                j__ = minn(WIDTH - 1, j + block);
                for(i_ = i; i_ < i__; i_ ++)
                {
                    for(j_ = j; j_ < j__; j_ ++)
                    {
                        img[i_][j_] = (img[i_][j_ - 1] + img[i_][j_ + 1] + img[i_ - 1][j_] + img[i_ + 1][j_]) / 4;
                    }
                }
            }
        }
    }
}

后记

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