2018q1 Homework1 (phonebook)

contributed by <PunchShadow>

---

Reviewed by raygoah

• 設定及學習 vim 可參考 成大資工 Wiki-vimrc設定教學
• 有提到在最原始的版本中 findName() 的方法是將已排序過的 linked list 以 node by node 的方式進行搜尋，也提到可能可採用 binary search 的方式將時間縮短，建議可以嘗試實作 Binary Search Tree ，並嘗試將資料打亂後觀察結果會有什麼不同
• commit message 的標題雖然打得很清楚，但還需要增加內文，說明實際做了什麼、為什麼怎麼做，以及這麼做所帶來的影響或結果，可參考【譯】如何撰寫Git提交訊息
• 覺得紀錄得很詳細且整理出很多重點，但因為花了較多時間在事前的準備以及熟悉工具，使得實際在嘗試改進 phonebook 的部份比較少，稍微有點可惜，建議有時間可以補齊

Reviewed by rwe0214

• git 的教學可參考 Basic git tutorial
• 內文有提到的想法 binary search ，可以試著觀察已經排序好的資料直接建立 BST 的時間與線性的 linked-list 的差別
• binary search tree 底下也有很多種種類，建議可以觀察這些不同的地方。
• 整份文件紀錄的鉅細靡遺，讓人很好理解重點，也可以讓自己了解自己在哪裡不足，很值得學習！
• 在 Git 和環境安裝 的第四點字打錯了，從新看文件 -> 重新看文件><

Reviewed by workat60474

• 雖然看得出你因為花了很多時間學習一些事前的準備工具，使得實驗在cache 和 效能上的改善較少，但是藉著作業熟悉這些開發工具，也是很有收穫的一件事！
• 除了建議嘗試實作binary search tree之外，也可以閱讀一下資料結構聖經本<Fundamentals of Data Structures in C >，後面部分的章節，有其他Balanced tree的介紹（如Red-Black tree），能夠有效的降低操作的複雜度！
• 希望有時間，可以研究一下，cache的特性，以及為何減少struct size 能夠造成cache misses下降的詳細分析。

實驗環境

$ uname -a
Linux punchshadow-G56JR 4.13.0-36-generic
#40-Ubuntu SMP Fri Feb 16 20:07:48 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

$ lscup
Architecture:            x86_64
CPU 作業模式：             32-bit, 64-bit
Byte Order:              Little Endian
CPU(s):                  4
On-line CPU(s) list:     0-3
Thread(s) per core:      2
Core(s) per socket:      2
Socket(s):               1
NUMA node(s):            1
Vendor ID:               GenuineIntel
CPU family:              6
Model:                   60
Model name:              Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz
Stepping:                3
CPU MHz:                 2793.614
CPU max MHz:             3400.0000
CPU min MHz:             800.0000
BogoMIPS:                5587.22
Virtualization:          VT-x
L1d cache:               32K
L1i cache:               32K
L2 cache:                256K
L3 cache:                3072K
NUMA node0 CPU(s):       0-3
Flags:                   fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti retpoline tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts

不需要附上自己的簡介，但請記得附上你的實驗環境資訊
課程助教

好的感謝助教，第一次還不太熟悉如何交作業 >""<
PunchShadow

Git和環境安裝

• 安裝Lubuntu和Linux tools都相當順利

• 由於對於git完全不熟，根本就是一個初心者的概念，所以得先從最基本的開始練習

  
  1.一開始建立新的respoitory和push pull 測試都還算順利。
  2.後來想要clone老師的phonebook到本地端後，想再push到自己創立的專案中就顯示 fatal: remote origin already exists. 的問題
  3.後來查出是因為remote還未清除，因此使用 $ git remote rm origin來清除origin，在重新add remote origin到自己的專案。

• 完全沒概念之Git快速上手推薦-

• 然後要編輯程式時，發現連vim都不會用，只好從新看文件（也太難過了吧，根本從零開始阿我

  ）

表示你進步的幅度很大，應該要開心

jserv

---

Perf、gnuplot 操作練習

• 一開始照著老師的perf原理與教學實做，發現內文中沒有教如何更改存取權限，所以自己就稍微試了一下，去把perf_event_paranoid設成0，就可以成功操作圓周率的程式了，方法提供給大家

