# 2017q1 Homework1 (raytracing)
contributed by<`jack81306`>
### Reviewed by `changyuanhua`
* commit 的標題要用命令口吻，所以不要用 ThirdOptimized 這類開頭（ 我之前也犯過相同錯誤 )
* 這裡有 [commit 錯誤](https://github.com/jack81306/raytracing/commit/a5ef3c8a1cd4ab20b1ca71b3732ded0491d2dbbf) 標題首字大寫
* 可以放你的程式碼在上面
* 可以加上圖表，比較你每次實驗的時間等等，這樣一眼就能看出你實驗的差異
###### tags:`jack81306`
## 開發環境
```
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 60
Model name: Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz
製程： 3
CPU MHz： 2463.049
CPU max MHz: 3200.0000
CPU min MHz: 800.0000
BogoMIPS: 5187.96
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
```
## 首次測試
* 為了和之後的優化做比較,因此先進行第一次尚未優化過的程式碼測試.
* 使用工具
* gprof: [gprof介紹教學](http://os.51cto.com/art/200703/41426.htm)
* graphviz: [graphviz使用](http://os.51cto.com/art/200703/41426_2.htm)
* gprof2dot: [gprof2dot安裝及使用](http://www.51testing.com/html/97/13997-79952.html)
---
* <big>第一次運行時間</big>
```
# Rendering scene
Done!
Execution time of raytracing() : 2.655307 sec
```
* <big>第一次運行時間（編譯時添加上-pg）</big>
```
# Rendering scene
Done!
Execution time of raytracing() : 5.475092 sec
```
* <big>運行時各 function 運行時間</big>
```
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
20.19 0.45 0.45 56956357 0.00 0.00 subtract_vector
18.40 0.86 0.41 69646433 0.00 0.00 dot_product
10.32 1.09 0.23 10598450 0.00 0.00 normalize
9.42 1.30 0.21 13861875 0.00 0.00 rayRectangularIntersection
8.08 1.48 0.18 17836094 0.00 0.00 add_vector
5.83 1.61 0.13 17821809 0.00 0.00 cross_product
5.61 1.74 0.13 31410180 0.00 0.00 multiply_vector
4.94 1.85 0.11 4620625 0.00 0.00 ray_hit_object
4.49 1.95 0.10 13861875 0.00 0.00 raySphereIntersection
3.14 2.02 0.07 1048576 0.00 0.00 ray_color
2.47 2.07 0.06 4221152 0.00 0.00 multiply_vectors
1.79 2.11 0.04 2110576 0.00 0.00 compute_specular_diffuse
0.90 2.13 0.02 3838091 0.00 0.00 length
0.90 2.15 0.02 1048576 0.00 0.00 rayConstruction
0.67 2.17 0.02 1204003 0.00 0.00 idx_stack_push
0.45 2.18 0.01 2520791 0.00 0.00 idx_stack_top
.
.
.
```
* 從運行時間中,我們可以發現到說`subtract_vector`和`dot_product`這兩個 function 是造成程式運行速度慢的原因,所以我第一次的優化打算對這兩個 funciton 進行優化.
>中英文字間請以空白隔開
>[name=課程助教][color=red]
---
* <big>圖表分析</big>
## 第一次優化
* 這次優化,我使用了[loop unrolling](https://zh.wikipedia.org/wiki/%E5%BE%AA%E7%8E%AF%E5%B1%95%E5%BC%80)的方法作為優化方法,我將subtract_vector和dot_product這兩個function進行循環展開,以降低浪費再計算回圈的時間.
* <big>第一次優化後運行時間</big>
```
# Rendering scene
Done!
Execution time of raytracing() : 2.236376 sec
```
* <big>第一次優化後運行時間(編譯時加上-pg選項)</big>
```
# Rendering scene
Done!
Execution time of raytracing() : 5.005224 sec
```
* 從這個結果看來,大約只有優化了0.4秒左右,實在是很少阿！現在我再來看一下,是什麼托慢了整體的運行時間.
* <big>運行時各function運行時間</big>
```
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
17.18 0.29 0.29 69646433 0.00 0.00 dot_product
12.06 0.49 0.20 31410180 0.00 0.00 multiply_vector
11.45 0.68 0.19 10598450 0.00 0.00 normalize
10.85 0.86 0.18 56956357 0.00 0.00 subtract_vector
7.84 0.99 0.13 4620625 0.00 0.00 ray_hit_object
7.53 1.11 0.13 17821809 0.00 0.00 cross_product
7.23 1.23 0.12 13861875 0.00 0.00 rayRectangularIntersection
5.42 1.32 0.09 17836094 0.00 0.00 add_vector
4.22 1.39 0.07 13861875 0.00 0.00 raySphereIntersection
3.01 1.44 0.05 4221152 0.00 0.00 multiply_vectors
3.01 1.49 0.05 2110576 0.00 0.00 compute_specular_diffuse
1.81 1.52 0.03 2520791 0.00 0.00 idx_stack_top
1.81 1.55 0.03 1048576 0.00 0.00 ray_color
1.81 1.58 0.03 1 0.03 1.64 raytracing
1.21 1.60 0.02 3838091 0.00 0.00 length
1.21 1.62 0.02 2110576 0.00 0.00 localColor
1.21 1.64 0.02 1 0.02 0.02 delete_sphere_list
0.60 1.65 0.01 1241598 0.00 0.00 reflection
0.60 1.66 0.01 1048576 0.00 0.00 rayConstruction
0.00 1.66 0.00 2558386 0.00 0.00 idx_stack_empty
0.00 1.66 0.00 10241598 0.00 0.00 protect_color_overflow
0.00 1.66 0.00 1241598 0.00 0.00 refraction
0.00 1.66 0.00 1204003 0.00 0.00 idx_stack_push
0.00 1.66 0.00 1048576 0.00 0.00 idx_stack_init
.
.
.
```
* 從這個運行時間可以觀察到說,subtract_vector的運行時間從0.45降低到0.18,而dot_product從0.41秒降0.29秒,雖然有降低,但是還不夠快,還要更快.
---
* <big>圖表分析</big>
<br>
## 第二次優化
* 第二次的優化,因為math-toolkit的function call都高達數千萬次,所以我把目標放在減少function call.
* 為了減少程式的function call,所以我把math-toolkit裡的funtion都加上了`__attribute__((always_inline))`.這條程式碼可以強制編譯器再編譯的時候,把function變為inline.
* <big>第二次運行時間</big>
```
# Rendering scene
Done!
Execution time of raytracing() : 1.929966 sec
```
* <big>第二次運行時間（編譯時附加參數-pg）</big>
```
# Rendering scene
Done!
Execution time of raytracing() : 2.634597 sec
```
* 這個結果讓我感到十分的驚訝阿！！沒有附加-pg參數的結果只減少了大約0.3秒,但是編譯時有附加pg參數的卻減少了2秒多.
* 於是我去閱讀了gprof的手冊,內容大概是,當你call一個function,會先執行額外的程式碼來紀錄時間與function名,**所以結果就是當function call變少時,加入-pg選項的所需的額外時間也會跟著減少.**
* 不過雖然function call 減少了許多,不過運行時間根第一次優化比起來,只減少了0.3秒左右,這速度還不夠快,還要更快阿！！！
---
* <big>圖表分析</big>
## 第三次優化
* 第三次優化原本打算使用pthread來進行平行處理,但是再看完pthread的使用方式以及程式碼後,發現我根本不知道從哪裡下手去切thread阿阿阿阿
* [pthread基本使用與介紹](http://dragonspring.pixnet.net/blog/post/32963482-posix%E7%B7%9A%E7%A8%8B(pthread)%E5%85%A5%E9%96%80%E6%96%87%E7%AB%A0%E5%88%86%E4%BA%AB)
* 於是我找了第二種方法,"OpenMP"來做平行處理,OpenMP的使用方式較為簡單,只要再回圈前面加入一些程式碼與參數即可,輸入之後,compile會自動將回圈內進行平行化處理.
* [OpenMP基本使用與介紹](https://kheresy.wordpress.com/2006/06/09/%E7%B0%A1%E6%98%93%E7%9A%84%E7%A8%8B%E5%BC%8F%E5%B9%B3%E8%A1%8C%E5%8C%96%E6%96%B9%E6%B3%95%EF%BC%8Dopenmp%EF%BC%88%E4%B8%80%EF%BC%89%E7%B0%A1%E4%BB%8B/)
* <big>第3-1次優化：失敗</big>
* 這次的優化我只有單純把raytracing裡的for回圈平行化,不過似乎會造成錯誤的結果,但是時間加快許多！！！
* <big>第3-1次優化運行時間</big>
```
# Rendering scene
Done!
Execution time of raytracing() : 0.999734 sec
```
* <big>第3-2次優化</big>
* 終於成功了,可喜可賀,這次我再優化選項後面添加了老師給的[共筆](https://embedded2016.hackpad.com/ep/pad/static/f5CCUGMQ4Kp)內所提到的private(stk,d,object_color),發現結果仍然錯誤.
* 於是我後來觀察了一下,發現r,g,b 3個變數會進行累加,如果進行平行化的話,會有錯誤的結果,於是又增加了參數private(r,g,b),給這3個變數增加副本,這次結果就正確了！！
* <big>3-2次優化運行時間</big>
```
# Rendering scene
Done!
Execution time of raytracing() : 0.907948 sec
```
## 參考資料
[loop unrolling簡介](https://zh.wikipedia.org/wiki/%E5%BE%AA%E7%8E%AF%E5%B1%95%E5%BC%80)
[forceInline方法](http://stackoverflow.com/questions/8381293/how-do-i-force-gcc-to-inline-a-function)
[OpenMG簡介與使用](https://kheresy.wordpress.com/2006/06/09/%E7%B0%A1%E6%98%93%E7%9A%84%E7%A8%8B%E5%BC%8F%E5%B9%B3%E8%A1%8C%E5%8C%96%E6%96%B9%E6%B3%95%EF%BC%8Dopenmp%EF%BC%88%E4%B8%80%EF%BC%89%E7%B0%A1%E4%BB%8B/)
[pthread簡介與使用](http://dragonspring.pixnet.net/blog/post/32963482-posix%E7%B7%9A%E7%A8%8B(pthread)%E5%85%A5%E9%96%80%E6%96%87%E7%AB%A0%E5%88%86%E4%BA%AB)
Sign in with Wallet
Connect another wallet