# 2017q1 Homework4 (phonebook-concurrent)
constributed by <`henry0929016816`>

## phonebook thread 版
* mmap
* 功能：
Linux 提供了記憶體映射函數 mmap ，它把文件內容映射到一段記憶體上(準確說是虛擬記憶體上)，通過對這段記憶體的讀取和修改，實現對文件的讀取和修改。映射成功的化，會回傳一個指向映射區域的 pointer ，然而失敗的話則會回傳 MAP_FAILED ( (void *) -1)

* 好處：
由於使用 fgets 讀取字典是 block I/O 所以 thread 開的在多，也會因為 block 的關係而無法做到平行化的讀取字典資料。而使用 mmap 可以得到一個對應檔案的記憶體，這個記憶體可以是 thread 間的共享記憶體，讀取時不會產生 block 所以能平行化。

* 函式解說：

* 函式樣板 ：
void *mmap(void *addr, size_t length, int prot, int flags,int fd, off_t offset)

* addr：
如果 addr 是 NULL ，那 kernel 會選擇適當的 address 建立映射（mapping)，如果不是 NULL ，kernel 會將填入的 addr 當作是暗示要再哪裡建立映射，而 kernel 會選擇在 addr 之上合適的位子建立映射。

* length：
代表映射的大小。將文件的多大長度映射到記憶體。

* prot：
映射區域的保護方式。可以為以下幾種方式的組合：
`PROT_EXEC 映射區域可被執行`
`PROT_READ 映射區域可被讀取`
`PROT_WRITE 映射區域可被寫入`
`PROT_NONE 映射區域不能存取`

* flags：
影響映射區域的各種特性：
`MAP_PRIVATE ：不允許其他映射該文件的行程共享，對映射區域的寫入操作會產生一個映射的複製(copy-on-write)，對此區域所做的修改不會寫回原文件。`

* fd ：
由 open 回傳的文件描述符 ，代表 mmap 要映射的文件

* offset ：
從文件映射開始處的偏移量，通常為 0，代表從文件最前方開始映射。 offset 必須是分頁大小的整數倍(在 32 位體系統結構上通常是 4K )。

* text_align
* 功能：
原本字典裡的字串長度是不固定的，所以如果使用 mmap 映射字典檔案，會因為每個字串長度的不固定，而無法確定下一個字串是從哪個記憶體位址開始存取，既然這樣那我們就重新修改原本字典的格式，將字串長度都固定就好了，不夠長的就補上 null character 使每個字串長度都固定，這樣 mmap 後也可以方便的找尋下一個字串開始位址。

* strncpy

* 函式樣板：
char *strncpy(char *dest, const char *src, size_t n)

* 函式解說：
strncpy 會將 src 字串 n 個長度 複製到 dest 字串，如果 n 比 src 長，會再字串後面補上 null character('\0') 確保複製的長度有 n 個 byte，而我們利用這點就可以使得每個字串的長度固定都是 MAX_LAST_NAME_SIZE（16 byte)。

* createThread_arg

* 函式樣板：
thread_arg *createThread_arg(char *data_begin, char *data_end, int threadID, int numOfThread,entry *entryPool)

* 功能說明：
由於 thread 實作的 append 函式只接收一個參數，所以我們要將必要的資訊都封裝進 structure 裡， data_begin 紀錄要從 mmap 映射出的記憶體的哪個位址開始讀取資料，避免 4 thread 執行 append 函式時重複讀取資料而導致程式沒有加快運行， data_end 紀錄了記憶體位址界線再哪，以免讀取超過界線

* 效能分析：
* 執行時間：
上圖可以看出原本 append 的時間為 0.080164 s，然而經過平行化處理，執行時間已經降為 0.004982 s 跟 findName 執行時間很接近。

* cache misses

397,275      cache-misses              #   31.523 % of all cache refs      ( +-  0.96% )
         1,260,273      cache-references                                              ( +-  1.41% )
       248,716,045      instructions              #    1.12  insn per cycle           ( +-  0.08% )
       222,848,294      cycles                                                        ( +-  0.82% )

       0.098804162 seconds time elapsed                                          ( +-  0.93% )

## 改善 cache-misses
* 觀點：
參考了 [LanKuDot (李昆憶)的共筆](https://hackmd.io/s/HJFhaiAp#)，讓我注意到了 thread 版的 append（）函式還有修正的空間，原版的由於考量到不讓資料重複讀取，而使得每次讀取字串長度都要跨過 thread 數量的字串，然而這樣的作法卻不是個好方法，由於 cache 會傾向 load 進連續的記憶體，所以這樣不連續的記憶體操作，則會導致 cache misses 的增加。

* 改善方式：
將要讀取資料分成 4 個部份，而 thread 分別在這 4 個部份，做連續的讀取，期許能降低 cache misses

* code：

## 參考資料
[concurrency](https://hackmd.io/s/Skh_AaVix#)
[記憶體映射函數 mmap 的使用方法](http://welkinchen.pixnet.net/blog/post/41312211-%E8%A8%98%E6%86%B6%E9%AB%94%E6%98%A0%E5%B0%84%E5%87%BD%E6%95%B8-mmap-%E7%9A%84%E4%BD%BF%E7%94%A8%E6%96%B9%E6%B3%95)
[mmap](http://man7.org/linux/man-pages/man2/mmap.2.html)
[LanKuDot (李昆憶)的共筆](https://hackmd.io/s/HJFhaiAp#)