phonebook

github contributed by <diana0651>

tags: `d0651` `sys`

Reviewed by <LitSnow>
*dNext已經搬到新的 __PHONE_BOOK_ENTRY 結構中，舊的 __PHONE_BOOK_DETAIL_ENTRY 結構中的 struct __PHONE_BOOK_DETAIL_ENTRY *dNext;就可以不用留著

已經修正

案例分析

作業要求

適度修改 phonebook_opt.c 和 phonebook_opt.h 兩個檔案，使得這兩者執行時期的 cache miss 降低。

預期目標

學習使用 Git 與 GitHub
學習效能分析工具
可能的效能改進方向：
- 改寫 struct__PHONE_BOOK_ENTRY 的成員，搬動到新的結構中
- 使用 hash function 來加速查詢
- 既然 first name, last name, address 都是合法的英文 (可假設成立)，使用字串壓縮的演算法，降低資料表示的成本
- 使用 binary search tree 改寫演算法

開發環境

$ cat /etc/issue
Ubuntu 14.04.5 LTS \n \l
$ cat /proc/version
Linux version 4.2.0-42-generic (buildd@lgw01-55) (gcc version 4.8.4 (Ubuntu 4.8.4-2ubuntu1~14.04.3) )
$ lscpu
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 8192K

Makefile

makefile規則的基本結構

目標(Target) : 一個目標檔，可以是Object檔，也可以是執行檔，還可以是一個標籤(Label)。
依賴(Dependency,Prerequisites) : 要產生目標檔(target)所依賴哪些檔。
命令(Command) : 建立專案時需要執行的shell命令 (命令部分的每行的縮進必須要使用Tab鍵而不能使用多個空格)。
注意：
- make只在意依賴性
- 顯式make命令
- 在Makefile中的命令，必須要以[Tab]鍵開始。

變數宣告

MACRO = value ：可利用$(MACRO)或${MARCO}來存取已定義的變數。
:= ：變數的值決定於它在 Makefile 中的位置，而不是整個 Makefile 展開後最終的值。
?= ：若變數未定義，則替它指定新的值。否則採用原有的值。

內部變數

$?：代表已被更新的 dependencies 的值。也就是 dependencies 中，比 targets 還新的值。
$@ ：代表 targets 的值。
$< ：代表第一個 dependencies 的值。
$* ：代表 targets 所指定的檔案，但不包含副檔名。

參考資料

http://maxubuntu.blogspot.tw/2010/02/makefile.html
http://mropengate.blogspot.tw/2015/06/makefile-makefile.html
http://mropengate.blogspot.tw/2015/06/makefile-makefile-2.html
http://tetralet.luna.com.tw/?op=ViewArticle&articleId=185

Gnuplot

gnuplot 是一個用於生成趨勢圖和其他圖形的工具。它通常用於收集基於時間的數據，同時也可以使用靜態數據。

gnuplot introduction(中文版)
gnuplot manual

簡易設定

設定標題：set title "title_description"
設定 x 軸 Label：set xlabel "x_description (unit)"
設定 x 軸值範圍：set xrange [ m : n ]
呈現圖式：plot
輸出圖檔：set output 'filename.png'

資料呈現

點與線：plot "filename" with linespoints
線條寬度(linewidth)、點大小(pointsize)。兩者都可以設置为整數或小數。
點：plot "filename" with points
點型(pointtype)，主要用於設置點得形狀
線：plot "filename" with line
線型(linetype )，主要用於設置線條的顏色

參考資料

http://applezu.netdpi.net/2014/02/gnuplot.html
http://fanli7.net/a/bianchengyuyan/C__/20160414/558945.html

GitHub

git init　建立目錄 .git
git status　確認現在所有檔案的狀況
git add 檔名　追蹤此檔案
git commit　確認檔案並snapshot（有點像暫時存檔）
git remote add <nickname> <repository-URL>　連結遠端的repository並給他取代稱
git push <nickname>　把檔案上傳到指定的repository

