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
分享上來的令一個理由是,我一年前看過現在又幾乎忘光了QAQ

準備工作

perf

(參考網址：http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
指令如下

$ 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

每個人的kernel版本需求有可能不同，請依照跳出的提醒作安裝

照他講的裝

$ 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安裝鍵盤輸入法系統gcin

gnuplot

用來畫圖表時的實用工具，可以撰寫script來作為畫圖時的腳本。

安裝

$ sudo apt-get install gnuplot

Origin

$ make run
size of entry : 136 bytes
execution time of append() : 0.039465 sec
execution time of findName() : 0.009147 sec

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

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％
下圖為圖表的比對

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Hash function

實作的時候猶豫了很久要開多大的hash table，所以也就查了一些資料（詳細請見reference）
在這邊採用的是 channing 的方式，將 lastname 經過 hash 轉換後得到一個 value，在拿那個value 去除以一個定數取餘數，然後根據餘數來看是要放在哪個index底下, struct長這樣

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),而有很大的改善。