phonebook

contributed by <snoopy831002>

開發環境

軟體:unbuntu 16

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 →

硬體:Macbook pro 2013(late)

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 →

*本專案搭配astyle+Git使"過去的我"、"現在的我"以及"未來的我"延續一致的coding style

code review

#include IMPL

在main.c裡面會使用到 gcc -DIMPL="" 的 macro。
這個marco可以使編譯時加入參數進去,以本案例來說gcc -DIMPL="phonebook_hash" 就是在編譯期間在main.c檔內加入一個IMPL的marco,其值為phonebook_hash

這個可以讓我們輕易的在同一個main.c執行多個版本的phonebook

從shell傳入marco時必須以字串傳入,雙引號還必須要跳脫。
例如:
gcc -DIMPL"\"phonebook_orig.h\""
或是寫成下面這個版本(不用跳脫):
gcc -DIMPL'\"phonebook_orig.h\"'

開始分析

原始版本(未優化)

./phonebook_orig

執行時間:

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 →

cache-miss 高達89%:

  • 作業中提到的目標是要讓執行時期的cache miss降低,但原本的結構體在佔用的空間達到136 Bytes,但電腦本身的L1 cache只有32KB = 321024 byte,計算出來可放的資料量約321024 / 136 = 240.941筆,但是讀取的檔案本身卻是有349900筆的資料量,也難怪cache miss的比例如此高了。

利用perf找熱點:
./phonebook_orig & sudo perf top -p $!

  • 由此圖可以發現明明findName執行時(0.005552 sec)< append執行時間(0.056274)但是findName所佔效能(16.94%)卻是append(1.04%)的15倍左右
    代表說findname內很可能有很多不必要的運算

opt版本

在phonebook_opt.h中我縮小了struct的大小,因為在搜尋時只用lastname做搜尋,故保留之

typedef struct __LAST_NAME_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; struct entry_detail *detail struct __PHONE_BOOK_ENTRY *pNext; } entry;

./phonebook_orig

執行時間:

執行時間比之前縮短約2秒

cache-miss 降為31%:

利用perf找熱點:

經由perf發現findName已經大幅減少佔據系統效能了

gnuplot:

Hash版本(使用djb2)

./phonebook_hash

我們可以發現花在append()的時間比之前還要多 但是findName()所花的時間接進0秒!

cache-miss

cache-miss 比之前更少

perf找熱點

我們可以發現系統把大多數的時間拿去進行hash了,所以append()[下圖]才會比之前再多花一點時間

參考資料

Select a repo