$ sudo sh -c " echo 0 >  /proc/sys/kernel/perf_event_paranoid"

• 一開始在進行 $ make plot 的時候突然彈出了
  make:*** No rule to make target 無法執行的警語，後發現，是之前還不熟悉vim的時候，不小心改到了 phonebook 內的一些東西，導致 make 找不到目標，找的好久都沒發現問題，好險還沒開始寫，只好乾脆直接重新clone一次

• 重新clone完後終於順利跑出人生地一張gnuplot，開始感覺有點厲害

  
  

---

實戰開始！！！

在終於比較清楚 linux 開發環境、git 及一些基礎工具的使用後，終於可以開始進入正題了，在開始之前，感謝 ryanpatiency同學 這篇真的整理得很詳細，讓我這個初心者獲益良多

釐清作業需求

• 了解程式架構

  • 學習 Makefile 運作
  • main.c 主程式架構
  • phonebook_orig.c 之 function
  • phonebook_orig.h 之資料結構

• 改善phonebook_opt.h 內的資料結構

• 降低phonebook_opt.c 內 findName()及 append() 執行時間

---

了解程式架構

• Makefile 理解
  • Makefile基本結構
    • target1 、target2 : 是想要建立的資訊，與目標檔須以 : 隔開，輸入 $ make target1 則可以執行 target1 之 command
    • target之目標檔 ： 具相關性之 object file，可以一個也可多個
    • <TAB> ： 要執行之 command 須以Tab隔開
    • command ： 對目標檔所執行的動作
    • clean : 清除原先目標檔

# comments  
#一些變數宣告

target1: target1之目標檔    
<TAB>command;    
target2: target2之目標檔
<TAB>command;
...
...
clean:
<TAB>rm -rf *.o

• 從phonebook 中的 Makefile 看起

CC ?= gcc
CFLAGS_common ?= -Wall -std=gnu99
CFLAGS_orig = -O0
CFLAGS_opt  = -O0

EXEC = phonebook_orig phonebook_opt

GIT_HOOKS := .git/hooks/applied
.PHONY: all
all: $(GIT_HOOKS) $(EXEC)

$(GIT_HOOKS):
	@scripts/install-git-hooks
	@echo

SRCS_common = main.c

• 1~7 : 基本上都在做變數的宣告，可以看做是為簡化後面的的程式宣告的，後面只要以 $(變數名) 就能取代隴長的指令。而 ?= 的意思未定義時為等號後面值

• 8 : := 為在執行這行時，該變數就已經被決定，不會因程式執行到後面而改變

  參考： makefile賦值運算符號

• 9 : .PHONY 主要是避免和同名文件發生衝突，以及提昇效能，所以.PHONY 是被用來定義假工作目標，這樣 Make 就知道這不是針對檔案

  參考：.PHONY解說

• 10 : 定義 all 為哪些目標

• 12~14 : 在 git/hooks/applied 下自動掛載一個 hook，不顯示執行掛載的指令及文件內的 echo 動作（install-git-hooks 中若成功執行 hook 掛載則會 echo 一個成功的訊息）

  參考：Git Hook Document

• 18~21: 當執行 $ make phonebook_orig 時的需要做的事情，將所有變數展開（可參考下方補充），可以看成以下程式

  ​​​​phonebook_orig: main.c phonebook_orig.c phonebook_orig.h
  ​​​​    gcc -Wall -std=gnu99 -o0 \
  ​​​​        -DIMPL="\"phonebook_orig.h\"" -o phonebook_orig \
  ​​​​        main.c phonebook_orig.c
  

  1. -Wall : 顯示所有警告字樣
  2. -std=gnu99 : 使用C99之規格
  3. -o0 : 還不曉得
  4. -DIML : -D 為定義 marco(巨集)之用，所以這裡將 IMPL 定義為 phonebook_orig.h ，代表其中使用的變數都可以在往後的程式內使用，這就是為何在 main.c 中無定義 entry 卻可以使用的原因
  5. -o : 指定輸出檔名為 phonebook_orig
  6. main.c phonebook_orig.c : 未知

  參考 : GCC and Make

