# 2017q1 Homework1 (phonebook)
contributed by <`yangyang95`>
###### tags: `sysprog2017` `HW1` `yangyang95`
github page 看 [這裡](https://github.com/yangyang95/phonebook)
作業要求看 [這裡](https://hackmd.io/s/rJYD4UPKe#作業要求)
### Reviewed by <`vtim9907`>
- 實做完優化後，除了比較執行時間外，還可以觀察 cache 運行的狀況，比較每種方法 cache-miss 出現的情況。
- 隨然內文題到 BST append 的時間很長，才做 Trie，但其實可以將兩種都實做出來，進行比較後才能知道正確的結果。
- 可以嘗試更多優化的方法。
- 為了貼近現實，除了新增和查詢，也可以實做看看刪除資料的功能。
- 尚未回答本作業須回答的問題。
## Linux 與電腦規格
電腦使用的作業系統本來就是 Ubuntu 16.10，所以就直接拿來用囉～～
```
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 58
Model name: Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
Stepping: 9
CPU MHz: 1316.186
CPU max MHz: 3200.0000
CPU min MHz: 1200.0000
BogoMIPS: 5187.80
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
NUMA node0 CPU(s): 0-3
```
## 講義閱讀
### perf 原理與實務
第一步是先把老師提供的這份 [perf 原理和實務](https://hackmd.io/s/B11109rdg) 講義先讀過，並且把不懂的部分先做搜尋。
根據教學順利的完成 perf 的安裝，再來把 ```$ perf list```, ```$ perf top``` 的指令都先試一遍看看。
這裡把讀到的專有名詞稍做整理：
- **cache miss** --> 處理器在快取記憶體內找不到需要的資料。
- **branch miss** --> 分支預測失敗導致處理器效能受到影響。
- **pipeline** --> 現代處理器多數採用的流水線式設計，可同時加工多條指令，增加效能。
**superscalar** --> 處理器中多條流水線同時進行。
**out-of-order execution** --> 先處理完的指令先執行，不需等待前面的指令。
- **trace point** --> 程式碼中的觸發點，指定的程式碼被運行時，tracepoint 就會被觸發。
參考資料：
- [Branch Patterns, Using GCC](http://cellperformance.beyond3d.com/articles/2006/04/branch-patterns-using-gcc.html) 內提到幾個有趣的規則來降低 branch miss 發生。
- 影片: [Explaining CPU Architecture: Pipelining, Pipeline Stages, Superscalar CPUs and Order](https://www.youtube.com/watch?v=3DSKn8ADtos)
### Prgramming Small
這裡也對這份 [Prgramming Small](https://hackmd.io/s/S1rbwmZ6) 進行閱讀。
剛開始就有一份有趣的例子，[快速計算和表達圓周率](http://chamberplus.myweb.hinet.net/ems_2.htm)內提到如何在嵌入式系統內表示 3.14 ，直接呼叫 C 語言內的浮點運算是相當奢侈的做法。
厲害的做法是`3.14 = 201 / 64 = 201 >> 8`，只利用8位元晶片就可以處理。
原本還搞不懂位元運算， 實際參考資料後，理解到原來可以把`>> n`跟`除2^n`做等效。
[快速計算和表達圓周率解說](http://godspeedlee.myweb.hinet.net/trick.html) 提到可以利用很簡單的交叉相乘公式與程式就可以找出省錢又精確的解。
參考資料：
- [邏輯（Logical）運算、位元（Bitwise）運算](https://openhome.cc/Gossip/CGossip/LogicalBitwise.html)
## 原始版本
首先清空快取 `$ echo 1 | sudo tee /proc/sys/vm/drop_caches`
然後執行原始版本程式 `$ ./phonebook_orig`，獲得以下結果：
```
size of entry : 136 bytes
execution time of append() : 0.084219 sec
execution time of findName() : 0.006319 sec
```
利用 perf top 分析熱點 `./phonebook_orig & sudo perf top -p $!`
```
47.81% libc-2.24.so [.] __strcasecmp_l_avx
25.33% phonebook_orig [.] findName
6.64% [kernel] [k] nmi
5.37% [kernel] [k] unmap_page_range
4.09% [kernel] [k] free_pcppages_bulk
2.71% [kernel] [k] release_pages
1.36% [kernel] [k] free_pages_and_swap_cache
1.36% [kernel] [k] __mod_zone_page_state
1.35% [kernel] [k] free_hot_cold_page_list
1.33% [kernel] [k] kmem_cache_alloc
1.31% phonebook_orig [.] _init
1.31% libc-2.24.so [.] __strcasecmp_avx
0.03% [kernel] [k] native_write_msr
0.01% [kernel] [k] native_sched_clock
```
可觀察出 findName() 佔 25.33%，但實際執行時間卻小於 append()。這是因為預設的 performance event 是 「cycles」，所以這條指令可以分析出消耗 CPU 週期最多的部份。
利用 `$ sudo make cache-test` 獲得跑100遍的數據：
```
Performance counter stats for './phonebook_orig' (100 runs):
1,897,857 cache-misses # 86.412 % of all cache refs ( +- 0.25% )
2,196,287 cache-references ( +- 0.37% )
262,729,224 instructions # 1.28 insn per cycle ( +- 0.02% )
204,875,269 cycles ( +- 0.46% )
0.073139541 seconds time elapsed ( +- 1.10% )
```
可觀察出 cache misses 為86.412% ，也可看出 cache miss 對效能影響之巨。
## 優化方法一： 減少 struct 大小
```C==
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
struct detail *pDetail;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
typedef struct __ENTRY_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;
```
```
$ ./phonebook_opt
size of entry : 32 bytes
execution time of append() : 0.069770 sec
execution time of findName() : 0.002947 sec
```
findName() 與 append() 執行時間都有稍微減少。
:::success
補充：
```
Performance counter stats for './phonebook_opt' (100 runs):
410,488 cache-misses # 66.447 % of all cache refs ( +- 0.28% )
617,763 cache-references ( +- 0.59% )
243,373,348 instructions # 1.63 insn per cycle ( +- 0.04% )
149,450,713 cycles ( +- 0.28% )
0.052516323 seconds time elapsed ( +- 1.28% )
```
分析看 --> [2017q1 Homework4 (phonebook-concurrent) : Cache-miss 分析](https://hackmd.io/s/rJ3Svb-hg#cache-miss-分析)
:::
## 方法二： Trie 字典樹
參考之前的筆記時，可看出 binary tree 能改善 findName()，但是 append() 所需時間卻會大幅增加，因此嘗試利用字典樹來改善 findName() 所需時間。
其實本來對資料結構沒什麼概念，只是單純想用類似查字典的方式來加快搜尋速度，因此做了些 [搜尋](http://www.geeksforgeeks.org/trie-insert-and-search/) 後，發現字典樹的想法相當接近查字典的感覺，因此決定套用看看。
然而，字典樹實際上是設計用來查尋字詞出現的頻率，因此在加入其他結構上會造成困難。搜尋之前的 [筆記](https://hackmd.io/s/Bkx3cYX6) 時也有看到字典樹的實作，還是試着改寫看看：
```C==
#define ALPHABET_SIZE 26
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;
} detail;
typedef struct __PHONEBOOK {
char ch;
struct __PHONE_BOOK_ENTRY *pDetail;
struct __PHONEBOOK *pChild[ALPHABET_SIZE+1];
} phonebook;
```
不過因為字典樹的特性，detail 結構內的東西其實都沒有用處。
findName() 跟 append() 也試着實作看看：
```C==
#define MAX_LAST_NAME_SIZE 16
// Converts key current character into index
#define CHAR_TO_INDEX(ch) ((int)ch - (int)'a')
phonebook *findName(char lastName[], phonebook *pHead)
{
int len = strlen(lastName);
char searched_string[MAX_LAST_NAME_SIZE+1];
for (int i = 0; i <= len && pHead; i++) {
searched_string[i] = pHead->ch;
pHead = pHead->pChild[CHAR_TO_INDEX(lastName[i])];
}
printf("String searched is %s\n", searched_string);
if (strcasecmp(lastName, searched_string) == 0)
return pHead;
return NULL;
}
phonebook *append(char lastName[], phonebook *pHead)
{
int len = strlen(lastName);
for (int i = 0; i <= len && pHead; i++) {
int index = CHAR_TO_INDEX(lastName[i]);
if (pHead->pChild[index] == NULL) {
pHead->pChild[index] = (phonebook*) malloc(sizeof(phonebook));
pHead->pChild[index]->ch = lastName[i];
}
pHead = pHead->pChild[index];
}
return pHead;
}
```
不過上面的嘗試出現 core dump 的錯誤，暫時找不到錯誤的地方@@
現在想想 Hash table 可以有類似查字典的感覺，也能在其中加入其他結構，所以更符合電話簿的功能實作需求。過程中也學習到使用適當的資料結構才能對解決問題有所幫助。
## 問題回答
:::success
補充：
本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？
* 有代表性嗎？跟真實英文姓氏差異大嗎？
* 資料難道「數大就是美」嗎？
* 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
回答看 --> [2017q1 Homework4 (phonebook-concurrent) : 問題回答](https://hackmd.io/s/rJ3Svb-hg#問題回答)
:::
## 參考資料：
- [jkrvivian HackMD 筆記](https://hackmd.io/s/SyOQgOQa#)
- [zmke HackMD 筆記](https://hackmd.io/s/Sy4SdnKte)
- [0140454 HackMD 筆記](https://hackmd.io/s/Bkx3cYX6)
- [從Trie樹（字典樹）談到後綴樹](http://blog.csdn.net/v_july_v/article/details/6897097)
- [AVL樹，紅黑樹，B樹，B+樹，Trie樹都分別應用在哪些現實場景中？](https://www.zhihu.com/question/30527705)
- [Binary Tree](http://www.csie.ntnu.edu.tw/~u91029/BinaryTree.html)
Sign in with Wallet
Connect another wallet