0

Optimize（程序优化） - 江水为竭

 1 year ago
source link: https://www.cnblogs.com/Az1r/p/16825441.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

十大优化法则

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. 比如在字符串遍历中，每次获取字符串长度：

      highlighter- axapta
      for(int i = 0; i < strlen(str); i ++ ) str[i] = i;

    4. 将体量小的函数使用inline内联优化，比如min函数，max函数。

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

    1. 原因：存在内存别名的情况。编译器保守的方法是不断的读和写内存，即使这样效率不高。
    2. 引入局部变量，用局部变量计算后，再写入内存。
    1. 理解现代处理器：流水线。
    2. 指令集并行：硬件可以并行执行多个指令。
    3. 超标量处理器：一个周期执行多条指令， 这些指令是从一个连续的指令流获取的，通常被动态调度的。
    4. 循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。

  5. 提高并行性

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

    2. 多个累计变量

      在计算Pn=∏i=0n−1ai时，可以写为Pn=PEn∗POn

      POn=∏i=0n/2−1a2i+1PEn=∏i=0n/2−1a2i

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

      highlighter- cpp
      /*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. 能用乘法就不用除法：

      highlighter- gcode
      //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 库， 获取运行前后时间钟，算出运行时间。

highlighter- javascript
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);
}

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

highlighter- inform7
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优化

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

highlighter- inform7
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;
	}
}

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

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

highlighter- inform7
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;
	}
}

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

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

c
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。

highlighter- inform7
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库。优化效果显著！

点击查看代码

highlighter- cpp
#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;
}

多进程优化

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

highlighter- inform7
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. 关于并发优化未实现优化仍未搞明白。

__EOF__


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK