# 2016q3 Homework2 (phonebook-concurrent)
contributed by <`CheHsuan`>

## 目標
* 學習第二週提及的 concurrency 程式設計
* 學習 POSIX Thread
* 學習效能分析工具
* code refactoring 練習
* 探索 clz 的應用

## 教材瀏覽紀錄
### Concurrency系列(一)~(五)
`sequeced-before`就是一種對同一個thread下，求值順序關係的描述
`happens-before`前一個操作的效果在後一個操作執行之前必須要可見
`synchronized-with`就是跨thread版本的happens-before，使用同步來達成
`Memory Consistency Models`
只要結果正確，實際程式怎樣編譯，怎樣run都沒有關係
`Sequential Consistency`

>1.對於每個獨立的處理單元，執行時都維持程式的順序(Program Order)
>2.整個程式以某種順序在所有處理器上執行

在網路上看到用成語來形容concurrency和parallelism，我覺得蠻貼切的
==concurency是一心二用，parallelism是一目十行==

在單核心CPU機器中，multi-threading無法達到parallelism，而只有concurrency
在多核心CPU機器中，concurrency通常具有parrallel特性

## 程式碼分析

先把沒使用過的用法man一下
* `mmap()`
* `pthread_setconcurrency()`
==The pthread_setconcurrency() function informs the implementation of the application's desired concurrency level, specified in new_level. The implementation takes this only as a hint.==
太玄了...
* `dprintf()`
類似fprintf，將資料輸出到fd上，不過不能指定是stdio

### mmap(), munmap(), msync()

mmap()是將檔案映射到一個virtual memory address上面，藉由直接對memory address修改的方式提高對檔案IO的效率(減少資料load到緩衝區的overhead)

在mmap()裡面flag這個參數可填入不同的數值，分別有
1. MAP_SHARED
==Updates to the mapping are visible to other processes that map this file, and are carried through to the underlying file.==
在該映射區域所做的修改對其他同樣映射此檔案的process是可見的，這些修改也會同步回檔案上面(但不保證馬上同步，可配合msync())
2. MAP_PRIVATE
==Create a private copy-on-write mapping. Updates to the mapping are not visible to other processes mapping the same file, and are not carried through to the underlying file. It is unspecified whether changes made to the file after the mmap() call are visible in the mapped region.==
當我們試圖針對映射去做修改(write)時，會產生一個映射的複製(copy-on-write)，而process只會去修改這份copy，因此對其他process來說，該修改是不可見的，除此之外，所有的修改並不會更新回原本的檔案上面。最後有提到，當我們直接或間接對檔案做修改時，並沒有明確定義該修改對於映射是可見的(並不一定同步)
3. MAP_FIXED
把addr當作確切的mapping空間的起始位址，必須是page大小的倍數，而當宣告的記憶體空間大小和其他mapping空間有重疊時，別人的空間會被覆蓋掉。如果指定的空間位址無法使用(例如與.text和.data區域重疊到？)，則mmap()失敗。
4. MAP_ANONYMOUS
==The mapping is not backed by any file.==
明確的指出mmap()配合這個flag所產出來的virtual memory address並不是某個file檔案的映射，在使用這個flag時，必須將fd設定成-1(見底下附注1)。stack和heap就是這種沒有對應到file的虛擬記憶體空間。<br>
這樣子mmap()的使用方式和我們所熟知的malloc()一樣(見底下附注2)，會新增heap的記憶體空間，但mmap()所mapping出來的空間是以page大小為單位，舉例來說，如果在自己的系統上記憶體分頁大小是4096-bytes(可以從<asm/page.h>的PAGE_SIZE得知)，那如果在mmap()宣告不足4096但kernel會自動補到4096，同理超過4096不足8192的話，則是會補到兩個分頁大小的空間。此外，這些被產出來的記憶體空間都會被初始成0。

:::info
#### 附注1
重要：如果要使用這個方式產生虛擬記憶體空間，一定要搭配MAP_PRIVATE flag，不然mmap()會發出error!
e.g.:

char *map = mmap(NULL, fs, PROT_READ | PROT_WRITE,
                 MAP_PRIVATE | MAP_ANONYMOUS,
                 -1, 0);

:::

>> for example 的縮寫是 "[e.g.](https://en.wiktionary.org/wiki/e.g.)"，不是 "ex" [name=jserv]

:::info
#### 附注2
==When allocating blocks of memory larger than MMAP_THRESHOLD bytes, the glibc malloc() implementation allocates the memory as a private anonymous mapping using mmap(2). MMAP_THRESHOLD is 128 kB by default, but is adjustable using mallopt(3).==
在malloc的manual裏面有提到，當如果要宣告的空間超過default值128kB時，會使用mmap()來取得記憶體空間
:::

