2017q1 phonebook-concurrent

phonebook-concurrent

首先看看 code。

大致上的概念是：

把資料對齊，產生一個「對齊版」的檔案
用 mmap 把對齊版的檔案映射。用這個檔案的大小 / 對齊的單位，就可以知道整個檔案有多少字串。
把整條 linked list 平均分成幾個部分，每個部分由一個 thread 負責。每個節點裡面的 last name 是直接指到剛剛 mmap 的記憶體中的不同部分，不用像原來的版本每次新增時都 malloc。
合併每個 thread 創造的小 linked list, 得到全部的 linked list。

concurrent-ll

我把這段貼到 mergesort-concurrent 去了

Lock-Free 有沒有比較快？

接下來我想看看 Lock-Free 的 Linked-List 跟原始版的 phonebook-concurrent 的比較。

Lock-Free 的 Linked-List 好處是插入、刪除、查詢都可以同時進行，而原始版的話只有對建立 Linked-List 做平行化，一邊插入一邊查詢則沒有用其他保護措施。

這裡預計將 phonebook-concurrent 中的 linked-list 用 concurrent-ll 中的 lock-free linked-list 代替，並且比較兩者只做 append 的時間差異。

首先發現 phonebook-concurrent 中的 phonebook-opt 是把 linked-list 跟所有資料寫在一起，所以不好套用新的 linked-list 實作。

所以我決定先暴力用 lock-free 的 linked-list 寫出另外一個 main, 然後再看看能不能做簡化。

只做 append

前面映射的部分大致相同。但是有些地方不一樣：

因為節點的構造改變了(node_t 只有一個指標)，就姑且把它當成 last_name 用。
因為 Lock-Free 的關係，所以就算共用 linked-list 也沒關係，所以執行緒吃得變數就變成：

typedef struct _thread_arg{
    void *map;
    llist_t *phonebook;
    int map_size;
    int no;
}thread_arg

另外，因為 lock-free 的關係，現在就算每個節點同時插入也不會出事。所以就大方給他用下去：

void append_job(void* arg)
{   
    thread_arg* a = (thread_arg*)arg;
    char *map = (char*)(a -> map);
    for (int i = no; i < (a -> map_size) / MAX_LAST_NAME_SIZE; i+= THREAD_NUM) {
        list_add(a -> phonebook, map + i * MAX_LAST_NAME_SIZE);
    }
    pthread_exit(0);
}

不過這樣搜尋就會有麻煩的事：因為本來的版本是比大小，但是現在比的是字典順序。所以 search 當中的條件就要做修改。比如說一開始的 while 迴圈要改成：
```
     while (is_marked_ref(t_next) || (strcmp((char*)(t->data), (char*)(val)) < 0)
```
以及 list_add 當中要改成：
```
    if (right != the_list->tail && strcmp((char*)(right->data) == (char*)val) == 0) {
        return 0;
    }
```
這裡有一個問題：strcmp 會不會破壞 lock-free 的性質呢？