# Raytracing

### Reviewed by `Quexint`

- 除了數學函式外，應試著平行化 raytracing 函式，較難平化但效益很大。
- `dot_product` 可全部寫在同一行，應該會快不少。
- 數學函式可試著開啟強制 `inline` 或用 CPU 指令集加速。

## 開發環境

* 作業系統： Ubuntu 16.04 LTS （64 bit）
* CPU：2-core Intel(R) Core(TM) 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 如何來？ [name=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後得到的數據又不一樣。[name=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還是能幫助使用者找出改善效能的地方，這是它實用的地方。[name=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