Try   HackMD

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，裡頭的命名和 programming model 很值得學習 jserv
簡單比較list實作, 感覺kernel這種允許自訂資料結構的做法比較有彈性 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就好 mingnus
kernel list_sort.c的做法滿特別, 它是把原本的list打散成數個null-terminated sorted sublist, 再把它們合併 mingnus

  • main.c
  • main(): max_cut只計算一次, 應該沒必要為了省略branch而寫成這樣
    max_cut = thread_count * (thread_count <= data_count) +
              data_count * (thread_count > data_count) - 1;

改用一般寫法也比較好理解

    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 mingnus
    你需要重新回顧資料結構和演算法的設計，可參考 Skip list jserv

  • cut_func()在分割list時重覆呼叫list_nth(), 實際上可用list->head->next取代

    _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 的成本 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也得以簡化
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

Last changed by 
 
Ming-Hung Tsai
0
1021
Published on HackMD