# 2016q3 Homework3 (mergesort-concurrent)

contributed by <`HaoTse`>

---

## 目標
- [x] Code refactor
- [x] 接受 phonebook-concurrent 的 35 萬筆資料輸入
- [ ] lock-free
- [ ] 學習 [concurrent-ll](https://github.com/jserv/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 私房菜 ](http://linux.vbird.org/linux_basic/0320bash.php) 才發現 `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]`。[name=鄭皓澤]

然後將 `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` 的行數 [name=鄭皓澤]

---

## 比較執行時間
使用 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` 目前還在尋找原因[name=鄭皓澤]
---

## 參考資料
- [addr2line](https://sourceware.org/binutils/docs/binutils/addr2line.html)
- [shell `wc`](http://blog.xuite.net/altohorn/linux/17259885-wc+%E8%A8%88%E7%AE%97%E6%AA%94%E6%A1%88%E7%9A%84%E8%A1%8C%E6%95%B8%E3%80%81%E5%AD%97%E6%95%B8%E3%80%81%E4%BD%8D%E5%85%83%E7%B5%84%E6%95%B8)

###### tags: `HaoTse` `sysprog21` `mergesort_concurrent`