2016q3 Homework2 (phonebook-concurrent)
===
contributed by <`vic85821`>

## 開發環境
* Ubuntu 16.04.1 LTS
* Linux version 4.4.0-38-generic
* CPU : Intel® Core™ i5-3230M CPU @ 2.60GHz
* Main memory : 8GB
* L1d cache : 32K
* L1i cache : 32K
* L2 cache : 256K
* L3 cache : 3072K

## 目標
- [x] 驗證結果
- [x] 實作hash table
- [ ] 實作thread pool

## Pthread

## mmap
Linux提供了記憶體映射函數 mmap，它把文件內容映射到一段虛擬記憶體上,**讓存取或是寫入檔案更快速直接**,不用經過buffer
>原本以為將align的長度減少(min = 13)可以降低cache-miss,但實驗結果顯示align長度=16時cache-miss最低
>> Hint: cache line size [name=jserv]

void *mmap(void *start,size_t length, int prot, int flags, int fd, off_t offsize);

**參數說明:**
* `start` : 指定從虛擬記憶體的哪個位置開始存放,若傳入`NULL`則會隨機配置可用的記憶體位置
* `length` : 要映射的記憶體大小
* `prot` 映射區域的保護方式

PROT_EXEC 映射區域可被執行
PROT_READ 映射區域可被讀取
PROT_WRITE 映射區域可被寫入
PROT_NONE 映射區域不能存取

* `flags` : 影響映射區域的各種特性,以下為常見的

MAP_SHARED  允許其他映射該文件的行程共享，對映射區域的寫入數據會複製回文件。
MAP_PRIVATE 不允許其他映射該文件的行程共享，對映射區域的寫入操作會產生一個映射的複製(copy-on-write)，對此區域所做的修改不會寫回原文件。

* `fd` : 由open返回的文件描述符，代表要映射到核心中的文件
>這部份不太清楚參數代表的意義[color=#6447c1]
* `off_size` : 從文件映射開始處的偏移量，通常為0，代表從文件最前方開始映射。(需為page size的整數倍)

參考資料 : [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)
## 案例分析
### 測試正確性及效能

size of entry : 24 bytes
execution time of append() : 0.006272 sec
execution time of findName() : 0.005810 sec

正確性的部份參考[tempoJiJi](/s/rymKa4aT)的共筆,將程式的輸出與原本的字典檔做比較

#ifdef OPT
    show_entry(e);
#endif

`./phonebook.opt > test.txt`
因為輸出的格式與字典檔內容有些不同,因此額外parse資料並sort
並利用`diff words.txt test.txt`檢測檔案差異

輸出只有349896筆,但word.txt有349900筆,少了幾筆資料
對程式碼做了修正

for (int i = 0; i < THREAD_NUM; i++) {
        if (i == 0) {
            pHead = app[i]->pHead;
            dprintf("Connect %d head string %s %p\n", i,
                    app[i]->pHead->pNext->lastName, app[i]->ptr);
        } else {
            etmp->pNext = app[i]->pHead;
            dprintf("Connect %d head string %s %p\n", i,
                    app[i]->pHead->pNext->lastName, app[i]->ptr);
        }

`pHead = app[i]->pHead->pNext;` 改成 `pHead = app[i]->pHead`
`etmp->pNext = app[i]->pHead->pNext;`改成`etmp->pNext = app[i]->pHead;`
原本的寫法,各個thread_ll head 單字都會消失,修正完之後,結果就是對的了

在作業1的phonebook,我是透過build binary search tree以提高findName()的速度,因此藉由檢查output檔的機會,這次便利用hash table來檢驗正確性
(原本想說利用array存取資料,再直接sort比較就好,但資料量太大了...)
* check_right.c

int hash_value(char* ptr)
{
    unsigned int value = 0;
    unsigned int seed = 31;
    int i = 0;
    while(i < strlen(ptr))
    {
        value = value * seed + *ptr;
        i++;
    }
    return value % TABLE_SIZE;
}

hTable *create()
{
    hTable *table;
    table = malloc(sizeof(hTable));
    table -> list = malloc(sizeof(entry_c*) * TABLE_SIZE);
    int i = 0;

    for(i = 0; i < TABLE_SIZE; ++i)
        table -> list[i] = NULL;

    return table;
}

寫完才得知,原來linux本身就有sort指令可以幫忙排序Orz!!
`$ sort output.txt`

### 原始版本的效能改善與問題

#### 效能改善
* thread pool
* hash table
#### 問題
* Pthread 假設有某個thread的執行時間過長,會拉低整個程式的效能
* 增加thread卻沒有增加效能的原因
* 透過 thread pool 來進行改善
* 程式是將整個words都串聯起來,因此findname()仍必須線性搜尋
* 透過hash table來提高findname()
* 但必定會犧牲append()的效能

### 優化1_Hash Table
使用hash table加快了findName()的速度,各個thread先分別建立hash table,最後再join
* append(): 建表的時候需要較多的時間
* findName(): 利用hash table降低了許多

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

           452,045      cache-misses              #   37.454 % of all cache refs      ( +-  1.26% )
         1,206,946      cache-references                                              ( +-  1.31% )
       323,977,868      instructions              #    1.16  insns per cycle          ( +-  0.06% )
       279,321,497      cycles                                                        ( +-  0.58% )

       0.080669329 seconds time elapsed                                          ( +- 11.95% )

### 優化2_Thread Pool
為了降低append()的時間,因此想實作看看thread pool (研究中...)

## Refactoring
**定義 : 在不改變軟體的外在行為之下，改善既有軟體的內部設計**
目標 : 判斷軟體中所存在的壞味道（smell），然後套用重構來移除這些壞味道

簡而言之,現行程式碼可以將內容分為**form**和**context**,我們可以透過挑除form當中的**壞味道**,讓程式更有效率.更好被理解

### 程式的壞味道

typedef struct _append_a {
    char *ptr;
    char *eptr;
    int tid;
    int nthread;
    entry *entryStart;
    entry *pHead;
    entry *pLast;
} append_a;

從`append()`,`new_append_a()`中可以發現,沒有使用到tid這個變數,因此將tid移除,並針對`append()`,`new_append_a()`,`main()`中有assign tid的地方修改,整個程式仍然是正確的

>> 良性的批評是一併提出改進方案，show me the code! [name=jserv]

參考資料:[什麼是refactoring](http://teddy-chen-tw.blogspot.tw/2014/04/refactoring.html)

###### tags: `phonebook` `concurrent` `refactoring` `Pthread`