# 2017q3 Homework1 (phonebook)
contributed by < `vasv75182366` >

## 開發環境
$uname -a
Linux uscca22-Aspire-M5810 4.4.0-96-generic #119-Ubuntu SMP Tue Sep 12 14:59:54 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux

$lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 16.04.3 LTS
Release: 16.04
Codename: xenial

$lscpu
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
每核心執行緒數：2
每通訊端核心數：4
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 30
Model name: Intel(R) Core(TM) i7 CPU 860 @ 2.80GHz
製程： 5
CPU MHz： 1200.000
CPU max MHz: 2801.0000
CPU min MHz: 1200.0000
BogoMIPS: 5586.03
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 8192K
NUMA node0 CPU(s): 0-7
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf pni dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm sse4_1 sse4_2 popcnt lahf_lm tpr_shadow vnmi flexpriority ept vpid dtherm ida

$free
total used free shared buff/cache available
Mem: 16423308 2705868 13140196 102348 577244 13297076
置換： 999420 0 999420

## Linux 效能分析工具: Perf

照著[perf 原理和實務](https://hackmd.io/s/HJJUmdXsZ)的步驟練習指令

* 偵測這個 process 每個指令所耗費的 CPU cycle，可按下 `a` 進一部做分析。
`$ perf top -p $pid`
* 列出可偵測的event。
`$ perf list`
* 針對 binary檔重複執行 n 次，偵測指定的event，在這個作業中主要需要顯示`cache-misses`、`cache-references`、`instructions`、`cycles`這四個 event。
`$ perf stat --repeat <num> -e <event> <bin>`

## 案例探討：電話簿搜尋

按照步驟先 clone 專案再執行 `make` 編譯

執行`make run`後的輸出：

size of entry : 136 bytes
execution time of append() : 0.068812 sec
execution time of findName() : 0.005673 sec
3

### 閱讀程式碼
觀察主程式流程：
`紀錄 append 起始時間`→`讀取資料並 append 建 Singly Linked List`→`紀錄 append 結束時間`→`紀錄 findName 起始時間`→`紀錄 findName 結束時間`→`釋放記憶體`

在 append 以及 findName 是要進行優化的地方，注意到在程式最後沒有妥善釋放記憶體：

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

先對 main.c 根據 phonebook_orig.h 的資料結構做修改：

    entry *tmp;
    while (pHead->pNext) {
        tmp = pHead->pNext;
        free(pHead);
        pHead = tmp;
    }
    free(pHead);

執行

$ make cache-test

查看未優化過的 cache-misses：

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

1,349,155 cache-misses # 93.717 % of all cache refs ( +- 0.10% )
1,439,606 cache-references ( +- 0.14% )
326,375,105 instructions # 1.18 insns per cycle ( +- 0.01% )
277,271,600 cycles ( +- 0.11% )

0.090609402 seconds time elapsed ( +- 0.33% )

### 優化
#### 修改 Makefile
參考 [HMKR](https://hackmd.io/s/HyyHC6moW) 的共筆修改 Makefile 內的 cache-test 讓資料更新

#### **修改資料結構 ( Data Structure )**
* 減少 entry 大小
由於僅須查找 lastName，所以只保留 lastName 以及 pNext 在 entry 內，並且另外建立一個資料結構紀錄其他資訊，使 entry size 從 136 bytes 變成 32 bytes

    typedef struct __PHONE_BOOK_DETAIL {
        char firstName[16];
        char email[16];
        char phone[10];
        char cell[10];
        char addr1[16];
        char addr2[16];
        char city[16];
        char state[2];
        char zip[5];

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

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

334,623 cache-misses # 79.267 % of all cache refs ( +- 0.41% )
422,146 cache-references ( +- 1.21% )
287,704,114 instructions # 1.45 insns per cycle ( +- 0.01% )
197,902,294 cycles ( +- 0.50% )

0.067796114 seconds time elapsed ( +- 0.72% )

降低 entry 的大小可以使 cache 內存放更多筆 entry 降低 cache-misses


#### **利用雜湊表加速搜尋 ( Hash Table )**

根據前面已修改過的資料結構增加 Hash Table 的查詢功能，另外新增了兩個檔案 `phonebook_hash.c` 、 `phonebook_hash.h` ， findName 以及 append 兩個函式都沒有做變動，僅增加運算雜湊值的函式：

**BKRD Hash**

unsigned int BKDRHash(char *str)
{

    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
    while (*str) {
        hash = hash * seed + (*str++);
    }
    return (hash & 0x7FFFFFFF) % HASH_TABLE_SIZE;
}

以及

`#define HASH 1`

用來在 `main.c` 內根據 `#ifdef HASH` 來做差別運算
修改 `Makefile` 、 `calculate.c` 、 `runtime.png` 以新增 hash 過後的數據進行比較

以下是使用 hash table size 為 1024 的 BKDRHash 結果

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

899,631 cache-misses # 60.016 % of all cache refs ( +- 0.31% )
1,498,980 cache-references ( +- 0.30% )
319,910,641 instructions # 1.05 insns per cycle ( +- 0.01% )
306,092,376 cycles ( +- 0.16% )

0.102225082 seconds time elapsed ( +- 0.46% )

Cache miss 明顯從 80% 下降至 60%


在 append 所需的時間由於要進行 hash 明顯上升，但是在 findName 的時間明顯可以透過查表大幅下降

## 回答問題
* 有代表性嗎？跟真實英文姓氏差異大嗎？
* 根據 `dictionary/words.txt` 內的資料來看，看起來並不太具有代表性，因為其中包含了如 `zzzzzz`、`zzz`之類的非英文姓氏的單字，並且在真實生活中名字會因各種情況而有其他差異，例如：部份名字較為熱門常見、根據地區或可能有所不同。
* 資料難道「數大就是美」嗎？
* 資料如果沒有辦法被分析成有用的資訊，甚至化為知識、成就智慧，對大部分的人而言就只是霸佔儲存空間，或許對於樂於挑戰將之化為有用的資訊的人才是美吧。
* 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
* 需有新增、查詢、修改、刪除功能
* 每一筆資料的完整度並不一定，資料結構上需要再做修改
* 實際電話簿是一筆龐大資料，虛有足夠儲存空間並配合如 hadoop 之類的分散式運算。