雖然code沒有使用到msync()，但是我還是想紀錄一下，當我們使用mmap()將file映射到我們的process的address space裡面時，針對裡面的記憶體位址做修改時，並不會馬上同步回硬碟的檔案上，在msync()的manual裏面有提到==Without use of this call there is no guarantee that changes are written back before munmap(2) is called.==，也就是說直到呼叫munmap()之前，所做的更改不保證會馬上寫回disk而是只在記憶體的範疇。

而使用msyn()也有三種flags,分別是MS_ASYNC、MS_SYNC和MS_INVALIDATE，其中的MS_ASYNC和MS_SYNC為互斥，MS_ASYNC是說會將更新的要求排到scheduler上，而call完會直接return，而MS_SYNC則是會等到真正完成IO後，才會return，而MS_INVALIDATE則是更新目前在memory的資料，這個flag通常是用在也有其他人或process也在對同一份檔案做IO然後需要同步。
>> 試著將 `main.c` 的 mmap() 參數變更，從 `MAP_SHARED` 換成 `MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS` 再對照執行時間的變化。注意，因為時間縮短很多，現在 gnuplot 的 Y 軸和測試標的 (也就是我們在意的 `append`) 也該一併變更。參照之前的 compute-pi 和 clz 的統計方法，計算出 `append()` 時間的分佈 [name=jserv]
>> OKOK!不過發現第一次看完還是不太懂manual的解說QQ，還要再查[name=林哲亘]

再來分析程式碼架構。

一開始程式必須先呼叫file_align()，該函式會將原本的words.txt轉換成align.txt，該文字檔裡的格式是lastName加上`\n`再補`\0`到共16bytes，在程式碼內這邊的時間成本沒有加上去

接下來，要記算出file的大小，這邊應該可以用第一次fgets時所得知的行數來計算出align.txt大小

再來是將檔案(align.txt)memory mapping到記憶體空間裡，這邊使用mmap()
宣告一個可以放所有entry的空間，在這邊[吳彥寬](https://www.facebook.com/profile.php?id=100002466873353)同學有提到，malloc是需要成本的，因此這邊用一次malloc()大空間取代多次malloc()小空間

再來就是分配每個thread的任務，完成後開始啟動multi-thread將last name放入到entry裡

最後則是把每個thread的linked list串回來成一條，這邊我覺得可以直接在append()時將指標指到下一個entry，這樣一來，就可以節省合併起來的時間。

### BUG

    if (pHead->pNext) free(pHead->pNext);
        free(pHead);

這邊應該改成while

    while (pHead != NULL) {
        e = pHead;
        pHead = pHead->pNext;
        free(e);
    }

>> 提出 bug-fix 時，應該一併列出你的 Git commit (附上網址，一次修正一個問題) [name=jserv]

[git commit](https://github.com/CheHsuan/phonebook-concurrent/commit/e38076fb8f229a90fb147513093135f6caa52961)
## 目標

1. 完成thread pool版本
2. 完成lock-free thread pool

## 實驗
### MAP Flags實驗
MAP_SHARED
先針對fork下來的專案編譯並跑一次測試，結果如上
MAP_PRIVATE

~~目前MAP_FIXED和MAP_ANONYMOUS有問題，有assertion~~
已找出失敗原因

>> 這是很重要的發現，請思考 mmap 在 multi-threaded 環境下，該怎麼設定。設定 `MAP_SHARED` 之後再觀察，然後記得手冊。交叉閱讀 Linux Device Drivers (2nd Edition) 的 [Chapter 13 mmap and DMA](http://www.xml.com/ldd/chapter/book/ch13.html) [name=jserv]
>> OK，會補在上面[name=林哲亘]

在執行時間上，不同的mapping flag對執行時間好像沒有太大的影響，考量到我們針對此份檔案並沒有做寫入的行為，也沒有其他的process也在修改這份檔案，讓kernel需要做同步，因此執行時間上並沒有顯著的差異
>> 如何證明你說「執行時間上並沒有顯著的差異」這句話？已經實驗多個檔案透過 mmap 存取了嗎？不要憑感覺說話 [name=jserv]
>> 老師我不太懂您的意思耶，是指用更多不同的檔案然後用mmap去實驗，還是說不同類型的檔案，那有沒有要加入其他process去存取，要有write行為嘛？

這是用time指令去取出sys時間，並各跑100次的實驗結果，我會想做這個實驗的考量是說，如果MAP_SHARED和MAP_PRIVATE如果會有顯著差異的話，那最主要應該是在kernel space執行時間的差別(因為記憶體的資料要和檔案做sync)。不過看起來還是大致落在同一個範圍內。
(因為time指令是針對一個執行檔，所以量測的sys時間是還會包含append以外的操作)

### 重構後實驗
移除append後的merge
很神奇的，findname時間大概減少了40%的時間，我根本沒有改findname的方法