# 2016q3 Homework3 (mergesort-concurrent)
contibuted by <`CheHsuan`>

## 目標

* 作為 concurrency 的展示案例
* 學習 POSIX Thread Programming，特別是 synchronization object
* 為日後效能分析和 scalability 研究建構基礎建設
* 學習程式品質分析和相關的開發工具

## 程式碼分析: mergesort-concurrent (對單向 Linked List)

1. 在main.c裡面定義了如何divide和conqure，如果我們要做效能測試的話，先把一些不重要的輸出關閉
如

printf("input unsorted data line-by-line\n");

和

list_print(_list);

2. 在main.c裡面放了太多函式，將merge sort相關的函式移出，放到mergesort.c裡面，如果有共用到的全域變數，則把==static==關鍵字刪除，讓可視範圍不局限於main.c，並在mergesort.c裡面使用==extern==取得這些變數

3. 為了讓效能測試更為準確，因此我們將原本tpool_free()裡面的兩個功能(等待所有thread結束和釋放資源)拆開來，也就是說tpool_free()只用來釋放資源，而等待thread結束的功能由tpool_close()來實現

## 加入效能測試
我們應該要先分析在這次的實驗當中，我們該用那種量測方式，以及時間單位來呈現我們的效能
1. 我們的input是由scanf所取得，這部份並不是concurrent所著重的部份(也沒有concurrent),因此在量測時，應該要把這部份所花的時間排除在外
2. wall-clock time vs CPU time
本次分析的merge sort concurrent應該著重在於演算法以及thread pool所帶來的成果，與IO無關，所以在測效能時，照裡應該使用CPU time來呈現數據，但是，如果使用CPU time的話，會將每個thread的時間都加在一起，這樣就無法凸顯多執行序的優點，因此這邊還是使用wall-clock time，但量測的起始點和結束點需仔細評估過，不要牽扯到IO時間
使用CLOCK_PROCESS_CPUTIME_ID，可以看到使用越多thread，CPU time越久
3. clock_gettime()參數
根據第2點的分析，在這次的測試當中我們應該要使用單調遞增的wall-clock time，也就是CLOCK_MONOTONIC_RAW

在push第一個task前使用clock_gettime()和在tpool_free後面使用clock_gettime(),相減後即可得到排序所花的時間

:::info
記得要在呼叫tpool_free()後才能呼叫clock_getttime()，原因是pthread_join放置在tpool_free裡面，如果在free之前就呼叫clock_getttime()，測出來的時間是不準確的
:::
>> 這樣又會有資源釋放的成本，thread pool 只需要確保 worker thread 都執行完畢，就能認定是完成了 [name=jserv]
>> 那我改寫一下threadpool.c，多一個close的函式，保證task queue的工作都完成，而tpool_free只用來釋放資源[name=CheHsuan]

## 實驗
實驗環境是產生100000個亂數並儲存在numbers.txt裡面，之後餵給測試程式，再針對2、4、8和16個thread去測試執行時間，結果如下

使用CLOCK_MONOTONIC_RAW

>> 該如何解釋嚴重跳動的數值分佈呢？ [name=jserv]
>> 因為我們使用的量測方法是clock_gettime()和並且是CLOCK_MONOTONIC_RAW來計算，是單調遞增的wall-clock time，因此會受到執行其他程式而影響到測出來的結果，導致有跳動的分佈[name=CheHsuan]