Try   HackMD

2016q3 Homework3 (mergesort-concurrent)

contributed by <HaoTse>


目標

  • Code refactor
  • 接受 phonebook-concurrent 的 35 萬筆資料輸入
  • lock-free
  • 學習 concurrent-ll (concurrent linked-list 實作) 的 scalability 分析方式
  • 使用 GraphViz

使用工具

Git Hooks

$ sudo apt-get install astyle cppcheck $ scripts/install-git-hooks

mutrace

$ sudo apt-get install mutrace

  • 搭配 addr2line 使用 (注意,要確保編譯時加入 -g 參數,確保包含 debug info 的執行檔正確產生。)

GraphViz


執行程式

$ (for i in {1..8}; do echo $RANDOM; done) | ./sort 4 8 input unsorted data line-by-line sorted results: [2800] [5021] [5549] [7120] [8134] [19684] [29149] [32265]

Code refactor

刪去 merge_sort()

在研究程式碼時發現 main.c 中的 cut_func() 呼叫 merge_sort() 的部份總是會直接 return list,與同學討論過後覺得 max_cutmerge_sort() 是沒有作用的,因此先將它拿掉,另外也將沒有用到的 cut_count 拿掉。
拿掉後初步執行看看結果是否改變

$ (for i in {1..8}; do echo $RANDOM; done) | ./sort 4 8 input unsorted data line-by-line sorted results: [1317] [3277] [4115] [8066] [12836] [16172] [26664] [31520]

可以發現 sort 後的結果在這裡看起來還是正確的。


驗證正確性

對程式做任何改變後都要驗證其正確性,上述僅僅只是執行一次對8個 random 的數字做排序,並不可靠。
為了驗證正確性,我先增加了 random_gen.c ,並在 Makefile 中做改變。
原本我在 Makefile 中寫

check: random_gen for i in `seq 1 1 10`; do\ ./random_gen $$i;\ ./sort 4 $$i;\ sort random > sorted;\ diff output sorted;\ done

後來參考 鳥哥的 Linux 私房菜 才發現 sort 需加上 -n ,作用為使用『純數字』進行排序(預設是以文字型態來排序的)。
檢查剛剛做的改變,首先 $make CHECK=1,開啟 CHECK 的功能,接著 make check,並且得到 OK 的結果。


減少 main.c 內容

原本 main.c 的行數不少,要追蹤程式碼有點累人,因此我將 merge sort 的部份拉出來到 mergesort.[ch]
另外也將 main.c 中比較容易混淆的部份做修改,例如將 merge() 改名為 merge_thread_list() ,原本的 merge() 容易讓人以為他是合併 sort 完的結果。

我一開始沒有注意就不小心把 merge() 移進 mergesort.[ch]鄭皓澤

然後將 cut_func() 改名為 merge_sort(),比較符合以前的習慣。


讀入 phonebook 的 word.txt

  • 首先先將 typedef 的部份變為 string
    typedef char val_t[16];
    接著將 stdin/stdout 的 %ld 部份改為 %s
  • mergesort.c(merge_list) 中的比較部份使用 strncmp
  • list.c(node_new) assign value 的部份改為使用 strcpy
  • 移除 sort 數字的部份以及前面寫來 check 正確性的程式碼
  • Makefile 中新增驗證正確性的方法

    這裡使用 wc 的指令計算 word.txt 的行數 鄭皓澤


比較執行時間

使用 gnuplot 畫出不同 thread 數量處理 phone book 的 word.txt 的執行時間


原本想說應該應thread愈多愈快,不過這個結果很明顯的跟我想的不一樣,還在研究當中。


mutrace

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

得到輸出如下

mutrace: Showing statistics for process sort (pid 32638).
mutrace: 3 mutexes used.

Mutex #0 (0x0xd069b0) first referenced by:
	/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7fabee2384b2]
	./sort(tqueue_init+0x38) [0x4011fd]
	./sort(tpool_init+0x6a) [0x401452]
	./sort(main+0x11c) [0x401ace]
	/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7fabedc6f830]

Mutex #1 (0x0x7fabeb83e860) first referenced by:
	/usr/lib/mutrace/libmutrace.so(pthread_mutex_lock+0x49) [0x7fabee2386b9]
	/lib/x86_64-linux-gnu/libgcc_s.so.1(_Unwind_Find_FDE+0x2c) [0x7fabeb63afec]
	[(nil)]

Mutex #2 (0x0x603100) first referenced by:
	/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7fabee2384b2]
	./sort(main+0xd8) [0x401a8a]
	/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7fabedc6f830]

mutrace: Showing 3 most contended mutexes:

 Mutex #   Locked  Changed    Cont. tot.Time[ms] avg.Time[ms] max.Time[ms]  Flags
       0      148       62       33        0.072        0.000        0.003 Mx.--.
       1       20       19        9        0.012        0.001        0.002 M-.--.
       2       29       19        8        0.014        0.000        0.001 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.301 ms.

mutrace: Results for SMP with 4 processors.

這裡按照作業要求中所教的使用 addr2line 都顯示 ??:0 目前還在尋找原因鄭皓澤


參考資料

tags: HaoTse sysprog21 mergesort_concurrent