# 2017q1 Homework1 (raytracing)
contributed by < `SeanCCC` >
### Reviewed by `divazone`
* 希望之後有時間可以在實體機上在實做一遍，期待看到比較好的結果
* 如果將全部的function都攤開的話，是否有可能會更快?
* 可以試著往平行化的方向發展，例如pthread

## 開發環境

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                1
On-line CPU(s) list:   0
Thread(s) per core:    1
Core(s) per socket:    1
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 62
Model name:            Intel(R) Xeon(R) CPU E5-2630L v2 @ 2.40GHz
Stepping:              4
CPU MHz:               2399.998
BogoMIPS:              4799.99
Virtualization:        VT-x
Hypervisor vendor:     KVM
Virtualization type:   full
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              15360K
NUMA node0 CPU(s):     0

## 準備期-gprof
* gprof的原理是會依照一定的頻率對PC(Program Counter)進行取樣，然後透過採樣點落在各個函式的比例來判斷運行的時間。這樣一來可以精準分析效率，但也不是沒有缺點。Grof的主要缺點如下：
* 無法對遞迴進行分析。
* 會拖累拉長運作時間。
* gprof假設函式運行時間每次都一樣，但實際上並不會。
* 會搶程序的記憶體。
* 無法用於non-preemptive的程式，畢竟無法interrupt。
* 相較起來計時器單純許多，他只是計算開始和結束的時間差異而已，如此一來並不會造成程序資源的占用。
* 但在單核心time-sharing或是計算資源吃緊的情況下會導致計時器失準，原因是其他程序會導致程序無法在最理想的狀態下運作，它可能會跑到到一半被插隊，但插隊時計算的時間卻還是繼續計算。
* 這次由於太晚開始準備作業，而實體機準備時又遇到很多問題，所以是租用VPS，而VPS又是租最便宜的單核心，可以期待gprof會的結果是失準的滿嚴重的。
* 加-pg進行gprof的結果

Execution time of raytracing() : 8.325076 sec

* 不加的結果

Execution time of raytracing() : 5.163579 sec

* grof 分析後的部分結果
* 可知道dot_product佔據1/4的時間，應該試圖針對該部分做加速。

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 25.67      0.78     0.78 69646433     0.00     0.00  dot_product
 15.47      1.25     0.47 56956357     0.00     0.00  subtract_vector
 11.68      1.61     0.36 13861875     0.00     0.00  rayRectangularIntersection
  7.57      1.84     0.23 10598450     0.00     0.00  normalize
  6.91      2.05     0.21 31410180     0.00     0.00  multiply_vector
  6.75      2.25     0.21 17836094     0.00     0.00  add_vector
  6.09      2.44     0.19 13861875     0.00     0.00  raySphereIntersection
  5.10      2.59     0.16  4620625     0.00     0.00  ray_hit_object

## Loop Unrolling
* 優先對象：dot_product
* 由程式碼中可以發現這個for-loop可以攤開，這樣可以避免七千萬次的i的加法與比較。
* 修改前

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;
}

* 修改後
* 把for-loop攤開

    dp = v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2];

* 速度差異達到1.2秒

    Execution time of raytracing() : 7.715813 sec

* 時間分布差異，可以看到dot_product的比例顯著下降

    18.16      0.47     0.47 56956357     0.00     0.00  subtract_vector
    13.91      0.83     0.36 31410180     0.00     0.00  multiply_vector
    11.20      1.12     0.29 69646433     0.00     0.00  dot_product
    10.43      1.39     0.27 10598450     0.00     0.00  normalize
     8.89      1.62     0.23  4620625     0.00     0.00  ray_hit_object