2017q2 Homework2 (raytracing) - HackMD

owned this note owned this note

<style> h1.part{color:#000000;} h2.part{color:#005BB0;} h3.part{color:#D92424;} h4.part{color:#005BB0;} h5.part{color:#FD6F0A;} h6.part{color:#4400B0;} </style> # 2017q2 Homework2 (raytracing) contributed by <bananahuang> ## 複習 makefile ``` CFLAGS = \ -std=gnu99 -Wall -O0 -g LDFLAGS = \ -lm ifeq ($(strip $(PROFILE)),1) PROF_FLAGS = -pg CFLAGS += $(PROF_FLAGS) LDFLAGS += $(PROF_FLAGS) endif ``` `?=`若變數有值則不變，否則設定新值。 `CFLAGS`C語言編譯器參數 `-std=gnu99`使用c99規範加上「gcc的C語言擴展」`-Wall`輸出所有警告訊息 `-O0`關閉最佳化 `-g`產生debugging information for gdb `LDFLAGS`鏈結器參數 `-lm`連結到math.h library `$(strip <string>)`去掉<string>字串中開頭和結尾的空字符 ex：$(strip a b c )結果為「a b c」(少了最後的空格！) `PROF_FLAGS`這變數名稱是自己取的，不像上面的變數有通俗的用法 `-pg`這就是這次作業的東西了，我們必須再編譯時偷偷把每個function加上mcount，而在執行完程式時會產生profile data以做分析參考: [陳品睿共筆](https://embedded2016.hackpad.com/2016q1-Homework-2A-bLGQtRraTES#:h=%E7%A8%8B%E5%BC%8F%E9%81%8B%E4%BD%9C%E5%88%86%E6%9E%90) ## 前置作業(問題分析) **安裝開發工具** ``` $ sudo apt-get update $ sudo apt-get install graphviz $ sudo apt-get i ``` --- **取得原始碼並且編譯執行** ``` $ git clone https://github.com/bananahuang/raytracing $ cd raytracing $ make $ ./raytracing ``` --- **用$ make PROFILE=1前先清空個剛編譯的內容(make clean)才能重新編譯,而 make PROFILE=1可以新增一些函式分析整體效能** `$ make clean` `$ make PROFILE=1` ``` cc -std=gnu99 -Wall -O0 -g -pg -c -o objects.o objects.c cc -std=gnu99 -Wall -O0 -g -pg -c -o raytracing.o raytracing.c cc -std=gnu99 -Wall -O0 -g -pg -c -o main.o main.c cc -o raytracing objects.o raytracing.o main.o -lm -pg ``` --- `$ ./raytracing` ``` # Rendering scene Done! Execution time of raytracing() : 6.471156 sec ``` ==跑的時間增加到6.4秒== --- `$ls` ![](https://i.imgur.com/wXD5DdR.png) ==多了效能分析檔案 gmon.out== `$ ls -l gmon.out` ![](https://i.imgur.com/KXwXR4D.png) `$ gprof ./raytracing | less`:用 gprof 去做分析 ``` Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 19.20 0.52 0.52 69646433 0.00 0.00 dot_product 15.14 0.93 0.41 56956357 0.00 0.00 subtract_vector 10.34 1.21 0.28 13861875 0.00 0.00 rayRectangularIntersection 10.15 1.49 0.28 31410180 0.00 0.00 multiply_vector 8.86 1.73 0.24 10598450 0.00 0.00 normalize 7.38 1.93 0.20 17836094 0.00 0.00 add_vector 7.38 2.13 0.20 13861875 0.00 0.00 raySphereIntersection 6.28 2.30 0.17 4620625 0.00 0.00 ray_hit_object 4.43 2.42 0.12 17821809 0.00 0.00 cross_product 3.32 2.51 0.09 1048576 0.00 0.00 ray_color 1.85 2.56 0.05 1 0.05 2.71 raytracing 1.29 2.59 0.04 4221152 0.00 0.00 multiply_vectors 1.11 2.62 0.03 2110576 0.00 0.00 compute_specular_diffuse 0.74 2.64 0.02 2110576 0.00 0.00 localColor 0.74 2.66 0.02 1241598 0.00 0.00 reflection 0.74 2.68 0.02 1048576 0.00 0.00 rayConstruction 0.37 2.69 0.01 3838091 0.00 0.00 length 0.37 2.70 0.01 1204003 0.00 0.00 idx_stack_push ``` ==最耗效能點積,向量減法,追蹤矩型,向量乘法,正規化== ``` Call graph (explanation follows) granularity: each sample hit covers 2 byte(s) for 0.37% of 2.71 seconds index % time self children called name 0.05 2.66 1/1 main [2] [1] 100.0 0.05 2.66 1 raytracing [1] 0.09 2.46 1048576/1048576 ray_color [3] 0.02 0.09 1048576/1048576 rayConstruction [15] 0.00 0.00 1/1 calculateBasisVectors [22] 0.00 0.00 1048576/1048576 idx_stack_init [26] ----------------------------------------------- <spontaneous> [2] 100.0 0.00 2.71 main [2] 0.05 2.66 1/1 raytracing [1] 0.00 0.00 3/3 append_sphere [29] 0.00 0.00 3/3 append_rectangular [28] 0.00 0.00 2/2 append_light [30] 0.00 0.00 1/1 write_to_ppm [35] 0.00 0.00 1/1 delete_rectangular_list [32] 0.00 0.00 1/1 delete_sphere_list [33] : ``` ==call graph追蹤function and function之間關係== --- 提升效能方式：改善數學 SIMD快只有當程式做連續的處理,像是連續的加法連續的乘法 ## 使用工具比較： ==perf top==:每隔一段period會去做採樣(Sample)，最後統計出大概的數據。 ==gprof==：他在compile期間會將每一個function加上mcount (or _mcount, or __mcount)，故在編譯時需加上`-pg`，而在run time期間並會執行並紀錄，所以跑起來會比原程式慢的許多 ==graphviz==: `$ gprof ./raytracing | gprof2dot | dot -T png -o output.png`產生關聯圖 `$ convert output.png output.jpg ` 可將圖檔轉換格式 ![](https://i.imgur.com/uZhK32s.jpg) 參考： [<hugikun999>](https://hackmd.io/s/HyHhgcv6#) [ gprof、gprof2dot.py、dot使用方法简介 ](http://blog.csdn.net/u012927281/article/details/51132064) [Graphviz-用指令來畫關係圖吧](https://www.openfoundry.org/tw/foss-programs/8820-graphviz-) [使用Gnu gprof进行Linux平台下的程序分析(1)](http://os.51cto.com/art/200703/41426.htm) ## 程式探討 ```clike= static inline double dot_product(const double *v1, const double *v2) { double dp = 0.0; for (int i = 0; i < 3; i++) dp += v1[i] * v2[i]; return dp; } ``` ==inline==：提示編譯器在==最佳化==時把 function call 轉成程式碼,減少函式呼叫的時間 **注意**：須要在定義時加，若在宣告時加沒有作用，且可能會造成在complier時main過度龐大。另外如果函式內含有其它複雜度高的函式，則效益不大。 ==static==：這邊是定義,如果後面有接程式碼是定義,沒接就是宣告,inline 後的函數不保證不會留外部符號，由於可能有多檔案引用.h會造成重複定義故加 static 讓這個定義只會在這個檔案裡面有效 ### 啟發 inline 要在最佳化才會有用,但是我們前面 makefile 已經把編譯器最佳化關掉,所以這邊使用==force inline==,將所有 math-tool.kit.h 有用到 ==inline== 的地方,改成__attribute__((always_inline)),至於為甚麼是打這個,因為這是 gcc 的 extension makefile: ``` CFLAGS = \ -std=gnu99 -Wall -O0 -g ``` 參考: [<ggary9424的共筆>](https://embedded2016.hackpad.com/2016q1-Homework-2A-bLGQtRraTES#:h=%E7%A8%8B%E5%BC%8F%E9%81%8B%E4%BD%9C%E5%88%86%E6%9E%90) [<hugikun999>](https://hackmd.io/s/HyHhgcv6#) ## 優化方向 * Loop unrolling 藉由展開 function 而不使用呼叫的方式，可以減少花費在呼叫的時間，但是會造成程式本身的膨脹，有點類似空間換取時間的做法。參考:[<hugikun999>](https://hackmd.io/s/HyHhgcv6#) * Force inline 將 math-tool.kit.h 內的 inline 都改成__attribute__((always_inline)) ## 優化步驟 ### 1. loop unrolling (在 ==math-toolkit. h==裡 for loop 會有 branch 判斷,拖慢速度,先從這進行修改) ==dot_product== 原始 ```clike= static inline double dot_product(const double *v1, const double *v2) { double dp = 0.0; for (int i = 0; i < 3; i++) dp += v1[i] * v2[i]; return dp; } ``` 改成(減少 for 迴圈運算量) ```clike= static inline double dot_product(const double *v1, const double *v2) { double dp=0.0; dp=v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2]; return dp; } ``` 結果(19.20->13.24) ``` Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 19.20 0.52 0.52 69646433 0.00 0.00 dot_product 13.24 0.91 0.27 69646433 0.00 0.00 dot_product ``` ==subtract_vector== 原始 ```clike= static inline void subtract_vector(const double *a, const double *b, double *out) { for (int i = 0; i < 3; i++) out[i] = a[i] - b[i]; } ``` 改成(減少 for 迴圈運算量) ```clike= static inline void subtract_vector(const double *a, const double *b, double *out) { out[0] = a[0] - b[0]; out[1] = a[1] - b[1]; out[2] = a[2] - b[2]; } ``` 結果(15.14->8.81) ``` Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 15.14 0.93 0.41 56956357 0.00 0.00 subtract_vector 8.81 1.21 0.17 56956357 0.00 0.00 subtract_vector ``` ==multiply_vectors== 原始 ```clike= static inline void multiply_vectors(const double *a, const double *b, double *out) { for (int i = 0; i < 3; i++) out[i] = a[i] * b[i]; } ``` 更改 ```clike= static inline void multiply_vectors(const double *a, const double *b, double *out) { out[0] = a[0] * b[0]; out[1] = a[1] * b[1]; out[2] = a[2] * b[2]; } ``` 結果(錯誤示範更改了效益不高的函式,反而時間上升,1.29->1.67) ``` Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 1.29 2.59 0.04 4221152 0.00 0.00 multiply_vectors 1.67 1.72 0.03 4221152 0.00 0.00 multiply_vectors ``` ==multiply_vector== 原始 ```clike= static inline void multiply_vector(const double *a, double b, double *out) { for (int i = 0; i < 3; i++) out[i] = a[i] * b; } ``` 更改 ```clike= static inline void multiply_vector(const double *a, double b, double *out) { out[0] = a[0] * b; out[1] = a[1] * b; out[2] = a[2] * b; } ``` 結果(10.15->6.67) ``` Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 10.15 1.49 0.28 31410180 0.00 0.00 multiply_vector 6.67 1.04 0.11 31410180 0.00 0.00 multiply_vector ``` ### 結論 ``` Execution time of raytracing() : 6.377524 sec(原始) Execution time of raytracing() : 5.825273 sec(修改 dot_product) Execution time of raytracing() : 5.677439 sec（再修改 subtract_vector） Execution time of raytracing() : 5.304445 sec(再修改 multiply_vector) ``` ### 2. force inline 因為沒開啟編譯器最佳化,所以 inline 失去功能,這邊使用 force inline,把 math-tool.kit.h 內的 inline 都改成__attribute__((always_inline)) ==出現問題==：scalar_triple_product and scalar_triple 只能用inline ``` math-toolkit.h:72:6: warning: ‘scalar_triple_product’ defined but not used [-Wunused-function] void scalar_triple_product(const double *u, const double *v, const double *w, ^ math-toolkit.h:80:8: warning: ‘scalar_triple’ defined but not used [-Wunused-function] double scalar_triple(const double *u, const double *v, const double *w) ``` 結果(5.3s->2.75s) ``` # Rendering scene Done! Execution time of raytracing() : 2.754019 sec ```

Cheatsheet

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.