技術文章 » Optimize（程式優化）

Optimize（程式優化）

2022-10-25 21:03: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;
}

多程序優化

也是沒有明顯的優化效果。

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. 關於並行優化未實現優化仍未搞明白。