# 2016q3 Homework3 (mergesort-concurrent)
contributed by <`TempoJiJi`>

## 預期目標
* 作爲concurrency的展示案例
* 學習 POSIX Thread Programming
* 為日後效能分析和 scalability 研究建構基礎建設
* 學習程式品質分析和相關的開發工具

## 開發環境

* Ubuntu 16.04 LTS
* L1d cache: 32K
* L1i cache: 32K
* L2 cache: 256K
* L3 cache: 3072K
* Architecture: x86_64
* CPU op-mode(s): 32-bit, 64-bit
* Byte Order: Little Endian
* CPU(s): 4
* Model name: Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz

---

先來測試程式效能跟檢查結果：

$ (for i in {1..8}; do echo $RANDOM; done) | ./sort 4 8

input unsorted data line-by-line
[11562] [17074] [20028] [20439] [20600] [21083] [29465] [32236] 

---

## 設計自動測試實驗

大致上閱讀程式碼後，先來設計自動測試的實驗，方便日後修改程式碼時能夠做對比：
先準備產生亂數的程式`intput_generator.c`
接着修改main.c，將`FIX ME`的部分都改成檔案輸入出
最後在Makefile中加入Bash腳本：

bench:
        for i in `seq 100000 10000 500000`; do \
            ./input_generator $$i; \
            for j in 1 2 4 8 16 32 64; do \
            	./sort $$j $$i; \
            done \
    	done

plot: bench
        gnuplot runtime.gp

執行

$ make plot

執行結果：
這個結果有點出乎意料，執行緒越多，時間抖動的越厲害，而且sorting的時間比一個執行緒還來的慢

---

## 閱讀程式碼及Refactoring

首先爲了確保每次更改後，sorting後的結果是正確的，我多加了一個CHECK的機制，每次只需利用`$ make check`就能確認結果有沒有正確：

check: input_generator
        for i in `seq 1 1 100`; do\
            ./input_generator $$i; \
            ./sort 4 $$i; \
            sort -n input > sorted; \
            diff output sorted; \
        done

---

參考老師的解說：[「你所不知道的 C 語言」：物件導向篇 ](https://www.youtube.com/watch?v=IG6q8WX0sK4)，首先在`list_add()`中，它並沒有回傳任何的address（list_t），加上傳入的參數只是副本，因此這裏需要改成回傳一個成功list_add的一個address，直接看code吧（這裏也可以使用pointer to pointer，避免傳入的只是副本），這部分不太清楚需不需要避免重復的值，我就直接連重復的值也加進去了：

list_t *list_add(list_t *e, val_t val)
{
    e->next = malloc(sizeof(list_t));
    e = e->next;
    e->data = val;
    e->next = NULL;

    return e;
}

還有在`tpool_init`時，也需要避免這個問題

接着我把node_t這個結構給刪掉，改成只有一個結構，因爲這樣的改動，所以`list_new()`已經不需要了，所有跟size有關的部分都需要更動：

typedef struct _LIST_T {
    val_t data;
    struct _LIST_T *next;
} list_t;

再來size這個變數已經沒有了，加上`list_nth`這個function的名字有點怪怪的，所以我把它改名成`getMiddle`也改變了裏面的行爲，就只是單純找出list的中間位置，不需要用到size：

list_t *getMiddle(list_t *list)
{
    if(!list)
        return list;
    list_t *slow = list;
    list_t *fast = list;
    while(fast->next && fast->next->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

> Wow，我沒有想過可以這樣找中間的 element XD [name=Kun-Yi Li]

再來是修改`merge_sort`跟`merge_list`的部分，我把它們都寫的比較簡單了一點，這個應該會比之前的容易理解很多：

list_t *merge_list(list_t *a, list_t *b)
{
    list_t *head = malloc(sizeof(list_t));
    list_t *cur = head;
    while (a && b) {
        if(a->data <= b->data){
            cur->next = a;
            a = a->next;
        }
        else if(a->data > b->data){
            cur->next = b;
            b = b->next;
        }
        cur = cur->next;
    }
    cur->next = (!a) ? b : a;
    return head->next;
}

list_t *merge_sort(list_t *list)
{
    if (!list || !list->next)
        return list;
    list_t *mid = getMiddle(list);
    list_t *half = mid->next;
    mid->next = NULL;
    return merge_list(merge_sort(list), merge_sort(half));
}   

---

排序的部分大致上都處理完畢後，來看一看關於lock contention的問題，觀察`cut_func`，其實這個這個部分並不需要lock，因爲各個thread都在處理各自的list，並不會影響到對方，所以我把這個部分的mutex_lock給拿掉了，這樣就減少了很多lock contention的問題：

void cut_func(void *data)
{
    list_t *list = (list_t *) data;
    if (list && list->next && cut_count <= max_cut) {
        cut_count++;

        /* cut list */
        list_t *mid = getMiddle(list);
        list_t *half = mid->next;
        mid->next = NULL;
        ....
        ....

接着`task_run`的部分我將它簡化了一點，不是利用`NULL`來終止，而是設立一個變數`shutdown`：

static void *task_run(void *data)
{
    (void) data;
    while (!shutdown) {
        task_t *task = tqueue_pop(pool->queue);
        if (task) 
            task->func(task->arg);
    }
    pthread_exit(NULL);
}    

最後在`task_run`這個部分其實有點疑問，如果沒有block着會不會一直佔着CPU的資源，所以我就想說沒有task時就block着，空出CPU的資源，有task時才進行，不知道這樣的效率會不會比較好，原本想說要做出來比較看看，可是一直遇到bug...(背景知識還不夠熟悉)

最後查看執行結果：
這裏雖然簡化了程式碼，但結果並沒有好很多，還有部分需要改進，還需要更加了解關於Thread pool跟[synchronization object](https://docs.oracle.com/cd/E19683-01/806-6867/6jfpgdcnd/index.html)的背景知識才行...
>> 提示: 試著透過 [phonebook-concurrent](https://hackmd.io/s/rJsgh0na) 提到的 SuperMalloc，比照執行結果 [name=jserv]

---

## SuperMalloc
經過老師提點後，就來嘗試看看，在[phonebook-concurrent](https://hackmd.io/s/rJsgh0na)中有提到的SuperMalloc，從[SuperMalloc](https://github.com/sysprog21/SuperMalloc)上下載程式碼安裝後，就可以開始使用，只要在`SuperMalloc/release`這個路徑底下輸入指令，就能使用：

$ LD_PRELOAD=libsupermalloc_pthread.so 程式路徑

利用SuperMalloc的執行結果：

這裏可以從橫軸中很明顯的看到，最大值只到1.6sec，跟之前的比起來效能快了很多

Original vs SuperMalloc:

由於還在啃論文中，所以還需要一點時間來理解關於SuperMalloc的原理跟行爲

參考資料：
[SuperMalloc: A Super Fast Multithreaded Malloc for 64-bit Machines](http://supertech.csail.mit.edu/papers/Kuszmaul15.pdf)

###### tags: `TempoJiJi` `mergesort-concurrent` `sysprog21`