# 2017q1 Homework2 (raytracing)
contributed by <`davis8211`>
### Reviewed by `Daichou`
* 在math-toolkit.h中，那大部分的程式碼註解其實可以不要保留，透過git的版本控制特性，這些如須還原僅須rollback即可，不需要留下。
* 同樣，math-toolkit_origin.h可以不必保留，因為你的程式中並沒有引用到，一個程式中保留兩個相同名稱的MARCO不是好事。還有math-toolkit_loop-unrooling.h檔案也可不必保留，這會讓日後閱讀你程式的人疑惑。
* 在建立Thread_parameter時可以先建立該struct的建構函式(OOP觀念)，對於日後建立該struct可讀性會比較好。
* 在thread_range中height1與height2這兩個變數命名需要調整，可調為base與height等。
* 可嘗試建立thread pool避免資源浪費。

## 開發環境

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
Thread(s) per core:    2
Core(s) per socket:    2
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 58
Model name:            Intel(R) Core(TM) i5-3210M CPU @ 2.50GHz
Stepping:              9
CPU MHz:               1282.043
CPU max MHz:           3100.0000
CPU min MHz:           1200.0000
BogoMIPS:              4988.74
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              3072K
NUMA node0 CPU(s):     0-3

## gprof
* 有點奇妙，在實體電腦沒辦法執行，如下圖
* 最後屈服了，只好在虛擬機上執行，未來再繼續嘗試
* 功能
* 印出程式執行中各個函式消耗的時間，可以從眾多函式中找出耗時最久的。
* 這個功能對於維護程式碼或是分析開源軟體來說是很棒的，可以對程式執行框架有初步的認識。
* 實現原理
* 透過在編譯和鏈結程式的時候，gcc 在程式的每個函數中都加入了一個名為 mount 的函式，他會在記憶體中紀錄函式呼叫圖，包含呼叫時間、呼叫次數
* 基本用法
1. 使用 -pg 編譯和鏈結你的程式
2. 執行你的程式產生 gmon，可供 gprof 分析
3. 使用 gprof 程式分析你的程式產生的檔案

## Loop Unrolling
* 優點
* 減少 branch，所以也減少 branch prediction 失敗機會
* 缺點
* 增加程式碼長度
* 減少彈性
* 嘗試
* 未展開 4.494825 sec (3.044483 sec)
* 展開一部分
* add_vector
* subtract_vector
* multiply_vectors
* multiply_vector
* 3.533118 sec (2.489814 sec)
* 增加新的部分
* dot_product
* 想嘗試將 dp 分成dp, dp1, dp2 最後再 sum 起來，但成效不佳。
* 3.229063 sec (2.212004 sec)

## Force Inline
* inline 是向編譯器提出建議，把 inline 的函數再函數位置直接展開，減輕系統 overhead，編譯器會對比兩者執行時間後選擇是否執行 inline
* 優點
* 減少 function call
* 由 gprof 紀錄的 calls 次數多的開始 Inline
* 原始 3.012592 sec
* dot_product 3.044357 sec
* subtract_vector 3.022543 sec
* 似乎沒有明顯改進
* loop-unrolling + Force inline
* 2.241127 sec -> 2.183361 sec

## Macro
* 對 dot_product 和 subtract_vector 做 Macro 進步到 1.748567 sec
* 加上 add_vector, multiply_vectors, multiply_vector, cross_product 進步到 1.456757 sec 離 Ofast 0.67 還有一些距離
* 在對 multiply_vector 時出了錯誤

#define multiply_vector(a, b, c) (c[0]=a[0]*b) ...

* 以上應該改成，須對 b 加上括號

#define multiply_vector(a, b, c) (c[0]=a[0]*(b)) ...

## Pthread
* 平行化會有 race condition 的問題，所以首先要讓各個 thread 有一份自己的參數(parameter)，所以先建立 struct

typedef struct{
    uint8_t *pixels;
    double *background_color;
    rectangular_node rectangulars;
    sphere_node spheres;
    light_node lights;
    const viewpoint *view;
    int width;
    int height;
    double *u;
    double *v;
    double *w;
    double *d;
    int factor;
}Thread_parameter;

