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
## 作業要求
* 降低 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)
Sign in with Wallet
Connect another wallet