# 2020q3 Homework3 (dict)
contributed by < `ignite1771` >

## 分析 Makefile: perf 在 `make plot` 的行為

# REMINDER: some contexts of Makefile are omitted.

TESTS = test_common

TEST_DATA = s Tai

OBJS_LIB = \
    tst.o bloom.o

# Control the build verbosity
ifeq ("$(VERBOSE)","1")
    Q :=
    VECHO = @true
else
    Q := @
    VECHO = @printf
endif

test_%: test_%.o $(OBJS_LIB)
        $(VECHO) "  LD\t$@\n"
        $(Q)$(CC) $(LDFLAGS)  -o $@ $^ -lm

plot: $(TESTS)
        echo 3 | sudo tee /proc/sys/vm/drop_caches;
        sudo perf stat --repeat 100 \
                -e cache-misses,cache-references,instructions,cycles \
                ./test_common --bench CPY $(TEST_DATA) \
                | grep 'ternary_tree, loaded 206849 words'\
                | grep -Eo '[0-9]+\.[0-9]+' > cpy_data.csv
        sudo perf stat --repeat 100 \
                -e cache-misses,cache-references,instructions,cycles \
                ./test_common --bench REF $(TEST_DATA)\
                | grep 'ternary_tree, loaded 206849 words'\
                | grep -Eo '[0-9]+\.[0-9]+' > ref_data.csv

### 理解過程：$(TESTS)
根據其對應，首先要弄清楚 `test_%` 這個 target 在做什麼:
- 為什麼呢？首先了解 `%` 是萬用字元，代表所有可能字串 (e.g. 例如 test_common 是 test_% 可能的字串之一), 所以 $(TESTS) 變數對到 test_common 值再對到 test_% 此 target, 並且因此會產生其相依目標檔 (prerequisites) 為：
- `test_%.o`
- `$(OBJS_LIB)`

