2016q3 Homework1 (phonebook)

contributed by <SarahCheng>

github:
https://github.com/SarahYuHanCheng/phonebook.git

Reviewed by <`snoopy831002`>

可以在github網站創立好repo之後再clone到本地端會比較方便喔
改良之後的cache miss還是太高(74%?)

好的,謝謝你！再用hash table試試

開發記錄

9/24 watch the video, register accounts
9/25 install lubuntu

不需要在內文標注「日期」，HackMD 會追蹤，應該紀錄「主題導向」的實驗和參考資料 jserv

9/26 problem:
- wifi setting
- ~~螢幕畫面截取~~
- ~~linux cmd instruction不熟~~
- problem:
  - $make 沒有出現"[sudo] password for"
  - $make plot沒有runtime.png,只有script/runtime.gp
    
    之後有了
  - $ lscpu | grep cache沒有反應..
    
    $ lscpu ~~| grep cache~~即可Tue, Sep 27, 2016 3:37 PM
  - ~~用astyle沒反應~~：因為少了空白
    astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none空格*.[ch]
  需要解釋「沒反應」為何 jserv
- reference:
  - linux指令
  - 螢幕截取-shutter
  - makefile裡GCC
  - TempoJiJi同學的開發記錄
  - ruby0109同學的開發記錄
  - c14006078同學的開發記錄

開發環境

CPU: Intel® Core™ i7-3520M cpu @ 2.90GHz
MEM: 125GB
Cache:
- L1d cache: 32K
- L1i cache: 32K
- L2 cache: 256K
- L3 cache: 4096K

使用 lscpu 和 sudo lshw 可看到硬體資訊

修改結構大小降低cache miss

steps:
1.修改phonebook_opt.h如下圖


















typedef struct __PHONE_BOOK_DETAILS {
    char firstName[16];
    char email[16];
    char phone[10];
    char cell[10];
    char addr1[16];
    char addr2[16];
    char city[16];
    char state[2];
    char zip[5];
} Details;

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __PHONE_BOOK_ENTRY *pNext;
    Details *details;
} entry;

2.phonebook_opt.c的append()和findName()複製orig版本
3.記得解開 the comment #define OPT 1
4.清空cache:

$echo 1 | sudo tee /proc/sys/vm/drop_caches

5.make plot 即得下列資訊

size of entry : 128 bytes
execution time of append() : 0.087335 sec
execution time of findName() : 0.005850 sec

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

         1,426,148      cache-misses              #   82.108 % of all cache refs      ( +-  0.48% )  (74.11%)
         1,736,927      cache-references                                              ( +-  0.54% )  (74.39%)
       305,721,382      instructions              #    1.47  insns per cycle          ( +-  0.18% )  (77.20%)
       207,828,652      cycles                                                        ( +-  0.24% )  (76.70%)

       0.068671339 seconds time elapsed                                          ( +-  1.91% )

size of entry : 24 bytes
execution time of append() : 0.036632 sec
execution time of findName() : 0.002973 sec

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

           232,097      cache-misses              #   74.079 % of all cache refs      ( +-  0.37% )  (74.46%)
           313,312      cache-references                                              ( +-  0.51% )  (74.79%)
       278,824,752      instructions              #    1.75  insns per cycle          ( +-  0.28% )  (76.75%)
       159,089,222      cycles                                                        ( +-  0.28% )  (77.42%)

       0.050675378 seconds time elapsed                                          ( +-  1.75% )

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

         1,469,675      cache-misses              #   81.589 % of all cache refs      ( +-  0.61% )
         1,801,320      cache-references                                              ( +-  0.60% )
       310,382,365      instructions              #    1.45  insns per cycle          ( +-  0.01% )
       214,099,227      cycles                                                        ( +-  0.17% )

       0.070388042 seconds time elapsed                                          ( +-  2.18% )

           235,670      cache-misses              #   79.971 % of all cache refs      ( +-  0.22% )
           294,695      cache-references                                              ( +-  0.21% )
       288,137,012      instructions              #    1.78  insns per cycle          ( +-  0.00% )
       162,238,829      cycles                                                        ( +-  0.08% )

fgets

Use fgets characteristic to delay the replacing '\n' with '\0'.

利用 fgets的特性，man 完就會發現它會在讀到 newline 或是 EOF停下來並且在他們後面會多種一個 '\0'，接著的 code 就是把 newline 變成 '\0'，我們延後替換 newline，我操作只比較前面的長度，真的找到了再把 newline 換掉即可。

main.c


while (fgets(line, sizeof(line), fp))
e = append(line, e);

phonebook_opt.c






/* because the assert test, we can’t modify the strcut*/
if (strncasecmp(lastname, pHead->lastName, len) == 0 &&
    (pHead->lastName[len] == ’\n’ ||
     pHead->lastName[len] == ’\0’)) {
    pHead->lastName[len] = ’\0’;
   return pHead;

原本的程式是將字典直接建好，這邊我們先建檢索，等到findName找到時我們再去補上他的資料，這樣也能減少 append()。

Q1:error: stray ‘342’ in program

A:ascii characters missing，程式碼用複製貼上，導致'\n'的引號格式不符
Q2:Assertion failed，還不知道怎解決

size of entry : 24 bytes
phonebook_opt: main.c:89: main: Assertion `0 == strcmp(findName(input, e)->lastName, "zyxel")' failed.
./phonebook_opt: 已經終止

6.用astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch]
7.ln -sf ../../scripts/pre-commit.hook .git/hooks/pre-commit

Hash

不明原因



error: conflicting types for ‘hashAppend’
    int *hashAppend(char *lastName, hashTable *ht)

無解,也許是編譯警告太多了

GIT

step:

1.指令參考
2.本機與github同步

貼id_rsa.pub所有內容到github上key的設定

2.若出現fatal: Not a git repository (or any of the parent directories): .git，因為還沒有.git目錄，要先git init
3.

fatal: The current branch master has no upstream branch.
To push the current branch and set the remote as upstream, use

   git push --set-upstream phonebook master