# 2016q3 Homework2 (phonebook-concurrent)
contribute by <`andy19950`>

### Refactor
#### 首先先詳讀程式碼，可以發現幾個問題
1. **main.c 裡面使用太多 #ifndef #if defined**
- 其實很多都可以放一起使用，把它們合併起來吧
2. **變數名稱看不懂**
- 許多變數名稱都宣告成 ptr i j 第一次看根本看不懂，把它改成有意義的名字吧！
3. **程式碼指標使用有誤**
- 在 main.c 後面把 linked-list 接起來時少接了每個 linked-list 的 head node
- findName() 裡面一開始也少找了第一個 node ，這些錯誤會讓程式搜尋其他名字的時候壞掉。
4. **額外的宣告**
- 像是 pdtail 之類的多餘的宣告或定義把它拿掉
---

### MMAP

void *mmap(void *addr, size_t length, int prot, int flags,
           int fd, off_t offset);

* `addr` : 要map到的記憶體位置，傳NULL系統會自行尋找一塊空間 mapping 完之後回傳。

* `length`:　要 mapping 的長度，它會從 fd + offset 的位置開始 mapping 檔案。
* `prot`: **不能跟 open mode 有衝突**
- `PROT_EXEC` Pages may be executed.
- `PROT_READ` Pages may be read.
- `PROT_WRITE` Pages may be written.
- `PROT_NONE` Pages may not be accessed.
* `flags`: 選擇 map file 能不能被其他程式看到
* `fd`: 用系統函式 open 打開的檔案位置，open mode 可以選擇檔案的讀寫屬性，不能跟 prot 有衝突。
* `offset`: 從檔案的哪裡開始 mapping，offset 必須是 page size 的倍數，可以用 sysconf(_SC_PAGE_SIZE) 取得。
>>`mmap` 是 UNIX 系統呼叫 [name=jserv]
- 一般來說把資料從硬碟搬進記憶體時，會建立 page table 來紀錄 virtual address 與 physical address 的相對關係，在程式執行時用動態位置轉換來取得實體位置裡面的資料。
- mmap 就有點像是這樣，只是它不把資料搬進記憶體，只將實體位置跟虛擬位置的關係記錄下來，如此可以省去許多 I/O 的時間。
>> 在這份程式碼中，缺乏驗證資料正確性的機制，請嘗試逐一輸出 last name 到一份檔案，再跟 `dictionary/words.txt` 比對。 [name=jserv]
---
### 資料正確性檢查
- 因為我把 append 稍做修改，改成比較像是 insert，所以 linked-list 的順序是完全亂掉的。
- 因此我在 main 的最下面把輸入資料再重新跑一遍，每個名字都去 findName() 確認有沒有在 linked-list 內。
- 時間複雜度是 O(n^2^)，因為資料量太龐大了所以驗證一次非常花時間。

while(fgets(line, sizeof(line), fp)) {
    e = pHead;
    printf("%s", line);
    if(strcmp(findName(line, e)->lastName, line) != 0) {
        printf("ERROR : Name %s is not in linked-list!!\n", line);
    }
}

- 然後我執行 `./phonebook-concurrent > output.txt` 搜尋 `ERROR` 之後找不到就代表 linked-list 內部資料完全正確
:::warning
E486: 找不到 ERROR
:::
- 若要加速驗證時間的話可以寫一個 linked-list sort function 把它排序成跟原來檔案的順序一樣，這樣時間複雜度是 O(nlogn)。
---
### findName() 的缺點

<s>
- 資料都在硬碟裡面，所以不允許修改它的內容，我本來想讓在 findName 找到的時候直接去把 \n 轉成 \0 ，但每次都會 segmentation fault。
</s>

>> `mmap` 可在記憶體映射 (map) 給定檔案時，指定存取模式，請詳細閱讀 man page: [mmap(2)](http://man7.org/linux/man-pages/man2/mmap.2.html) [name=jserv]
>> 謝謝老師，正在想有沒有辦法解決呢！！ [name=andy19950]
>> 下面有修改過 findName 的版本所以刪掉的地方就當做沒看到吧 [name=andy19950]
- 後來我發現原本的程式碼是把要找的名字跟 map 裡的資料做比較，找到後就 malloc 一塊記憶體位置把要找的名字寫入。
- 但是如果這支程式長時間的執行，當所有名字都在記憶體內部之後，這隻程式依然會傻傻的一直 malloc 空間給它，所以如果多執行幾次 findName 可能會發生 segmentation fault 。

### 修改 open mode 及 mmap prot
- 我把兩邊的參數都修改成 read write 模式
- 然後我就可以對檔案做修改了！！

int fd = open(ALIGN_FILE, O_RDWR | O_NONBLOCK);
char *map = mmap(NULL, fs, PROT_READ | PROT_WRITE,
                 MAP_SHARED, fd, 0);

#### 於是我可以把 findName 改成可直接把 \n -> \0
- 因為我有修改過變數名稱，看不懂的話可以先去 github 看一下 .h 檔

while (current != NULL) {
    if (strncasecmp(lastName, current->lastName, len) == 0) {
        current->lastName[len] = '\0';
        current->dtl = (detail *) malloc( sizeof(detail));
        return current;
    }
    current = current->pNext;
}

---
### 使用 thread pool -- [source code](https://github.com/mbrossard/threadpool)

threadpool_t *threadpool_create(int thread_count,
                                int queue_size,
                                int flags);

int threadpool_add(threadpool_t *pool,
                   void (*routine)(void *),
                   void *arg, int flags);
		
int threadpool_destroy(threadpool_t *pool, int flags);

1. `threadpool_create`：傳入 thread 的數量，queue 的大小，回傳 threadpool 型態是 threadpool_t
2. `threadpool_add`：傳入 threadpool，要執行的function位置，要傳入的參數
3. `threadpool_destroy`：傳入 threadpool，會把 threadpool 的空間 free 掉
:::info
flags 只有 destroy 會用到， threadpool_graceful = 1，其他的傳 NULL 就可以了。
:::
- 我個人覺得用起來跟 pthread 很像
- 程式碼改起來也很像，就是把
- `pthread_create` -> `threadpool_create` + `threadpool_add`
- `pthread_join` -> `threadpool_destroy`

threadpool_t *pool = threadpool_create(THREAD_NUM, 512, NULL);
for (int i = 0; i < THREAD_NUM; i++) {
    threadpool_add(pool, &append, app[i], NULL);
}
threadpool_destroy(pool, 1);

#### 執行結果

- 效果好像不大， ~~THREAD_NUM = 4 是最佳了~~
>> 我們只對 append() 有興趣，可以單獨製圖，然後調整 Y 軸刻度，得以比較不同 thread 數量對效能的影響。讓視覺效果更顯著 [name=jserv]
#### 今天把 THREAD_NUM = 1 ~ 64 跑了一次，竟然是一條 thread 跑最快！！

---
Reference
- [mmap](https://read01.com/8G70jy.html)