owned this note
owned this note
Published
Linked with GitHub
# 2016q3 Homework 1 (phonebook)
contributed by <`FZzzz`>
### Reviewed by `believe7028`
- 可以對 perf 所量測得到的信息做說明更細緻的解釋,以及是否有其他事件數據可說明程式的狀況。
- Hash 取餘數採用的數`MAX_KEY_VALUES`使用質數是否比較好。
- 可以比較更多的雜湊函式。
- Hash 對資料表增加與刪除的操作會使得程式整體效能下降,也可以增加刪除的方法與效能評估。
- 如果未來資料一直增長,Hash 沒有機制應對而退化成Linked list。
- 如果資料一直增加,記憶體會放置不下。
- git commite message 可以增加細部說明來描述"remove useless"的詳細動作。
## 開發環境
* Destribution: Ubuntu 14.04.5 LTS (晚點更新)
* Kernel version: Linux4.4.0-38-generic
* CPU Cache:
* L1d: 32K
* L1i: 32K
* L2: 256K
* L3: 8192K
## 前情提要
我因為很久沒碰C了,所以想藉由這堂課重新摸一下和進一步去理解C和確認一下自己大學四年來學的東西
,另外原本是使用ubuntu 16.04 LTS的,但後來因為亂搞玩壞了,只好重灌成lubuntu 14.04 QQ,所以暫時應該是不會升上去(至少在完成作業前不會)
很久很久以前有看過一篇不錯的東西,分享上來給各位看看
[Deep C](http://www.slideshare.net/olvemaudal/deep-c)
分享上來的令一個理由是,我一年前看過現在又幾乎忘光了QAQ
## 準備工作
### perf
(參考網址:http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
指令如下
```shell
$ sudo apt-get install linux-tools-common
```
perf top 一次
```
WARNING: perf not found for kernel 4.4.0-18
You may need to install the following packages for this specific kernel:
linux-tools-4.4.0-18-generic
linux-cloud-tools-4.4.0-18-generic
```
:::warning
每個人的kernel版本需求有可能不同,請依照跳出的提醒作安裝
:::
照他講的裝
```shell
$ sudo apt-get install linux-tools-4.4.0-18-generic linux-cloud-tools-4.4.0-18-generic
```
### gcin
新酷音的很難用...,打這篇的時候一直被搞,所以推個 gcin。(感謝李奇霖大大告訴我)
不是功課重點不贅述,直接附上網址
http://blog.xuite.net/yh96301/blog/287374341-Ubuntu+14.04%E5%AE%89%E8%A3%9D%E9%8D%B5%E7%9B%A4%E8%BC%B8%E5%85%A5%E6%B3%95%E7%B3%BB%E7%B5%B1gcin
### gnuplot
用來畫圖表時的實用工具,可以撰寫script來作為畫圖時的腳本。
安裝
```shell
$ sudo apt-get install gnuplot
```
## Origin
```shell
$ make run
size of entry : 136 bytes
execution time of append() : 0.039465 sec
execution time of findName() : 0.009147 sec
```
```shell
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):
992,786 cache-misses # 80.752 % of all cache refs ( +- 0.94% )
1,229,426 cache-references ( +- 0.38% )
2,527,059 L1-dcache-load-misses ( +- 0.20% )
<not supported> L1-dcache-store-misses
<not supported> L1-dcache-prefetch-misses
45,292 L1-icache-load-misses ( +- 4.30% )
0.067631317 seconds time elapsed ( +- 0.79% )
```
## Struct變動( 縮小 entry )
因為搜尋 lastname 時不會用到細節部份,所以將細節部份拉出來,entry 裡只保留 pointer
```C
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
phonebook_detail* detail;
struct __PHONE_BOOK_ENTRY *pNext;
```
entry大小變動為136bytes->32bytes
大幅度的減少cache misses
(因為entry size變小了,cache所對應到的資料比數也增多,自然 cahce-misses 會大幅下降)
```
Performance counter stats for './phonebook_opt' (100 runs):
162,512 cache-misses # 38.290 % of all cache refs ( +- 0.70% )
424,425 cache-references ( +- 0.74% )
245,576,974 instructions # 1.84 insns per cycle ( +- 0.02% )
133,707,669 cycles ( +- 0.26% )
0.037950422 seconds time elapsed ( +- 3.54% )
```
從原本的80.752%->38.290%
下圖為圖表的比對
![](https://i.imgur.com/iXfGcAr.png)
## Hash function
實作的時候猶豫了很久要開多大的hash table,所以也就查了一些資料(詳細請見reference)
在這邊採用的是 channing 的方式,將 lastname 經過 hash 轉換後得到一個 value,在拿那個value 去除以一個定數取餘數,然後根據餘數來看是要放在哪個index底下, struct長這樣
```C
typedef struct __CABINET {
entry* value;
struct __CABINET* next;
} cabinet;
```
實驗結果如下
```
Performance counter stats for './phonebook_opt' (100 runs):
347,467 cache-misses # 51.772 % of all cache refs ( +- 0.98% )
671,148 cache-references ( +- 0.97% )
436,845,193 instructions # 1.74 insns per cycle ( +- 0.01% )
251,102,337 cycles ( +- 0.14% )
0.067775080 seconds time elapsed ( +- 0.16% )
```
可以看到hash function的作法,雖然在append的時間因為要建表而拉長不少,但在find的部份有極大的改善。雖然cache misses高了單純改動entry的方法20%,但因為時間複雜度從O(N) -> O(N/k)
(k取決於我們開多大的cabinet,這邊是1024),而有很大的改善。
![](https://i.imgur.com/lhZbmYc.png)
## Reference
* [課程網站](http://wiki.csie.ncku.edu.tw/sysprog/schedule)
* [作業網站](https://hackmd.io/s/S1RVdgza)
* HackMD Tutorial---左上有個小小的問號,點下去就對了。
* [Gnuplot tutorial from duke university](http://people.duke.edu/~hpgavin/gnuplot.html)
* [Programming Small](https://hackmd.io/s/S1rbwmZ6)
* [CS50 Hash Table Youtube](https://www.youtube.com/watch?v=h2d9b_nEzoA)
* [Google到不錯的PDF - Hashing](https://www.csie.ntu.edu.tw/~hsinmu/courses/_media/dsa_12spring/hashing.pdf) by Michel Tsai
* [DeepC](http://www.slideshare.net/olvemaudal/deep-c)
###### tags: `Fzzzz` `sysprog`