2018q3 Homework3 (dict)

# 2018q3 Homework3 (dict) contributed by < [`TerryShu`](https://github.com/TerryShu/dict) > ## 環境 ``` $ cat /etc/os-release NAME="Ubuntu" VERSION="18.04.1 LTS (Bionic Beaver)" ID=ubuntu ID_LIKE=debian PRETTY_NAME="Ubuntu 18.04.1 LTS" VERSION_ID="18.04" HOME_URL="https://www.ubuntu.com/" SUPPORT_URL="https://help.ubuntu.com/" BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/" PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy" VERSION_CODENAME=bionic UBUNTU_CODENAME=bionic ``` 因為此次實驗會到探討 `cache` 故列出 `CPU` 的資訊 ``` $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 8 On-line CPU(s) list: 0-7 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 142 Model name: Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz Stepping: 10 CPU MHz: 800.209 CPU max MHz: 4000.0000 CPU min MHz: 400.0000 BogoMIPS: 3984.00 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 8192K NUMA node0 CPU(s): 0-7 Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp flush_l1d ``` ## 安裝必要套件 ``` $ sudo apt-get install linux-tools-common $ sudo apt-get install linux-tools-4.15.0-36-generic ``` ## Makefile * 先觀察 `makefile` 內的變數設置 ```clike= TESTS = test_cpy test_ref TEST_DATA = s Tai CFLAGS = -O0 -Wall -Werror -g ``` * `TESTS` 內的 `test_cpy` 和 `test_ref` 是指 make 過後產生的執行檔在這裡設定變數的目的是方便後面的相依性檢查 * `TEST_DATA` 這裡是後面執行 `test` 時會用到的參數 `s` 是 search `Tai` 代表要查詢的開頭 * `CFLAGS` 代表 `GCC` 編譯時用的參數此次 lab 主要會用到的指令有 `test` `bench` `clean` ### `test` ```clike= test: $(TESTS) echo 3 | sudo tee /proc/sys/vm/drop_caches; perf stat --repeat 100 \ -e cache-misses,cache-references,instructions,cycles \ ./test_cpy --bench $(TEST_DATA) perf stat --repeat 100 \ -e cache-misses,cache-references,instructions,cycles \ ./test_ref --bench $(TEST_DATA) ``` 執行 `meke test` 會使用 `pref` 各去測試 `test_cpy` 和 `test_ref` 100次測試的數據是 `f Tai` 找出 prefix 是 Tai 的字串並找出 cache-misses , cache-references , instructions , cycles 的數量 ### `bench` ```clike= bench: $(TESTS) @for test in $(TESTS); do\ ./$$test --bench $(TEST_DATA); \ done ``` 若執行 `make bench` 則會對兩個執行檔 `test_cpy` 和 `test_ref` 做測試測試的數據是 `f Tai` 找出 prefix 是 Tai 的字串 ### `clean` ```clike= clean: $(RM) $(TESTS) $(OBJS) $(RM) $(deps) rm -f bench_cpy.txt bench_ref.txt ref.txt cpy.txt caculate ``` 此處用到的 `$(RM)` 是 `GNU make` 預先定義的定義如下 [source](https://www.gnu.org/software/make/manual/html_node/Implicit-Variables.html) ``` RM Command to remove a file; default ‘rm -f’. ``` 故若執行 `make clean` 會去刪除執行 `make` 過後產生的 obj檔以及一些用來記錄的 txt --- ## Test結果執行 `$ sudo make test` test_cpy 測試結果 ``` Performance counter stats for './test_cpy --bench s Tai' (100 runs): 380,1967 cache-misses # 40.447 % of all cache refs ( +- 0.57% ) 939,9933 cache-references ( +- 0.16% ) 5,2764,8718 instructions # 1.32 insn per cycle ( +- 0.01% ) 3,9910,0372 cycles ( +- 0.15% ) 0.146737114 seconds time elapsed ( +- 0.27% ) ``` test_ref 測試結果 ``` Performance counter stats for './test_ref --bench s Tai' (100 runs): 437,6063 cache-misses # 39.491 % of all cache refs ( +- 0.66% ) 1108,1231 cache-references ( +- 0.35% ) 5,8903,7793 instructions # 1.18 insn per cycle ( +- 0.00% ) 4,9980,1878 cycles ( +- 0.14% ) 0.178547840 seconds time elapsed ( +- 0.27% ) ``` --- ## 程式流程 ### 資料結構 ```clike= typedef struct tst_node { char key; /* char key for node (null for node with string) */ unsigned refcnt; /* refcnt tracks occurrence of word (for delete) */ struct tst_node *lokid; /* ternary low child pointer */ struct tst_node *eqkid; /* ternary equal child pointer */ struct tst_node *hikid; /* ternary high child pointer */ } tst_node; ``` 此次的資料結構是使用 `ternary search tree`，故我們會需要 * `key` 用來存他的值 * `refcnt` 用來刪除時用的 * `lokid` low child 用來存放value比目前小的node * `eqkid` equal child 用來存放value相同的node * `hikid` high child 用來存放value比目前大的node ### `test_cpy` ```clike= #define IN_FILE "cities.txt" FILE *fp = fopen(IN_FILE, "r"); ``` 先將字典檔(城市名稱)讀入此處使用 `fopen()` 觀察 `fopen()` 使用的參數 ``` FILE *fopen(const char *pathname, const char *mode); The fopen() function opens the file whose name is the string pointed to by pathname and associates a stream with it. The argument mode points to a string beginning with one of the follow‐ ing sequences (possibly followed by additional characters, as described below): r Open text file for reading. The stream is positioned at the beginning of the file. r+ Open for reading and writing. The stream is positioned at the beginning of the file. w Truncate file to zero length or create text file for writing. The stream is positioned at the beginning of the file. w+ Open for reading and writing. The file is created if it does not exist, otherwise it is truncated. The stream is positioned at the beginning of the file. a Open for appending (writing at end of file). The file is cre‐ ated if it does not exist. The stream is positioned at the end of the file. a+ Open for reading and appending (writing at end of file). The file is created if it does not exist. The initial file position for reading is at the beginning of the file, but output is always appended to the end of the file. ``` 此處的 `'r'` 代表只能讀不能寫入接著紀錄此次的 `tst` 讀入了多少的 `words` ```clike= double tvgetf() { struct timespec ts; double sec; clock_gettime(CLOCK_REALTIME, &ts); sec = ts.tv_nsec; sec /= 1e9; sec += ts.tv_sec; return sec; } t1 = tvgetf(); while ((rtn = fscanf(fp, "%s", word)) != EOF) { char *p = word; if (!tst_ins_del(&root, &p, INS, CPY)) { fprintf(stderr, "error: memory exhausted, tst_insert.\n"); fclose(fp); return 1; } idx++; } t2 = tvgetf(); fclose(fp); printf("ternary_tree, loaded %d words in %.6f sec\n", idx, t2 - t1); ``` ``` clike= ternary_tree, loaded 259112 words in 0.132248 sec ``` :::info 對他計時的方式感興趣所以去trace了一下他的程式碼 ```clike= double tvgetf() { struct timespec ts; double sec; clock_gettime(CLOCK_REALTIME, &ts); sec = ts.tv_nsec; sec /= 1e9; sec += ts.tv_sec; return sec; } ``` ```clike= struct timespec { __time_t tv_sec; /* Seconds. */ __syscall_slong_t tv_nsec; /* Nanoseconds. */ }; ``` 接著一直去 trace 他 `tv_sec` 和 `tv_nsec` 的型態 `__time_t` -> `__TIME_T_TYPE` -> `__SYSCALL_SLONG_TYPE` -> `__SLONGWORD_TYPE` -> `long int` 最後得知兩種 `tv_sec` 和 `tv_nsec` 都是 `long int` 的格式一開始的疑問是為甚麼不用float去存? 後還想了一下覺得可能是會有誤差的關係然後又想到一個之前聽過的論述大意是: 不太可能精確的量到 cpu 執行的時間因為在取時間的這個指令動作本身也需要時間所以會有誤差所以如果又用了 float 去存的話誤差+誤差可能又更測不準了另一個問題比較奇怪是關於他宣告的方式一個用了 `__time_t ` 一個用了 `__syscall_slong_t ` 但最後都是宣告成 `long int` 為甚麼不一開始就宣告成`__time_t `較好理解 ::: :::info 觀察到很多 C 程式都會有這樣多重(層層) Define 的情況，但仔細思考了一下這樣是不是有可以最佳化的空間，例如我 `#include a.h` `#include b.h` `#include c.h`但實際上只用了其中 `#Define` 的部份，故在最後 `include` 可以跳過大部份內容，例如上面情況`__time_t` -> `__TIME_T_TYPE` -> `__SYSCALL_SLONG_TYPE` -> `__SLONGWORD_TYPE` -> `long int` 對 `__time_t` 這一行進行最佳化，直接替換成`long int`，不知是否可行，或是目前的編譯器已經實現? ::: ## Bug fix 發現於 `bench.c` 中有一小段時間紀錄錯誤以及 `array`大小錯誤原先程式碼 `bench.c` ```clike= char prefix[3] = ""; ... strncpy(prefix, word, 3); t1 = tvgetf(); tst_search_prefix(root, prefix, sgl, &sidx, max); t2 = tvgetf(); fprintf(fp, "%d %f sec\n", idx, (t2 - t1) * 1000000); ... ``` `array` 大小錯誤是指在進行 `strncpy` 時並沒有將終止字元 `\0` 放進去故 `prefix` 在使用時會出現問題相關敘述在 `man page` 中也有提到 > $ man strncpy > Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated. 故最後修正 `array` 大小改為4 ~~此處紀錄的時間單位是秒，但程式碼卻將他 `* 1000000` 故將他修正並將其位數顯示出來~~ ~~修改為以秒的形式顯現並顯示12位數修正後 `bench.c`~~ ```clike= char prefix[4] = ""; ... strncpy(prefix, word, 3); t1 = tvgetf(); tst_search_prefix(root, prefix, sgl, &sidx, max); t2 = tvgetf(); fprintf(fp, "%d %.12lf sec\n", idx, (t2 - t1) ); ... ``` 後面發現使用 `plot` 時數字太小不方便表示所以修改成以下故修回原本但單位變換為 `microsec` ```clike= char prefix[4] = ""; ... strncpy(prefix, word, 3); t1 = tvgetf(); tst_search_prefix(root, prefix, sgl, &sidx, max); t2 = tvgetf(); fprintf(fp, "%d %f microsec\n", idx, (t2 - t1)* 1000000 ); ... ``` ## 問題與心得 :::info 發現很多 `C` 程式在寫無限迴圈時會表示為 ```clike= for(;;) ``` 而非 ```clike= while(1) OR while(true) ``` 對這個部分覺得困惑所以去查了一下原因 [source](https://www.zhihu.com/question/52311366) 這篇雖然是在講 `Java` 但其中有講到是源於 `C` 寫法節錄其中一小段 > 在C语言里，如果不include某些头文件或者自己声明的话，是没有内建的_Bool / bool类型，也没有TRUE / FALSE / true / false这些_Bool / bool类型值的字面量的。所以，假定没有include那些头文件或者自己define出上述字面量，最常见的是这样 while (1) …但不是所有人都喜欢看到那个魔数“1”的。為保持原意故並未轉回繁體中文 ::: :::info 對應 `C99` 規格書 P256 > The header <stdbool.h> defines four macros. > The macro bool expands to _Bool. > ==true== which expands to the ==integer constant 1== > ==false== which expands to the ==integer constant 0== > __bool_true_false_are_defined which expands to the integer constant 1. ::: :::success 心得:有些時候歷史也是很重要的...，原先認為 while(true) 這種寫法很直觀 for(;;) 很怪異，但看完這個解釋之後才發現他的緣由原來是這樣的。我認為也可以跟之前有提過的 `C的第一個編譯器是怎麼產生的` 做連結，還記得之前做筆記的時候有提到就是一直縮減可以取代的東西，最後做出一個 C~0~ 的編譯器，所以也可以得知 `true` 和 `false` 並不是必要，而可以由 `int` 去取代 :::

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.