2016q3 Homework3 (mergesort-concurrent)

# 2016q3 Homework3 (mergesort-concurrent) contributed by <`linachiu`> --- ## 預期目標 * 作為 [concurrency](/s/H10MXXoT) 的展示案例 * 學習 POSIX Thread Programming，特別是 [synchronization object](https://docs.oracle.com/cd/E19683-01/806-6867/6jfpgdcnd/index.html) * 為日後效能分析和 scalability 研究建構基礎建設 * 學習程式品質分析和相關的開發工具 --- ## 先跟著老師做在 GNU bash 中，可善用 `$RANDOM` 環境變數，取得介於 0~32767 之間的亂數，於是我們可透過以下指令來作自動測試: ```shell $ (for i in {1..8}; do echo $RANDOM; done) | ./sort 4 8 ``` 輸出的 "sorted results" 訊息後方應該有 8 組數值，由小到大排列。 * 延伸閱讀: [第十章、認識與學習BASH](http://linux.vbird.org/linux_basic/0320bash.php)，《鳥哥的 Linux 私房菜》 ``` input unsorted data line-by-line sorted results: [3119] [3464] [6262] [12000] [13325] [27311] [28389] [30002] ``` ___ ## GraphViz [ [source](http://www.openfoundry.org/tw/foss-programs/8820-graphviz-) ] [Graphviz](http://www.graphviz.org/) 是個依據給定指令的製圖軟體，不過說是繪圖軟體，它能繪的圖並不是一般人想像中的漫畫或 logo，而是數學意義上的 "graph"，比較通俗的說法就是「關係圖」。 * 以下就用 Lock-free Thread Pool 做練習 ```graphviz digraph { Worker_Thread_1[shape="box", style=rounded]; Worker_Thread_2[shape="box", style=rounded]; Worker_Thread_3[shape="box", style=rounded]; Worker_Thread_4[shape="box", style=rounded]; Work_Queue[label="Work_Queue",shape="box", style=rounded]; Work__Queue[label="Work_Queue",shape="box", style=rounded]; Work_Queue_[label="Work_Queue",shape="box", style=rounded]; Work__Queue_[label="Work_Queue",shape="box", style=rounded]; Main_thread[shape="box", style=rounded]; Main_thread->Work_Queue->Worker_Thread_1 Main_thread->Work__Queue[label="put_work"] Work__Queue->Worker_Thread_2[label="Get_work"] Main_thread->Work__Queue_->Worker_Thread_4 Main_thread->Work_Queue_->Worker_Thread_3 } ``` ___ ## 分析 mutex contention mutrace 可用來偵測 [lock contention](https://en.wikipedia.org/wiki/Lock_(computer_science)#Granularity)，使用很方便，不需要重新編譯程式碼。 ```shell $ sudo apt-get install mutrace ``` 加入前面的Random ``` $ (for i in {1..8}; do echo $RANDOM; done) | mutrace ./sort 4 8 ``` mutrace: 0.2 sucessfully initialized for process sort (pid 1868). input unsorted data line-by-line ``` sorted results: [2603] [4188] [5494] [6453] [6830] [8725] [14730] [21292] mutrace: Showing statistics for process sort (pid 1868). mutrace: 3 mutexes used. Mutex #0 (0x0x6ab9b0) first referenced by: /usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7f9ecfea34b2] ./sort(tqueue_init+0x38) [0x401277] ./sort(tpool_init+0x6a) [0x4014cc] ./sort(main+0x161) [0x401c74] /lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7f9ecf8da830] Mutex #2 (0x0x7f9ecd4a9860) first referenced by: /usr/lib/mutrace/libmutrace.so(pthread_mutex_lock+0x49) [0x7f9ecfea36b9] /lib/x86_64-linux-gnu/libgcc_s.so.1(_Unwind_Find_FDE+0x2c) [0x7f9ecd2a5fec] [(nil)] Mutex #1 (0x0x603120) first referenced by: /usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7f9ecfea34b2] ./sort(main+0x11d) [0x401c30] /lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7f9ecf8da830] mutrace: Showing 3 most contended mutexes: Mutex # Locked Changed Cont. tot.Time[ms] avg.Time[ms] max.Time[ms] Flags 0 182 34 26 0.044 0.000 0.002 Mx.--. 2 20 5 1 0.007 0.000 0.002 M-.--. 1 13 5 0 0.004 0.000 0.000 M-.--. |||||| /||||| Object: M = Mutex, W = RWLock /|||| State: x = dead, ! = inconsistent /||| Use: R = used in realtime thread /|| Mutex Type: r = RECURSIVE, e = ERRRORCHECK, a = ADAPTIVE /| Mutex Protocol: i = INHERIT, p = PROTECT / RWLock Kind: r = PREFER_READER, w = PREFER_WRITER, W = PREFER_WRITER_NONREC mutrace: Note that the flags column R is only valid in --track-rt mode! mutrace: Total runtime is 1.213 ms. mutrace: Results for SMP with 4 processors. ``` 其中 `tqueue_init+0x38` 就是實際執行的地址，可用 `addr2line` 來找出對原始程式碼的對應，注意，要確保編譯時加入 `-g` 參數，確保包含 debug info 的執行檔正確產生。以這個地址來說，對應的原始程式碼為: ```shell $ addr2line -e sort 0x38 ``` ___ ## 修改 ### UNIX 指令組合的魔法 * [phonebook-concurrent](https://github.com/sysprog21/phonebook-concurrent) 裡頭的 `dictionary/words.txt` 複製出來，然後透過 UNIX 指令打亂順序，之後重新導向到另一個檔案這樣就有新的資料輸入。 * words.txt ``` aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaah aaaaaaauugh aaaaaagh aaaaaahhhhh ``` ```shell $ uniq words.txt | sort -R > input.txt ``` * input.txt ``` bromines corrects bixaceous osteectomy pygidid toumanova failure sibincic subradiance ``` ### 將程式修改成針對string的mergesort val_t改為char array list.h ```c== typedef char val_t[MAX_LAST_NAME_SIZE]; ``` main.c 裡面的 merge_list() ```c== llist_t *small = (llist_t *) ((intptr_t) a * (a->head->data <= b->head->data) + (intptr_t) b * (a->head->data > b->head->data)); ``` ```c== llist_t *small = (llist_t *) ((intptr_t) a * (strcmp(a->head->data,b->head->data) < 0 ? 1:0) + (intptr_t) b * (strcmp(a->head->data,b->head->data) < 0 ? 0:1)); ``` ## 參考資料 * 助教 * [VVN筆記](https://hackmd.io/EwNgZgnAjFIAwFoDGSDsIEBYCmBDMCEAJlJgttgKyqVhgAccll9QA===?both)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.