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

### Interface
為了讓程式有更好的可讀性，避免放置一堆 ```#define```，目前實做介面如下：

void *init();
void *readFile(void *);
void *append(char [], void *);
void *findName(char [], void *);
void memory_free(void *);

* init: 初始化 phonebook 必要結構
* readFile: 讀入檔案，並使用 append 新增資料項到 phonebook
* append: 建立必要結構將資料加入 phonebook
* findName: 從 phonebook 找出指定資料項
* memory_free: 釋放動態配置結構的記憶體

### mmap
* Great for multiple processes accessing the same file in read-only fasion
* Single vs. multiple system call
* No need to copy the data to the buffer C runtime maintain

## Original Version

size of entry : 136 bytes
execution time of append() : 0.077778 +- 0.000892 sec
execution time of findName() : 0.004927 +- 0.000030 sec
(95% 信賴區間)

 Performance counter stats for './phonebook_orig' (100 runs):

     2,010,723	cache-misses		#87.332% of all cache refs	( +-  0.13% )
     2,302,381	cache-references                             		( +-  0.07% )
   387,959,515	instructions    	#1.51  insns per cycle		( +-  0.01% )
   256,717,122	cycles							( +-  0.13% )

0.070331387 seconds time elapsed ( +-  1.31% )

## Optimization

### mmap 讀檔
1.
* **假設：** 若將所有 lastName 放置於一連續記憶體會提昇整體效能。
* **實做：**
* **entry struct**

		typedef struct __PHONE_BOOK_ENTRY {
		    char *lastName;
		    struct __PHONE_BOOK_DETAIL *pDetail;
		    struct __PHONE_BOOK_ENTRY *pNext;
		} entry;

* 使用 mmap 讀入所有 lastName，並以 '\0' 取代所有 '\n'，將每個 lastName 視為獨立字串
* append 時，不使用 strcpy，而是將 entry->lastName 指向對應位置

* **結果：** 相對原版 append 時間減少了 0.03 秒，但相對重要的 findName 時間卻增加了 0.001 秒

	size of entry : 24 bytes
	execution time of append() : 0.043081 +- 0.000606 sec
	execution time of findName() : 0.006310 +- 0.000031 sec
	(95% 信賴區間)

2.
* **假設：** 將各 entry 其 lastName 放置連續空間能夠提昇搜尋效能
* **實做：**
* **entry struct**

		typedef struct __PHONE_BOOK_ENTRY {
		    char lastName[MAX_LAST_NAME_SIZE];
		    struct __PHONE_BOOK_DETAIL *pDetail;
		    struct __PHONE_BOOK_ENTRY *pNext;
		} entry;

* 使用 mmap 讀入所有 lastName，並以 '\0' 取代所有 '\n'，將每個 lastName 視為獨立字串
* append 時，使用 strcpy 將 lastName 複製到 entry
* 釋放 mmap 所配置空間

* **結果：** 相對原版 append 時間減少 0.02 秒，且 findName 時間減少 0.0015 秒

	size of entry : 32 bytes
	execution time of append() : 0.057684 +- 0.000508 sec
	execution time of findName() : 0.003563 +- 0.000017 sec
	(95% 信賴區間)

>> 需要用統計方法，取出 95% 信賴區間，最好還能用 perf 分析效能 hotspot [name=jserv]
>> 收到！[name=Shaoyu-Chen]

3. **討論**
* 前者 lastName 並不伴隨 entry，兩者在相對較遠的位置，較少機率會在同一快取線上
* 計算 append 時間時，需使用 ```echo 3 > /proc/sys/vm/drop_caches``` (to free **pagecache**, **dentries** and **inodes*)，否則因為 page cache 的原因，append 時間會因為不須真正做 I/O 而加速很多

### Entry Slab
* **假設：** 預先建立 **entry pool**，配置時直接於 pool 內取出，預期會比 malloc 數次花上較少時間（接續 mmap 讀檔第二項方法）
* **實做：**
* **entry pool container：** 紀錄 entry pool 串列

	static struct Pool_Cont
	{
		struct Entry_Pool *pHead;
		struct Entry_Pool *pCurrent;
		struct Entry_Pool *pTail;
	} ppool_cont;

* **entry pool：** 共有 64 entry 可供配置，並以 bitmap 紀錄各 entry 的配置情形

	static struct Entry_Pool
	{
		uint64_t bitmap;
		entry *pPool;
		struct Entry_Pool *pNext;
	};

* **結果：** append 時間多了 0.015 秒，findName 時間多 0.00025 秒，兩者皆無進步。若考慮到釋放 entry 與再次配置所需的額外檢測，則 append 時間則會大幅增加至 1 秒左右。

size of entry : 32 bytes
execution time of append() : 0.072752 +- 0.000958 sec
execution time of findName() : 0.003801 +- 0.000018 sec
(95% 信賴區間)

* **討論：**
推估原因為 runtime library 並不真的向作業系統 malloc 使用者指定大小空間，而是一次 malloc 更大的空間並進行管理，從結果來看我的作法顯得並不恰當。

**Source of this article: https://hackmd.io/s/BJlPwHmA**