# phonebook-concurrent
contributed by <`HuangWenChen`> , <`aweimeow`>

### 預期目標
* 以足夠大量的資料來測試結果，且資料需要以真實姓名測試，而非亂數產生之無意義文字
* 撰寫過濾信賴區間之程式，把頭尾等極端的資料去除掉

>>1.請補上「預期目標」
>>2.中英文關鍵字中間要使用空白隔開喔!
>>[color=red][name=課程助教]

# Refactoring
## 何謂重構(refactoring)
* 參考閱讀 [ Refactoring - Improving the Design of Existing Code](https://www.csie.ntu.edu.tw/~r95004/Refactoring_improving_the_design_of_existing_code.pdf)

Refactoring 是以一種方式改變軟件系統的過程，「在不改變軟體外部行為的前提下，改變其內部結構」，使其更容易理解且易於修改。
就是可以改進軟體設計、減少錯誤、增加可讀性或者簡化結構而不影響輸出結果。

## 什麼時候該重構
1. 三次法則 (The Rule of Three)
簡單來說三次做相似的事情時，就可以將它們使用重構。 事不過三，三則重構。
2. 添加功能時重構 (Refactor When You Add Function)
3. 修補錯誤時重構 (Refactor When You Need to Fix a Bug)
4. 程式碼審查時重構 (Refactor As You Do a Code Review)

壞味道是指遇到什麼情況該使用重構。而在書中提及到共有22種壞味及各種改善方法。
22種壞味道如下:
duplicated code、long method、large class、long parameter list、divergent change、shotgun surgery、feature envy、data clumps、primitive obsession、switch statements、parallel inheritance hierarchies、lazy class、speculative generality、temporary field、message chains、middle man、inappropriate intimacy、alternative classes with different interfaces、incomplete library class、data class、refused bequest、comments
改善方法就大概略過。

# Concurrency
* 參考資料
* [Concurrency系列](http://enginechang.logdown.com/posts/784600-concurrency-series-1-the-road-to-understand-concurrency)

### 名詞定義
* Sequenced-Before - 先完成之後才開始進行
* Happens-Before - 同一個 thread 前一個操作的效果在後一個操作執行之前必須要可見
* Synchronized-with - 不同的 thread 前一個操作的效果在後一個操作執行之前必須要可見

# SuperMalloc: A super Fast Multithreaded Malloc for 64-bit Machines

## Abstract

* SuperMalloc 是一原先設計於 x86 HTM(Hardware Transcantional Memory) 的 malloc 實作
* 在 1 個 thread 時，SuperMalloc 比 DLmalloc, JEmalloc, Hoard, TBBmalloc 還要快 2.1 倍
* 在 8 個 threads 時，有 HTM 的情況之下，SuperMalloc 比上述所說的還要快 2.75 倍
* 在 32 個 threads 時，無 HTM 的情況之下，SuperMalloc 比上述所說的還要快 3.4 倍
* 一般而言，SuperMalloc 比其他 Memory Allocator 還要：更快、可擴充性更高、速度更快且程式碼更少。
* <s>SuperMalloc 很快就是了（Abstract 第一段的說明）</s>
>> 不要過度簡化，這樣跟腦補有什麼差別？注意到論文提到的要素 [name=jserv]

* 利用的特性是：在 x64 實體記憶體雖然很稀有（precious），但虛擬記憶體就相對容易取得

## Intro

malloc & free 影響著程式的執行效能（allocation 操作在多執行緒的環境會慢）
簡單來說可以把影響效能切分為三個部份：alloc 速度、footprint、複雜度
記憶體在 alloc 的時候，通常被分為 Virtual Allocation 和 Physical Allocation 兩種。
* System Call（mmap）會配置出一段連續的虛擬記憶體空間，此時並未真正分配實體記憶體給程式
* 但是當程式真正要存取記憶體的時候會產生 Page Fault，此時才會真正去 alloc 實體記憶體
* 如果這一塊虛擬記憶體有對應到實體記憶體，我們稱之為 `committed page`，反之則為 `uncommitted page`

<s>DLmalloc 是 Linux 的預設 allocator</s>，他相對簡單且穩定，每一塊被配置的記憶體物件前面都會有 8 byte 的前綴，這表示：這一個物件的 Size、前一塊記憶體位置是正在使用的或是閒置（Free）的。
>> glibc 以 [ptmalloc3](http://www.malloc.de/en/) 為基礎 [name=jserv]

當 DLmalloc 把一個物件釋放掉的時候，也能夠立即將接續的下一個物件合併起來。

# Phonebook-concurrent
## 閱讀程式碼
### file.c - file_align function
* 主要是將檔案讀進來的字串都 padding (補白)成同一個長度大小。
>為什麼要這麼做是因為再利用 mmap 將檔案都讀進記憶體空間時，每個字串長度大小不同這樣還要額外去紀錄每個字串偏移量，如果都是同大小不需多這一步驟。

int main(int argc, char *argv[])
{
    assert(argc == 4 && "./main orgfName modfName Padded");

    char *org = argv[1];
    char *mod = argv[2];
    int pad = atoi(argv[3]);

    printf("orginal file size = %ld\n", fsize(org));

    FILE *fd0 = fopen(org, "r");
    FILE *fd1 = fopen(mod, "w+");

    char rbuf[MAX_BUFF_SIZE];
    int suffix;

    // 這邊是 wbuf 的 new, 但是還沒 init, init 於 #38
    char *wbuf = (char *) malloc(sizeof(char) * pad);

    // get data from fd0 to rbuf
    while (fgets(rbuf, sizeof(rbuf), fd0)) {
        // 把 wbuf 的 pad 個字元 都設定成 NULL
        memset(wbuf, '\0', pad);

        // pad - strlen(rbuf) == 0 時 != 不成立，所以不會做 strncpy 
        if ((suffix = (pad - strlen(rbuf))) != 0)
            strncpy(wbuf, rbuf, strlen(rbuf));

        // fwrite(*ptr, size, nmemb, *FILE_STREAM)
        // 看不懂 nmemb 是要幹嘛的參數
        fwrite(wbuf, pad, 1, fd1);
    }

    fclose(fd0);
    fclose(fd1);

    return 0;
}

### file.c - fsize function
* 利用 [stat()](http://blog.csdn.net/tigerjibo/article/details/11695763) 讀取檔案文件訊息，回傳一個檔案大小。
`int stat(const char *restrict pathname, struct stat *restrict buf)`

mmap() 參考[記憶體映射函數 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) ，讓 thread 可以同時存取。

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

* `start` ：指向欲映射的核心起始位址，通常設為 NULL，代表讓系統自動選定位址，核心會自己在進程位址空間中選擇合適的位址建立映射。
* `length`：代表映射的大小。
* `prot`：映射區域的保護方式。
* `flags`：影響映射區域的各種特性。
* `fd`：由 open 返回的文件描述符，代表要映射到核心中的文件。
* `offset`：從文件映射開始處的偏移量。

pthread_setconcurrency()：設定系統明確的並行數量，預設為0。
[pthread_create()](http://blog.xuite.net/nikoung/wretch/154071878-Pthread+%E7%A8%8B%E5%BC%8F%E6%92%B0%E5%AF%AB) 使用方法

int pthread_create(pthread_t *tid , const pthread_attr_t *attr , 
            void *(*function)(void *) , void *argument)

## 改善
* 參考資料
* [Free First-name and Last-name Databases ](http://www.quietaffiliate.com/free-first-name-and-last-name-databases-csv-and-sql/)

1. 資料要夠（要真實資料）
2. 以統計的方式率掉信賴區間以外的資料
3. 資料型態（分成資料結構大的與小的）

使用美國常見的姓氏 Last-name Databases 去做 append() 與 findName()

#### flle_align

    while (fgets(rbuf, sizeof(rbuf), fd0)) {
        memset(wbuf, '\0', pad);

		// 直接把 if statement 拿掉了
    	strncpy(wbuf, rbuf, strlen(rbuf));

        fwrite(wbuf, pad, 1, fd1);
    }

因為真實姓名字典只有 16751 行，因此為了比較，將隨機（不真實）的字典數量減少至 16751 行
>> 調整下方圖表的 Y 軸，否則視覺化效果很差 [name=jserv]
>> 已調整 ～！[name=aweimeow]

#### 原本的隨機（不真實）資料

#### 以真實人名測試之資料

88797 筆的對照組
#### 隨機資料
#### 真實資料

### 信賴區間
* 參考閱讀
* [估計與信賴區間](http://web.ydu.edu.tw/~alan9956/docu3/0991stat/Statistics_09.pdf)

參考[oiz5201618同學共筆](https://hackmd.io/s/BJdYsOPa#信賴區間)以直接運算母體算出 lower/upper endpoint
公式:
* Lower Endpoint = avg(X) − 1.96 * σ
* Upper Endpoint = avg(X) + 1.96 * σ

標準差公式(Standard deviation)
過濾95%以外的值。

所以在 calculate.c 檔案修改加上信賴區間算法
使用 `make plot` 產生圖表。

僅保留信賴區間之資料，結果對照如下：
* 無過濾信賴區間
* 有過濾信賴區間

>>記得更新github上程式碼
>>[color=red][name=課程助教]