十大优化法则

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

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

3.更美（UI 交互）

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

5.更可靠

6.可移植

7.更强大（功能）

8.更方便（使用）

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

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

优化概述

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

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

消除循环的低效率

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

重新排列提高空间局部性：尽量优先使用连续空间内的值，因为cache line 载入值时会将其附近的值一同载入分块，提高每个cache块的利用率，将反复多次调用的值先运算完再更新cache line，减少cache miss的次数，提高cache利用率。

时间局部性：如果一个存储器位置被引用了一次，那么程序很可能在不远的将来重复引用它。

空间局部性：如果一个存储器位置被引用了一次，那么程序很可能在不远的将来引用附近的一个存储器位置。

减少过程调用

过程调用会带来开销，而且妨碍大多数形式的的程序优化。

程序行为中严重依赖执行环境的方面，程序员要编写容易优化的代码，以帮助编译器。

比如在字符串遍历中，每次获取字符串长度：

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

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

消除不必要的内存引用

保守

不断的读和写内存

引入局部变量

循环展开

一个周期执行多条指令

循环展开

提高并行性

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

多个累计变量

在计算\(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;

}

重新结合变换

/*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;

}

COMVxx指令

原理：代替test/cmp+jxx，减少条件的判断，直接实现功能

实现方案：利用指令CMOVxx代替test/cmp + jxx

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

面向编译器的优化。

期望编译器能提高速度或者能够节省内存，对程序进行有偏向性的编译。

多线程优化

面向CPU的优化，利用CPU多核的性质，将任务分为多个线程

多线程与多进程的区别：

线程是进程的子集，一个进程可能由多个线程组成

多进程的数据是分开的，共享复杂。比如你可以一边听歌，一边玩游戏，实际上CPU在不断切换地工作，只是太快感觉不出来。

多线程共享进程数据，共享简单。

嵌入式汇编

原理

实现方案

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

用移位代替乘除法。

能用乘法就不用除法：

//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;

}

GPU编程

原理

实现方案

多进程优化

使用Linux C语言fork函数

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

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

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;

					}

				}

			}

		}

	}

}

Optimize（优化实验）

十大优化法则

优化概述

优化实验

实验任务

前言

测量性能

原始版本

面向cache优化

循环展开

并发优化

分块优化

多线程优化

多进程优化

后记

Optimize（优化实验）的相关教程结束。

相关推荐

OSPF 多区域配置实验

MySQL中的sql优化

（4）MySQL进阶篇SQL优化（常用SQL的优化）

MySQL系列(七)--SQL优化的步骤

[转]Mysql中的SQL优化与执行计划

（6）MySQL进阶篇SQL优化（MyISAM表锁）

基于mysql数据库关于sql优化的一些问题

MySQL 学习四 SQL优化

Optimize（优化实验）

十大优化法则

优化概述

优化实验

实验任务

前言

测量性能

原始版本

面向cache优化

循环展开

并发优化

分块优化

多线程优化

多进程优化

后记

Optimize（优化实验）的相关教程结束。

相关推荐

OSPF 多区域配置实验

MySQL中的sql优化

（4）MySQL进阶篇SQL优化（常用SQL的优化）

MySQL系列(七)--SQL优化的步骤

[转]Mysql中的SQL优化与执行计划

（6）MySQL进阶篇SQL优化（MyISAM表锁）

基于mysql数据库 关于sql优化的一些问题

MySQL 学习四 SQL优化

基于mysql数据库关于sql优化的一些问题