2016q3 Homework 1 (phonebook)

contributed by <ChienChing>

架設環境

~

初步了解phonebook程式碼

• main.c

  assert(findName(input, e) && "Did you implement findName() in " IMPL "?");
  assert(0 == strcmp(findName(input, e)->lastName, "zyxel"));

assert是用來將檢查某些變數是否正確，若是不正確即跳出程式碼並印出資訊。

method1-將struct變小

想法是將struct變小後，cache能夠容納的資料筆數就會變多，cache missed rate就能夠降低。所以把struct中除了lastName之外的都刪除了，cache missed rate的確是降低了20%左右，但是findName()的時間沒有任何改變… why?

請注意記憶體配置的方式 jserv

…在看了看Makefile後，發現我沒有定義OPT所以結果都沒丟到opt.txt內，導致算出來一模一樣啊 Orz

經過這個笨點終於使得作業得以進行下去，以下是將Struct變小後的圖

method2-hash table

想法：建立一個bucket為26的hash table，利用Name的第一個位元的Ascii碼當成hash table的index加入鍊結串列中，搜尋也是使用Name的第一個位元之Ascii碼去該bucket中尋找。

縮小struct後，再加入hash table後的perf資訊

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

​​​​     3,419,092      cache-misses              #   93.015 % of all cache refs      ( +-  0.02% )
​​​​     3,675,840      cache-references                                              ( +-  0.05% )
​​​​   261,214,545      instructions              #    1.32  insns per cycle          ( +-  0.02% )
​​​​   197,357,309      cycles                                                        ( +-  0.15% )

​​​​   0.075308425 seconds time elapsed                                          ( +-  0.16% )

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

​​​​       411,564      cache-misses              #   74.904 % of all cache refs      ( +-  0.29% )
​​​​       549,458      cache-references                                              ( +-  0.46% )
​​​​   187,801,190      instructions              #    1.64  insns per cycle          ( +-  0.11% )
​​​​   114,783,279      cycles                                                        ( +-  0.23% )

​​​​   0.044134299 seconds time elapsed                                          ( +-  0.27% )

output.txt

​instrut		org		opt
​append()	0.053186	0.042253
​findName()	0.005989	0.000025

what?怎麼會append降低了…?

Questions

• Q1

在撰寫hash table進去main.c的時候想要定義bucket的長度，所以使用了

​​​​#define BUCKET_SIZE 26

但是不知為何make不過…，以下是error:

​error expected ')' before numeric constant

• Q2

對於一開始的main()中的free struct，這樣寫是對的嗎?

​if (pHead->pNext) free(pHead->pNext);
​free(pHead);

如此一來不是只free到兩個節點而已嗎?

tags: chienching