# 2018q1 Homework2 (prefix-search)
contributed by <`ryanpatiency`>
###### tags: `ryanpatiency` `homework`
前往 [課程 wiki](http://wiki.csie.ncku.edu.tw/sysprog/schedule)
## 環境

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              3072K

## 實驗大綱
* 目的：改進 test_ref.c , 使其效能比 test_cpy.c 還要好
* 特別要求：可以使用 make bench 直接比較
* 我想做的實驗：（操縱變因）
* Traverse to generate suggestion : 連 memory pool 都不用
* Traverse to generate suggestion version 2: 改變 api 以求更快的速度
* 測量方法：（應變變因）
* 時間 `tvgetf`
* 額外實驗：
* 為什麼要用 `tvgetf()` 不用 `clock()` 呢？
* gcc 會不會自動將 len-1 和 --len 合併？
* gcc 能不能將某些 if else 自動改變成 a=?b:c
* echo 3 | tee ... 真的有差別嗎？
* Improve data: 目前國家和城市放在一起，而且 "," 符號也會放進去，我想處理這個問題

## 實驗： Traverse to generate suggestion
### 原理：
* 不複製字串於最後，節省一半的空間。
* 在 suggest 時動態 malloc suggest 所需的字串

### 預測實驗結果：
* 節省空間。因為不需要為每一個節點複製字串
* `tst_ins_del` 的時間變快，同樣的道理
* `tst_search_prefix` 的時間變慢，因為需要動態 malloc；

### 實驗步驟
- [x] 更改原本 `tst_ins_del` 的程式碼，將最後 `node-eqkid` 改為 `NULL`
- [x] 實作 `tst_traverse` 的程式碼，能將參數節點以下的所有字串複製到參數 `char **a` 中，當然需要 `malloc`
- [x] 更改 `tst_search_prefix` 的程式碼，將 `tst_suggest` 改成 `tst_traverse`

#### 測量時間 -- build tree

我寫了 shell script, 分別跑 100 次。對建立樹的平均值做圖如下：


#### 測量空間 -- build tree

我使用 valgrind, 發現結果如下

$ valgrind ./test_cpy
total heap usage: 588,254 allocs, 588,254 frees, 16,969,720 bytes allocated
$ valgrind ./test_ref
total heap usage: 502,754 allocs, 502,754 frees, 16,094,696 bytes allocated

對空間做圖如下：

#### 測量時間 -- prefix search
用 city 的前3個字查詢，看結果如何。

我寫了一個程式 gen_cmd.c 產生 command.txt 和一個 shell script 計算 measure prefix time

* 將執行時間分成十份做圖：

### 實驗結論
原來相比整個樹來說，`strdup` 的 size 可說微乎其微。因為每一個 node 都有 lokid, hikid, eqkid 加起來就 8*3 = 24 bytes 了。而 key 才一個 byte 而已。所以時間、空間都只好一點而已。

## 實驗：Traverse to generate suggestion version 2
### 觀察：
如果不為 array alloc memory dynamically，可能可以快一些吧
### 方法：

新增 quick_tst_search_prefix 的 api，省略
1. char **a,
2. int *n,
3. const int max

直接產生 suggestion, 測量速度。
### 實驗結果：

:::danger
version 2 慢了很多，可以發現到使用 array + malloc + stack 的時間仍然 < printf
:::

# 額外實驗
這部份的實驗和改善時間空間沒直接關係

## 實驗： 改善 data
### 觀察：
現在的 data 將 city 和 country 混在一起。我就順手把他改過來了：

### 原本的：

suggest[885] : Vizze,
suggest[886] : Vizzini,
suggest[887] : Vizzolo

### 後來的：

suggest[1021] : Villa Santa Rita, Argentina
suggest[1022] : Villa Santina, Italy
suggest[1023] : Villa Santo Stefano, Italy

原本的有 `,` 等莫名其妙的資料，修改完就好多了。

## 實驗： echo 3 | tee ... 的影響
### 目的：
了解cache 的影響，
### 方法：
將上面提到的 shell script 註解掉 echo... 的部份

### 實驗結果

對 test_cpy 的做圖如下

可以發現，有 cache 真的會比較快一些

## 實驗：使用 `clock()` 不用 `tvgetf()`
經過實驗，大部份的 tst_prefix_search 的執行都只要 1 cycle or 2 cycle, 不能精確比較。
## 實驗：觀察 assembly, 確認 gcc 能不能將某些 if else 自動改變成 a=?b:c

txt.c 中，有些 if else 可以更精簡。由於學過 branch prediction 的 penalty 很大，想了解 gcc -O3 的特性

測試對象：

else if (diff < 0) {      
    curr = (curr->lokid); 
} else {                   
    curr = (curr->hikid); 
}

改成

else {      
    curr =  (diff < 0) ? (curr->lokid):(curr->hikid); 
}

Makefile 改成：
`CFLAGS = -g -O3`

原本的

304                       } else if (diff < 0) /* handle the less than case */
0000000000401cb0:   js      0x401cc0 <tst_search+48>
307                           curr = curr->hikid; /* handle the greater than case */
0000000000401cb2:   mov     0x18(%rdi),%rdi
0000000000401cb6:   jmp     0x401c90 <tst_search>
0000000000401cb8:   nopl    0x0(%rax,%rax,1)
305                           curr = curr->lokid;
0000000000401cc0:   mov     0x8(%rdi),%rdi
0000000000401cc4:   jmp     0x401c90 <tst_search>
0000000000401cc6:   nopw    %cs:0x0(%rax,%rax,1)

