2018q1 Homework1 (phonebook)

2018q1 Homework1 (phonebook) === contributed by <`piggyking1421`> ### Reviewed by `nashi5566` * cache 分成 L1i L1d 的理由可以思考一下 instruction 和 data 之間被使用時有什麼行為差異 (eg. read or write) ### Reviewed by `0922james0922` * 應該確實將改正過程跟結果放上去，不該只有想法跟理念，確實實做吧！！ ## 系統環境 ``` $ uname -a Linux pc 4.10.0-28-generic #32~16.04.2-Ubuntu SMP Thu Jul 20 10:19:48 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux $lscpu Architecture: x86_64 CPU 作業模式： 32-bit, 64-bit Byte Order: Little Endian CPU(s): 8 On-line CPU(s) list: 0-7 每核心執行緒數： 2 每通訊端核心數： 4 Socket(s): 1 NUMA 節點： 1 供應商識別號： GenuineIntel CPU 家族： 6 型號： 58 Model name: Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz 製程： 9 CPU MHz： 2136.828 CPU max MHz: 3900.0000 CPU min MHz: 1600.0000 BogoMIPS: 6784.41 虛擬： VT-x L1d 快取： 32K L1i 快取： 32K L2 快取： 256K L3 快取： 8192K NUMA node0 CPU(s): 0-7 ``` ## 前置作業 * 順利安裝 Lubuntu 雙系統，不過一兩週後因為某些原因要換台電腦使用，希望不會有什麼意外 * 由於對 git 和 linux 指令以及 vim 等工具都很不熟，剛開始完全不知道要怎麼下手，感謝[`ryanpatiency`](https://hackmd.io/s/B1SSiTM_G#)的重點整理讓我能有個大概，但許多教學看了卻都還沒練習，只知道了比較基本的操作，剩下的要邊做邊讀了 (感覺一週16小時遠遠不夠 CS:APP 也還沒讀完呢 ## 基本練習先以原始版本的檔案練習先清空 cache $ echo 1 | sudo tee /proc/sys/vm/drop_caches $ make run 其中一筆執行時間及資料大小 ``` size of entry : 136 bytes execution time of append() : 0.067350 sec execution time of findName() : 0.005744 sec ``` $ make cache-test 剛開始執行時因為權限無法執行 ``` Consider tweaking /proc/sys/kernel/perf_event_paranoid, which controls use of the performance events system by unprivileged users (without CAP_SYS_ADMIN). The current value is 3: -1: Allow use of (almost) all events by all users >= 0: Disallow raw tracepoint access by users without CAP_IOC_LOCK >= 1: Disallow CPU event access by users without CAP_SYS_ADMIN >= 2: Disallow kernel profiling by users without CAP_SYS_ADMIN Makefile:33: recipe for target 'cache-test' failed make: *** [cache-test] Error 255 ``` 剛開始直接用 sudo 去 make，後來參照[`team6612 `](https://hackmd.io/Yuo-57rAQ3q79A-20oVLTg?view#)改好權限即可直接用user執行 ``` Performance counter stats for './phonebook_orig' (100 runs): 2,055,227 cache-misses # 94.373 % of all cache refs ( +- 0.08% ) 2,177,780 cache-references ( +- 0.13% ) 261,722,381 instructions # 1.31 insn per cycle ( +- 0.02% ) 200,287,265 cycles ( +- 0.24% ) 0.056767669 seconds time elapsed ( +- 1.97% ) ``` 可看到 chche-misses 機率約為94% $ make plot ![](https://i.imgur.com/a5Ijp2f.png) ## 作業要求 * 降低 findname( ) 的 cache miss * 縮短 append( ) 時間 * 引入多項效能改進方式並進行比較 * 用其他資料結構改寫 e.g. binary search tree * 使用 hash function 加速查詢 * 嘗試字串壓縮 ## Cache 改善效能前發現對cache印象有點模糊，看了[ Cache 原理和實際影響](https://hackmd.io/s/HkW3Dr1Rb#)和[ Cache 原理和實驗](https://hackmd.io/s/S14L26-_l#)中的一些參考資料釐清了一些基本觀念 * L1 Cache 分成 L1i 和 L1d ， L1i ( i for instruction )用來放指令， L1d ( d for data )用來放資料，暫時想不到這樣分有哪些好處 * CPU 執行運算時會先到 L1i 看接下來要做的指令，再依照指令到 L1d 中尋找資料，若找不到便向 MMU (記憶體管理單元)請求資料，MMU 會到TLB (存放虛擬記憶體位址到實體記憶體位址的分頁表快取)，若在 TLB 中找到 (TLB hit)，便依序到L2 , L3 , 記憶體請求資料，若是 TLB 中沒有要找的虛擬地址(TLB miss)，MMU 便會去實體記憶體中的分頁表找，並且存入TLB。 * 看文章的意思似乎是 L1 中放的是虛擬地址，而其餘的是實體位址，為何？ * ==cache line== 是 cpu cache 中的最小單位，多為 64 Bytes * 我的電腦 L1i 和 L1d 皆為 32k，也就是各有500個 cache line * 我的 CPU i7-3770 是 Ivy Bridge 架構， cache line是64 Bytes ，使用的 mapping function 是 8-way associative ## Makefile * 在看 phonebook 的 makefile 時候覺得有點難懂，所以紀錄一下。 * 看[ Makefile 語法和示範](https://hackmd.io/c/rJKbX1pFZ/https%3A%2F%2Fhackmd.io%2Fs%2FSySTMXPvl)之後還是很模糊，可能我的背景知識不太夠，或是因為我可憐的語文理解能力，之後另外查了[ GNU Make info](https://www.gnu.org/prep/standards/)，但是發現實在是太多了，決定對照其他資料，遇到問題在看這個info文件 * [ Makefile 語法和示範](https://hackmd.io/c/rJKbX1pFZ/https%3A%2F%2Fhackmd.io%2Fs%2FSySTMXPvl)裡面的參考資料的==詳盡語法==好像失連了？ * Makefile 基本語法 * 最主要大概就是 ```= target : 相依檔案 command ``` * ==target==通常是要產生的文件名稱或是一個動作的名稱 * 當具備 target 需要的相依檔案，就會去執行command，並產生target檔案 * 相依檔案也會有target，像是 ```= test : a.o b.o command a.o : a.c gcc a.c -o a.o b.o : b.c gcc b.c -o b.o ``` * a.o 和 b.o 就是產生test的相依檔案的過程target，當 test 沒有 a.o 和 b.o 時，便會去執行 a.o 和 b.o 兩個 target，而test是最終需要的target * 也能使用 make a.o 單獨執行其中一個target，以 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 phonebook_orig: $(SRCS_common) phonebook_orig.c phonebook_orig.h $(CC) $(CFLAGS_common) $(CFLAGS_orig) \ -DIMPL="\"$@.h\"" -o $@ \ $(SRCS_common) $@.c phonebook_opt: $(SRCS_common) phonebook_opt.c phonebook_opt.h $(CC) $(CFLAGS_common) $(CFLAGS_opt) \ -DIMPL="\"$@.h\"" -o $@ \ $(SRCS_common) $@.c run: $(EXEC) echo 3 | sudo tee /proc/sys/vm/drop_caches watch -d -t "./phonebook_orig && echo 3 | sudo tee /proc/sys/vm/drop_caches" cache-test: $(EXEC) perf stat --repeat 100 \ -e cache-misses,cache-references,instructions,cycles \ ./phonebook_orig perf stat --repeat 100 \ -e cache-misses,cache-references,instructions,cycles \ ./phonebook_opt output.txt: cache-test calculate ./calculate plot: output.txt gnuplot scripts/runtime.gp calculate: calculate.c $(CC) $(CFLAGS_common) $^ -o $@ .PHONY: clean clean: $(RM) $(EXEC) *.o perf.* \ calculate orig.txt opt.txt output.txt runtime.png ~ ``` * 若是只 make clean (第49行)，因為沒有相依檔案，便只會執行 clean 中的 command * 因為並沒有叫做 clean 的檔案，因此使用 ==.PHONY==可以使 clean 變成一個"假的" target，當 make clean 的時候會不管是否有 clean 這個檔案，都會執行 clean 這個 target。可以避免有同樣叫做 clean 的檔案存在，導致 clean 不執行。 * ==.PHONY==也可以讓make一次默認執行多個 target，第9~10行便是讓 all 變成假的 target，不會產生 all 檔案，可是 all 又和三個檔案有相依關係，所以會執行3個 target。 * 執行 target 時除了相依檔案不存在時會影響要執行的部份，makefile 也會自行判斷 target 與相依檔案之間的新舊程度去決定是否要執行相依檔案的 target。若是 target 比相依檔案都來的新，那就不會再次執行那個target。可以減少不必要的編譯量。 * 而若是 make plot 便會去找 output.txt，找不到就會執行 output.txt 這個 target，且還會去找 calculate 和cache-test 存不存在，以此類推直到所有相依檔案都存在或是相依檔案比target舊為止。 * 1~8行都是在宣告變數和指定值，使用時要以$(變數名稱)的方式使用，有以下幾種 * = 一般的給予變數初始值，會在整個 makefile 展開後才決定變數的值，也就是 makefile 中最後被指定的值 * := 在 makefile 展開途中就決定變數的值 ``` = x = abc y = $(x) bar x = xyz # 這時 y 的值為 xyz bar ``` 但若是使用了:= ``` = x := abc y := $(x) bar x := xyz # 這時 y 的值為 abc bar ``` 也就是說變數的值會和其被指定值的位置有關係 * ?= 若變數尚未被指定值，則指定其值，若已有值則忽視此行 * += 將值加在現在變數已有的值的後方 * **自動化變數**，用來省略檔名，makefile 中大量使用，剛開始看的時候讓我眼花撩亂，有以下幾種 * $@ 當下那個 target 的檔名 * $< 當下那個 target 的第一個相依檔名 * $^ 當下那個 target 中所有相依檔的檔名，會以空格分開 * $* 最主要的 target 檔名 * **反斜線** * \ * **換行符**，雖然 makefile 沒有限制命令的長度，但為了可以不用一直向右滾螢幕才看得到命令，使用 \ 可以把指令打在下一行，但實際上仍然會在同一行，像是第18~26行。 * **轉義字元**　在一些有特殊功能的符號前面加上反斜線可以使其失去其意義，並顯示出來，像是＃原本是用來表示該行是註釋，而打 ==\\#== 即可打出# * **萬用字元** * % 可以取代任何字元，像是%.c便可以代表所有.c檔 * **特殊字元** * ==@== 一般make執行的command會顯示出來，而在command前面加上@就可以不顯示執行的指令 * ==-== 一般make只要遇到錯誤就會中斷執行，如果有不影響make的指令在前方加上 - 即可使指令即使錯誤仍然可以繼續make * 之前看影片老師說要記得安裝 git.hook，這次作業上卻寫說執行 make 會自動安裝 hook ，看到 Phonebook 的 makefile 第8和12~14行才知道是在 makefile 中利用 scripts 去安裝，了解了 makefile 寫好可以省很多事，不過 scripts 還看不懂，之後應該還要看 git.hook 的 info 和一些 shell 的寫法。 * 第20和25行的 -D 是 gcc 的定義巨集的語法，[GCC Command Options](https://gcc.gnu.org/onlinedocs/gcc-2.95.2/gcc_2.html)，原本我還以為是makefile的。 * 第20行和25行還看不懂，知道是定義IMPL但是看不太懂那些雙引號和反斜線 * 還有許多高深的用法，但是在沒有練習的情況下感覺記不住，上面的內容能夠大概看懂 phonebook 的 makefile 了 ## 實驗 ### 方法一改動entry size * 在原本的phonebook_orig中 ```clike= typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; 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]; struct __PHONE_BOOK_ENTRY *pNext; } entry; ``` * 資料大小直接相加應該會為 131 bytes，但使用sizeof 得到的卻是 136 bytes，去查了是因為記憶體對齊 (alignment)的關係，我的電腦是64位元，因此會以8 bytes 當作一個 word，因為每一筆資料大小不相同，而為了不讓一筆資料( e.g. int )在記憶體分配的時候橫跨超出一個word，導致搜尋一個資料要存取記憶體兩次(存取兩個 word size)，記憶體對齊會加上 padding byte 使資料不會橫跨 word ，因此這裡才會是 136 bytes，在之後打程式的時候也許能盡量分配資料量，減少padding bytes的出現 * 我的電腦是 L1大小是 32 KB，cache line 是 64 bytes，使用的是 8-way associative，一筆 entry 是 136bytes，也就是說一筆entry會佔用3個cache line 卡住了　我再想想 ## 待查問題 * L1 cache 分成 L1i 和 L1d 有哪些好處？我的猜測是因為 instruction 和 data 的更新頻率會相差很多，instruction的重複性比較高，替換頻率比較低，之後再詳細查閱 ## Reference [CPU Cache 原理探討](https://hackmd.io/s/H1U6NgK3Z#) [Makefile 心得](https://wwssllabcd.github.io/blog/2016/10/03/how-to-write-make-file/) [跟我一起写Makefile:书写规则](http://wiki.ubuntu.org.cn/%E8%B7%9F%E6%88%91%E4%B8%80%E8%B5%B7%E5%86%99Makefile:%E4%B9%A6%E5%86%99%E8%A7%84%E5%88%99) [Data structure alignment](https://en.wikipedia.org/wiki/Data_structure_alignment)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.