2016q3 Homework3 (mergesort-concurrent)

contributed by <linachiu>

預期目標

  • 作為 concurrency 的展示案例
  • 學習 POSIX Thread Programming，特別是 synchronization object
  • 為日後效能分析和 scalability 研究建構基礎建設
  • 學習程式品質分析和相關的開發工具

先跟著老師做

在 GNU bash 中，可善用 $RANDOM 環境變數，取得介於 0~32767 之間的亂數，於是我們可透過以下指令來作自動測試:

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

輸出的 "sorted results" 訊息後方應該有 8 組數值，由小到大排列。

input unsorted data line-by-line

sorted results:
[3119] [3464] [6262] [12000] [13325] [27311] [28389] [30002]

GraphViz

[ source ] Graphviz 是個依據給定指令的製圖軟體，不過說是繪圖軟體，它能繪的圖並不是一般人想像中的漫畫或 logo，而是數學意義上的 "graph"，比較通俗的說法就是「關係圖」。

  • 以下就用 Lock-free Thread Pool 做練習
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，使用很方便，不需要重新編譯程式碼。

$ 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 的執行檔正確產生。以這個地址來說，對應的原始程式碼為:

$ addr2line -e sort 0x38

修改

UNIX 指令組合的魔法

  • phonebook-concurrent 裡頭的 dictionary/words.txt 複製出來，然後透過 UNIX 指令打亂順序，之後重新導向到另一個檔案

這樣就有新的資料輸入。

  • words.txt
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaah
aaaaaaauugh
aaaaaagh
aaaaaahhhhh

$ 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

typedef char val_t[MAX_LAST_NAME_SIZE];

main.c 裡面的 merge_list()




 llist_t *small = (llist_t *)
                         ((intptr_t) a * (a->head->data <= b->head->data) +
                          (intptr_t) b * (a->head->data > b->head->data));






        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));

參考資料

Select a repo