Mergesort 效能分析

contributed by <fzzzz> , <nekoneko> , <abba123>

tags fzzzz nekoneko abba123 sysprog

中英文關鍵字之間請記得使用空白隔開
課程助教

目標

• 試圖找出之前實驗時，數據抖動的原因
• 分析 lock contention 對於執行時間的影響
• 整理semaphore, mutex, condition variable資料與比較三者差異
• 了解何謂coarse locking

找出數據抖動原因

在原本的實驗中，我們測試的時候發現執行時間會有不規律的抖動情況出現，即便是使用 gnu 內建的 __buildin___clear_cache() 仍然會存在著不規律抖動，所以我們推測，該抖動的來源可能是來自各 thread 的有效利用率不足。
歸類出以下兩種

• 有效執行的 task 在各 thread 中分佈不均勻
• lock contention 導致大量 thread 處於等待鎖釋放的階段

單一數量執行緒測試

for i in `seq 1 1 50`; do ./sort 100 input.txt; done

各thread執行有效task的分佈

希望能探討分佈平均與否對於效能的影響 `fzzzz`
多次實驗後發現沒有太大的影響（利用variance來作為分散程度的表示方法）
等等補圖 `fzzzz`

分佈均勻度對時間影響

就實驗結果看來在大量執行緒時，分佈均勻與否並不影響執行時間

將mutex改成POSIX semaphore的實做

將main.c和threadpool.*的mutex改成POSIX semaphore

• benchmark
  

• 各 thread 執行有效 task 的分佈
  

semaphore 與 mutex 的差別，有需要再讀資料了解cheng hung lin
信號標和鎖的不同，鎖會有擁有者(task)，semaphore 的話比較像信號標，來告知可不可以過`fzzzz`

上面那行到底在寫什麼？拜託清楚解釋差異，不要用不清不楚的詞彙來自欺欺人 jserv

利用 mutrace and gprof 來找出效能瓶頸

mutrace

Mutex #   Locked  Changed    Cont. tot.Time[ms] avg.Time[ms] max.Time[ms]  Flags
       0  3440715  2706841  1711166      461.433        0.000        4.445 Mx.--.

gprof

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 43.83      0.07     0.07  2805641     0.00     0.00  tqueue_pop
 43.83      0.14     0.07   198755     0.00     0.00  merge_list
  6.26      0.15     0.01   349900     0.00     0.00  list_add
  6.26      0.16     0.01                             main
  0.00      0.16     0.00   395224     0.00     0.00  list_new

經多次測量並觀察後發現，mutex contention 次數愈多的，執行時間會愈久，tqueue_pop 的呼叫次數也會變多
但 function 的呼叫次數與 contention 相比， contention 的影響是大於無意義的 function call
原因是發生 mutex contention 時，該 thread 會被卡在同一個地方，直到 lock 擁有者釋放 lock
和組員討論過後的第一個想法是使用 condition variable，讓不必要的 thread 進入 wait 的狀態（此時該執行緒就不會使用任何 CPU 資源）
這樣就不會浪費 CPU 資源再多次嘗試獲取 mutex 上 –> 使 mutex contention 大幅下降 –> 各 processor 有效執行效率也會變高

晚點補上測資 `fzzzz`
剩下的問題就是若改成 lock-free 的版本的話，效能是否更進一步提升？
在andy19950的共筆裏有提到改成 lock-free 卻無法提升效能
目前想法是，問題應該是出在沒意義的 function call 就變得更多了（待驗證）`fzzzz`
使用htop指令來看 CPU 的使用量，可以發現 mutex 版本的 cpu 使用量會是滿載，而 condition variable 的狀況卻是約一半(每個core)`nekoneko`
這個程式主要探討 lock 的影響，thread queue pop 操作會佔用大部分 CPU 資源的原因是，內部不是採用 coarse locking jserv

利用 condition variable 的實驗

以下測試皆為利用 mutrace 對128個 thread 做100次追蹤的結果

mutrace ./sort 128 input.txt

使用到128個執行緒的原因是，我們想觀看大量並行的效率如何