• 後面 : 都是在建立 target 即 輸入 $ make XXX 時會發生什麼事

• 補充與整理：

  • % : 為萬用符號，可以為任意字元，可大幅取代相同或相似的指令
  • @ : 不顯示後面指令名稱（看下例）
  • $< : 為指定第一必要條件檔名（因為使用了萬用符號 %，所以無法明確指出檔名為何，故用此來代表
  • $@ : 為目標檔名（同樣使用萬用符號 %，所以以此表示目標檔名）
  • $^ : 為指定全部必要條件檔名（有可能有多個條件檔）
  ​​​​%.o: %.c
  ​​​​    gcc -c $<
  

  若將上方程式寫入 Makefile中，執行 $ make foo.o ，則系統會去搜尋是否有 foo.c ，若無則無法執行，找到的話便會去執行且印出 $ gcc -c foo.c，其中foo可以換成任何字元皆能做相同指令

  ​​​​$ ls
  ​​​​foo.c
  ​​​​$ make foo.o
  ​​​​gcc -c foo.c
  ​​​​$ ls
  ​​​​foo.c foo.o
  

  若不想顯示 gcc -c foo.c 則改成 @gcc -c foo.c 即可

  在這個Makefile中

  1. $< : foo.c
  2. $@ : foo.o

  參考：Makefile 語法示範 、 Makefile逐步基礎教學、@ symbol in Makefile

  發現 Makefile教學 中的底下的 詳盡語法 連結無法

---

main.c 主程式架構

• <time.h> 和 clock_gettime() 介紹
  首先，先來談談有關 time.h 內的clock，在這個 library 內有定義了以下的 clock

1. CLOCK_REALTIME： 系統根據現在的 wall-clock 所計算出最佳時間，會因為管理者改變時間而被影響， main.c 中就是使用這種 clock 作為 append() 等 function 執行時間

2. CLOCK_REALTIME_COARSE：相較於 CLOCK_REALTIME ，較為不精準但執行較快速

3. CLOCK_MONOTONIC : 系統從一個固定的時間點，對照 wall-clock 所計算出的時間點，不會隨著程式跳躍而改變

4. CLOCK_MONOTONIC_COARSE : 相較於 CLOCK_MONOTONIC ，較為不精準但執行較快速

5. CLOCK_MONOTONIC_RAW : 類似於 CLOCK_MONOTONIC ，但提供更多 raw hardware-based time

6. CLOCK_BOOTTIME : 相同於 CLOCK_MONOTONIC ，不同地方在於它會將系統閒置的時間算入

7. CLOCK_PROCESS_CPUTIME_ID : 計算所有 thread 所佔之 CPU 時間

8. CLOCK_THREAD_CPUTIME_ID : 計算單一 thread 所佔之 CPU 時間

   而在在 <time.h> 這個 libray 中還有定義一個 structure timespec

   ​​​​struct timespec {
   ​​​​    time_t   tv_sec;        /* seconds */
   ​​​​    long     tv_nsec;       /* nanoseconds */
   ​​​​}
   

   所以 17~28 之 diff_in_second() 便是利用 timespec 去計算 append() 和 findName() 執行時間

   參考 :
   CLOCK_REALTIME v.s. MONOTONIC
   $ man clock_gettime 、 man page of clock_gettime()

再來看回 main.c

• 45~50 : 建立一個entry
• 52~54 : 這段的意思相當於清空 cache 內原先有的資料
• 55、63 : 將當時的 CLOCK_REALTIME 分別存於 start 和 end 中
• 56~62 : 建立一個用 linked-list 除存的 phonebook ， append() 則是定義在 IMPL(phonebook_orig.c) 內
• 71~77 : 給定一個 input 為 zyxel 要去 phonebook 內找
  • assert() : 可判斷()內的條件是否成立，若不成立則會中止程式，並在終端機上列印出中止原因

​​​​*    ++79~81++ : 若使用的為 GNUC 的編譯器，則清空 cache 內的資料
​​​​*    ++82~86++ : 計算 findName() 之執行時間
​​​​*    ++88~90++ : 將兩個執行時間寫入 output file 中

---

Phonebook_orig.c 之 function

