# 2016q3 Homework3 (mergesort-concurrent)
contributed by <`mingnus`>
###### tags: `ncku` `sysprog` `mergesort`
## Code Review
- [ ] threadpool.c
* queue的操作應該是push to tail, pop from head, 但是threadpool.c寫反了
>> 很敏銳的觀察，很好！請一併參照 GLib 的 [Asynchronous Queues](https://developer.gnome.org/glib/stable/glib-Asynchronous-Queues.html)，裡頭的命名和 programming model 很值得學習 [name=jserv]
>> 簡單比較[list實作](https://hackmd.io/s/rkkg8vJJe), 感覺kernel這種允許自訂資料結構的做法比較有彈性 [name=mingnus]
* tqueue_push()和tqueue_pop()實作看起來有點複雜, 還要判斷head及tail是不是NULL。可以試看看改用Linux kernel的list實作來簡化code。用circular queue也可省掉tqueue_t的tail pointer。
>> non-circular list也不利於加入節點到list結尾, 例如merge_list()就必須維護一個指向`_list`結尾的指標`current`。不過話說回來merge_list()或許不用另外宣告`_list`, 只要把list b併到list a就好 [name=mingnus]
>> kernel list_sort.c的做法滿特別, 它是把原本的list打散成數個null-terminated sorted sublist, 再把它們合併 [name=mingnus]
* struct _task的成員命名不好, 連結前後元素的pointer應為prev & next。寫成prev ＆ last容易讓人誤解
* 資料結構封裝不佳: 目前在threadpool.c之外仍可存取tpool_t::queue, 但threadpool的工作很單純，應該沒必要讓客戶端指定worker thread的function。參考Linux kernel workqueue實作:
* [《Linux Device Drivers》 3/e, ch7.6](https://static.lwn.net/images/pdf/LDD3/ch07.pdf)
* [Concurrency Managed Workqueue](https://www.kernel.org/doc/Documentation/workqueue.txt), Linux kernel documentation
* [Concurrency-managed workqueues](http://lwn.net/Articles/355700/), LWN
- [ ] main.c
* main(): max_cut只計算一次, 應該沒必要為了省略branch而寫成這樣
```C
max_cut = thread_count * (thread_count <= data_count) +
data_count * (thread_count > data_count) - 1;
```
改用一般寫法也比較好理解
```C
max_cut = MIN(thread_count - 1, data_count - 1);
```
* cut_func()是用cut_count決定是否要切割傳入的sublist, 在多執行緒環境下可能導致sublists長度不均
* merge()以FIFO方式合併sublists, 先排完的sublist先合併 (排序完成的sublist儲存於全域變數tmp_list, 等待另一個sublist排序完成後合併), 這樣在多執行緒時無法預測哪些sublist會互相合併, 長度不同的sublist也可能互相合併。為何不在merge()的參數指定要合併的sublists?
>> 還沒想到確實做法, sibling list的資訊可能要儲存在list head [name=mingnus]
>> 你需要重新回顧資料結構和演算法的設計，可參考 [Skip list](https://en.wikipedia.org/wiki/Skip_list) [name=jserv]
* cut_func()在分割list時重覆呼叫list_nth(), 實際上可用list->head->next取代
```C
_list->head = list_nth(list, mid);
_list->size = list->size - mid;
list_nth(list, mid - 1)->next = NULL;
```
* mutex設計不良。程式包含分割及合併兩種task, 當task開始執行時(`cut_func()`或`merge()`)為了檢查全域變數, 必須持有全域mutex `data_context::mutex`, 這樣容易造成lock contention。但這兩種task可以不必共用mutex:
* 分割task: 以sublist長度決定是否要分割, 不必檢查全域變數`cut_thread_count`
* 合併task: 以現行的FIFO合併方式, 可能免不了要用一塊shared memory來儲存已排序完成的sublists。存取這塊shared memory還是要握mutex。
>> 非常好！透過 `mutrace`，你可以發現，事實上有些 lock 是根本不需要存在，就像之前 thread pool 的設計中，善用 ring buffer 就可以省去部分 lock 的成本 [name=jserv]
* threadpool worker thread function `task_run()` 以polling方式詢問taskqueue, 極易造成lock contention。傳統做法是採用conditional variable避免polling。
* task function命名不佳, 不易看出程式脈絡
* cut_func()從名稱上來看是負責分割list, 但它卻會呼叫merge_sort()及merge()
* merge_sort()的地位可提升為task function。merge_sort()不該由cut_func()呼叫, 改由cut_func()直接將不需再分割的sublist傳給merge_sort()
* 按照原作邏輯, 我認為寫成下面這樣, 將call graph扁平化比較好理解。雖merge_sort()多了一道merge() task的轉發手續, 不過cut_func()的call graph也得以簡化
```C
void cut_func(void *data)
{
llist_t *list = (llist_t *) data;
int cut_count = data_context.cut_thread_count;
if (list->size > 1 && cut_count < max_cut - 1) {
++data_context.cut_thread_count;
...
// create new cut_func() tasks for the left & right sublist
} else if (cut_count == max_cut - 1) {
// create new merge_sort() tasks for the left & right sublist
}
}
void merge_sort(void *data)
{
llist_t *list = (llist_t *) data;
// do the plain mergesort on list
// create new merge() task for the sorted list
}
void merge(void *data)
{
// like the current merge() does...
}
```
* gprof分析
* list_new()用法不當: merge_sort()和merge_list()都會呼叫list_new(), 造成大量malloc()
* TODO
* lock-free threadpool
## Refactoring
* list實作以kernel list.h取代
* Merge sort參考kernel list_sort.c
* merge():
* merge_and_restore_back_links():
* 重點: 合併一個節點時, 只需更新其與前一個節點的連結(兩個指標)，不需更新與下一個節點的連結(因為下次合併會再更新)
## Lock-free algorithm
## References
* Some articles about merge sort
* [Linux kernel list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
* https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/analysis-of-merge-sort
* http://www.geeksforgeeks.org/merge-sort-for-linked-list/
* Some articles about parallel merge sort
* http://zobayer.blogspot.com/2010/09/threaded-merge-sort.html
* 很陽春的實作, 未使用threadpool: 每個sublist合併動作都是一個task
* 對於長度N的list, 在分割步驟可能會產生N個threads (worst case); 如果系統不允許產生這麼多個thread, 就會產生deadlock
* http://www.drdobbs.com/parallel/parallel-in-place-merge-sort/240169094
* 使用Intel TBB, 概念和zobayer的實作很像
* https://blogs.msdn.microsoft.com/pfxteam/2011/06/06/parallel-merge-sort-using-barrier/
*
* mergesort.cpp in [threadpool lib](http://threadpool.sourceforge.net)
* 不會合併不同長度的list: 所有長度2^n的sublists都合併完成後, 才會開始合併長度2^(n+1)的sublists
* 參考共筆
* [TempoJiJi](https://hackmd.io/s/B1-Kytv0)
* 簡化list實作, 不記錄list size
* 取得list中間元素的方法 [Floyd's cycle-finding algorithm](https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
* [andy19950](https://hackmd.io/s/rJ6m3IvC)
* multiple workqueue: 每個thread都有自己的workqueue。round-robin將tasks平均分配給每個workqueue
* jkrvivian
* [Makefile for auto testing](https://github.com/jkrvivian/compute-pi/blob/master/Makefile)
* [shelly4132](https://hackmd.io/s/HkX7l7YA)
* 合併merge_sort()和cut_func() (把merge_sort()刪掉，留下cut_func()就好)
* 副作用: 產生過多的merge tasks? 就算合併兩個長度為1的sublist, 也需產生task
* [LanKuDot](https://hackmd.io/s/S1ezGhIA)
* scability評估方法[[1]](http://stackoverflow.com/questions/9420014/what-does-it-mean-scalability)
* [0140454](https://hackmd.io/s/rkx7_9DR)
* 同shelly4132的做法, 合併cut_func()及merge_sort()
* [王紹華](https://hackmd.io/s/r1puDF9R)
* pipe usage?
* [ierosodi](https://hackmd.io/s/HyXCDd_R)
* multiple workqueue
* lock-free threadpool
* [FZzzz](https://hackmd.io/s/SJfa8wFR)
* 字串版實驗
* [SwimGlasses](https://hackmd.io/s/r1Y9r_OR)
* 實驗
* [vic85821](https://hackmd.io/s/rkyY8VjR)
* 改寫thread pool
* [CheHsuan](https://hackmd.io/s/ry24aKiA)
* 解釋為何執行時間會跳動
* [ruby0109 2016q1筆記](https://embedded2016.hackpad.com/concurrent-merge-sort-p3rF7g0t09S)
* bottom-up & top-down
Sign in with Wallet
Connect another wallet