# 2016q3 Homework1 (phonebook)
contributed by <`yenWu`>
這次的目標會放在減少 append()時間 和 挑戰題 還有修改 hash function
Code Review: [Mar 8, 2016](https://embedded2016.hackpad.com/Mar-8-2016--kpfgwU6YgOF)
## 開發環境
* 作業系統： Ubuntu 14.04 LTS （64 bit）
* CPU：4-core 2.16 GHz
* Memory：4G
* Cache：
* L1 data : 24kB
* L1 instruction : 32kB
* L2 : 1024kB
使用 `lscpu` 和 `sudo lshw` 可看到硬體資訊
## 學習使用 Github
先前按照老師給的作業指示跟著操作，這次有稍微閱讀一下相關資訊，並且嘗試看看強大的回復功能，和了解一下add的真正意義
* `git init` 建立目錄 `.git`
* `git status` 確認現在所有檔案的狀況
* `git add 檔名` 追蹤此檔案
* `git commit` 確認檔案並snapshot（有點像暫時存檔）
* `git remote add <nickname> <repository-URL>` 連結遠端的repository並給他取代稱
* `git push <nickname>` 把檔案上傳到指定的repository
大概對git的原理和用法有比較基本的認識，但尚未看到branch那邊（有先看fork）
之後會補上SSH的過程(之前都先做完了，沒紀錄到 = =)
## Vim設定
自己寫入設定檔
```
$ vim ~/.vimrc`
```
* vimrc means Run Commands
參考資料：
* [vim設定L::檔](http://note.drx.tw/2008/01/vimrc-config.html)
* [鳥哥vim指令](http://linux.vbird.org/linux_basic/0310vi.php)
## astyle 和 pre-commit hook
~~我使用我自己比較偏愛的astyle格式~~
```shell
$astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch]
```
~~在 pre-commit hook 我卻沒有成功，我有給 hook/ 底下一個soft link，但我在 commit 時卻沒有偵測我亂寫的格式~~
>> 考慮到團隊合作，請配合原本的指示，使用一致的 coding style [name=jserv]
>> 我已經做了修改了。[name=彥寬]
這邊要說明一下 pre-commit，這邊我搞錯了一件事，就是 softlink 會以 source 會以 target的所在目錄當作相對位置的起點，其實只要 `ll`你就會發現，softlink 顯示就是這樣，所以要去看target的link。
`ln -sf ../../scripts/pre-commit.hook .git/hooks/pre-commit`
## 效能分析工具 Perf
* `echo -1 > /proc/sys/kernel/perf_event_paranoid`
* `$ ./yourapp & sudo perf top -p $!` 這可以省略寫sleep()再開令一個終端機輸入pid
## Makefile 語法
當只有輸入make時只會進行第一個target，但要執行target前，必須先有後面的相依檔案，如果找不到就會再往下面的target找，把所有相依檔按找完才會執行下面的commond，首先先註記一些較少用到的gcc用法
* 不是依序！應該說每個 target 被 satisfied 後，就會執行指定命令，若回傳值非 0 就會失敗
* gcc後面可以加上:
* `-E` : 只進行前處理，不進行編譯，結果由 console 直接輸出
* `-C` : 進行前處理時保留註解
* `-S` : 產生組合語言程式碼 (.s)
* `-c` : 只編譯不進行連結 (產生 .o 檔)
* `-I` : 指定 INCLUDE PATH
* `-L` : 指定 LIBRARY PATH
* `-llibrar`y -- 指定要連結的函式庫
* `-Dname` : 定義 macro，同 #define
* `-Uname` : 解除 macro 定義，同 #undef
參考資料:
* [GCC](http://www.cmlab.csie.ntu.edu.tw/~daniel/linux/gcc.html)
注意: GCC 是 compiler driver
Makefile 裡頭使用 gcc 的示範:
```shell
CC = gcc
INC = -I ./include
OBJ = main.o op.o
test: ${OBJ}
$(CC) -o $@ ${OBJ}%.o: %.c
${CC} $< ${INC} -c
.PHONY: clean
clean:
rm -f test ${OBJ}
```
* Makefile 基本語法
```shell
目標檔案 (Target)： 相依檔案 (Prerequisites)
指令 (Commond)
```
比方說:
```shell
test: main.c op.c
gcc main.c op.c -o test
```
其中
* `CC=gcc` 變數asign
* `${CC}` 取出CC裏面存放的值
* `%.o : %.c` 這是像C++的Template的用法，指令要尋找main.o時，%.o = main.o %.c = main.c
* `$@` = Target
* `$<` = First Dependent File
參考資料：
* [Makefile簡易教學](http://jayextmemo.blogspot.tw/2015/01/linux-gcc-makefile-2.html)
## Gnuplot
這邊我用老師提供的 runtime.gp 當學習範例:
```shell
reset # 這是清除前面的設定
set ylabel 'time(sec)' # 將y軸的label寫上 'time(sec)'
set style fill solid
set title 'perfomance comparison' # 設定 title name
set term png enhanced font 'Verdana,10' # 設定 png 為輸出格式
set output 'runtime.png' # 設定output file name
plot [:][:0.150]'output.txt' using 2:xtic(1) with histogram title ’original’, \
using ($0-0.06):($2+0.001):2 with labels title ' ', \
using 3:xtic(1) with histogram title 'optimized', \
using ($0+0.3):($3+0.0015):3 with labels title ' '
```
最近想要再使用時發生這個問題，進入gnuplot 時畫不出 sin(x) (我想要直接顯示在螢幕)，然後看到 terminal type set to ’unknown’，經過查詢得知是抓不到連結，所以方法之一就是更新gnuplot到version 11
參考資料
* [gnuplot安装，及error:terminal type set to 'unknown'的解决](http://blog.csdn.net/deng529828/article/details/24325787)
* [Solution: GNUPlot in Ubuntu - Terminal type set to 'unknown'
](http://lordamit.blogspot.tw/2012/12/solution-gnuplot-in-ubuntu-terminal.html)
* [gnuplot教學](http://gtchen.pixnet.net/blog/post/5873441-gnuplot-(part-i))
## 案例分析：Phonebook
### 未優化版本
`$ make run`
```
size of entry : 136 bytes
execution time of append() : 0.127555 sec
execution time of findName() : 0.015991 sec
```
`$perf stat --repeat 5 -e cycles,instructions,cache-references,cache-misses,branch-instructions,branch-misses ./phonebook_orig`
* 
```
Performance counter stats for ’./phonebook_orig’ (5 runs):
447,819,700 cycles ( +- 1.62% ) [34.16%]
273,082,321 instructions # 0.61 insns per cycle ( +- 0.75% ) [51.33%]
11,489,866 cache-references ( +- 0.81% ) [52.31%]
3,459,780 cache-misses # 30.112 % of all cache refs ( +- 1.59% ) [50.76%]
48,161,780 branch-instructions ( +- 0.58% ) [32.11%]
5,558,063 branch-misses # 11.54% of all branches ( +- 0.71% ) [32.97%]
0.182893634 seconds time elapsed ( +- 0.92% )
```
* `$perf stat -r 10 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-store-misses,L1-dcache-prefetch-misses,L1-icache-load-misses ./phonebook_orig`
```
Performance counter stats for ’./phonebook_orig’ (10 runs):
3,508,579 cache-misses # 29.720 % of all cache refs ( +- 0.25% ) [49.65%]
11,805,580 cache-references ( +- 0.74% ) [51.67%]
1,347,036 L1-dcache-load-misses ( +- 0.69% ) [50.75%]
<not supported> L1-dcache-store-misses
<not supported> L1-dcache-prefetch-misses
419,659 L1-icache-load-misses ( +- 3.05% ) [48.73%]
0.186848163 seconds time elapsed ( +- 0.60% )
```
### 優化版本:
#### 減少 entry 空間
* 因為搜尋電話簿時，沒必要先把他的資料全部讀到 cache 裡，只需要讀 `lastName` 就好，所以我就把詳細資料跟 `lastName` 分離開來找 。其中 `append()` 和 `findName()` 直接複製orig的
* `phonebook_opt.h`
```C
typedef struct phonebooK_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;
```
* 第二次寫我居然犯了一個笨點，就是直接放detail的 struct 而不是 pointer 難怪結果怪怪的，更新新的圖表，結果也差不多
* 
<s>時間上都有減少，但是append不應該減少才對，我猜想是我再append是貼原本code所以他只會malloc entry的空間，但沒有malloc detail的空間</s>
* 我還沒看完老師的範例就先做了，後來有看到不需要malloc的原因
* 並且發現我並沒有真正看懂題目的意思，append是要建立一個dictionary所以我並不需先malloc
附上detail 也malloc後的圖，結果是append()增高,且findname()也因為這樣而升高了
* 將原本一個的 malloc變成兩個，會對系統造成負擔
<s></s>
這次去 dictionary 看，發現搜的字根本不在，本來有再考慮要用 多個東西一起搜讓搜尋更有保有區域性，看來接下來的方法應該要朝分類進行。
## 降低 append() 時間開銷：延後fgets完newline的替換 + 延後補上 detail
利用 fgets的特性，man 完就會發現它會在讀到 newline 或是 EOF停下來並且在他們後面會多種一個 `'\0'`，接著的 code 就是把 newline 變成 `'\0'`，我們延後替換 newline，我操作只比較前面的長度，真的找到了再把 newline 換掉即可。
* `main.c`
```C
while (fgets(line, sizeof(line), fp))
e = append(line, e);
```
* `phonebook_opt.c`
```C
/* because the assert test, we can’t modify the strcut*/
if (strncasecmp(lastname, pHead->lastName, len) == 0 &&
(pHead->lastName[len] == ’\n’ ||
pHead->lastName[len] == ’\0’)) {
pHead->lastName[len] = ’\0’;
return pHead;
```
原本的程式是將字典直接建好，這邊我們先建檢索，等到findName找到時我們再去補上他的資料，這樣也能減少 append()。
* 這邊紀錄一下一個 bug `strcpy-sse2-unaligned.S not found` 這只有在 gdb 時會看到，簡單來說就是 strcpy很像有問題，而外面就是直接 core dump，而這個問題即是我的 assert 沒考慮清楚，順帶一提 assert並沒辦法做到即時回傳，因為我的 bug 是出在 assert裏面的 function 所以他會直接 core dump 而不會等到你 assert，簡單說就是我忘了我已經我已經替換了 newline 所以我第二次 call findname 就找不到結果了。
>> 我們應該使用 backtrace 來對付這個，因為他沒有指名是哪個 str出問題。(gdb) [name=彥寬]
## Multi-thread version
~~不說了，悲劇，append大概 0.36 ...~~
這邊我使用mutithread在append上
## mmap() preload file to memory space
thread 1:
but thread 4 ...:
...thread 8 ...:
>> I notice that more thread and more append() time shake.[name=Yen-Kuan Wu]
>> findName() time will decrease because we use the cross append(), and the benchmark only measure the time we find `zyxel`. [name=Yen-Kuan Wu]
* ==終於找到原因了，原因就是 muti-thread 上使用了 malloc()，由於 malloc system call，所以是根本無法平行化的地方。==
# 使用 "Pthread" + "file alignment" + "mmap" + "簡易 memory pool" + 檢索省略尋找 \`\n\`
thread 1:
thread 2:
thread 4:
thread 8:
thread 16:
* 這邊很清楚的看出來，太多 thread 會變慢沒問題，但奇怪的是 1 2 4的差別卻不大，我也開啟我自己設定的 debug 模式，發現大加搜尋的數目都是正確的，但問題出在我是使用 sync 的方式，所以假如有一個thread跑比較慢，那總體時間也就會比較慢。
* ### 檢索省略尋找 \`\n\`
這就是我上 `降低 append() 時間開銷：延後fgets完newline的替換 + 延後補上 detail`的作法
## Pthread用法
這邊很單純的，我是打算讓大家先各自串一個 link list 之後我再把他連起來，但一開始成效真的是讓人吐血...，經過老師指點，我知道了 fgets 是一個 blocking IO所以就算我開再多 thread，也只是白搭，老師提示我可以用 mmap()。
## mmap() + file alignment
首先想要使用 mmap的動機就是 fgets這個 blocking IO，讓程式更可以平行化，但是由於我們不知道每個字元的 offset，所以我先將 file整理成 16 char alignment，之後再使用 mmap()，就能夠直接 offset 16到下一個 word了。
## 簡易 memory pool
做完面的東西後，發現效能還是沒有多好，而且跟 thread 的使用量不成正比，找了很久很久...，之後才發現是 malloc()再搞鬼，因為 malloc 也屬於 system call，所以他也是無法平行化的東西，所以我們再使用了簡易的memory pool。
為什麼講簡易呢？ 因為我就直接 malloc 開linklist 會用到的總空間，然後交叉串聯，當然這不是正統的方式，老師有貼給我正確的 memory pool 用法，他將會是我下一個改善的目標。
## 改善空間
說白了就是 ansyc，由於我是使用 sync的方式，所以 join 一定要等慢的那位，造成我 4 個thread 只要有一個太慢就會拖累總體時間。
## 使用 Hash function
**Hash 42737 bucket**
Hash bucket 我使用老師例子裡的 42737 當作第一次測試，而結果不如預期，append() time 太高了，而我也試圖去找一下問題
>「程式輸出的文字訊息」請勿使用圖片表示，請改由文字貼上[name=課程助教]
>不好意思這是從我的 Hackpad貼過來的，年代久遠= =，我記得老師也有提醒過我，我不會再犯的，感謝。[name=彥寬]
* `./phonebook_opt & sudo perf top -p $!`
* 我找到了是在這邊，也就是太多碰撞，可能要調整bucket的大小或者直接紀錄最尾巴
```c
{
while( ep->pNext != NULL) {
ep = ep->pNext;
}
```
新增 pLast 減少找尾巴時間
* `hash_bucket`
```c
typedef struct _hash_bucket {
entry *pNext;
entry *pLast;
} hash_bucket;
```
```
Execution time
size of entry : 32 bytes
execution time of append() : 0.168732 sec
execution time of findName() : 0.000003 sec
```
* 還需要繼續改進:
* `hash function` 時間過長，要改進
* `append()`
寫到一半有bug，嘗試使用了gdb
```shell
$ gdb ./phonebook.opt
```
就會進入gdb的shell，之後再輸入b(breaking)再來輸入run就能看到我的memory dump掛在那一個function
```shell
(gdb) b
(gdb) run
```
[ntu gdb 筆記](http://www.cmlab.csie.ntu.edu.tw/~daniel/linux/gdb.html)
---
man index 有這個func
###### tags: `yenWu` `phonebook` `sysprog21`
Sign in with Wallet
Connect another wallet