Optimize(优化实验)

时间:2022-10-25 17:08:28

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 < strlen(str); i ++ ) str[i] = 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 < limit; i+=2){
      		acc0 = acc0 OP data[i];
      		acc1 = acc1 OP data[i+1];
      	}
      
      	/* Finish any remaining elements */
      	for(; i < limit ; i++){
      		acc0 = acc0 OP data[i];
      	}
      	*dest = acc0 OP acc1;
      }
      
    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 < limit; i+=2) {
      		acc = acc OP (data[i] OP data[i+1]);
          }
          /* Finish any remaining elements */
          for (; i < length; i++) {
              acc = acc OP data[i];
          }
          *dest = acc;
      }
      
  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 %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. 关于并发优化未实现优化仍未搞明白。