Linux 效能分析工具: Perf

Perf (Performance Event) 提供一個簡便的效能分析方案，另有即時的效能分析等應用，是用來進行軟體性能分析的工具。

$ uname : 顯示作業系統
sudo perf top : 查看整體系統負載
perf list : 列出所有能夠觸發 perf 採樣點的事件
- Perf 能觸發的事件分為三類
  - hardware : 由 PMU 產生的事件，比如 cache-misses、cpu-cycles、instructions、branch-misses …等等，通常是當需要瞭解程序對硬體特性的使用情況時會使用。
  - software : 是核心程式產生的事件，比如 context-switches、page-faults、cpu-clock、cpu-migrations …等等。
  - tracepoint : 是核心中的靜態 tracepoint 所觸發的事件，這些 tracepoint 用來判斷在程式執行時期，核心的行為細節，比如 slab 記憶體配置器的配置次數等。
perf stat : 概括提供程序運行的整體情況

參考資料

http://mropengate.blogspot.tw/2016/04/perf.html

未優化版本 phonebook_orig

測試程式效能

make run 執行時間




size of entry : 136 bytes
execution time of append() : 0.102741 sec
execution time of findName() : 0.007556 sec
3

make cache-test cache-misses 90%









Performance counter stats for './phonebook_orig' (100 runs):

         2,029,918      cache-misses              #   89.885 % of all cache refs    
         2,275,583      cache-references                                            
       263,219,831      instructions              #    1.22  insns per cycle        
       221,815,824      cycles                                                      

       0.076515784 seconds time elapsed                                          ( +-  1.48% )
![](https://i.imgur.com/NH22hCN.png)

解釋：
cache-misses: 沒有在cache中找到需要的資料, 反過來就是cache hit
cache-references: 讀取cache的次數
instructions: 機器指令的數目
cycles: 程式中的指令所需要的總cycle次數

sudo perf top 尋找熱點

小結

L1 Cache : 32KB = 32*1024，PhoneBook size = 136 bytes，321024 / (136*8) = 30.12 (只能存 30 筆左右)
若把整個 __PHONE_BOOK_ENTRY 的 struct 都丟進 findName() 尋找， L1 cache 最多也只能放 30 個 entry，一共有 35 萬個單字，必定會發生頻繁的 cache miss。

效能：findName() 較 append() 好
執行時間：append() 較 findName() 久
目標：縮短 findName() 的執行時間

改善方向

Reduce search times
- Hash table
- Binary Search Tree
Reduce struct size
- Data structure
- string compression

優化版本 phonebook_opt: 1。減少資料結構大小

搜尋時只比對 lastName, 所以針對 cache-misses，嘗試將 struct __PHONE_BOOK_ENTRY 縮小，把其它資訊包裝起來放到 struct __DETAIL_ENTRY，再用指標指向他





typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];\
    struct __DETAIL_ENTRY *pDetail;
    struct __PHONE_BOOK_ENTRY *pNext;		     
} entry;

測試程式效能

$ make cache-test
size of entry : 136 -> 32
cache-miss : 90% -> 53%












size of entry : 32 bytes
execution time of append() : 0.046319 sec
execution time of findName() : 0.003430 sec

Performance counter stats for './phonebook_opt' (100 runs):

           406,381      cache-misses              #   53.221 % of all cache refs    
           685,441      cache-references                                            
       246,015,882      instructions              #    1.60  insns per cycle        
       147,728,355      cycles                                                      

       0.048182165 seconds time elapsed                                          ( +-  0.81% )

$ eog runtime.png

優化版本 phonebook_opt: 2。 hash function 加速查詢

Hash 將資料透過特別的函數轉換成表格索引進行存取，所以實做的重點在於建立表格及建立轉換的函數。

參考概念

參考實作

