Try   HackMD

2017q1 Homework4 (mergesort-concurrent)

contributed by <paul5566>

開發環境

Lubuntu 16.04 LTS

系統效能-指令

$ lscpu
  • CPU: Intel® Core i5-3210M CPU @ 2.50GHz
  • Mem: 8 GB
  • Cache:
    L1d cache: 32 KB
    L1i cache: 32 KB
    L2 cache: 256 KB
    L3 cache: 4096 KB

閱讀程式碼

list.h

首先看看 linked list 的結構

typedef struct { node_t *head; uint32_t size; } llist_t;

原本的程式在建立 linked list 的時候就會順便紀錄長度,所以在分割 list 的時候只需要花

O(N) 的時間就好,不需要重新計算長度。

實際的資料則是儲存於 node_t,並利用 typedef intptr_t val_t 來定義自己的 type。
如此一來,若要更換資料類型,只需要改變 typedef 語句就好。

typedef struct node { val_t data; struct node *next; } node_t;

list.c

這一部份主要是處理 linked list 的各種操作。

threadpool.[ch]

這邊的 thread pool 是採用單一 queue 的架構。

先看看 queue 的部份,利用 mutex 來確保不會有 race condition 的發生。而 condition variable 在觀看的時候發現只有被初始化而已,沒有其他地方使用到。

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 指向應有的地方。

typedef struct _task { void (*func)(void *); void *arg; struct _task *next, *last; } task_t;

在 queue 的部份,原本程式碼的設計是從 head 插入,從 tail 拿出來。雖然符合 FIFO 的定義,但對於常規來說,有點不符合直覺。因此這一部份是可以改善的。

另外,merge sort 的東西都混在 main.c 中,未來可以把他提取出來,成為一個檔案,這樣 main.c 比較簡潔。

Code Refactoring

list.c

  • list_add
    該函數所 return 的東西永遠是 0。我們可以改成 return list head,在使用上能夠更加彈性。

    ​​​​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) 才對。

    ​​​​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 中只有初始化他卻沒有使用他。

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 變修改成以下的樣子。

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 如下

... _task->func = NULL; ...

因為這邊沒有將 _task->arg 設成 NULL,因此會造成 free 有錯誤產生,只要將他初始化就能解決問題。

修改程式

讓程式能夠接受 phonebook 的 dictionary

首先,將 list.h 中的 val_t 改定義為 char array。

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!"

UNIX 指令組合的魔法

boring@boring-K55VM:~/paul5566/mergesort-concurrent/test_data$ uniq words.txt | sort -R > input.txt
boring@boring-K55VM:~/paul5566/mergesort-concurrent/test_data$ 

然後就會產生這個input.txt這個東西

boring@boring-K55VM:~/paul5566/mergesort-concurrent/test_data$ ls
input.txt  words.txt

觀念