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_cut 和 merge_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
Last changed by 
 
鄭皓澤
0
325
Published on HackMD