2017q1 Homework1 (phonebook)

contributed by <njjack>

進度嚴重落後，請快快跟上
課程助教

Reviewed by `natetang`

在 mian.c 裡的第47行，malloc有可能失敗，應該要處理這種情況
在 phonebook_orig.c 裡的第12行，應該可以有更簡潔的寫法
未回答作業所要求之問題

前置作業

開發環境

Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              61
Model name:            Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz
製程：              4
CPU MHz：             887.573
CPU max MHz:           2700.0000
CPU min MHz:           500.0000
BogoMIPS:              4389.48
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           3072K
NUMA node0 CPU(s):     0-3

original版本

先清空cache
$ echo 1 | sudo tee /proc/sys/vm/drop_caches

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

結果：

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

         3,442,741      cache-misses              #   92.939 % of all cache refs      ( +-  0.02% )
         3,704,301      cache-references                                              ( +-  0.06% )
       262,283,146      instructions              #    1.39  insn per cycle           ( +-  0.02% )
       188,777,340      cycles                                                        ( +-  0.10% )

       0.072757781 seconds time elapsed                                          ( +-  1.12% )

請詳細閱讀作業要求(文字訊息請避免用圖片來表示，否則不好搜尋和分類)，這是課程最低要求課程助教
好的
njjack

清空後第一次執行的時間：

size of entry : 136 bytes
execution time of append() : 0.069368 sec
execution time of findName() : 0.005774 sec

優化實驗

方案一：調整 struct

中英文字間請以空白隔開
課程助教

由於 findname() 只用到 lastname 和 pointer,因此將用不到的其他資料存到另一個 struct,並在原來的 struct 多設一個指向新 struct 的pointer
,則可縮小原本的struct,如結果所示size of entry降低到32 bytes,cache miss也降到70.706%

結果：

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

         1,210,488      cache-misses              #   70.706 % of all cache refs      ( +-  0.16% )
         1,712,005      cache-references                                              ( +-  0.35% )
       244,564,624      instructions              #    1.86  insn per cycle           ( +-  0.02% )
       131,582,410      cycles                                                        ( +-  0.66% )

       0.051964711 seconds time elapsed                                          ( +-  1.22% )

size of entry : 32 bytes
execution time of append() : 0.065296 sec
execution time of findName() : 0.002353 sec