2017 q1 homework(phonebook)

contributed by <asssde2002>

Reviewed by henry0929016816

• 可以用 lscpu 這個指令取得電腦相關的資訊，例如 L1 cache 的大小
• git commit 只寫了一個 add another struct 看不出來目的是為什麼，可以再底下加入相關的資訊，例如 修改 data struct 是為了減少 cache miss

github

請加快進度!! 進度停在六天前!
課程助教

開發環境

請列出硬體相關資訊，如：cache, memory
課程助教

Original

• 執行 :

$ ./phonebook_orig

• 得到的結果：

size of entry : 136 bytes
execution time of append() : 0.045063 sec
execution time of findName() : 0.005203 sec

• Cache-test :

$ sudo perf stat --repeat 100 -e cache-misses,cache-references,instructions,cycles ./phonebook_orig

           567,234      cache-misses              #   64.188 % of all cache refs      ( +-  1.19% )
           883,711      cache-references                                              ( +-  0.36% )
       262,098,055      instructions              #    1.32  insn per cycle           ( +-  0.03% )
       198,258,590      cycles                                                        ( +-  0.58% )

       0.066059274 seconds time elapsed                                          ( +-  0.60% )
       

發現cache-misses有64.188%

Optimization

1.Struct

從程式碼當中發現在執行 findname() 時只會用到 lastname 而已，但是其他的宣告也要跟著被讀取，因此造成整個效能降低，所以另外建構一個 struct 來宣告，如此就可以讓整體效能提升。

• 執行時間

size of entry : 32 bytes
execution time of append() : 0.040180 sec
execution time of findName() : 0.002094 sec

• Cache-test

  ​​​​​​     127,624      cache-misses              #   29.817 % of all cache refs      ( +-  0.67% )
  ​​​​​​     428,016      cache-references                                              ( +-  0.67% )
  ​​​​​​ 243,002,108      instructions              #    1.77  insn per cycle           ( +-  0.02% )
  ​​​​​​ 137,275,891      cycles                                                        ( +-  0.63% )
  
  ​​​​​​ 0.045749571 seconds time elapsed                                          ( +-  0.67% )
  

得到的結果告訴我們 cache-misses 從原本的 64.188% 降到了 29.817% 下降了將近 35%

• Plot

進度加快亮谷

2.Binary Search Tree

3.Hash Function

4.壓縮

參考資料