HackMD
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所使用的變數
- 因為shell所使用的變數
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]