• entry *findName(char lastName[], entry *pHead)
  比對 pHead->lastName 和 所輸入之 lastName 是否相等，若相等則回傳 pHead 這個 entry ，若不相等則往 pHead->pNext 移動，直到全部 linked list 皆檢查完畢
• entry *append(char lastName[], entry *e)
  將 lastName linked 到 e 之最後面

心得：
從這個搜尋方法來看，屬於最基本的 search in linked-list 的方法，採 node by node，但 linked list 已是 sorted 的話，可能可採用 binary search 的方式將時間縮短

---

Phonebook_orig.h 之 Data Structure

在 phonebook_orig.h 中最主要是定義 entry 這個 data structure ，除了用來比較的 lastName 外， 還有其他的資訊及一個連結下個 node 的 link

心得：
想要降低 cache miss，可以從加大 block 或是縮小一個 entry 的資料量開始，從前人的實驗中也可看出這方法是可行的，因此往後應該會先從縮小 entry 的資料量開始著手

---

Astyle-Git 小插曲

寫到這邊，不得不小小抱怨一下關於 vim 設定和 coding style 的檢查方式（不過也應該是自己沒熟悉 vim 的關係

），以下開始講故事時間

講故事時間開始 :

由於是新手，稍加利用網路上的資源簡單的設定了一下我的 vim 就準備開始寫 code 了，但殊不知悲劇就此發生…

先從我最一開始的 vimrc 開始說起好了，以下是一部分的設定檔

set nu
set cursorline
set tabstop=4

一開始看著林林總總的設定變數，完全不知道該如何下手阿，於是就選了幾個看似重要的設定上去，這邊我有稍微注意到 tab 跟 space 之間的關係，所以還特別去加上了 set tabstop=4 這條，但就在我要進行 git commit 的時候，竟然出現 coding style 不一致的情況（心裡 os：我才新增個沒幾行，你就跟我說 style 出問題

)，仔細一看，好像是沒對齊，發現 對齊的 tab 大小要另外設定，然後在 vimrc 內加上這幾行就給過了，弄的我心好累

set expandtab
set shiftwidth=4

推薦

線上 vim 配色工具
參考：將 vim tab 轉成 space

---

Phonebook_opt.h 之改良

為了驗證 entry 變小可導致 cache miss 下降，我先將 phonebook_orig.h 中，不會用來比較的部份存在另外一個 node 中，而 phonebook_opt.c 則是先用 phonebook_orig.c

/* Define a new struct to include the detail of phonebook. */
typedef struct __PHONE_BOOK_DETAIL{
    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];
}detail;

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __PHONE_BOOK_ENTRY *pNext;
    /* Linking to the detail. */
    struct __PHONE_BOOK_DETAIL *pDetail;
    
} entry;

原先的 cache miss performance

1,178,508        cache-misses      # 83.173 % of all cache refs ( +-  0.28% )
1,416,940        cache-references                               ( +-  0.22% )
276,900,133      instructions      # 1.34  insn per cycle       ( +-  0.01% )
206,135,397      cycles                                         ( +-  0.27% )

0.062861794 seconds time elapsed                                ( +-  0.31% )

減小 entry 後的 performance

87,989          cache-misses      # 41.687 % of all cache refs ( +-  1.08% )
211,070         cache-references                               ( +-  0.81% )
252,100,537     instructions      # 1.93  insn per cycle       ( +-  0.00% )
130,667,427     cycles                                         ( +-  0.56% )

0.039911044 seconds time elapsed                               ( +-  0.57% )

時間比較

由以上的數據可以看出當 entry 縮小時，cache miss 能有效的減少，執行時間也可以縮短

---

心得與未來改進

時間真的過得很快，兩個禮拜的時間一下過不見惹

，感覺才剛進行程式的改進就到了 deadline 了，說來慚愧，光是把一些環境和工具的搞定，了解整個 phonebook 的運作和看完了文件和影片，就花了我大部分的時間，像是在理解 git 的運作和使用上，就整整花了一整天（還不見得都會用QQ）。而在真正要去修改程式時，雖然有一些想法，不過礙於一些程式能力，都沒辦法在短時間內實現出來，真是 書到用時方恨少阿，希望在比較熟悉 linux 和 vim 之後，下次作業能做的更好