# 2018q3 Homework3 (dict)
Contributed by <`aben20807`>
###### tags: `sysprog2018`
<style>
.red {
color: red;
}
</style>
## 環境
```
$ lscpu
Architecture: x86_64
CPU op-mode(s): 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: 142
Model name: Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz
Stepping: 9
CPU MHz: 702.352
CPU max MHz: 3500.0000
CPU min MHz: 400.0000
BogoMIPS: 5808.00
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 4096K
NUMA node0 CPU(s): 0-3
```
## 計時
+ `tvgetf()`：獲取當前時間的秒數
+ 定義在 bench.c 中 [[link]](https://github.com/sysprog21/dict/blob/c6700cd5260e8c81eb8e4bcd30dc8cb1482402ed/bench.c#L10)
+ 利用 [`clock_gettime()`](https://linux.die.net/man/3/clock_gettime)
+ 從標準時間點 (epoch) 1970-01-01 00\:00\:00
+ return 0 for success, or -1 for failure (in which case errno is set appropriately).
## perf
+ 權限全開 `$ sudo sh -c " echo -1 > /proc/sys/kernel/perf_event_paranoid"`
+ 測試
```c
static char array[10000][10000];
int main (void){
int i, j;
for (i = 0; i < 10000; i++)
for (j = 0; j < 10000; j++)
array[j][i]++;
return 0;
}
```
```bash
$ gcc cache_miss.c -o v1
$ perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./v1
Performance counter stats for './v1' (5 runs):
2088,5552 cache-misses # 5.292 % of all cache refs ( +- 8.71% )
3,9464,1930 cache-references ( +- 0.50% )
23,9823,4687 instructions # 1.27 insn per cycle ( +- 0.01% )
18,8919,7407 cycles ( +- 1.19% )
0.542310617 seconds time elapsed ( +- 1.15% )
```
```c
static char array[10000][10000];
int main (void){
int i, j;
for (i = 0; i < 10000; i++)
for (j = 0; j < 10000; j++)
array[i][j]++;
return 0;
}
```
```bash
$ gcc cache_miss.c -o v2
$ perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./v2
Performance counter stats for './v2' (5 runs):
224,2803 cache-misses # 89.966 % of all cache refs ( +- 0.21% )
249,2955 cache-references ( +- 1.13% )
23,9755,2326 instructions # 2.51 insn per cycle ( +- 0.01% )
9,5651,4574 cycles ( +- 0.31% )
0.274339463 seconds time elapsed ( +- 0.33% )
```
## Makefile
+ 清除 cache
+ linux 2.6.16 後提供 [[Ref]](https://linux-mm.org/Drop_Caches)
```bash
$ echo 3 | sudo tee /proc/sys/vm/drop_caches;
```
+ tee 指令 [[man]](http://man7.org/linux/man-pages/man1/tee.1.html)
+ 顯示並另存一份文檔
+ 例如上方指令就是在螢幕印出 `3`，且將 `3` 寫入 /proc/sys/vm/drop_caches 中
+ 指定搜尋字串
```bash
$ make test TEST_DATA='s Tain'
```
+ `$ make plot`
```
bench_cpy.txt: test_cpy
./test_cpy --bench
bench_ref.txt: test_ref
./test_ref --bench
plot: bench_cpy.txt bench_ref.txt
gnuplot scripts/runtimept.gp
eog runtime2.png &
```
## gnuplot
### cpy.txt
```bash
$ make
$ ./test_cpy
```
+ 會把製作 ternary_tree 載入時間計算出來存在 cpy.txt
```bash
$ make test # 執行 100 次 ./test_cpy --bench $(TEST_DATA)
```
+ 因為寫入 cpy.txt 時是用 append 所以會記錄 100 次時間
### bench_cpy.txt
+ 安裝 `$ sudo apt-get install gnuplot`
+ 發現專案中 scripts 中有 gnuplot 的 .gp 檔
+ 其中 scripts/runtime3.gp 有提到 bench_cpy.txt
+ 發現 test_cpy.c 中有寫到若有 `--bench` 的 argv[1] 就會輸出 bench_cpy.txt
```bash
$ make
$ ./test_cpy --bench
$ gnuplot scripts/runtime3.gp
$ eog runtime3.png &
```
+ 發現全部壓在 0 附近
+ 利用 `$ vim -u NONE bench_cpy.txt` 觀察，y 軸最大設 1000 過大
+ 把 y 軸的最大值 1000去掉 `[:1000]` -> `[:]`
+ 
### ref.txt
+ 比較 test_ref.c、test_cpy.c 發現 test_ref.c 缺少一部份程式碼
```c
FILE *output;
output = fopen("ref.txt", "a");
if (output != NULL) {
fprintf(output, "%.6f\n", t2 - t1);
fclose(output);
} else
printf("open file error\n");
```
```bash
$ make test # 產生 100 次建置時間
```
### bench_ref.txt
+ 一樣在 test_ref.c 補上缺少區塊
```c
if (argc == 2 && strcmp(argv[1], "--bench") == 0) {
int stat = bench_test(root, BENCH_TEST_FILE, LMAX);
tst_free_all(root);
return stat;
}
```
```bash
$ make
$ ./test_ref --bench # 產生 bench_ref.txt
```
### scripts/runtimept.gp
+ 有了 bench_cpy.txt、bench_ref.txt 就可以畫 scripts/runtimept.gp 了
+ 一樣修改 y 軸最大值
```bash
$ gnuplot scripts/runtimept.gp
$ eog runtime2.png &
```
+ 
+ 發現數值相當奇怪
+ 參考[`siahuat0727`](https://hackmd.io/s/HJElcrA9Q#benchc-%E4%B8%AD-bug-%E4%BF%AE%E5%BE%A9)解決 bench.c 中 `char prefix[4] = "";`
+ 解決後利用一樣指令即可畫出
+ 
+ 修改單位問題 (是 **µs** 不是 s)
+ 
+ 發現執行 test_ref `$ ./test_ref --bench` 會有 Address boundary error
```bash
$ gdb -q test_ref
Reading symbols from test_ref...done.
(gdb) r --bench
Starting program: /home/ben/pro/col7/dict/test_ref --bench
ternary_tree, loaded 259112 words in 0.126777 sec
Program received signal SIGSEGV, Segmentation fault.
0x00007ffff76ddc01 in __GI___libc_free (mem=0x7fffd8986eea) at malloc.c:3123
3123 malloc.c: No such file or directory.
(gdb) f 1
#1 0x00005555555569df in tst_free_all (p=0x555555ba7470) at tst.c:413
413 free(p->eqkid);
```
Sign in with Wallet
Connect another wallet