---
tags: ncku-course
---
# 2016q3 Homework3 (mergesort-concurrent)
contributed by <`0140454`>
## 閱讀程式碼
### list.h
首先看看 linked list 的結構
```clike=
typedef struct llist {
node_t *head;
uint32_t size;
} llist_t;
```
原本的程式在建立 linked list 的時候就會順便紀錄長度，所以在分割 list 的時候只需要花 $O(N)$ 的時間就好，不需要重新計算長度。
實際的資料則是儲存於 `node_t`，並利用 `typedef intptr_t val_t` 來定義自己的 type。
如此一來，若要更換資料類型，只需要改變 typedef 語句就好。
```clike=
typedef struct node {
val_t data;
struct node *next;
} node_t;
```
### list.c
這一部份主要是處理 linked list 的各種操作。
在這邊比較有爭議的地方應該就是 `list_nth()` 這個函數，從字面上是表示取得第 n 個 node，但在實作上所返回的卻是 index 為 n 的 node。這一部份會在 code refactoring 做修改。
### threadpool.[ch]
這邊的 thread pool 是採用單一 queue 的架構。
先看看 queue 的部份，利用 mutex 來確保不會有 race condition 的發生。而 condition variable 在觀看的時候發現只有被初始化而已，沒有其他地方使用到。
```clike=
typedef struct {
task_t *head, *tail;
pthread_mutex_t mutex;
pthread_cond_t cond;
uint32_t size;
} tqueue_t;
```
再來是儲存工作資訊的結構，所採用的 doubly linked list。紀錄前一個 task 的用意在於，當從 queue 中拿出工作後，可以在 $O(1)$ 的時間將 queue 的 tail 指向應有的地方。
```clike=
typedef struct _task {
void (*func)(void *);
void *arg;
struct _task *next, *last;
} task_t;
```
在 queue 的部份，原本程式碼的設計是從 head 插入，從 tail 拿出來。雖然符合 FIFO 的定義，但對於常規來說，有點不符合直覺。因此這一部份是可以改善的。
### main.c
看到 `cut_func()` 時發現有用`max_cut` 來限制切割次數，但是不太了解實際的功用。因為在函數中已經有透過 `if (list->size > 1)` 來判斷了。
這一部份與[賴紹芊同學](https://hackmd.io/MwQwRgpiAcAMBmBaA7MALMxaBsAmArItLsNIgJwjACMI2yu02wEQA===?view)討論後，有詢問過作者。發現移除掉 `cut_count < max_cut` 之後，結果並沒有異常。
>> 太好了，你可以大幅縮減程式碼 [name=jserv]
另外，merge sort 的東西都混在 main.c 中，未來可以把他提取出來，成為一個檔案，這樣 main.c 比較簡潔。
## Code Refactoring
### list.c
* list_add
該函數所 return 的東西永遠是 0。我們可以改成 return list head，在使用上能夠更加彈性。
```clike=
llist_t *list_add(llist_t *list, val_t val)
{
node_t *e = node_new(val, NULL);
e->next = list->head;
list->head = e;
list->size++;
return list;
}
```
* list_nth
如同閱讀程式碼那邊所說的，應該把函數名稱改為 `list_get()` 較為妥當。
除此之外，index 不應該大於 size - 1，因此在函數一開始的邊界檢查，應改為 `if (idx >= list->size)` 才對。
```clike=
node_t *list_get(llist_t *list, uint32_t idx)
{
if (idx >= list->size)
return NULL;
node_t *head = list->head;
while (idx--)
head = head->next;
return head;
}
```
### threadpool.[ch]
把 `tqueue_t` 中的 cond 移除，因為在 threadpool.c 中只有初始化他卻沒有使用他。
```clike=
typedef struct {
task_t *head, *tail;
pthread_mutex_t mutex;
uint32_t size;
} tqueue_t;
```
再來是剛剛上面提過的，queue 的 push/pop 方向有點不符合直覺。
所以這邊把他改成從頭 pop，從尾巴 push。
但改完發現，其實 `task_t` 間並不需要利用 doubly linked list 來串，因為誰是前一個並不重要。所以 `task_t` 變修改成以下的樣子。
```clike=
typedef struct _task {
void (*func)(void *);
void *arg;
struct _task *next;
} task_t;
```
另外，在 `tqueue_free()` 中是使用 free() 來釋放 `task_t` 記憶體。可是，這樣會導致 task argument 沒有被釋放到，所以應該要改用 `task_free()` 才對。
值得注意的是，在 main.c 的 `merge()` 中，有一段 code 如下
```clike=
...
_task->func = NULL;
...
```
因為這邊沒有將 `_task->arg` 設成 NULL，因此會造成 free 有錯誤產生，只要將他初始化就能解決問題。
### main.c
上禮拜 code review 時老師提到 main.c 中不應該過於龐大、複雜。在原始的程式碼中，main.c 總共有 183 行，如果把 merge sort 相關的函數分離，應該可以減少不少行。
首先，先針對上面說的，`max_cut` 的切割限制似乎沒有太重要的地方，所以先把相關的部份移除。mutex 之所以還需要留著是因為有其他的 static global variable 需要受到保護。
```clike=
struct {
pthread_mutex_t mutex;
} data_context;
```
再來是，因為因為 `cut_func()` 已經將切割 list 的動作都做好了，所以 `merge_sort()` 中不需要再進行切割，因此這一部份的 code 是可以移除的。
最後，把 `merge_list()` 抽出，放置 merge_sort.c 中，讓 main.c 裏面只留必要的東西。除此之外，也把 `merge()` 改名成 `merge_threads_list()`，因為他主要是在合併 thread 間已經 sort 完成的 list。
## 修改程式
### 讓程式能夠接受 phonebook 的 dictionary
首先，將 list.h 中的 `val_t` 改定義為 char array。
```clike=
typedef char val_t[16];
```
並將 input/output 部份改用 `%s` 來操作。
最後修改 merge_sort.c 中的 `merge_list()`，讓他使用 `memcpy()` 來比較。
### 設計自動化測試
在 Makefile 中加入以下規則，利用系統內建的工具來隨機產生資料以及比較結果。
```
THREAD_NUM ?= $(shell nproc)
check: all
sort -R dictionary/words.txt | ./sort $(THREAD_NUM) $(shell wc -l dictionary/words.txt) > sorted.txt
diff -u dictionary/words.txt sorted.txt && echo "Verified!" || echo "Failed!"
```
### 改為 lock-free 版本
**原始版本效能**
首先，先來看看 merge sort 所花的時間以及 mutex 的使用情況。
```shell=
execution time: 0.511178 sec
mutrace: 3 mutexes used.
Mutex #0 (0x0x2d43e20) first referenced by:
/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7f762e57b4b2]
./sort(tqueue_init+0x38) [0x40173a]
./sort(tpool_init+0x6a) [0x401959]
./sort(main+0x119) [0x4014cf]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7f762dfb2830]
Mutex #2 (0x0x603120) first referenced by:
/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7f762e57b4b2]
./sort(main+0xdf) [0x401495]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7f762dfb2830]
Mutex #1 (0x0x7f762bb81860) first referenced by:
/usr/lib/mutrace/libmutrace.so(pthread_mutex_lock+0x49) [0x7f762e57b6b9]
/lib/x86_64-linux-gnu/libgcc_s.so.1(_Unwind_Find_FDE+0x2c) [0x7f762b97dfec]
[(nil)]
mutrace: Showing 3 most contended mutexes:
Mutex # Locked Changed Cont. tot.Time[ms] avg.Time[ms] max.Time[ms] Flags
0 2238787 1724928 1040095 298.548 0.000 0.049 Mx.--.
2 699798 567352 117699 80.506 0.000 0.039 M-.--.
1 20 13 3 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 的結果可以看出，在維護 thread pool 的 queue 時，總共用了不少的時間。接著，先針對 thread pool 進行改善。
**lock-free thread pool**
Sign in with Wallet
Connect another wallet