- 至於 `$(VECHO)` 顧名思義為 Verbose Echo, 我們如果給環境變數 `make VERBOSE=1` 時其值為 `@true` , 探討 Makefile 為何有 `@true` 與 `@false` 兩個值的作用：
- 特別字元 `@` 會讓執行的指令不顯示在 stdout 上面
- 參考 [What is “@false” and “@true” in makefile?](https://stackoverflow.com/questions/49756183/what-is-false-and-true-in-makefile) 得知 Makefile 遇到 `@true` 及 `@false` 時分別會呼叫 shell built-in 的 ELF (Executable and Linkable Format) `true` (指令繼續執行，結束後返回 status code = 0) 以及 `false` (指令失敗，返回 status code = 1)
- 可用在終端機用 `$?` 來看上一次指令返回的 status code

- 至於 `" LD\t$@\n"`, 這邊就是如果沒有給 VERBOSE 的話那就會 printf 出來這字串到 stdout
- `$@` 是一個自動化變數，對應到工作目標檔名 (target), 以此例即為 `test_%`

- 至於 `$(Q)` 顧名思義代表 Quiet, 探討為何要用 `:=` 來 assign 其值呢？:
- 參考 [Makefile的賦值運算符(=, :=, +=, ?=)](http://dannysun-unknown.blogspot.com/2015/03/makefile.html) 得知：
- `=` 會讓變數的值在 Makefile 完全展開後才決定
- `:=` 會讓變數的值取決於其在 Makefile 中的位置

簡單的例子如下：

        # =
        x = hello
        y = $(x) world!
        x = hi

        all:
             @echo $(y)
        # make all 會得到 stdout = hi world
        
        # :=
        x := hello
        y := $(x) world!
        x := hi

        all:
             @echo $(y)
        # make all 會得到 stdout = hello world

:::warning
判斷在此例 Makefile 中 Q 之內含值指派選用其一應該皆沒有差別，因為非 if 即 else 成立，不知為何還要特別使用 `:=` 呢？
> 程式碼是寫給你們研究和改進的，不是拿來背誦，請不要用探究古文的方式推敲，有想法就去做實驗
> :notes: jserv

我設計實驗 Shell Script 如下，並將用 diff 工具來觀察 stdout 的不同：

    make all
    make clean
    make test
    make clean
    make bench
    make clean
    make plot
    make clean

    make all VERBOSE=1
    make clean
    make test VERBOSE=1
    make clean
    make bench VERBOSE=1
    make clean
    make plot VERBOSE=1
    make clean

- **Control Group**: 原本 Makefile
- **Treatment Group**: 將內容 `:=` 都替換成 `=` (vim 指令：`:%s/:=/=/g`) 的 Makefile

        @@ -6,14 +6,14 @@ CFLAGS = -O0 -Wall -Werror -g

         # Control the build verbosity
         ifeq ("$(VERBOSE)","1")
        -    Q :=
        +    Q =
             VECHO = @true
         else
        -    Q := @
        +    Q = @
             VECHO = @printf
         endif

        -GIT_HOOKS := .git/hooks/applied
        +GIT_HOOKS = .git/hooks/applied

         .PHONY: all clean

        @@ -26,11 +26,11 @@ $(GIT_HOOKS):
         OBJS_LIB = \
             tst.o bloom.o

        -OBJS := \
        +OBJS = \
             $(OBJS_LIB) \
             test_common.o \

        -deps := $(OBJS:%.o=.%.o.d)
        +deps = $(OBJS:%.o=.%.o.d)

- 因為內容會有每次執行時間 (sec) 誤差, 所以透過指令 `seq -i '/sec/d' $FILE` 來刪除有關 sec 字串的 lines
- 最後用 `vimdiff` 來看兩個 stdout 的內容，其二並沒有任何差異
- **結論**：判斷在此例在 Makefile 中用 `=` 可以得到相同的預期結果，沒有必要特別使用 `:=`
:::

- 至於 `${CC}` , 參考 [Variables Used by Implicit Rules](https://www.gnu.org/software/make/manual/html_node/Implicit-Variables.html) 知道其為 Program for compiling C programs; default `cc`. 而 `$(LDFLAGS)` 為 Extra flags to give to compilers when they are supposed to invoke the linker, ‘ld’, such as -L. Libraries (-lfoo) should be added to the LDLIBS variable instead.
- 參照 [GNU Ld初探](http://wen00072.github.io/blog/2014/03/14/study-on-the-gnu-ld/) 得知流程為 gcc -> collect2 -> ld

- 至於 `$^` 也是自動化變數，其為所有必要條件的檔名，並以空格隔開這些檔名

- 至於 `-lm` 是因為程式碼有用到 C 的數學函式庫`libm.a` 所以把它一起加進來編譯而丟給 `${CC}` 的參數

以下為參照以上說明之 `make plot` 首先 build prerequisite $(TESTS) 對應 stdout:

### OUTPUT of building target $(TESTS) ###

# if VERBOSE=1 enviroment parameter is given
cc -o test_common.o -O0 -Wall -Werror -g -c -MMD -MF .test_common.o.d test_common.c
cc -o tst.o -O0 -Wall -Werror -g -c -MMD -MF .tst.o.d tst.c
cc -o bloom.o -O0 -Wall -Werror -g -c -MMD -MF .bloom.o.d bloom.c
cc   -o test_common test_common.o tst.o bloom.o -lm
# else
  CC	test_common.o
  CC	tst.o
  CC	bloom.o
  LD	test_common

### 理解過程：perf 部分
* 用 `perf-stat` 來重複執行 100 次 program 並觀察目標 events 發生的次數，此例中觀察的 cache-misses, cache-references, instructions, cycles 等皆屬於 hardware events
* 抓出 ternary_tree 讀檔 words 建立 TST 的時間：運用 grep 的 `-E` (extended regular expression) 來抓出時間輸出到 csv，藉此比較 $CPY$ 機制與 $REF$ 機制之時間差異 (`make plot` 雖然有給程式 test_common 一個 input `s Tai` 去 search 'Tai' 字串，但是最後只輸出讀檔 words 建立 TST 的時間, 因為 `grep 'ternary_tree, loaded 206849 words' | grep -Eo '[0-9]+\.[0-9]+' > $CSVFILE`)

輸出如下：

# CPY
sudo perf stat --repeat 100 \
                -e cache-misses,cache-references,instructions,cycles \
                ./test_common --bench CPY s Tai \
	| grep 'ternary_tree, loaded 206849 words'\
	| grep -Eo '[0-9]+\.[0-9]+' > cpy_data.csv

 Performance counter stats for './test_common --bench CPY s Tai' (100 runs):

           1048313      cache-misses              #   36.940 % of all cache refs      ( +-  0.26% )
           2837872      cache-references                                              ( +-  0.10% )
         640085509      instructions              #    1.26  insn per cycle           ( +-  0.01% )
         509712283      cycles                                                        ( +-  0.06% )

          0.151744 +- 0.000155 seconds time elapsed  ( +-  0.10% )

# REF
sudo perf stat --repeat 100 \
                -e cache-misses,cache-references,instructions,cycles \
	./test_common --bench REF s Tai\
	| grep 'ternary_tree, loaded 206849 words'\
	| grep -Eo '[0-9]+\.[0-9]+' > ref_data.csv

 Performance counter stats for './test_common --bench REF s Tai' (100 runs):

           1014360      cache-misses              #   35.726 % of all cache refs      ( +-  0.32% )
           2839305      cache-references                                              ( +-  0.06% )
         606467594      instructions              #    1.21  insn per cycle           ( +-  0.00% )
         500247356      cycles                                                        ( +-  0.06% )

          0.148576 +- 0.000148 seconds time elapsed  ( +-  0.10% )

可以看出不論是在 $CPY$ 機制還是 $REF$ 機制，在 cache-miss 都有 35% 以上的機率發生在 cache-reference 時，而 IPC 則是在 1.2 以上，雖然 $CPY$ 機制 IPC = 1.26 大於 $REF$ 機制 IPC = 1.21, 但因為 $REF$ 機制少了約 9,464,927 個 cycles，所以其執行時間還是較短，少了約 3 ms

### References
- [Makefile 語法和示範](https://hackmd.io/@sysprog/SySTMXPvl)
- [Linux 效能分析工具: Perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)