# 2018q1 Homework1 (phonebook)
contributed by < `BodomMoon` >
###### tags `BodomMoon` `phonebook` `sysprog2018`
[github](https://github.com/bodommoon/phonebook)、 [作業區](https://hackmd.io/s/SJONH8fuz)、 [作業要求](https://hackmd.io/s/SykZ8IMOf)
### Reviewed by `AliennCheng`
* 首先我特別敬佩你的精神，這篇共筆寫得有夠詳細 XD，那個嚇到吃手手我還真的沒去實測過
* 繕打文章時，若遇到中英文交界可以用空白鍵分開，會比較容易閱讀
* **TODO** 的部分如果已經完成可以清除
* 我看了你的程式碼，好像有滿多功能都寫在 main function 裡，讓整個 main 落落長，這樣可能導致 debug 及 code review 甚至未來要新增移除功能等等的困難
* 霍夫曼編碼壓縮字串之後實作在這次 phonebook 裡的成效如何呢?
* 關於 GCC Branch Pattern 那篇文章，你提出問題的那段我大概翻譯一下，但我也對 GCC 不太熟，若有其他高手發現有誤麻煩更正><
* GCC 預設的靜態預測 (static prediction) 是可以被內建函式 (builtin function) 更動的，操作細節我就不贅述，他的結論 (也就是你看不太懂那段) 是：
* 避免使用這個內建的函式去改變 GCC 的預測行為，而是採用自己修改程式碼順序的方式。
* 如果一定要用，則必須符合「原本是動態預測，改變成靜態預測」及「已經分析過資料，確保資料在掌控之中」的條件下，才可以叫用這個內建的 ==__builtin_expect==
* 關於分支預測可以參考這篇 [CPU 的分支預測器是怎樣工作的？](https://www.zhihu.com/question/23973128)
> BodomMoon:感謝指教及補充，翻譯的部份已經更新上去，至於霍夫曼樹我正在種，種好了就會第一時間更新上去。
至於 Main function 的確被我塞的落落長，我們偉大的信仰中心 jserv 有指示我改成用 function pointer包裝起來，等待良辰吉時我會就會試著去優化的。 ->2018/03/22
更新：霍夫曼樹種好了請慢用。 ->2018/03/24
----
部份格式參照自 `ryanpatiency`的文件，因為看了一下覺得這位同學的最為豐富及清楚
## 內容大綱
* 安裝流程筆記
* 對於GCC編譯機制的程式編寫優化測試
* 參數設置補充
* 解題思考方向
* 開發環境
* 重構struct
* 引入Hash
* 試作HashTable + Binary Search Tree
* 試用霍夫曼編碼壓縮字串
* 編譯器O2優化催下去之後的神奇改變
* 作業本身設計的問題思考
* Makefile之CFLAG設定
* Git分支控制紀錄
## 安裝流程筆記
有鑑於我從寒假就開始看了本課程的一些相關要求，其中在上一學期的課程中提到
* 安裝 GNU/Linux，建議安裝 [Lubuntu](http://lubuntu.net/) 16.10 (注意: 應安裝 64-bit 版本)
我就傻傻的開工了，其中遇到EOL更新到EOL版本的問題，這個問題在網路上似乎非常少見故在此紀錄一下：
`https://askubuntu.com/questions/999360/how-can-i-upgrade-my-eol-16-10-to-any-new-version/999371`
這是我在網路上找到唯一一個討論有關EOL to EOL升級的討論串
ubuntu16.10是已經結束支援的版本，結束支援之後的版本在apt相關指令中所參照到的repository會被關閉，必須手動修改為`/etc/apt/sources.list`中的`archive.ubuntu.com` 和 `security.ubuntu.com` 為 `old-releases.ubuntu.com`
但是`old-releases.ubuntu.com`中的package並不齊全更新也很慢，因此在apt install時會有大量的套件無法安裝。針對此問題的解決方法有兩種
**1.把Lubuntu版本更新上去**
```
$ sudo apt-get update
$ sudo apt-get install
$ update-manager-core
$ sudo do-release-upgrade
```
理論上只要這樣做就可以更新版本了。
But！Ubuntu only supports upgrading from LTS (long term support) to LTS, or from one intermediate version to the next.
所以如果你的Lubuntu版本的下一個版本也EOL了又不是(LTS版本)就無語問蒼天了，因為ubuntu規定系統之間只能階梯式升級，而我安裝的16.10下一個版本17.04也已經EOL，我沒辦法從一個已經EOL的版本升級到另外一個也已經EOL版本。
**2.把連接的soure.list竄改成最新的版本(不穩定的作法)**
直接把source.list中
`http://security.ubuntu.com/ubuntu "artful"-security main restricted`
版本號的部份改成最新的
`http://security.ubuntu.com/ubuntu "新的版本名稱"-security main restricted`
然後就可以正常apt安裝軟體了
But！有鑑於當時我裝
ubuntu16.10是gnome的桌面系統（EOL）
ubuntu17.04是unity的桌面系統（EOL）
ubuntu17.10是gnome的桌面系統
當我apt-update的時候等於是直接抓17.04->17.10的軟體更新安裝在16.04上
然後我的桌面系統就整個炸了，所以這並不是一個好的解決方式，最好的解決方式依然是：
* 永遠先檢查你安裝的版本是否EOL(End of Life)
## 對於GCC編譯機制的程式編寫優化
[Branch Patterns, Using GCC](http://cellperformance.beyond3d.com/articles/2006/04/branch-patterns-using-gcc.html)
非常優質的文章一篇，在運算控制的說明上非常淺顯易懂並且符合事實，解決了很多我一直以來都有的到底該用哪種運算子做決策的疑問。以下節錄我整理的重點及實驗
1. 隨著科技的發展對於branch 控制的優化日漸重要
Intel Pentium4有31個pipeline，故對於Branch預測錯誤時發生的功能耗損也更加嚴重
2. 盡量減少Branch的可能性，不使用if之類會造成Branch的寫法
複雜的程式不可能沒有Branch，但我們可以減少Branch 如[Programe smell](https://hackmd.io/s/SkfffA-jZ#)所寫到原本涉及到Branch的陳述:
`if (b < 0) a++;`
可更換為沒有Branch的版本:
`a -= b >> 31;`
進階一點的
```=c
if (data[c] >= 128)
sum += data[c];
```
也可以更改成
```=c
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
//This is really beautiful
//p.s:This isn't equal to unsigned!!!
```
3. 永遠把比較可能的程式放在then讓行程在執行時可以直接進行下一個讀到fetch的指令
這部份的原理請參照Instruction pipeline的設計，這是計算機概論的課程範圍
3. 將條件式放在最後是更好的 可以省下第一次的branch so change while and for to -> do while
測試程式如下
```c=
#define N 5000000
//這是For的版本
static int array[N] = { 0 };
void normal_loop(int a) {
int i;
for (i = 0; i < N; i++)
array[i] = array[i]+a;
}
void unroll_loop(int a) {
int i;
for (i = 0; i < N; i+=5){
array[i] = array[i]+1;
array[i+1] = array[i+1]+a;
array[i+2] = array[i+2]+a;
array[i+3] = array[i+3]+a;
array[i+4] = array[i+4]+a;
}
}
int main() {
normal_loop(1);
unroll_loop(1);
return 0;
}
```
對照組
```c=
#define N 5000000
//這是do-while的版本
static int array[N] = { 0 };
void normal_loop(int a) {
int i = 0;
do
{
array[i] = array[i]+a;
i++;
} while ( i < N );
}
void unroll_loop(int a) {
int i =0;
do{
array[i] = array[i]+1;
array[i+1] = array[i+1]+a;
array[i+2] = array[i+2]+a;
array[i+3] = array[i+3]+a;
array[i+4] = array[i+4]+a;
i+= 5;
} while ( i < N );
}
int main() {
normal_loop(1);
unroll_loop(1);
return 0;
}
```
編譯出來的組合語言差別如下（在normal_loop這個函式的部份）代碼透過gcc -s -o生成
```
normal_loop:
.LFB0:
...
jmp .L2
.L3:
...
.L2:
...
jle .L3
```
```
normal_loop:
.LFB0:
...
.L2:
...
jle .L2
```
可以明顯看見do-while的版本少了一個Banch
並運用perf stat對照其指令數
```
163,693,784 instructions # 1.40 insn per cycle ( +- 0.01% ) for的版本
V.S
163,663,630 instructions # 1.48 insn per cycle ( +- 0.01% ) do_while的版本
```
4. 在高效能的程式中Switch的使用需要特別留意
總結如下(在gcc version 7.2.0實測證實)
五個以下的case->改寫為if-else並將發生機率從大排到小，時間複雜度為O(n)
五個以上的case(不跳號)->
用switch撰寫後編譯器會自動編譯為JumpTable，時間複雜度為O(1)
五個以上的case(跳號)->
用switch撰寫後編譯器會用binary Search來尋找並跳轉，時間複雜度為O(logn)
故在撰寫switch時請盡量避免跳號的情形，讓我們聰明的編譯器自動幫我們建表並且跳轉
5. Don't use the __builtin_expect extension to change GCC's default branch prediction, rearrange your code instead. Only use this extension to convert what would have been dynamically predicted branches to statically predicted ones, and only where the data has been analyzed and the predicability is well-known in advance.
~~這段太高深了其實看不太懂~~
* GCC 預設的靜態預測 (static prediction) 是可以被內建函式 (builtin function) 更動的，操作細節我就不贅述，他的結論 (也就是你看不太懂那段) 是：
* 避免使用這個內建的函式去改變 GCC 的預測行為，而是採用自己修改程式碼順序的方式。
* 如果一定要用，則必須符合「原本是動態預測，改變成靜態預測」及「已經分析過資料，確保資料在掌控之中」的條件下，才可以叫用這個內建的 ==__builtin_expect==去修改
* 關於分支預測可以參考這篇 [CPU 的分支預測器是怎樣工作的？](https://www.zhihu.com/question/23973128)
>特別感謝 AliennCheng 補充翻譯
6. 避免複雜的布林運算，過於複雜的布林運算會將規則隱藏起來，造成branch predict難以預測結果
7. 當事件發生的可能性不均勻的時候，用and來運算並且從最可能發生->最不可能發生來排序
8. 當發生的可能性相對均勻的時候，用or來運算並且從排序的順序不太重要
9. 位元運算比邏輯運算更讚
因為位元運算不會創造branch的分支可能性
## 參數設置補充
在[perf 原理和實務](https://hackmd.io/s/B11109rdg)中有提到
perf_event_paranoid一共有四種權限值:
- `2` : 不允許任何量測。但部份用來查看或分析已存在的紀錄的指令仍可使用，如 perf ls、perf report、perf timechart、 perf trace。
- `1` : 不允許 CPU events data。但可以使用 perf stat、perf record 並取得 Kernel profiling data。
- `0` : 不允許 raw tracepoint access。但可以使用 perf stat、perf record 並取得 CPU events data。
- `-1`: 權限全開。
**但其實不只這四種!**，在[LWN.NET](https://lwn.net/Articles/696216/)中提到
```
Jeff Vander Stoep posted the patch on July 27. It adds a another value that
can be set for the sysctl parameter (i.e. kernel.perf_event_paranoid=3) that
restricts perf_event_open() to processes with the CAP_SYS_ADMIN capability.
Currently, perf_event_paranoid is set to 2 by default, which disallows
access to some perf features (raw tracepoint access, CPU event access, and
kernel profiling) to processes without the proper capabilities; the patch
does not change the default. He also submitted another patch that would
allow configuring the kernel to make 3 be the default perf_event_paranoid value.
```
他提到過去權限預設為2時會限制perf_event_open()處理[CAP_SYS_ADMIN](https://lwn.net/Articles/486306/)(分割後的部份root特權)的能力這導致部份perf的功能(raw tracepoint access, CPU event access, and kernel profiling)無法取得適當的執行權限，他並沒有更改2這個值的權限設定而是提交了一個新的補丁並將新的預設權限值設為3。
所以我的lubuntu17.10預設就是3。
此外這篇報導下面還有其他人在跟他互嗆說設為2禁用perf就是因為perf有漏洞會造成被攻擊的風險，他回嘴說perf很重要而且你說的問題兩年多了都沒事blublu之類的，感覺似乎還有挺趣的。
## 解題思考方向
~~在討論這一段之前我不知道有影片可以看~~
我：欸欸Phone book這題你看了有什想法嗎？
同學A:最簡單就塞Heap array來做吧。
我：50萬筆你塞個頭array喔，而且是字串耶，我目前想到的只有在cache中塞滿hash table後面再用BST串起來。
同學A：你知道BST如何存字串？
我：我看之前的同學有用byte-by-byte comparsion的方法下去存，應該可以試試看。
(參考自`ryanwang522`[2017q1 Homework1 (phonebook)](https://hackmd.io/s/Sk-qaWiYl#))
同學A：那你知道2-3 tree AVL tree或是紅黑樹嗎？
我：不知道。
同學A：那些挺難的你先試試BST吧。
## 開發環境
```
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數： 2
每通訊端核心數： 2
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 60
Model name: Intel(R) Core(TM) i5-4200M CPU @ 2.50GHz
製程： 3
CPU MHz： 2494.221
CPU max MHz: 3100.0000
CPU min MHz: 800.0000
BogoMIPS: 4988.44
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
```
## 重構struct
```=c
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
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];
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
```
原始的struct長這樣，可以發現光一個就佔了136KB。
但我們findName根本只會找lastName阿，故可知剩下多的根本是都白塞到cache的。為了解決這個問題另外新增一個struct來塞
```=c
typedef struct __PHONE_BOOK_DETAIL_ENTRY {
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];
struct __PHONE_BOOK_ENTRY *pNext;
detail *pDetail;
} entry;
```
## 引入hash function
~~對於資料結構混過去的人來說我是生平第一次認真用hash function~~
看完作業區的介紹之後[哈希函数BKDR的解析- CSDN博客](http://blog.csdn.net/MBuger/article/details/61663097)跟風使用BKDR
首先寫出
```=c
unsigned int BKDRHash(char *cPtr)
{
unsigned int seed = 31;
unsigned int hash = 0;
while(*cPtr)
hash = hash * seed + (*cPtr++);
return (hash % MAX_TABLE_SIZE);
}
```
看到hash % MAX_TABLE_SIZE有沒有覺得很熟悉？想起考試中的
`給定B為2的N次方，則 A%B=A&(B-1)成立`
馬上應用上去
```
return (hash ＆ (MAX_TABLE_SIZ-1));
```
然後再想起[Branch Patterns, Using GCC](http://cellperformance.beyond3d.com/articles/2006/04/branch-patterns-using-gcc.html)說為了減少Branch我們應該用do-while取代while
``` =c
do
hash = hash * seed + (*cPtr++);
while(*cPtr != '\0');
```
接著看到文章中提到
```
為何seed使用31？
因為在使用bkdrhash时你会发现里面大多源码使用的都是特殊的奇数2^n-1，那是因为在CPU的运算中移位和减法比较快。
```
But 在 `hash = hash * 31 + (*cPtr++)`的情況下難道神奇的GCC會自動把*31改成`hash = hash<<5 - hash + (*cPtr++)`這樣嗎？
實測一下
```=c
int main()
{
int a = 3;
int b = a*31;
}
```
```
$ gcc -S -O0 muti_test.c -o muti_test.s
main:
.LFB0:
...
sall $5, %eax
subl %edx, %eax
```
(在gcc version 7.2.0實測)
哇靠！gcc你也太機智了吧。
接著修改main那邊append的機制來對應hashtable
```=c
do {
line[strlen(line) -1] = '\0'; //change while loop to strlen
unsigned int hashValue = BKDRhash(line);
hashTable[hashValue] = append(line, hashTable[hashValue]);
} while (fgets(line, sizeof(line), fp));
}
append(line , hashTable[hashValue]);
}
```
這樣建構hashTable的部份就差不多了，剩下修改一下呼叫findName的輸入參數部份
```=c
char input[MAX_LAST_NAME_SIZE] = "zyxel";
e = tableHead[BKDRhash(input)];
```
最後改一下free的部份讓程式在結束時釋放整個table
```=c
counter = 0;
do {
free(tableHead[counter] -> pNext);
free(tableHead[(counter++)] );
} while (counter < MAX_TABLE_SIZE);
```
最終配上大量[Branch Patterns, Using GCC](http://cellperformance.beyond3d.com/articles/2006/04/branch-patterns-using-gcc.html)中所提到的優化(ex.所有的while 跟 for 我都改寫成do-while了)
```
Performance counter stats for './phonebook_orig' (100 runs):
1,178,051 cache-misses # 80.781 % of all cache refs ( +- 0.97% )
1,458,320 cache-references ( +- 0.61% )
261,427,986 instructions # 1.20 insn per cycle ( +- 0.02% )
217,243,310 cycles ( +- 1.42% )
0.074059248 seconds time elapsed ( +- 1.86% )
Performance counter stats for './phonebook_opt' (100 runs):
130,280 cache-misses # 20.212 % of all cache refs ( +- 4.07% )
644,575 cache-references ( +- 1.55% )
229,190,247 instructions # 1.37 insn per cycle ( +- 0.03% )
166,934,060 cycles ( +- 2.47% )
0.059234874 seconds time elapsed ( +- 3.28% )
```
喔！ cache-misses 20.212 %耶！
不過這個是很浮動的數字 大概19~26%之間都有可能
此外1.37的insn per cycle也比原版漂亮，經過優化的指令branch miss的機會更低執行更有效率
要是在多作弊一點就可以調出
(拔free 把測資改成word.txt中的第一個aaaa 然後只測五次XD)
```
Performance counter stats for './phonebook_opt' (5 runs):
78,782 cache-misses # 13.189 % of all cache refs ( +- 1.46% )
597,331 cache-references ( +- 5.25% )
229,049,447 instructions # 1.71 insn per cycle ( +- 0.00% )
134,007,014 cycles ( +- 1.58% )
0.044590878 seconds time elapsed ( +- 1.53% )
```
突破天際的cache-references 13.189% ~ 不過當然這個不能當作參考啦...
最後附上一些針對gcc優化的範例
```=c
//把可能性較高的放在then
fp = fopen(DICT_FILE, "r");
if (fp != NULL) {
/*
fopen successful, continue execution.
*/
}else {
printf("cannot open the file\n");
return -1;
}
```
```=c
//while轉do-while並把then放可能性比較高的
entry *findName(char lastName[], entry *pHead)
{
do {
if (strcasecmp(lastName, pHead->lastName) != 0)
pHead = pHead->pNext;
else
return pHead;
} while (pHead != NULL);
return NULL;
}
```
## 試作HashTable + Binary Search Tree
~~有鑑於BST建構時需要大量的if作branch控制，而且每個hashTable內的Tree都是從頭開始一個一個建到底，反而讓建構的效率大幅下降~~ 因為words.txt內是用字典順序排好的，所以在建構BST時用 strcasecmp 會導致單向排列，而且由於hashTable內的碰撞元素每格平均只有86個，故提昇的效益並不是特別明顯`(950 clock->706 clock)`，至於較有效率的建構二元樹方法請參考[ryanwang522](https://hackmd.io/s/Sk-qaWiYl)同學的筆記
`利用輸入的linked list排序好的特性直接折成AVL-Tree`
```
execution time of append() : 1.215140 sec
execution time of findName() : 0.000001 sec
execution clock of findName() : 747 clock
Performance counter stats for './phonebook_bst' (10 runs):
22,582,677 cache-misses # 75.921 % of all cache refs ( +- 1.29% )
29,744,951 cache-references ( +- 0.60% )
1,165,787,188 instructions # 0.34 insn per cycle ( +- 0.02% )
3,419,902,982 cycles ( +- 1.79% )
1.174656713 seconds time elapsed ( +- 1.40% )
```
最終效果如圖
BST把樹蓋起來約1.2秒左右
(BST為HashTable後面再串Binary Search Tree)
**append速度 BST<original<optimized
findName速度** **original<optimized<BST**
## 嘗試更換data Set
所嘗試之第一筆data set
[name.txt](http://web.archive.org/web/20010419123305/http://freespace.virgin.net/philip.dance1/offstats/names1-500.htm)
複製下來資料格式長這樣
1 SMITH 1.15 1.15
共500筆手動刪除數字真的太麻煩，重複的行為就要讓程式來處理
``` =c
fgets(line, sizeof(line), fp);
line[strlen(line) -1] = '\0';
sscanf(line, "%*s %s",line);
```
%*s會自動把第一個讀到的字串格式丟掉，再加上sscanf系列都會用空白鍵當分隔，所以就可以自動把前面數字的部份丟掉。但500筆資料真的太少了，所以我又找了下一個資料來源
->[lastname.txt](https://github.com/aakashkag/People-Name-List)
共890640筆資料
有部份並不類似人名如 internationalstudies
但有鑑於phonebook不一定只紀錄人名，紀錄單位名也是很正常的，故我認為international studies 或是 young professionals 這一類也是非常符合我們需求的測資，故以此測資來進行後續實驗。
words.txt 與 lastname.txt的差別整理
1. 數量 349900 -> 890640
2. 單字性質 亂碼 -> 詞彙組合
3. 最大長度 16 -> 20
4. 按照長度及字母排序 -> 僅按照長度排序
測試一下更換前後的運行狀態
```
此為words.txt版本數據 phonebook_orig
execution time of append() : 0.038125 sec
execution time of findName() : 0.005890 sec
execution clock of findName() : 5890225 clock
Performance counter stats for './phonebook_orig' (100 runs):
1,203,955 cache-misses # 86.261 % of all cache refs ( +- 0.23% )
1,395,716 cache-references ( +- 0.15% )
262,072,382 instructions # 1.43 insn per cycle ( +- 0.03% )
183,510,089 cycles ( +- 0.19% )
0.060627409 seconds time elapsed ( +- 0.22% )
vs
此為lastname.txt版本數據 phonebook_orig
execution time of append() : 0.089377 sec
execution time of findName() : 0.014266 sec
execution clock of findName() : 14266365 clock
Performance counter stats for './phonebook_orig' (100 runs):
2,929,410 cache-misses # 86.617 % of all cache refs ( +- 0.24% )
3,382,044 cache-references ( +- 0.16% )
665,813,558 instructions # 1.61 insn per cycle ( +- 0.02% )
414,695,567 cycles ( +- 0.05% )
0.136094654 seconds time elapsed ( +- 0.09% )
```
origin的append,findName,findName時間都大幅增加(主因為linked-list的長度遽增)
instructions 跟 cache-miss都大幅增加
```
此為words.txt版本數據 phonebook_opt
execution time of append() : 0.039495 sec
execution time of findName() : 0.000001 sec
execution clock of findName() : 823 clock
Performance counter stats for './phonebook_opt' (100 runs):
98,574 cache-misses # 19.595 % of all cache refs ( +- 2.84% )
503,054 cache-references ( +- 0.23% )
230,480,249 instructions # 1.79 insn per cycle ( +- 0.03% )
129,016,130 cycles ( +- 0.41% )
0.043316626 seconds time elapsed ( +- 0.51% )
vs
此為lastname.txt版本數據 phonebook_opt
execution time of append() : 0.093327 sec
execution time of findName() : 0.000002 sec
execution clock of findName() : 1771 clock
Performance counter stats for './phonebook_opt' (100 runs):
185,372 cache-misses # 15.238 % of all cache refs ( +- 1.14% )
1,216,479 cache-references ( +- 0.52% )
574,890,415 instructions # 2.13 insn per cycle ( +- 0.03% )
270,055,430 cycles ( +- 0.36% )
0.089481815 seconds time elapsed ( +- 0.43% )
```
optimized的append,findName,findName時間也都大幅增加(主因為碰撞的linked-list長度遽增)
由於instructions的數量大幅增加，配上HashTable分類後的局部性，讓cache-miss稍微下降了一點，但總體執行時間還是上升許多
```
此為words.txt版本數據 phonebook_bst
execution time of append() : 1.173750 sec
execution time of findName() : 0.000001 sec
execution clock of findName() : 1385 clock
Performance counter stats for './phonebook_bst' (10 runs):
24,569,350 cache-misses # 74.126 % of all cache refs ( +- 0.25% )
33,145,336 cache-references ( +- 0.16% )
1,169,675,560 instructions # 0.34 insn per cycle ( +- 0.02% )
3,483,911,374 cycles ( +- 1.11% )
1.151235334 seconds time elapsed ( +- 0.31% )
vs
此為lastname.txt版本數據 phonebook_bst
execution time of append() : 0.663722 sec
execution time of findName() : 0.000000 sec
execution clock of findName() : 366 clock
Performance counter stats for './phonebook_bst' (10 runs):
11,012,545 cache-misses # 51.704 % of all cache refs ( +- 0.46% )
21,299,030 cache-references ( +- 0.32% )
1,075,951,911 instructions # 0.53 insn per cycle ( +- 0.05% )
2,048,496,826 cycles ( +- 0.74% )
0.678606634 seconds time elapsed ( +- 0.45% )
```
hash+BST的append,findName,findName時間反而相對的大幅降低了？ 更大的資料量丟進來之後反而變快了！ cache-miss降低了，instructions也變少了，cycle也變少了，搜尋也變得更快了。為何會發生這種現象呢？
**推測原因：由於words.txt是以字典順序排序的，故在binary search tree中理論上會不斷的往右長分支，形成一個非常糟的直線型單向linked list，而新的data set並沒有這個問題**
- 實測對照：將BST內的平均高度 最低極值 最高極值 顯示出來看看
```
Words.txt版本
avg = 86 max = 124 min = 66 sd = 9.19084
```
```
lastname.txt版本
avg = 22 max = 40 min = 17 sd = 3.45025
```
**推測實證：將資料順序更改為高度分佈標準差更低的型態可以取得更佳的運行效果**
- 更改data Set的順序 降低BST高度分佈的標準差
藉由將長度居中的字串移到檔案開頭作為BST的Root來降低高度分佈的標準差
```
更改前->
BST高度平均數:22.35327 , BST高度標準差:3.45025
execution time of append() : 0.827688 sec
execution time of findName() : 0.000000 sec
execution clock of findName() : 342 clock
Performance counter stats for './phonebook_bst' (10 runs):
13,912,653 cache-misses # 64.133 % of all cache refs ( +- 1.96% )
21,693,479 cache-references ( +- 0.25% )
1,083,116,660 instructions # 0.47 insn per cycle ( +- 0.05% )
2,297,841,157 cycles ( +- 0.90% )
0.797273738 seconds time elapsed ( +- 1.06% )
更改後->
BST高度平均數:21.97168 , BST高度標準差:3.41921
execution time of append() : 0.744742 sec
execution time of findName() : 0.000000 sec
execution clock of findName() : 225 clock
Performance counter stats for './phonebook_bst' (10 runs):
12,930,487 cache-misses # 59.764 % of all cache refs ( +- 0.61% )
21,635,742 cache-references ( +- 0.30% )
1,079,546,427 instructions # 0.48 insn per cycle ( +- 0.03% )
2,251,963,212 cycles ( +- 0.50% )
0.762843449 seconds time elapsed ( +- 0.38% )
```
可以看見在標準差僅下降1%的情況下 append 的效率就增加了10％，對應 cache-miss,instructions,cycle 也都全部隨之下降 ，故可得證在更改 data set 後 append 時間的大幅縮短的確是BST高度標準差大幅下降導致的結果。
:::info
延伸問題：將BST 改為B Tree, AVL等進階樹狀結構取得更好的效能優化
:::
## 試用霍夫曼編碼壓縮字串
利用bitwise操作將字串編碼壓縮，對應表格長度做位移操作來直接用bit表達字串，假設用最簡單的方法 5bit 表達a~z，可以把一個char壓縮到最多 5bit 8*16=128就可以壓縮成 5 * 16 = 80
一個struct 32個byte就可以壓縮成26個byte
還可以額外使用變長編碼表的方法來編碼，其中之一的霍夫曼編碼又稱為最優二元樹，是一種帶權路徑長度最短的二元樹([詳細證明請參見維基百科](https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81))
表達方式如下
建構方式讓我貼上一張很生動的gif來表示
這樣想想，以前大同資料結構在教的：
以前資料結構教的(霍夫曼編碼？)
的霍夫曼編碼根本只是變長編碼表......哪裡是霍夫曼編碼了= =
接著針對lastname.txt實作霍夫曼樹來取得編碼表
->[buildtree.c](https://github.com/BodomMoon/phonebook/blob/master/buildtree.c)
取得編碼表後將lastname.txt內的字串全部先按照「正常的」霍夫曼編碼編一次之後看看其長度改變：
->[encoder.c](https://github.com/BodomMoon/phonebook/blob/master/encoder.c)
```
bodommoon@bodommoon:~/文件/dataset$ gcc -o encoder encoder.c
bodommoon@bodommoon:~/文件/dataset$ ./encoder
max = 93 avg = 37
```
可以看見壓縮後最長的原本我打算直接開個12byte的資料結構來儲存壓縮後的字串。
>去哪裡找一個12byte的資料結構也是個我還沒想清的問題
接著發現了[e94046165](https://hackmd.io/s/SkklCcwOM#Hash-function--sdbm)同學在共筆中提到的「記憶體對齊」的問題，實測發現真的struct的size在64bits的作業系統下只能塞 8byte 的倍數，測試一下在霍夫曼壓縮過後會超過64bit的字串只有5787個，那乾脆直接試著塞成24byte好了，超過的那幾個另外開個entry塞吧
實作結果先上統計過長好的編碼表
```
a 111
l 1101
s 1100
m 10111
v 101101
y 101100
o 1010
A 100 <-終止符號
n 0111
u 01101
c 01100
r 0101
h 01001
p 010001
x 010000111
q 010000110
j 01000010
f 0100000
i 0011
k 00101
t 00100
e 0001
b 000011
g 000010
w 0000011
z 0000010
d 000000
```
因為霍夫曼不是固定長度的編碼，在實作時考慮到資料型態的pending必須紀錄每筆資料的長度，但是如果花int去額外紀錄長度就等於又花了 4byte ，於是我決定額外將每行的EOL也計算次數編進去成為一個符號，這樣可以更有效的縮短壓縮後的「總體」長度。
在 encode 時選擇直接生成對應的字母表陣列來處理有最快的效果，直接將 char - 'a' 即可對應至陣列內的編碼
接著將字串從左邊的開頭開始往右編碼，並用 unsigned long int 的方式紀錄
`ear`->
`0001111101011000000000000000000000000000000000000000000000000000` ->
`2211267417038913536`
```=c
unsigned long int encode(char line[])
{
int codeLen[27]= {3,6, 5,6,4, 7,6,5,4, 8,5, 4, 5,4, 4, 6, 9,4, 4,5, 5, 6,7, 9, 6,7,3};
long int code[27] ={7,3,12,0,1,32,2,9,3,66,5,13,23,7,10,17,134,5,12,4,13,45,3,135,44,2,4};
// a b c d e f g h i j k l m n o p q r s t u v w x y z a
int move = BIT_OF_LONG;
unsigned long int out = 0;
//int flag = 0;
for(int i = 0 ; i < strlen(line); i++){
int test = 0;
test = line[i]-'a';
move -= codeLen[test];
if(move >= 3){
out |= (code[test] << move);
//printf("move = %d char = %c code = %ld out = %ld \n", move ,line[i],(code[test] << move),out);
}
else{
exit(1);
}
}
move -= codeLen[26];
out |= (code[26] << move);
return out;
}
```
decode時則用 Heap array 的方式儲存整個Huffman tree的編碼。如讀取到 xyz(皆為二進位數字) 的話則對應Heap array 中 (((1*2)+x)*2+y)*2+z)的位置去存取 'a' 來還原字串
```=c
int size = strlen(input);
do{
place = place * 2 + (input[counter] -'0');
if(letter[place]!=0){
if(letter[place]!='A'){
printf("%c"letter[place]);
place=0;
}else
break;
}
}while(counter - size - 1);
//由於本程式用不到解碼的部份，此部份有實作在程式中但並未使用
```
這樣在BST內比對時也不用 byte-by-btye 去比較了，有鑑於有加入非全0的 EOL 編碼，每個字串都會編出不同的大小數值，直接拿數字去對照即可，也更適合BST的比較和建立
```
size of entry : 32 bytes
execution time of append() : 0.749705 sec
execution time of findName() : 0.000000 sec
execution clock of findName() : 159 clock
Performance counter stats for './phonebook_huf' (20 runs):
5,687,528 cache-misses # 47.137 % of all cache refs ( +- 0.35% )
12,065,981 cache-references ( +- 0.19% )
1,841,708,600 instructions # 0.80 insn per cycle ( +- 0.00% )
2,302,525,225 cycles ( +- 0.30% )
0.773821413 seconds time elapsed ( +- 0.27% )
```
可以看見 findName 的速度又快了一咪咪， struct 變小隨之 cache-miss 也又下降了一個層級，但在findName的部份時間卻上升了10％？ instructions 數量也大漲，這我不能接受R
用 perf 找找看資源消耗的熱點
```
Samples: 2K of event 'branch-misses:u', Event count (approx.): 14023007
Overhead Command Shared Object Symbol ◆
60.33% phonebook_huf libc-2.26.so [.] __GI_____strtoull_l_internal ▒
28.05% phonebook_huf phonebook_huf [.] append ▒
6.72% phonebook_huf libc-2.26.so [.] _IO_vfscanf ▒
4.03% phonebook_huf libc-2.26.so [.] malloc ▒
0.72% phonebook_huf phonebook_huf [.] malloc@plt ▒
0.08% phonebook_huf libc-2.26.so [.] _IO_sputbackc ▒
0.04% phonebook_huf ld-2.26.so [.] _dl_important_hwcaps ▒
0.03% phonebook_huf libc-2.26.so [.] __uflow ▒
0.00% phonebook_huf ld-2.26.so [.] _dl_start ▒
0.00% phonebook_huf libc-2.26.so [.] _int_malloc
```
`__GI_____strtoull_l_internal`佔了超過 60% 的 branch-miss 找找看這是何物
```
It's an internal function within libc, related to `strtol()`
```
再回頭看看 man 對於 fscanf 的解釋
```
fscanf - input format conversion
```
原來效能全部都花在讀取字串流再進行型別轉換的作業上了
```
Samples: 2K of event 'branch-instructions:u', Event count (approx.): 441979326
Overhead Command Shared Object Symbol ◆
49.99% phonebook_huf libc-2.26.so [.] _IO_vfscanf ▒
32.17% phonebook_huf libc-2.26.so [.] __GI_____strtoull_l_internal ▒
4.13% phonebook_huf libc-2.26.so [.] _int_malloc ▒
3.98% phonebook_huf phonebook_huf [.] append ▒
3.97% phonebook_huf phonebook_huf [.] main ▒
3.25% phonebook_huf libc-2.26.so [.] __isoc99_fscanf ▒
1.10% phonebook_huf libc-2.26.so [.] _IO_sputbackc ▒
1.04% phonebook_huf libc-2.26.so [.] malloc ▒
0.06% phonebook_huf phonebook_huf [.] __isoc99_fscanf@plt ▒
0.06% phonebook_huf phonebook_huf [.] malloc@plt ▒
0.06% phonebook_huf libc-2.26.so [.] __strtoull_internal
```
在 branch-instructions 的 report 中也可以看到光 scanf + strtol 的轉換就佔據了超過七成的比例，我還以為一次讀取整個數字會比字串快，原來反而字串才是OS的真愛阿！
> 延伸問題：不知道試著自己將字串轉成編碼的效果會不會更好，不過我覺得似乎不太可能就是了。
## 編譯器O2優化催下去之後的神奇改變
GCC -OX 有提供不同的程式優化層級，使用者可以按照需求下指令來生成不同的執行檔
具體優化內容可見[GUN官方解釋](https://gcc.gnu.org/onlinedocs/gcc-4.8.1/gcc/Optimize-Options.html#Optimize-Options)
讓我們來催下去看看
```
-------------gcc -O0 不優化的版本----------
size of entry : 136 bytes phonebook_orig
execution time of append() : 0.080739 sec
execution time of findName() : 0.014451 sec
execution clock of findName() : 14450635 clock
size of entry : 40 bytes phonebook_opt
execution time of append() : 0.085640 sec
execution time of findName() : 0.000002 sec
execution clock of findName() : 1661 clock
size of entry : 48 bytes phonebook_bst
execution time of append() : 0.674968 sec
execution time of findName() : 0.000000 sec
execution clock of findName() : 222 clock
size of entry : 32 bytes phonebook_huf
execution time of append() : 0.765965 sec
execution time of findName() : 0.000000 sec
execution clock of findName() : 183 clock
```
```
-------------gcc -O2 優化的版本----------
size of entry : 136 bytes phonebook_orig
execution time of append() : 0.081436 sec
execution time of findName() : 0.013962 sec
execution clock of findName() : 13961851 clock
size of entry : 40 bytes phonebook_opt
execution time of append() : 0.071558 sec
execution time of findName() : 0.000001 sec
execution clock of findName() : 1296 clock
size of entry : 48 bytes phonebook_bst
execution time of append() : 0.660783 sec
execution time of findName() : 0.000000 sec
execution clock of findName() : 183 clock
size of entry : 32 bytes phonebook_huf
execution time of append() : 0.724686 sec
execution time of findName() : 0.000000 sec
execution clock of findName() : 87 clock
```
其中最讓我驚訝的是 phonebook_huf 的版本搜尋時間可以說是直接砍半， 183 -> 87 個 clock ，效果遠超其他不同的版本，~~可見我的霍夫曼版本寫的有多爛~~。從編譯的訊息來看主要似乎是去掉了某些不必要的 fscanf 回傳值，但整體的影響為何如此之大還有待深入研究釐清
:::info
延伸問題：為何 gcc 的優化對於 huf 版本的影響如此之大
:::
## 作業本身設計的問題思考
**1. 建表之後馬上搜尋**
這樣等於把建表所用的cache-miss跟搜尋時的cache-miss全部混在一起了，甚至連free時的行為也算進去了，並沒有辦法個別觀察不同行為所帶來的優缺點。
(ex.拔掉free的部份減少指令當然可以帶來更高的效能表現，但這不是正確的編程手段)
**2. 建表跟搜尋之間所佔的效能比例差距過大**
建表那邊必須完整建立35萬筆資料的表格，但搜尋卻只執行1次，這樣執行完所觀察到的效能數據(cache-miss,instructions)比例非常不均，基本上幾乎都是建表行為所帶來的數據。
**3. 使用固定的搜尋目標**
程式基本上只會搜尋一次"zyxel"這個字串，導致針對findName()的評估根本毫無可信度，只要剛好被放在list或是tree的前面就可以展現接近O(1)的效能。
(而且findName()所得之時間為固定的常數時間，不管跑幾次都不會有差別)
**4. 使用詞彙庫與正式詞彙相差甚遠**
words.txt內有大量非正式的詞彙(ex.aaaaaaauugh)
與現實情境不符，個別字母出現頻率也跟正式詞彙相差甚遠。
## Makefile之CFLAG設定
CFLAG可以用來控制多版本的編譯行為，這樣就不用整天開main1.c main2.c main3.c 可以整合寫在一起並且按照自己的需求分別編譯，編譯器只會按照對應的內容生成執行檔，每個if都要對應到endif並且可以按照巢狀結構使用，範例如下：
```=c
#if BST == 1
#if OPT == 1
puts("BST=1 OPT =1");
#else
puts("BST=1 OPT =0");
#endif
#elif OPT == 1
puts("BST =0 OPT=1");
#else
puts("BST =0 OPT=0");
#endif
```
定義CFLAG參數的方法有兩種
1. 在關聯的檔案中寫上＃Define CFLAG ＝ N
2. 在編譯時追加參數 gcc -D CFLAG=N
都可以達到同樣的效果。
## Git分支控制紀錄
有鑑於有一次我不小心push了錯誤的檔案上去而且又在push了一次才發現打錯，故把紀錄回推再重新push的部份也紀錄一下：
**以下方法切勿在多人共同開發時使用**
`$ git reset --hard HEAD^^`
這個指令可以回滾兩個版本，注意在同一分支上別人提交的版本也會被回滾，所以才說多人開發時最好別使用，很有可能一不小心幹掉別人push的檔案。
`$ git push --fouce`
這個指令可以強制提交，不然在回滾後git會一直跟你說前面有版本可以修復不能push。
以下是一些常用指令紀錄
`$ git status`
查看檔案更新及追蹤狀態
`$ git add 檔案名`
新增檔案到暫存區(不寫檔案名則是全部新增)
`$ git commit -m '說明'`
提交並且新增標題，標題只能一行不超過50個字元
`$ git commit -e`
開啟提交編輯器可以打一大堆包含標題加說明
`$ git push`
把寫了半天的檔案用力推上去
## 作業QA
- 改善電話簿的效能分析，透過大量的重複執行，找出 95% 信賴區間，而且允許動態新增資料 (較符合現實) 和查詢。
-- 在findName新增了單純用clock計算的輸出，輸入$ ./phonebook_ent就可以執行可動態新增及查詢的版本。
- 有代表性嗎？跟真實英文姓氏差異大嗎？
-- 只能代表Hash 或 BST等資料結構的效率會比單純的Linked-list好而已。
- 資料難道「數大就是美」嗎？
-- 數大固然好，但資料必須平均分佈並且符合真實情境 。
- 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
-- 在區分男女性的情況下用真實姓名去組合，並且不能侷限在特定地區(黃家村 中國城之類的)。
## 參考連結
[[1] Disallowing perf\_event\_open() \[LWN.net\]](https://lwn.net/Articles/696470/)
[[2] CAP\_SYS\_ADMIN: the new root \[LWN.net\]](https://lwn.net/Articles/486306/)
[[3] Branch Patterns, Using GCC](http://cellperformance.beyond3d.com/articles/2006/04/branch-patterns-using-gcc.html)
[[4] Fast and slow if-statements: branch prediction in modern processors](http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/)
[[5] ryanpatiency-開發紀錄(phonebook)](http://cellperformance.beyond3d.com/articles/2006/04/branch-patterns-using-gcc.html)
[[6] ryanwang522-開發紀錄(phonebook)](https://hackmd.io/s/Sk-qaWiYl)
[[7] 哈希函数BKDR的解析- CSDN博客](http://blog.csdn.net/MBuger/article/details/61663097)
[[8] Git – 寫點科普，請給指教。](https://hellolynn.hpd.io/tag/git/)
[[9] 霍夫曼编码\- 维基百科，自由的百科全书](https://zh.wikipedia.org/zh-tw/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81)
[[10] Git Git 自學筆記 : 退版(reset) ,重拉(pull), 強推(push)](https://dotblogs.com.tw/michaelfang/2016/09/07/git-reset-log-reflog)
[[11] Is it possible to speed up a hash table by using binary search trees for separate chaining?](https://softwareengineering.stackexchange.com/questions/280762/is-it-possible-to-speed-up-a-hash-table-by-using-binary-search-trees-for-separat)
[[12] Binary Search Tree: Search(搜尋資料)、Insert(新增資料)](http://alrightchiu.github.io/SecondRound/binary-search-tree-searchsou-xun-zi-liao-insertxin-zeng-zi-liao.html)
[[13]【Git】 隨手筆記](http://fireqqtw.logdown.com/posts/196392-git-casually-notes)
[[14] 如何寫一個 Git Commit Message
](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)[[15] 用CFLAGS -D來定義Makefile中global變數
](https://bryceknowhow.blogspot.tw/2013/11/linux-cflags-dmakefileglobal.html)[[16] 撰寫Makefile教學](http://hsian-studio.blogspot.tw/2008/09/makefile_08.html)
[[17] #if、#elif、#else 和 #endif 指示詞 (C/C++)](https://msdn.microsoft.com/zh-tw/library/ew2hz0yd.aspx)
[[18] C语言strcasecmp()函数：判断字符串是否相等(忽略大小写)](http://c.biancheng.net/cpp/html/159.html)
[[19] How can I **upgrade** my **EOL** 16.10 to any new version?](https://www.google.com.tw/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&cad=rja&uact=8&ved=0ahUKEwjIi8G6wuLZAhVLjpQKHe2pC34QrAIITSgBMAI&url=https%3A%2F%2Faskubuntu.com%2Fquestions%2F999360%2Fhow-can-i-upgrade-my-eol-16-10-to-any-new-version&usg=AOvVaw02b1sIGVnrXqGM1HvOoytE)
Sign in with Wallet
Connect another wallet