owned this note
owned this note
Published
Linked with GitHub
# 2018q1 Homework1 (phonebook)
contributed by < `vulxj0j8j8` >
### Reviewed by `bauuuu1021`
* 請附上 Github 連結
* 請附上 Hash table 的實驗紀錄
* 終端機訊息直接貼文字
* 中英文中間記得空格
* 可以參考一下 [共筆示範](https://hackmd.io/s/rk5ayZDKx#)
---
### Reviewed by `potter903p`
* 請把實驗結果 push 到 github 帳號內
* 加入壓縮演算法時 append() 的時間超出了圖表的邊界因而無法看到數值，建議更改 guuplot 的繪圖 script 以符合顯示需求。 參考資料：[gunplot 語法解說及示範 ](https://hackmd.io/c/rJKbX1pFZ/https%3A%2F%2Fhackmd.io%2Fs%2FSkwp-alOg)
## 系統環境
```
$ uname -a
Linux yanghau-UX410UQK 4.13.0-36-generic #40~16.04.1-Ubuntu SMP Fri Feb 16 23:25:58 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ 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) i5-7200U CPU @ 2.50GHz
Stepping: 9
CPU MHz: 2700.000
CPU max MHz: 3100.0000
CPU min MHz: 400.0000
BogoMIPS: 5424.00
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
NUMA node0 CPU(s): 0-3
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 aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti retpoline intel_pt rsb_ctxsw tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp
```
## 參考連結
感謝陳磊恩同學幫忙整理 https://hackmd.io/s/B1SSiTM_G
先讓我供著當紀錄
感謝piggyking1421 的[開發紀錄(phonebook)](https://hackmd.io/MRKuSOV0R2ODWYOSmOL8oQ?view) 教了我不少事情 供著當紀錄
## 基本練習
清空cache
```
$ sudo echo 1 | sudo tee /proc/sys/vm/drop_caches
```
使用 cache-test
```
$ sudo make cache-test
```
phonebook_orig 的測試結果
```
Performance counter stats for './phonebook_orig' (100 runs):
466,6537 cache-misses # 92.503 % of all cache refs ( +- 0.07% )
504,4765 cache-references ( +- 0.14% )
2,6354,8966 instructions # 1.41 insn per cycle ( +- 0.02% )
1,8729,9888 cycles ( +- 0.12% )
0.061756465 seconds time elapsed ( +- 0.86% )
```
先什麼都不管照著老師的作法先把perf跑一遍並畫出圖
但是關於make 來 編譯的部份還是沒有很懂@@
不知道怎麼邊兩個出來的
## 改進
試著將entity裏面非 lastName的資料都搬到另一個sturct 但是跑make plot沒有差異
然後發現是因為自己還不會測試
因為執行個別檔案速度有差很多
然後git push 遇到問題
查詢後發現是因為origin 位置還是原本的位置, 我必須改成我自己的
了解為何不能測試的問題後, 對上述第一個修改進行測試, 得到結果:
```
Performance counter stats for './phonebook_opt' (100 runs):
158,3549 cache-misses # 67.799 % of all cache refs ( +- 0.16% )
233,5651 cache-references ( +- 0.21% )
2,4485,9725 instructions # 1.99 insn per cycle ( +- 0.02% )
1,2332,1347 cycles ( +- 0.19% )
0.040467392 seconds time elapsed ( +- 0.57% )
```
## 加入壓縮演算法
[smaz github link](https://github.com/antirez/smaz)
使用老師建議的smaz library, 因為此演算法對於短字串的壓縮較為在行, 因此若是應用這個演算法, 應該可以有效降低lastName在cache中所佔的空間, 進而減少cahce miss
但同時可預期的, 若是多次使用這個演算法, 應該會使程式太多次呼叫加解密函式, 造成程式執行時間過長的問題
經過測試後發現與單純減少struct size 相比沒有大幅減少cahce misses但是時間大幅增加
```
Performance counter stats for './phonebook_opt' (100 runs):
212,8823 cache-misses # 64.537 % of all cache refs ( +- 0.61% )
329,8614 cache-references ( +- 0.77% )
30,2465,8173 instructions # 2.30 insn per cycle ( +- 0.00% )
13,1255,9063 cycles ( +- 0.25% )
0.427712277 seconds time elapsed ( +- 0.26% )
```
## main return value
讀main.c 的時候發現若是無法打開字典檔, 則return -1
查詢資料後發現 [stackoverflow link](https://stackoverflow.com/questions/204476/what-should-main-return-in-c-and-c)
```
The return value for `main` should indicate how the program
exited.Normal exit is generally represented by a 0 return value
from `main`. Abnormal termination is usually signalled by a
non-zero return but there is no standard for how non-zero
codes are interpreted.
```
## Hash table
[原理解說](http://alrightchiu.github.io/SecondRound/hash-tableintrojian-jie.html)
透過hash function 讓原本的資料範圍(key值) m, 縮小到Hash table僅有 n的範圍大小
### iterator int i = 0 的宣告位置
發現老師使用iterator時, i是宣告在main函式的最前面, 讓接下來的loop共享這個 變數i
猜測原因是宣告變數的時候比較花時間, 因此這樣做減少時間
但仍需資料搜尋
## vim的快捷鍵
* 整行刪除 **dd**
* 全部複製 **ddyG**
* 回上一步 **u**
* 選取 **v** 小寫 v，這是屬於字元標示（character visual），按下 v 後就可移動游標，游標走過的地方就會標示起來。再按一次v就會結束 v-mode。您用 mouse 拉出的標示區也是屬於這類的標示。
### Makefile 筆記
[課程hackMD](https://hackmd.io/c/rJKbX1pFZ/https%3A%2F%2Fhackmd.io%2Fs%2FSySTMXPvl)
https://wwssllabcd.github.io/blog/2016/10/03/how-to-write-make-file/
由於一開始忘記把opt 的#define OPT註解拿掉, 所以其實花了不少時間再研究如何處理這個問題, 後來再朋友協助下使用-DOPT的方式, 在Makefile裡面直接 #define OPT
-D是 define的意思, 然後緊跟的字符為要define的文字
另外Makefile的基本概念是, 如果沒有特別指令就去執行all tag然後根據tag後面的要求, 去找相映的tag或檔案 並執行裡面的任務
有趣的點是說, 因為我vim的設定是
```
:set tabstop=4
```
所以單純按tab不能符合Makefile指令的語法要求 (指令前面必須是tab)
所以得使用 <CTRL-V><Tab> 才能輸入tab, 但是這方法有時候鍵盤會讀取太多字輸入失敗
#### 單行編譯
此時 smazTest.c, smaz.c, smazTest.h, smaz.h 都位於相同資料夾下
```
$gcc -c smazTest.c smaz.c
$gcc -o smazTest smazTest.o smaz.o
```
就可以使用了
```
$./smazTest
```
### gcc 指令[link](http://aikosenoo.pixnet.net/blog/post/23038692-%5B筆記%5D-gcc參數指令%28轉錄%29)
-Wall : 顯示所有的警告訊息
-o filename : 指定輸出檔名
-c : 只做編譯(不做連結)
### #if defined
[參考文章](https://msdn.microsoft.com/zh-tw/library/ew2hz0yd.aspx)
簡單例子
```
#if defined(CREDIT)
credit();
#elif defined(DEBIT)
debit();
#else
printerror();
#endif
```
在main.c 裏面使用 #if defined 以區分現在使用的是OPT或者是ORIG
## Memory Pool
void *的意義 [詳細解說](https://jingyan.baidu.com/article/6c67b1d68f93bb2786bb1e46.html)
void *可以指向任何類型的數據
例子
```
float *p1;
int *p2;
//其中p1 = p2语句会编译出错，提示“'=' : cannot convert from 'int *' to 'float *'”，必须
p1 = p2;
//改成
p1 = (float *)p2;
```
但是如果是void * 則
```
void *p1;
int *p2;
p1 = p2;
```
但是沒辦法把有型態轉換成無形態
```
void *p1;
int *p2;
p2 = p1;
//提示“'=' : cannot convert from 'void *' to 'int *'”。
```
## 問題討論
Q1 有代表性嗎？跟真實英文姓氏差異大嗎？
覺得在網站存放帳號密碼的資料庫可能會有遇到類似的問題, 畢竟帳號密碼是不太需要以英文字為單位所產生的組合
但這個dataset跟真實姓名資料應該差異很大
Q2 資料難道「數大就是美」嗎？
資料大勢必有難以快速找到資料的問題, 但再裏面資料都沒有不合常理的狀況下, 是一個非常好的練習
Q3 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
真實的電話簿可能還要對地區or 種類進行分類, 所以struct 裏面可能要多其他element
Google Drive
Gist
Clipboard
Sign in with Wallet