後來的

306                           curr = (diff < 0) ? curr->lokid : curr->hikid;
0000000000401cb0:   js      0x401cc0 <tst_search+48>
0000000000401cb2:   mov     0x18(%rdi),%rdi
0000000000401cb6:   jmp     0x401c90 <tst_search>
0000000000401cb8:   nopl    0x0(%rax,%rax,1)
0000000000401cc0:   mov     0x8(%rdi),%rdi
0000000000401cc4:   jmp     0x401c90 <tst_search>
0000000000401cc6:   nopw    %cs:0x0(%rax,%rax,1)

### 結論：
gcc 在 -O3 的情況下能將這一部份最佳化

## 實驗：觀察 assembly, gcc 會不會自動將 len-1 和 --len 合併？
test_xxx 中，這幾行看起來怪怪的，

static void rmcrlf(char *s)
{
    size_t len = strlen(s);
    if (len && s[len - 1] == '\n')
        s[--len] = 0;
}

我把他改成

static void rmcrlf(char *s)
{
    size_t len = strlen(s);
    if (len && s[--len] == '\n')
        s[len] = 0;
}

觀察實驗如下：

原本的：

                  rmcrlf:
0000000000400a3c:   push    %rbp
0000000000400a3d:   mov     %rsp,%rbp
0000000000400a40:   sub     $0x20,%rsp
0000000000400a44:   mov     %rdi,-0x18(%rbp)
 30                   size_t len = strlen(s);
0000000000400a48:   mov     -0x18(%rbp),%rax
0000000000400a4c:   mov     %rax,%rdi
0000000000400a4f:   callq   0x400810 <strlen@plt>
0000000000400a54:   mov     %rax,-0x8(%rbp)
 31                   if (len && s[len - 1] == '\n')
0000000000400a58:   cmpq    $0x0,-0x8(%rbp)
0000000000400a5d:   je      0x400a88 <rmcrlf+76>
0000000000400a5f:   mov     -0x8(%rbp),%rax
0000000000400a63:   lea     -0x1(%rax),%rdx
0000000000400a67:   mov     -0x18(%rbp),%rax
0000000000400a6b:   add     %rdx,%rax
0000000000400a6e:   movzbl  (%rax),%eax
0000000000400a71:   cmp     $0xa,%al
0000000000400a73:   jne     0x400a88 <rmcrlf+76>
 32                       s[--len] = 0;
0000000000400a75:   subq    $0x1,-0x8(%rbp)
0000000000400a7a:   mov     -0x18(%rbp),%rdx
0000000000400a7e:   mov     -0x8(%rbp),%rax
0000000000400a82:   add     %rdx,%rax
0000000000400a85:   movb    $0x0,(%rax)

後來的

                  rmcrlf:
0000000000400a3c:   push    %rbp
0000000000400a3d:   mov     %rsp,%rbp
0000000000400a40:   sub     $0x20,%rsp
0000000000400a44:   mov     %rdi,-0x18(%rbp)
0000000000400a48:   mov     -0x18(%rbp),%rax
0000000000400a4c:   mov     %rax,%rdi
0000000000400a4f:   callq   0x400810 <strlen@plt>
0000000000400a54:   mov     %rax,-0x8(%rbp)
 31                   if(len && s[--len] == '\n')
0000000000400a58:   cmpq    $0x0,-0x8(%rbp)
0000000000400a5d:   je      0x400a84 <rmcrlf+72>
0000000000400a5f:   subq    $0x1,-0x8(%rbp)
0000000000400a64:   mov     -0x18(%rbp),%rdx
0000000000400a68:   mov     -0x8(%rbp),%rax
0000000000400a6c:   add     %rdx,%rax
0000000000400a6f:   movzbl  (%rax),%eax
0000000000400a72:   cmp     $0xa,%al
0000000000400a74:   jne     0x400a84 <rmcrlf+72>
 32                       s[len] = 0;
