# 2017q1 phonebook-concurrent

# phonebook-concurrent

首先看看 code。

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

<!--

# 問題

偷看一下發現要實作 `remove()`, 不過如果發生「邊刪除邊查詢」或是「兩個刪除同一個節點的動作非常接近」的狀況，就會發生錯誤。

最簡單的方法大概是直接用 mutex 鎖住，或是直接改成 lock-free。

因為覺得用 mutex 鎖有點麻煩，所以來看看 lock-free 好了。
-->

# concurrent-ll

我把這段貼到 [mergesort-concurrent](https://hackmd.io/s/H154LN6og) 去了

# 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

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

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

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

3. 另外，因為 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);
}

4. 不過這樣搜尋就會有麻煩的事：因為本來的版本是比大小，但是現在比的是字典順序。所以 `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 的性質呢？