* 除此之外，每個 thread 必須設好自己的執行範圍，這邊把圖片分割成許多個 row，讓不同 thread 負責不同的 row。

typedef struct {
    int height1;
    int height2;
    Thread_parameter *ptr;
} Thread_range;

* 接下來，開始設定每個 thread 的參數，並設定 thread 要執行的函數，學著使用 pthred。

void raytracing(uint8_t *pixels, color background_color,
                rectangular_node rectangulars, sphere_node spheres,
                light_node lights, const viewpoint *view,
                int width, int height)
{
    point3 u, v, w, d;
    THREAD_NUMBER = get_nprocs();
    pthread_t id[THREAD_NUMBER];
    Thread_parameter para;
    Thread_range range[THREAD_NUMBER];

    /* calculate u, v, w */
    calculateBasisVectors(u, v, w, view);

    int factor = sqrt(SAMPLES);
   
    para.factor = factor;
    para.u = u;
    para.v = v;
    para.w = w;
    para.pixels = pixels;
    para.background_color = background_color;
    para.rectangulars = rectangulars;
    para.spheres = spheres;
    para.lights = lights;
    para.view = view;
    para.width = width;
    para.height = height;
 
    for(int i=0; i<THREAD_NUMBER; i++) {
        range[i].height1 = i;
        range[i].height2 = height;
        range[i].ptr = &para;
    }

    for(int i=0; i<THREAD_NUMBER; i++) {
        if(pthread_create(id+i, NULL, parallel, &range[i])) {
            printf("thread fail\n");
            exit(1);
        }
    }

    for(int i=0; i<THREAD_NUMBER; i++)
        pthread_join(id[i], NULL);
}

* 在 pthread_create 呼叫了 parallel 的函數，說明讓這些 thread 去執行 parallel 這個函數，也就是原本 raytracing 的函數。
* 在這個函數中，為了避免 race condition 的問題，必須將原先的參數，改成 thread 各自的參數。

static void *parallel(void* range1)
{
    Thread_range *range = (Thread_range *)range1;

    point3 d;
    color object_color = { 0.0, 0.0, 0.0 };
    idx_stack stk;


    
    for (int j = range->height1; j < range->height2; j+=THREAD_NUMBER) {
        for (int i = 0; i < range->ptr->width; i++) {
            double r = 0, g = 0, b = 0;
            /* MSAA */
            for (int s = 0; s < SAMPLES; s++) {
                idx_stack_init(&stk);
                rayConstruction(d, range->ptr->u, range->ptr->v, range->ptr->w,
                                i * range->ptr->factor + s / range->ptr->factor,
                                j * range->ptr->factor + s % range->ptr->factor,
                                range->ptr->view,
                                range->ptr->width * range->ptr->factor, range->ptr->height * range->ptr->factor);
                if (ray_color(range->ptr->view->vrp, 0.0, d, &stk, range->ptr->rectangulars, range->ptr->spheres,
                              range->ptr->lights, object_color,
                              MAX_REFLECTION_BOUNCES)) {
                    r += object_color[0];
                    g += object_color[1];
                    b += object_color[2];
                } else {
                    r += range->ptr->background_color[0];
                    g += range->ptr->background_color[1];
                    b += range->ptr->background_color[2];
                }
                range->ptr->pixels[((i + (j * range->ptr->width)) * 3) + 0] = r * 255 / SAMPLES;
                range->ptr->pixels[((i + (j * range->ptr->width)) * 3) + 1] = g * 255 / SAMPLES;
                range->ptr->pixels[((i + (j * range->ptr->width)) * 3) + 2] = b * 255 / SAMPLES;
            }
        }
    }
}

* 做了以上修改後，就可以來編譯了。編譯時別忘記加上 -pthread。
* 平行化後大幅度加快了執行時間，進步到 0.620587sec，成功超越 Ofast。
* 未來會再繼續改進此程式，之後補上 gunplot 圖
# Reference
* http://os.51cto.com/art/200703/41426.htm
* https://www.ptt.cc/bbs/C_and_CPP/M.1246071002.A.A54.html