0000000000400a76:   mov     -0x18(%rbp),%rdx
0000000000400a7a:   mov     -0x8(%rbp),%rax
0000000000400a7e:   add     %rdx,%rax
0000000000400a81:   movb    $0x0,(%rax)

### 實驗結論：
預設情形下，不同程式結果不同

## 測試 gcc `-O3` 時的行為
同樣的實驗，但是 Makefile 改成：
`CFLAGS = -g -O3`
原本的

                  rmcrlf:
00000000004010c0:   mov     %rdi,%rdx
00000000004010c3:   mov     (%rdx),%ecx
00000000004010c5:   add     $0x4,%rdx
00000000004010c9:   lea     -0x1010101(%rcx),%eax
00000000004010cf:   not     %ecx
00000000004010d1:   and     %ecx,%eax
00000000004010d3:   and     $0x80808080,%eax
00000000004010d8:   je      0x4010c3 <rmcrlf+3>
00000000004010da:   mov     %eax,%ecx
00000000004010dc:   shr     $0x10,%ecx
00000000004010df:   test    $0x8080,%eax
00000000004010e4:   cmove   %ecx,%eax
00000000004010e7:   lea     0x2(%rdx),%rcx
00000000004010eb:   mov     %eax,%esi
00000000004010ed:   cmove   %rcx,%rdx
00000000004010f1:   add     %al,%sil
00000000004010f4:   sbb     $0x3,%rdx
 31                   if(len && s[--len] == '\n')
00000000004010f8:   sub     %rdi,%rdx
00000000004010fb:   je      0x401107 <rmcrlf+71>
00000000004010fd:   lea     -0x1(%rdi,%rdx,1),%rax
0000000000401102:   cmpb    $0xa,(%rax)
0000000000401105:   je      0x401110 <rmcrlf+80>
0000000000401107:   repz    retq 
0000000000401109:   nopl    0x0(%rax)
 32                       s[len] = 0;
0000000000401110:   movb    $0x0,(%rax)
0000000000401113:   retq    
0000000000401114:   nopw    %cs:0x0(%rax,%rax,1)
000000000040111e:   xchg    %ax,%ax

後來的

                  rmcrlf:
00000000004010c0:   mov     %rdi,%rdx
00000000004010c3:   mov     (%rdx),%ecx
00000000004010c5:   add     $0x4,%rdx
00000000004010c9:   lea     -0x1010101(%rcx),%eax
00000000004010cf:   not     %ecx
00000000004010d1:   and     %ecx,%eax
00000000004010d3:   and     $0x80808080,%eax
00000000004010d8:   je      0x4010c3 <rmcrlf+3>
00000000004010da:   mov     %eax,%ecx
00000000004010dc:   shr     $0x10,%ecx
00000000004010df:   test    $0x8080,%eax
00000000004010e4:   cmove   %ecx,%eax
00000000004010e7:   lea     0x2(%rdx),%rcx
00000000004010eb:   mov     %eax,%esi
00000000004010ed:   cmove   %rcx,%rdx
00000000004010f1:   add     %al,%sil
00000000004010f4:   sbb     $0x3,%rdx
 31                   if(len && s[--len] == '\n')
00000000004010f8:   sub     %rdi,%rdx
00000000004010fb:   je      0x401107 <rmcrlf+71>
00000000004010fd:   lea     -0x1(%rdi,%rdx,1),%rax
0000000000401102:   cmpb    $0xa,(%rax)
0000000000401105:   je      0x401110 <rmcrlf+80>
0000000000401107:   repz    retq 
0000000000401109:   nopl    0x0(%rax)
 32                       s[len] = 0;
0000000000401110:   movb    $0x0,(%rax)
0000000000401113:   retq    
0000000000401114:   nopw    %cs:0x0(%rax,%rax,1)
000000000040111e:   xchg    %ax,%ax

一模一樣

### 實驗結論：
gcc 在 -O3 時能將這一部份最佳化。

## 參考
這一部份是我找到的，對我自己有幫助的資訊
* https://hackmd.io/s/BkiEdEj3-#Reviewed-by-amikai
在畫圖上面有值得參考的地方

* C 有提供 `getopt.h` 幫助編程者管理 option, 直接用 `argv` 取得 argument 不夠嚴謹

* https://hackmd.io/s/SkeKQEq3Z
實驗紀錄的很清楚，值得重複

* https://hackmd.io/K4v3wF-8SFudCT2-ckK9Hg?both
紀錄 tina 程式碼的缺陷，如果有人想重複 tina 同學的實驗請先參考這篇

## 問題
* Makefile