Optimize（優化實驗）
十大優化法則
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編程
- 原理：利用GPU多核的特點，擁有更強的算力，可以更快的完成任務
- 實現方案：利用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;
}
}
}
}
}
}
後記
- 當把除法改為移位：無明顯優化。
- 內聯函數：無明顯優化。
- 多執行緒優化在96核的泰山伺服器上運行反而性能拖慢了很多，查閱資料得知，這應該是Windows和Linux系統對執行緒不同的管理造成的， Linux和windows下多執行緒的區別，Linux下多執行緒反而造成Cache互相擾亂，從而極大拖慢了程式。
- 關於並發優化未實現優化仍未搞明白。
