2016q3 Homework1 (phonebook)

contributed by <pzq317>

Reviewed by <aweimeow>

• 作業的格式沒有按照要求 XD 寫上 contribute by 之類的標示
• git commit 有點雜亂，建議可以分開做 commit，結果不需要上傳到 github，可以考慮寫一下 .gitignore
  • .gitignore ref 可以從這邊生出 template 再去修改～～
• 不過蒸陣再食做hash function的時候小寫就有error
  • :s/蒸陣再食做/真正在實作/g
• 而不是順續執行
  • 順序執行 / 依序執行 ？

===

• perf
  

---

• gnuplot

MAKEFILE

• CFLAG
• MAKEFILE請使用TAB

名詞

• cache miss
• collision

a collision or clash is a situation that occurs when two distinct pieces of data have the same hash value, checksum, fingerprint, or cryptographic digest.

• hash function
• L1d cache
• L1i cache
• other level cache
• branch prediction

依據之前的紀錄，猜測最有可能的下一條指令，而不是順續執行

優化方法

---

• smaller struct size
• hash function

smaller struct size

• 將原本128byte的struct size縮小成24byte，讓一個cache中可以中更多個struct減少cache miss的發生．
  

HASH function

• 為什麼要選一個很大的質數會減少collision

• why djb2 times 32 會使效率變佳
  Why are 5381 and 33 so important in the djb2 algorithm?

• 試試看不要5381試試42737

• ＃define 的時候都要是大寫，一開始試小寫還可以，不過蒸陣再食做hash function的時候小寫就有error
  

• 使用hash function可以大量減少find name的時間，不過在append的時候效率會變差．
  

hash function+smaller struct

比起純粹使用smaller struct append的部分慢了一點

• switch 5831 -> 42737