hash function：
先將字串資料轉換成數值，使用最容易實做的 division 計算 index。
hash table size：
為了降低 collision 發生，我們希望 hash table 愈大愈好，然而較大的 table 容易造成空間的浪費。
由於 hash function 採用 division，在實做上table size＝ D，且為了降低 collision 的發生，所以選擇 D 為質數。
overflow handling：
當 hash value 對應到 hash table 中的欄位已經有資料了，使用 Chaining，可以有效利用原本結構體的 pNext 將 overflow 的資料加進該欄位的 list 中。

測試程式效能














$ ./phonebook_hash
size of entry : 32 bytes
execution time of append() : 0.077230 sec
execution time of findName() : 0.000000 sec

Performance counter stats for './phonebook_hash' (100 runs):

           446,120      cache-misses              #   75.538 % of all cache refs    
           589,839      cache-references                                            
       303,567,973      instructions              #    1.67  insns per cycle        
       181,623,645      cycles                                                      

       0.062899824 seconds time elapsed                                          ( +-  1.29% )

改善方向

測試 hash table size

其他的 HASH function

各種字符串Hash函數比較

可以實作的方向

Programming Small
提到 djb2 hash function & BKDR hash function

參考實作

djb2 hash function
初始 hash 值為 5381，key 為 hash*33 加上字串的內容。










unsigned int DJB2_hash(char lastName[], int hash_table_size)
{
        unsigned int hash = 5381;
        int c;
        int i = 0;

        while (c = lastName[i++])
            hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

        return hash %= hash_table_size;

BKDR hash function
計算過程中有係數(seed)參與，seed為31 131 1313














unsigned int BKDR_hash(char lastName[], int hash_table_size)
{

    unsigned int seed = 131;
    unsigned int hash = 0;
    int i = 0;
    while(lastName[i] != '\0')
    {
        hash = hash * seed + lastName[i];
        i++;
    }

    return hash %= hash_table_size;
}

優化版本 phonebook_opt: 3。字串壓縮的演算法，降低資料表示的成本

Smaz is a simple compression library suitable for compressing very short strings.

參考實作

測試程式效能













$ ./phonebook_smaz
size of entry : 32 bytes
execution time of append() : 0.181449 sec
execution time of findName() : 0.008812 sec

Performance counter stats for './phonebook_smaz' (100 runs):

           681,816      cache-misses              #   58.851 % of all cache refs    
         1,191,106      cache-references                                            
       806,187,790      instructions              #    1.46  insns per cycle        
       554,662,350      cycles                                                      

       0.163610323 seconds time elapsed                                          ( +-  0.51% )

其他的資料壓縮方法

參考

資料壓縮
- 失真壓縮
  - 影像處理
- 無失真壓縮
  - 字串壓縮
常見之壓縮方法
- 霍夫曼編碼
  將資料先搜尋一遍來建編碼樹
- smaz 方法
  即時的壓縮方法
  適合短字串, 英文字串效果好
- shoco 方法
  即時運算的壓縮方法
  特性與 smaz 相反

優化版本 phonebook_opt: 4。 binary search tree 改寫演算法

…

Code Review

coding style
$ astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch]
github
- commit 的敘述明確
- branch 的版本控制

phonebook

tags: d0651 sys

案例分析

作業要求

預期目標

開發環境

Makefile

makefile規則的基本結構

變數宣告

內部變數

參考資料

Gnuplot

簡易設定

資料呈現

參考資料

GitHub

Linux 效能分析工具: Perf

參考資料

未優化版本 phonebook_orig

測試程式效能

小結

改善方向

優化版本 phonebook_opt: 1。減少資料結構大小

測試程式效能

優化版本 phonebook_opt: 2。 hash function 加速查詢

測試程式效能

改善方向

其他的 HASH function

可以實作的方向

優化版本 phonebook_opt: 3。字串壓縮的演算法，降低資料表示的成本

測試程式效能

其他的資料壓縮方法

優化版本 phonebook_opt: 4。 binary search tree 改寫演算法

Code Review

tags: `d0651` `sys`