# 2017q1 Homework2(raytracing)
contributed by < `potinglee` >
## 開發環境
* OS： Ubuntu 16.04.2 LTS
* L1d cache： 32K
* L1i cache： 32K
* L2 cache： 256K
* L3 cache： 6144K
* Architecture： x86_64
* CPU 作業模式： 32-bit, 64-bit
* Byte Order： Little Endian
* CPU(s)： 4
* Model name： Intel(R) Core(TM) i5-6300HQ CPU @ 2.30GHz
* **memory**
description： System memory
physical id： 0
size： 7872MiB

## 未優化版本
* 執行：`$ make`、`$ ./raytracing`
* 程式執行時間如下：

# Rendering scene
Done!
Execution time of raytracing() : 3.040014 sec

* 加上gprof重行編譯：`$ make PROFILE=1`、`./raytracing`
* 程式執行時間如下：

# Rendering scene
Done!
Execution time of raytracing() : 6.169772 sec

* gprof分析結果：`$ gprof ./raytracing`
* 結果如下：

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 20.24      0.53     0.53 56956357     0.00     0.00  subtract_vector
 18.71      1.02     0.49 69646433     0.00     0.00  dot_product
 11.27      1.32     0.30 31410180     0.00     0.00  multiply_vector
  9.93      1.58     0.26 10598450     0.00     0.00  normalize
  7.64      1.78     0.20 17836094     0.00     0.00  add_vector
  7.64      1.98     0.20 13861875     0.00     0.00  raySphereIntersection
  5.73      2.13     0.15 13861875     0.00     0.00  rayRectangularIntersection
  3.82      2.23     0.10  4620625     0.00     0.00  ray_hit_object
  2.67      2.30     0.07  1048576     0.00     0.00  ray_color
  2.29      2.36     0.06 17821809     0.00     0.00  cross_product
  2.29      2.42     0.06  1241598     0.00     0.00  refraction
  2.10      2.47     0.06  4221152     0.00     0.00  multiply_vectors
  1.53      2.51     0.04  2110576     0.00     0.00  compute_specular_diffuse
  1.53      2.55     0.04        1     0.04     2.62  raytracing
  0.76      2.57     0.02  2110576     0.00     0.00  localColor
  0.38      2.58     0.01  3838091     0.00     0.00  length
  0.38      2.59     0.01  2520791     0.00     0.00  idx_stack_top
  0.38      2.60     0.01  1241598     0.00     0.00  protect_color_overflow
  0.38      2.61     0.01   113297     0.00     0.00  fresnel
  0.38      2.62     0.01    37595     0.00     0.00  idx_stack_pop
  0.00      2.62     0.00  2558386     0.00     0.00  idx_stack_empty
  0.00      2.62     0.00  1241598     0.00     0.00  reflection
  0.00      2.62     0.00  1204003     0.00     0.00  idx_stack_push
  0.00      2.62     0.00  1048576     0.00     0.00  idx_stack_init
  0.00      2.62     0.00  1048576     0.00     0.00  rayConstruction
  0.00      2.62     0.00        3     0.00     0.00  append_rectangular
  0.00      2.62     0.00        3     0.00     0.00  append_sphere
  0.00      2.62     0.00        2     0.00     0.00  append_light
  0.00      2.62     0.00        1     0.00     0.00  calculateBasisVectors
  0.00      2.62     0.00        1     0.00     0.00  delete_light_list
  0.00      2.62     0.00        1     0.00     0.00  delete_rectangular_list
  0.00      2.62     0.00        1     0.00     0.00  delete_sphere_list
  0.00      2.62     0.00        1     0.00     0.00  diff_in_second
  0.00      2.62     0.00        1     0.00     0.00  write_to_ppm

## 優化版本1 - loop unrolling
將`add_vector`、`sub_vector`、`multiply_vectors`、`multiply_vector`、`dot_product`中的for迴圈展開，以空間換取時間。
* eg.原本的`add_vector`為

static inline
void add_vector(const double *a, const double *b, double *out)
{
    for (int i = 0; i < 3; i++)
        out[i] = a[i] + b[i];
}

改為

static inline
void add_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];
}

* 執行：`$ make PROFILE=1`、`$ ./raytracing`
* 程式執行時間如下：

# Rendering scene
Done!
Execution time of raytracing() : 4.785422 sec

* gprof分析：`＄ gprof ./raytracing`
* 結果如下：

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 20.36      0.30     0.30 56956357     0.00     0.00  subtract_vector
 13.46      0.49     0.20 69646433     0.00     0.00  dot_product
 13.11      0.68     0.19 10598450     0.00     0.00  normalize
 11.39      0.85     0.17 13861875     0.00     0.00  rayRectangularIntersection
  8.63      0.97     0.13 17821809     0.00     0.00  cross_product
  6.56      1.07     0.10 13861875     0.00     0.00  raySphereIntersection
  4.83      1.14     0.07 31410180     0.00     0.00  multiply_vector
  3.45      1.19     0.05 17836094     0.00     0.00  add_vector
  3.45      1.24     0.05  4620625     0.00     0.00  ray_hit_object
  2.76      1.28     0.04        1     0.04     1.44  raytracing
  2.42      1.31     0.04  4221152     0.00     0.00  multiply_vectors
  2.07      1.34     0.03  2110576     0.00     0.00  compute_specular_diffuse
  2.07      1.37     0.03  1048576     0.00     0.00  ray_color
  1.38      1.39     0.02  2110576     0.00     0.00  localColor
  1.38      1.41     0.02  1241598     0.00     0.00  protect_color_overflow
  0.69      1.42     0.01  3838091     0.00     0.00  length
  0.69      1.43     0.01  1241598     0.00     0.00  refraction
  0.69      1.44     0.01  1048576     0.00     0.00  rayConstruction
  0.69      1.45     0.01        1     0.01     0.01  delete_sphere_list
  0.00      1.45     0.00  2558386     0.00     0.00  idx_stack_empty
  0.00      1.45     0.00  2520791     0.00     0.00  idx_stack_top
  0.00      1.45     0.00  1241598     0.00     0.00  reflection
  0.00      1.45     0.00  1204003     0.00     0.00  idx_stack_push
  0.00      1.45     0.00  1048576     0.00     0.00  idx_stack_init
  0.00      1.45     0.00   113297     0.00     0.00  fresnel
  0.00      1.45     0.00    37595     0.00     0.00  idx_stack_pop
  0.00      1.45     0.00        3     0.00     0.00  append_rectangular
  0.00      1.45     0.00        3     0.00     0.00  append_sphere
  0.00      1.45     0.00        2     0.00     0.00  append_light
  0.00      1.45     0.00        1     0.00     0.00  calculateBasisVectors
  0.00      1.45     0.00        1     0.00     0.00  delete_light_list
  0.00      1.45     0.00        1     0.00     0.00  delete_rectangular_list
  0.00      1.45     0.00        1     0.00     0.00  diff_in_second
  0.00      1.45     0.00        1     0.00     0.00  write_to_ppm

* 和未優化版本比較結果如下：
* 程式執行時間從原本的6.17秒降到4.78秒。且`math-toolkit.h`中的函式執行時間較原本的版本皆有下降。
## 優化版本2 - 使用SSE、SSE2 instruction set