原版的 contention 數量與執行時間的關係

基本上是正相關，但有些許飄動可能是 clock_gettime() 所導致的浮動

換成使用 condition variable 的版本

這邊的 contention 數量愈多時間基本上還是會上漲，但會上下飄動，理由推斷是 thread 喚醒時的 contex switch 時間不一 `fzzzz`

資料分佈

假設

• cut_func是將link list的資料切成左半llist和右半llist，再透過push task到work queue將資料交給下一個cut_func做處理。若當傳進去的llist 長度為1或是cut_count大於等於max_count時，cut_func則呼叫merge做單個thread mergesort和thread與thread之間的merge。

void cut_func(void *data)
{
    llist_t *list = (llist_t *) data;
    pthread_mutex_lock(&(data_context.mutex));
    int cut_count = data_context.cut_thread_count;

    if (list->size > 1 && cut_count < max_cut) {
        ++data_context.cut_thread_count;
        pthread_mutex_unlock(&(data_context.mutex));

        /* cut list */
        int mid = list->size / 2;
        llist_t *_list = list_new();
        _list->head = list_nth(list, mid);
        _list->size = list->size - mid;
        list_nth(list, mid - 1)->next = NULL;//cut
        list->size = mid;

        /* create new task: left */
        task_t *_task = (task_t *) malloc(sizeof(task_t));
        _task->func = cut_func;
        _task->arg = _list;
        tqueue_push(pool->queue, _task);

        /* create new task: right */
        _task = (task_t *) malloc(sizeof(task_t));
        _task->func = cut_func;
        _task->arg = list;
        tqueue_push(pool->queue, _task);
    } else {
        pthread_mutex_unlock(&(data_context.mutex));
        merge(merge_sort(list));
    }
}

• 在我們的認知中，mergesort的示意圖應該如下
  • list->size > 1 的情況，如左圖
  • cut_count < max_count ，其中max_count假設為3(4條thread)，如右圖

• 這次的mergesort-concurrency是用thread pool實做。cut_func會不斷新增cut_func到task_queue，給work thread去執行。cut_func停止cut的其一判斷條件為cut_count，cut_count是一個會被多個執行cut_func更動的共享全域變數。所以可能會發生cut_func分到list長度很大，但卻不會繼續切半list，就因為cut_count被其他cut_func更新到等於max_count。所以同樣max_count為3的情況下，list可能會被分成圖下情況

驗證

• 在cut_func呼叫merge(merge_list(list))前，印出list長度

pthread_mutex_unlock(&(data_context.mutex));
+ printf("%d\n", list->size)
merge(merge_sort(list));

• 以 128 threads為例，擷取一小段
• 比較好的分佈情況

2734
1367
2734
1367
1367
1366
1367
2734
1367
1367
2733
2734
2733
1367
1367
1366
2733

• 比較壞的分佈情況

85
10935
10934
86
10934
10935
342
342
342
86
341
171
341
171
170
171

這邊應該要用圖表示比較精確，擷取部份只是為突顯分佈不均的情況cheng hung lin
有比對過 contention 數量和分佈的關係嗎? fzzzz

還沒比較兩者之間的關係，太急著想改善資料分佈的情況，直接實做相對均勻的分佈，並測試原本和新的兩者之間執行時間的分佈情況cheng hung lin

改善

code 連結

• cut 策略示意圖，在4條thread的情況，也就是max_count為3

points

linespoints

跟fzzzz討論，認為要將資料分佈的變異數(或標準差)計算出來，因為圖表只能呈現大概的結果，但還是要靠數學量化。cheng hung lin

mutrace 參數說明

• Locked:
  how often the mutex was locked during the entire runtime
• Changed:
  how often the owning thread of the mutex changed
• Cont.:
  how often the lock was already taken when we tried to take it and we had to wait
• tot.Time[ms]:
  lock的總時間
• avg.Time[ms]:
  平均每個lock的時間
• max.Time[ms]:
  lock最久的時間

References

• 恐龍本
• Conditional Variable
• Covariance