HackMD
Raytracing
Reviewed by Quexint
- 除了數學函式外，應試著平行化 raytracing 函式，較難平化但效益很大。
dot_product可全部寫在同一行，應該會快不少。- 數學函式可試著開啟強制
inline或用 CPU 指令集加速。
開發環境
-
作業系統： Ubuntu 16.04 LTS （64 bit）
-
CPU：2-core Intel® Core™ i5-5257U CPU @ 2.70GHz
-
Memory：16G
-
Cache：
- L1 data : 32kB
- L1 instruction : 32kB
- L2 : 256kB
使用 lscpu 和 sudo lshw 可看到硬體資訊
預期目標
- 善用gprof
- 了解光線追蹤如何運行
按照作業步驟實作，併紀錄問題
$ git clone https://github.com/sysprog21/raytracing
$ cd raytracing
$ make
$ ./raytracing
結果
#Rendering scene
Done!
Execution time of raytracing() : 2.568730 sec
comment
execution time of raytracing 2.568730 sec 如何來？ HankLo
打開-pg編譯，可以使程式生成gprof數據併分析。
$ make clean
$ make PROFILE=1
$ ./raytracing
結果時間從原本的2.568730s 提升到 5.65922s秒，因為將程式生成gprof數據要花費時間。
# Rendering scene
Done!
Execution time of raytracing() : 5.659222 sec
gprof分析數據，如何程式提升效能。
$gprof ./raytracing | less
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
26.16 0.57 0.57 69646433 0.00 0.00 dot_product
20.20 1.01 0.44 56956357 0.00 0.00 subtract_vector
10.33 1.24 0.23 31410180 0.00 0.00 multiply_vector
7.80 1.41 0.17 17836094 0.00 0.00 add_vector
6.88 1.56 0.15 10598450 0.00 0.00 normalize
6.43 1.70 0.14 13861875 0.00 0.00 rayRectangularIntersection
6.43 1.84 0.14 13861875 0.00 0.00 raySphereIntersection
5.51 1.96 0.12 17821809 0.00 0.00 cross_product
4.13 2.05 0.09 4620625 0.00 0.00 ray_hit_object
1.84 2.09 0.04 1048576 0.00 0.00 ray_color
1.38 2.12 0.03 2110576 0.00 0.00 compute_specular_diffuse
1.15 2.14 0.03 4221152 0.00 0.00 multiply_vectors
0.92 2.16 0.02 3838091 0.00 0.00 length
0.46 2.17 0.01 1241598 0.00 0.00 protect_color_overflow
0.46 2.18 0.01 1 0.01 2.18 raytracing
0.00 2.18 0.00 2558386 0.00 0.00 idx_stack_empty
前三項dot_product、subtract_vector、multiply_vector所花時間最劇，佔了總體時間46%。可能針對這三個數學式子作改善，提昇效能。
觀察math-toolkit
- 觀察dot_product
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;
}
原始dot_product是用迴圈來計算dot_product，而使用迴圈會有branch的情況發生。這地方可以不需要用loop，可直接將其展開，減少程式執行序。
static inline
double dot_product(const double *v1, const double *v2)
{
double dp = 0.0;
dp += v1[0] * v2[0];
dp += v1[1] * v2[1];
dp += v1[2] * v2[2];
return dp;
}
結果，時間從5.659222降為5.285118，快了0.374秒。
# Rendering scene
Done!
Execution time of raytracing() : 5.285118 sec
使用gprof檢查。
$gprof ./raytracing | less
dot_product時間從0.57s降為0.10s。
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
31.97 0.54 0.54 56956357 0.00 0.00 subtract_vector
11.84 0.74 0.20 31410180 0.00 0.00 multiply_vector
10.66 0.92 0.18 13861875 0.00 0.00 rayRectangularIntersection
9.77 1.09 0.17 17836094 0.00 0.00 add_vector
6.51 1.20 0.11 4620625 0.00 0.00 ray_hit_object
5.92 1.30 0.10 69646433 0.00 0.00 dot_product
5.33 1.39 0.09 17821809 0.00 0.00 cross_product
3.55 1.45 0.06 13861875 0.00 0.00 raySphereIntersection
3.55 1.51 0.06 10598450 0.00 0.00 normalize
1.78 1.54 0.03 2110576 0.00 0.00 localColor
1.78 1.57 0.03 1048576 0.00 0.00 rayConstruction
1.78 1.60 0.03 1048576 0.00 0.00 ray_color
1.78 1.63 0.03 1 0.03 1.69 raytracing
1.48 1.65 0.03 3838091 0.00 0.00 length
- 觀察subtract_vector
subtract_vector跟dot_product用一樣的方法，建議將迴圈拿掉，減少branch發生，減少程序運算數目。
void subtract_vector(const double *a, const double *b, double *out)
{
for (int i = 0; i < 3; i++)
out[i] = a[i] - b[i];
}
改寫subtract_vector。
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];
}
結果，時間從5.285118s降為5.045020s，快了0.240秒。
# Rendering scene
Done!
Execution time of raytracing() : 5.045020 sec
使用gprof檢查。結果subtract_vector從0.54s降為0.14，但dot_product從0.10升到0.15
comment
dot秒數為合上升？嘗試將檔案清楚後在make PROFILE=1後得到的數據又不一樣。HankLo
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
15.16 0.20 0.20 17836094 0.00 0.00 add_vector
14.78 0.40 0.20 31410180 0.00 0.00 multiply_vector
11.37 0.55 0.15 69646433 0.00 0.00 dot_product
10.61 0.69 0.14 56956357 0.00 0.00 subtract_vector
9.85 0.82 0.13 13861875 0.00 0.00 rayRectangularIntersection
7.20 0.91 0.10 17821809 0.00 0.00 cross_product
6.82 1.00 0.09 4620625 0.00 0.00 ray_hit_object
4.55 1.06 0.06 1048576 0.00 0.00 ray_color
3.79 1.11 0.05 13861875 0.00 0.00 raySphereIntersection
3.79 1.16 0.05 10598450 0.00 0.00 normalize
3.03 1.20 0.04 4221152 0.00 0.00 multiply_vectors
3.03 1.24 0.04 2110576 0.00 0.00 compute_specular_diffuse
- 嘗試將檔案make clean後在make PROFILE=1後得到的數據又不一樣。同樣的程式，dot_product從0.15降為0.13，而subtract_vector從0.14升到0.17。
comment
gprof可以量測程式執行時間，因為是量測，會有誤差是可接受的行為。gprof還是能幫助使用者找出改善效能的地方，這是它實用的地方。HankLo
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
15.37 0.22 0.22 31410180 0.00 0.00 multiply_vector
12.15 0.39 0.17 56956357 0.00 0.00 subtract_vector
11.08 0.54 0.16 13861875 0.00 0.00 rayRectangularIntersection
10.72 0.69 0.15 17836094 0.00 0.00 add_vector
8.93 0.82 0.13 69646433 0.00 0.00 dot_product
6.43 0.91 0.09 10598450 0.00 0.00 normalize
6.43 1.00 0.09 4620625 0.00 0.00 ray_hit_object
5.72 1.08 0.08 1048576 0.00 0.00 ray_color
5.72 1.16 0.08 17821809 0.00 0.00 cross_product
5.36 1.23 0.08 13861875 0.00 0.00 raySphereIntersection
2.86 1.27 0.04 4221152 0.00 0.00 multiply_vectors
