# 2017q1 Homework4 (mergesort-concurrent)
contributed by `<yangyang95>`
###### tags: `sysprog2017` `HW4` `yangyang95`
開發環境看 [這裡](https://hackmd.io/s/HJ2c_XYKx)
作業要求看 [這裡](https://hackmd.io/s/B1xV_p_jl#作業要求)
github page 看 [這裡](https://github.com/yangyang95/mergesort-concurrent)
## Doxygen 文件產生
這個作業超級複雜的阿 = =
不過現實開發中的程式一定會比這份作業更加複雜，所以必須趕快學習如何對複雜的專案進行開發
先學習 [0xff07 大大](https://hackmd.io/s/H154LN6og#mergesort-concurrent) 用 doxygen 產生文件幫助自己理解
參考了這篇文章 [Doxygen 程式文件產生器 與 簡易筆記](https://www.jerrynest.com/doxygen/) 安裝 doxygen 來使用
原本還想參考這篇 [Auto-deploying Doxygen documentation to gh-pages with Travis CI](https://gist.github.com/vidavidorra/548ffbcdae99d752da02)
利用 Travis-CI 自動部署 doxygen 文件的 github page，不過又失敗惹 orz
個人感覺 Travis 對 C 語言的專案不太友善啊...
只好用最簡單的方式手動製作 [Doxygen 文件](https://yangyang95.github.io/mergesort-concurrent)
## 程式碼修改
### 字串處理
來看看 link list 節點的資料結構
```C
typedef intptr_t val_t;
typedef struct node {
val_t data; /**< Data of the node */
struct node *next; /**< Pointer to the next node */
} node_t;
```
`intptr_t` 這個資料型別可以在不同位元上的機器調整大小
舉例來說，當機器是64bit
intptr_t 就是 long int ( 64位元的 long int 是64 bit, 但32位元的 long int 是32 bit)
否則就是 int ( 64位元的 int 是32 bit, 32位元的 int 也是32 bit)
直接把 `val_t` ，也就是 `intptr_t` ，拿來放字串的 ascii code
在 `main.c` 的讀取函式做了修改：
原本想使用
```C==
/* bilud_list_from_file func */
char buffer[16];
while (fgets(buffer, 16, fp) != NULL) {
list_add(_list, (val_t)buffer);
}
```
可是發現 list 出來都是亂碼，參考 [0xff07](https://github.com/0xff07/mergesort-concurrent/commit/c2de063fd09090e17caf5d68be1f1923dd9b0f1c) 做修改
```C==
/* bilud_list_from_file func */
char buffer[16];
while (fgets(buffer, 16, fp) != NULL) {
char *name = (char*)malloc(16);
strcpy(name, buffer);
list_add(_list, (val_t)name);
}
```
如此一來就可以正確讀取字串，我認為是 list_add 函式的傳入資料需為 pointer 導致亂碼
對 pointer 的掌握度實在還需要再加強
輸出 `list_print` 函式的部分也稍加修改
```C==
void list_print(const llist_t * const list)
{
const node_t *cur = list->head;
while (cur) {
xprint((char*)cur->data);
cur = cur->next;
}
}
```
如此一來就完成字串的支援囉，數字的排序依然可以使用
參考資料：
* [使用變數型別的良好習慣](http://b8807053.pixnet.net/blog/post/164224857-%E4%BD%BF%E7%94%A8%E8%AE%8A%E6%95%B8%E5%9E%8B%E5%88%A5%E7%9A%84%E8%89%AF%E5%A5%BD%E7%BF%92%E6%85%A3)
## 效能分析
既然能夠支援電話簿的輸入，那就來執行程式看看效能如何
```
$ ./sort 4 test_data/words.txt (sorted)
#Total_tasks_consumed: 12
#Elapsed_time: 99.519 ms
#Throughput: 120 (per sec)
```
```
$ ./sort 10 test_data/words.txt (sorted)
#Total_tasks_consumed: 30
#Elapsed_time: 121.599 ms
#Throughput: 246 (per sec)
```
使用 `$ make genData`
也就是 `uniq test_data/words.txt | sort -R > test_data/input.txt` 來產生所有名字只出現一次 (uniq) 且亂序排列 (sort -R) 的電話簿
:::warning
注意： 根據 man page，sort 是基於 shuf 工具來亂序排列，而老師上課時有提到過這個工具並非完全隨機。有機會可以驗證看看。
:::
```
$ ./sort 4 test_data/input.txt (random order)
#Total_tasks_consumed: 12
#Elapsed_time: 206.756 ms
#Throughput: 58 (per sec)
```
```
$ ./sort 10 test_data/input.txt (random order)
#Total_tasks_consumed: 30
#Elapsed_time: 247.542 ms
#Throughput: 121 (per sec)
```
又再一次將每一個實驗都再跑一次，發現 `Total_tasks_consumed` 不變，但 `Elapsed_time` 跟 `Throughput` 都有不小的變動。
```
$ ./sort 4 test_data/words.txt (sorted)
#Total_tasks_consumed: 12
#Elapsed_time: 69.094 ms
#Throughput: 173 (per sec)
```
```
$ ./sort 10 test_data/words.txt (sorted)
#Total_tasks_consumed: 30
#Elapsed_time: 82.656 ms
#Throughput: 362 (per sec)
```
```
$ ./sort 4 test_data/input.txt (random order)
#Total_tasks_consumed: 12
#Elapsed_time: 196.514 ms
#Throughput: 61 (per sec)
```
```
$ ./sort 10 test_data/input.txt (random order)
#Total_tasks_consumed: 30
#Elapsed_time: 311.850 ms
#Throughput: 96 (per sec)
```
重新執行一遍 `$ make genData` 來產生不同亂序的電話簿來比較
```
$ ./sort 4 test_data/input1.txt (random order)
#Total_tasks_consumed: 12
#Elapsed_time: 192.473 ms
#Throughput: 62 (per sec)
```
```
$ ./sort 10 test_data/input1.txt (random order)
#Total_tasks_consumed: 30
#Elapsed_time: 211.888 ms
#Throughput: 141 (per sec)
```
將上方實驗流程用 Flow Chart 做圖
```flow
op=>operation: 4,10 threads 排序過字典 (第一次)
op2=>operation: 4,10 threads 亂序字典 (第一次)
op3=>operation: 4,10 threads 排序過字典 (第二次)
op4=>operation: 4,10 threads 亂序字典 (第二次)
op5=>operation: 重新產生亂序字典
op6=>operation: 4,10 threads 亂序字典
op->op2->op3->op4->op5->op6
```
(這圖好大啊 XD)
接下來就實驗結果做圖來比較
**執行時間** ：
> 註：最後兩條 4,10 threads random (third) 與前面的 random 使用不同的亂序字典
由這張圖可以看出執行時間可能有以下趨勢：
$$ 4 執行緒(排序) < 10 執行緒(排序) < 4 執行緒(亂序) < 10 執行緒(亂序) $$
使用不同的亂序字典則有以下關係：
$$ 4 執行緒(字典1) \approx 4 執行緒(字典2)，10 執行緒(字典1) > 10 執行緒(字典2) $$
:::warning
不過此實驗只執行兩次，雖然可以幫助我們發現可能的趨勢，卻需要設計強度更高的實驗來驗證
:::
**Throughput** ：
由圖可看出通量：
$$ 4執行緒(亂序) < 4執行緒(排序) \approx 10 執行緒(亂序) << 10 執行緒(排序) $$
使用不同的亂序字典則有以下關係：
:::warning
如上所述，實驗代表性還不夠，還需要加以驗證
:::
## 正確性驗證
實驗排序跑出來的結果我存在 txt 裡，然後使用 `diff` 指令來跟原始的字典做比較，結果都正確。
不過執行之前留下來的驗證程式 `$ make check` 的時候卻出現錯誤，不知是何處的問題
稍微看了一下，`$ make check` 是用數字來驗證，不過結果看起來沒什麼問題，待我看看程式碼是如何執行驗證。
來分析 `$ make check` 的程式碼
```c
# Default variables for auto testing
THREADS ?= 4
TEST_DATA_FILE ?= /tmp/test_number.txt
NUM_OF_DATA ?= 1024
SORTED_DATA_FILE ?= $(TEST_DATA_FILE).sorted
SORTED_RESULT ?= /tmp/sort_result.txt
ITERATIONS ?= 100
check: sort
# Generate testing data
@bash scripts/gen-random-numbers.sh $(NUM_OF_DATA) $(TEST_DATA_FILE)
# Sort the testing data first to generate ground truth
@sort -g $(TEST_DATA_FILE) > $(SORTED_DATA_FILE)
# Use sort implementation to sort the testing data, and ignore first
# 3 lines of output. Because we only want the sorting result.
@./sort $(THREADS) $(TEST_DATA_FILE) | tail -n +4 > $(SORTED_RESULT)
@bash scripts/compare.sh $(SORTED_DATA_FILE) $(SORTED_RESULT)
```
使用 `gen-random-numbers.sh` 在 `/tmp` 資料夾建立隨機數字的文件
再用 `sort -g` 進行排序，作為 baseline
這邊解釋一下 `tail -n +4` 的作用，就是將結果從第 4 行開始輸出，避開前三行多出來的結果
程式碼讀到這裡，打開 `sort_result.txt` 一看，不得了...
```
sorted_result.txt: test_number.txt.sorted:
1000 56
10142 120
10154 170
10160 184
10195 266
```
數字都被當成字串處理 (這不是廢話嗎...)
::: warning
目前還沒有好的想法解決數字排列錯誤問題，不過字串排列結果確定是正確的
:::
## 研究 [concurrent linked-list](https://github.com/jserv/concurrent-ll)
這份專案內有兩個 concurrent linked list 的實作，分別是 lock-free 版與 lock-based 版
兩個實作都包含以下功能：
* 在 list 內增加項目
* 在 list 內刪除項目
* 在 list 內尋找項目
lock-free 的實作使用 Harris 演算法
lock-based 的實作使用 hand-over-hand locking 的技巧
lock 可以想象成十字路口的紅綠燈
* lock-based 指的是當兩個 thread 要對同一個記憶體空間作用時，一個先執行，另外一個需等待前一個執行完成
* lock-free 可想像成高架橋，兩個 thread 都不需等待紅綠燈
Sign in with Wallet
Connect another wallet