# 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?
>> 請注意記憶體配置的方式 [name=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`