2016q3 Homework3 (mergesort-concurrent)
===

## 測試
#### mergesort-concurrent

$ git clone https://github.com/sysprog21/mergesort-concurrent
$ cd mergesort-concurrent
$ make
$ (for i in {1..8}; do echo $RANDOM; done) | ./sort 4 8
input unsorted data line-by-line

sorted results:
[5511] [14518] [18351] [19478] [19498] [24777] [25044] [26372] 

#### 使用 mutrace 來偵測 lock contention

$ (for i in {1..8}; do echo $RANDOM; done) | mutrace ./sort 4 8
mutrace: 0.2 sucessfully initialized for process sort (pid 13333).
input unsorted data line-by-line

sorted results:
[5314] [6430] [14409] [18347] [21803] [23998] [27489] [31961] 

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

Mutex #1 (0x0x20859b0) first referenced by:
	/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7f2fd046a4b2]
	./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) [0x7f2fcfea1830]

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

mutrace: Showing 2 most contended mutexes:

 Mutex #   Locked  Changed    Cont. tot.Time[ms] avg.Time[ms] max.Time[ms]  Flags
       1       29        4        0        0.005        0.000        0.001 Mx.--.
       0       20        3        0        0.003        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 0.649 ms.

mutrace: Results for SMP with 8 processors.

#### 用 addr2line 來找出對原始程式碼的對應，編譯時要加入 -g 參數，產生debug info的執行檔

$ addr2line -e sort 401277
/home/taikiz/mergesort-concurrent/threadpool.c:15

#### 使用Git Hooks測試程式碼錯誤
多加一行free(the_task);

$ scripts/install-git-hooks
$ git commit -a
--- .merge_file_guVA0a	2016-10-09 20:16:58.818858805 +0800
+++ /tmp/.merge_file_guVA0a.rCG06S	2016-10-09 20:16:58.842858767 +0800
@@ -4,8 +4,8 @@ int task_free(task_t *the_task)
 {
     free(the_task->arg);
     free(the_task);
-	free(the_task);
-	return 0;
+    free(the_task);
+    return 0;
 }
 
 int tqueue_init(tqueue_t *the_queue)
[!] threadpool.c does not follow the consistent coding style.

Make sure you have run astyle as the following:
    astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none threadpool.c

[threadpool.c:7]: (error) Memory pointed to by 'the_task' is freed twice.

Fail to pass static analysis.

#### 使用UNIQ得到亂序的phonebook
$ uniq words.txt | sort -R > input.txt

## 作業實做
#### 改為排序phonebook lastname
* 方法：
* 將struct node_t->data的type改為char
* 先使用buffer來存取phonebook lastname
* 再以輸入的rand從buffer中讀取去做list_add
* 時間計算從phonebook開始到task結束為止

$ (for i in {1..8}; do echo $((($RANDOM+349900)%349900)); done) | ./sort 4 8
grallatory
anice
oxyntas
zaebal
batholith
rotwang
drukar
pilgarlic
execution time of sort() : 0.019877 sec

sorted results:
[anice] [batholith] [drukar] [grallatory] [oxyntas] [pilgarlic] [rotwang] [zaebal] 

#### 使用 Makefile 執行排序
* 方法：
* 因為shell所使用的變數$RANDOM調用失敗，所以使用Makefile裡的$$$$當作隨機變數，但是測試時出來的數字是隨次數遞增2，並不是很好用的隨機數，因此就乘上i值使變化增加，雖然不完美但以可當實驗方法

run: sort
	for i in `seq 1 8`; do \
		echo `expr $$i \* $$$$ % 349900`; \
	done | ./sort 4 8

* 結果
其實排序的時間果不一定比較接近，原因待證

#first test
$ make run
for i in `seq 1 8`; do \
	echo `expr $i \* $$ % 349900`; \
done | ./sort 4 8
datagram
dimondale
unnestled
whiskerage
fausto
busybodyism
nietzscheism
practicalism
execution time of sort() : 0.051203 sec

sorted results:
[busybodyism] [datagram] [dimondale] [fausto] [nietzscheism] [practicalism] [unnestled] [whiskerage] 

#second test
$ make run
for i in `seq 1 8`; do \
	echo `expr $i \* $$ % 349900`; \
done | ./sort 4 8
werekena
peisley
antheral
chaffman
funston
deputatively
cancri
glycide
execution time of sort() : 0.017735 sec

sorted results:
[antheral] [cancri] [chaffman] [deputatively] [funston] [glycide] [peisley] [werekena]