# 2017q1 Homework2 (raytracing) contributed by <`xdennisx`> ### Reviewed by `PeterTing` * 可以使用 OpenMP 來進行優化，個人覺得它簡單且好用。 * 可以加上圖表分析，使差異能夠一眼看出來。 ## 前置作業 ### gprof gprof 可以讓你知道你的程式在哪些部份花了多久的時間，也可以知道 function 之間 call 來 call 去的關係，這些資訊可以讓你發現你的程式中哪些部份執行的速度比你預期中的慢，或是哪些 function call 的次數比想像中的多，這些都是開發者想要增進效能一個很好切入的點 使用前將編譯器加入 `-pg`，這邊就打 `make PROFILE=1` 就好 ```shell dennis@dennis-X550CC:~/raytracing$ 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. cc -std=gnu99 -Wall -O0 -g -pg -c -o main.o main.c cc -o raytracing objects.o raytracing.o main.o -lm -pg ``` 執行他！ ```shell dennis@dennis-X550CC:~/raytracing$ ./raytracing # Rendering scene Done! Execution time of raytracing() : 7.107704 sec ``` 追蹤他！ ```shell $ gprof ./raytracing | less ``` 結果 ```shell Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 24.21 0.60 0.60 69646433 0.00 0.00 dot_product 17.35 1.03 0.43 56956357 0.00 0.00 subtract_vector 11.10 1.31 0.28 31410180 0.00 0.00 multiply_vector 10.09 1.56 0.25 13861875 0.00 0.00 rayRectangularIntersection 8.07 1.76 0.20 10598450 0.00 0.00 normalize 5.65 1.90 0.14 17821809 0.00 0.00 cross_product 5.25 2.03 0.13 17836094 0.00 0.00 add_vector 4.03 2.13 0.10 13861875 0.00 0.00 raySphereIntersection 3.23 2.21 0.08 2110576 0.00 0.00 compute_specular_diffuse 2.42 2.27 0.06 4620625 0.00 0.00 ray_hit_object 2.02 2.32 0.05 1048576 0.00 0.00 ray_color 1.21 2.35 0.03 2110576 0.00 0.00 localColor 1.01 2.37 0.03 4221152 0.00 0.00 multiply_vectors 0.81 2.39 0.02 1241598 0.00 0.00 reflection 0.61 2.41 0.02 2558386 0.00 0.00 idx_stack_empty 0.61 2.42 0.02 1204003 0.00 0.00 idx_stack_push 0.40 2.43 0.01 3838091 0.00 0.00 length 0.40 2.44 0.01 2520791 0.00 0.00 idx_stack_top : ``` ## 優化 ### Loop Unrolling 從上面那張圖發現 `dot_product` 花的時間最多，所以我們從這裡下手，把裡面的 for loop unrolling ```c= dp = v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2]; ``` 再分析一次 ```shell dennis@dennis-X550CC:~/raytracing$ ./raytracing # Rendering scene Done! Execution time of raytracing() : 6.665834 sec ``` 時間成功下降！ ```shell Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 21.50 0.49 0.49 56956357 0.00 0.00 subtract_vector 13.60 0.80 0.31 69646433 0.00 0.00 dot_product 11.19 1.06 0.26 31410180 0.00 0.00 multiply_vector 9.22 1.27 0.21 10598450 0.00 0.00 normalize 8.56 1.46 0.20 13861875 0.00 0.00 rayRectangularIntersection 8.34 1.65 0.19 17836094 0.00 0.00 add_vector 7.02 1.81 0.16 17821809 0.00 0.00 cross_product 6.14 1.95 0.14 4620625 0.00 0.00 ray_hit_object 5.92 2.09 0.14 13861875 0.00 0.00 raySphereIntersection 2.41 2.14 0.06 4221152 0.00 0.00 multiply_vectors 2.19 2.19 0.05 1048576 0.00 0.00 ray_color 1.32 2.22 0.03 2110576 0.00 0.00 compute_specular_diffuse 0.66 2.24 0.02 1204003 0.00 0.00 idx_stack_push 0.44 2.25 0.01 2520791 0.00 0.00 idx_stack_top 0.44 2.26 0.01 37595 0.00 0.00 idx_stack_pop 0.44 2.27 0.01 1 0.01 2.28 raytracing 0.22 2.27 0.01 2558386 0.00 0.00 idx_stack_empty 0.22 2.28 0.01 1048576 0.00 0.00 rayConstruction : ``` `dot_product`，成功從第一名變第二名 把所有的迴圈 unroll ```shell dennis@dennis-X550CC:~/raytracing$ ./raytracing # Rendering scene Done! Execution time of raytracing() : 6.454031 sec ``` ### inline `inline` 對 compiler 來說只是個**建議**的詞，不是說你打 `inline` 就一定會 `inline`，所以如果要強制 `inline` ，就需要在 `inline` 後面加上 `__attribute__ ((always_inline))` 從6.45秒變成2.94秒是否有點誇張:fearful: ```shell dennis@dennis-X550CC:~/raytracing$ ./raytracing # Rendering scene Done! Execution time of raytracing() : 2.941980 sec ``` ### pthread 把 `raytracing()` 裡面的 `for loop` 做平行化處理，這是把一張圖等分成四份，從上到下 ```c= int gap = arg->height / arg->thread_count; int end = (arg->thread_index == (arg->thread_count)-1) ? arg->height : gap * (arg->thread_index + 1); for (int j = arg->thread_index * gap; j < end; j++) { for (int i = 0; i < arg->width; i++) { ``` 大概下降 0.5 秒 ```shell= dennis@dennis-X550CC:~/raytracing$ ./raytracing # Rendering scene Done! Execution time of raytracing() : 2.465868 sec ``` 有個奇妙的地方，我用一樣多的 thread 去做同樣的事，只是順序不太一樣，結果竟然有差！ ```c= for (int j = arg->thread_index; j < arg->height; j+=arg->thread_count) ``` 跟上一種 thread 大概也差了 0.4 秒，這樣前後差了就快 1 秒 ```shell dennis@dennis-X550CC:~/raytracing$ ./raytracing # Rendering scene Done! Execution time of raytracing() : 2.086082 sec ``` 不知道怎樣的順序會是最快的？ ## Reference - [twzjwang](https://hackmd.io/OwFgzAbAhlCcwFoQCMoEYkA4AmmGdgCYwEAzWUkUgBmTWmwFYg==?both)