2017q1 Homework1 (phonebook)

contributed by <ryanpatiency>

Reviewed by `changyuanhua`

我認為實做方面可以多添加一些方法，不要只用一個做觀察比較
記得問題的第二題，以及第三題還沒有回答

開發環境

Cache:

Intel® Core™ i5-4210U CPU @ 1.70GHz × 4

L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              3072K

linux kernel：

$ uname -a

Linux  4.4.0-62-generic

目標

作業要求 B01: phonebook

觀察程式 phonebook中的 phonebook_orig 的 cache miss 以及 append()和findName()的執行時間
修改 phonebook_opt.c 和 phonebook_opt.h 兩個檔案，降低 cache miss 和findName()的執行時間，並使append()的執行時間不增加太多
以 gnuplot 繪製效能分析圖表

如何觀察程式效能

觀察 Makefile ，發現：

編譯：可用make phonebook_orig來 compile phonebook_orig ，其中的-DIMPL $@.h目的是用來指定 Micro IMPL 的值
執行：可用make run來執行程式，其中echo 3 | sudo tee /proc/sys/vm/drop_caches功能可見這裡，
觀察 cache miss ：可用make cache-test，會重覆執行 orig 和 opt 各一百次，將結果寫進 orig.txt 和 opt.txt，記錄四個 event: cache-misses,cache-references,instructions,cycles ，印出結果
畫圖：可用 make plot畫圖，會執行 cache-test ,並畫圖

修改前的程式效能

findName()和append()的執行時間:

size of entry : 136 bytes
execution time of append() : 0.068975 sec
execution time of findName() : 0.006140 sec

其中append()是用來將 DICT_FILE (這裡是./dictionary/words.txt) 建立成資料結構(這裡是linked list)，而findName()是用來在此資料結構尋找含一名字的節點

cache miss:

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

         1,260,786      cache-misses              #   88.433 % of all cache refs      ( +-  0.43% )
         1,425,695      cache-references                                              ( +-  0.36% )
       261,104,813      instructions              #    1.35  insns per cycle          ( +-  0.02% )
       194,024,625      cycles                                                        ( +-  0.47% )

       0.076814845 seconds time elapsed                                          ( +-  0.62% )

實驗過程

實作一：減少資料節點的大小

重複共筆demo中的優化版本 1 的實驗

cache miss:

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

           153,395      cache-misses              #   29.770 % of all cache refs      ( +-  0.86% )
           515,261      cache-references                                              ( +-  1.02% )
       244,213,713      instructions              #    1.63  insns per cycle          ( +-  0.02% )
       149,662,137      cycles                                                        ( +-  1.04% )

       0.062095272 seconds time elapsed                                          ( +-  1.40% )

可見 cache miss 從 88% 減為 30%

plot:

可見findName()的執行時間從 0.006255 減為 0.002870 (s)

實作二：

回答問題

Q1. 有代表性嗎？跟真實英文姓氏差異大嗎？
Ans: words.txt 中的名字前五個分別是：

aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa

我覺得沒有代表性，與真實名字差異很多。
Q2. 資料難道「數大就是美」嗎？
Ans:
Q3. 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
Ans:

參考資料

0140454
共筆demo