2018q1 Homework1 (phonebook)

# 2018q1 Homework1 (phonebook) contributed by < `TingL7` > ### Reviewed by `rex662624` * github commit 大多都只有標題，沒有具體的內文敘述做了什麼。 * 提到了測試資料單一，因此可以改變測試資料，多 find 幾個不同的單字再平均做比較。 * 問題與討論說到資料對現有的字串壓縮法代表性不高，但或許不同型態的 dataset ，有最適合的字串壓縮演算法，可以多方比較。 ### Reviewed by `WillemChen` * github commit [2ebaf55](https://github.com/TingL7/phonebook/commit/2ebaf5520ff3cb310c12f5527cc7bd06788bef10) 和 [a8fd9b9](https://github.com/TingL7/phonebook/commit/a8fd9d93e7b2e36550783292bc4350746419efee) 標題過長，可以將實作的細節放入內文 * 有幾張直方圖中的數字互相重疊，可以修改 `runtime.gp` 每個數字的高度 ## 系統環境 ``` $ uname -r 4.14.0-041400-generic $ 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: 2000.000 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 intel_pt 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 ``` L1、L2 cache實際上的size為上列的size*core，也就是128K及1024K。 ## 工具準備 1. Linux * 從 [ubuntu](https://www.ubuntu.com/download/desktop)下載喜歡的版本，先切割好硬碟後，用usb安裝 * 電腦中,有設定fast boot、 secure boot必須先關閉。 * 安裝好後，找不到wifi連線，而電腦無法使用有線網路時 * `$ iwconfig` 如果只有lo(對內網路）表示沒有連接到網路卡,可能沒有驅動程式 * `$ lspci -v` 最後一段network controller可以看出網路卡的型號，再去找出相對應的驅動程式,有些驅動程式需要到網路上才找的到，沒有內建的，因此能用網路的電腦或作業系統去下載在傳到ubuntu上使用。 2. perf * 參考[安裝](https://hackmd.io/s/B11109rdg#)使用 apt-get 安裝，可能會遇到要求安裝找不到的套件 `` E: Unable to locate package linux-tools-4.14.0-041400-generic `` * 這時候改由第一個方法安裝。版本只需要選比較相近的即可，如4.14.0-041400改選4.14.24，不需要與kernel完全相同。 3. github 4. hackMD 5. astyle ## 資料閱讀疑問 * cache [cache 原理和實驗](https://hackmd.io/s/S14L26-_l#) 中，提到**n-way associative**的worst case是把整個cache都搜尋過一次。但是，n-way的優點就是有分割幾個set，這樣最差應該是把整個set搜尋過一次，沒有就去memory裡找資料，而不需要搜尋整個cache吧？ ## 原始版本 * 部份報表 ``` $ echo 1 | sudo tee /proc/sys/vm/drop_caches $ sudo make cache-test ``` 結果 ``` size of entry : 136 bytes execution time of append() : 0.034833 sec execution time of findName() : 0.004478 sec Performance counter stats for './phonebook_orig' (100 runs): 5,406,122 cache-misses # 87.629 % of all cache refs ( +- 0.17% ) 6,169,344 cache-references ( +- 0.13% ) 323,818,182 instructions # 1.49 insn per cycle ( +- 0.02% ) 216,974,738 cycles ( +- 0.17% ) 0.062936362 seconds time elapsed ( +- 1.71% ) ``` * plot `$ sudo make plot` ![](https://i.imgur.com/j0doTTB.png) ## 縮小struct 尋找是以lastname搜尋，這表示只需要lastname列表即可搜尋。 * 實做將entry改為只有last name，其它資料另外存放。 ``` typedef struct __PHONE_BOOK_ENTRY { char firstName[16]; char email[16]; char phone[10]; char cell[10]; char addr1[16]; char addr2[16]; char city[16]; char state[2]; char zip[5]; } fatEntry; typedef struct __PHONE_BOOK_LASTNAME_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; fatEntry *data; struct __PHONE_BOOK_LASTNAME_ENTRY *pNext; } entry; ``` * 結果 ``` size of entry : 32 bytes execution time of append() : 0.025610 sec execution time of findName() : 0.001512 sec Performance counter stats for './phonebook_opt' (100 runs): 1,720,488 cache-misses # 61.211 % of all cache refs ( +- 0.86% ) 2,810,741 cache-references ( +- 0.16% ) 283,634,331 instructions # 2.11 insn per cycle ( +- 0.02% ) 134,602,586 cycles ( +- 0.35% ) 0.036033924 seconds time elapsed ( +- 0.56% ) ``` ![](https://i.imgur.com/k4UJOOp.png) * 觀察與分析 * 在entry size變小的情況下，cache可以存取的資料數變大，因此cache miss減少，87.629% 降至61.211% 。 ## hash function hash的作法有許多種，主要考量是hash table大小以及hash function的選擇。 * hash table大小 * 太小的話，會使衝突增加，失去作hash的意義。 * 太大的話，可能會使cache無法負荷，miss大增。 * 應以cache為考量，可以做多方嘗試。 * hash function * 參考[各種字符串Hash函數比較](https://www.byvoid.com/zht/blog/string-hash-compare)中，以有意義的英文字為數據的結果，選擇表現較好的作為嘗試。推測hash function間會有明顯差異。 * BKDR hash function * RS hash function * DJB hash function * SDBM hash function * JS hash function ### hash table大小測試以BKDR hash function實作為例，由於測資zyxel為比較好的case，因此將測資改為"aaah"。 * size:1 ``` size of entry : 32 bytes execution time of append() : 0.031839 sec execution time of findName() : 0.002015 sec Performance counter stats for './phonebook_hash1' (100 runs): 902,335 cache-misses:u # 60.508 % of all cache refs ( +- 1.41% ) 1,491,270 cache-references:u ( +- 0.23% ) 281,439,929 instructions:u # 2.27 insn per cycle ( +- 0.02% ) 123,836,904 cycles:u ( +- 0.30% ) 0.039240234 seconds time elapsed ( +- 0.36% ) ``` * size:2^5^ ``` size of entry : 32 bytes execution time of append() : 0.032956 sec execution time of findName() : 0.000158 sec Performance counter stats for './phonebook_hash1' (100 runs): 164,354 cache-misses:u # 57.035 % of all cache refs ( +- 2.14% ) 288,162 cache-references:u ( +- 0.87% ) 223,813,912 instructions:u # 2.08 insn per cycle ( +- 0.02% ) 107,670,833 cycles:u ( +- 0.27% ) 0.035010414 seconds time elapsed ( +- 0.49% ) ``` * size:2^10^ ``` size of entry : 32 bytes execution time of append() : 0.031982 sec execution time of findName() : 0.000002 sec Performance counter stats for './phonebook_hash1' (100 runs): 15,558 cache-misses:u # 24.541 % of all cache refs ( +- 1.13% ) 63,397 cache-references:u ( +- 3.12% ) 221,997,899 instructions:u # 2.14 insn per cycle ( +- 0.02% ) 103,910,316 cycles:u ( +- 0.22% ) 0.032771593 seconds time elapsed ( +- 0.40% ) ``` * size:2^15^ ``` size of entry : 32 bytes execution time of append() : 0.034812 sec execution time of findName() : 0.000000 sec Performance counter stats for './phonebook_hash1' (100 runs): 27,316 cache-misses:u # 3.429 % of all cache refs ( +- 2.86% ) 796,708 cache-references:u ( +- 0.94% ) 222,014,236 instructions:u # 2.06 insn per cycle ( +- 0.02% ) 107,825,111 cycles:u ( +- 0.20% ) 0.035401871 seconds time elapsed ( +- 0.47% ) ``` * size:2^20^ ``` size of entry : 32 bytes execution time of append() : 0.050148 sec execution time of findName() : 0.000000 sec Performance counter stats for './phonebook_hash1' (100 runs): 1,158,246 cache-misses:u # 63.570 % of all cache refs ( +- 1.31% ) 1,822,013 cache-references:u ( +- 0.56% ) 227,000,271 instructions:u # 1.49 insn per cycle ( +- 0.02% ) 152,674,293 cycles:u ( +- 0.70% ) 0.061190897 seconds time elapsed ( +- 1.49% ) ``` * plot ![](https://i.imgur.com/LbJO5Gc.png) * 觀察與分析 * miss rate隨hash table變大遞減。 * L3 cache為8192K，每個entry \*佔8byte，所以，若L3 cache 全放hash table，size為8192*2^10^*2/8＝2^20^。因此在size為2^20^時，cache miss爆增。 * 因為與L3 cache大小有關，因此最佳的hash table size要視電腦而定。 * append()基本上在size:2^5^~2^15^都差不多，2^20^也是因為cache，所以爆增。 * size為1的時候，除了資料放置排序不同，其他都與縮小struct的版本相同，相當於沒有作hash。 * 總結來說，在hash table不超出cache能夠負荷的大小下，越大越可以減少衝突，進而減少cache miss。不過，為了避免不同function的差異太小，以下實作hash table size皆選擇2^10^。 ### BKDR Hash Function 給定seed值（31,131,1313,13131..）每個字符分別乘上seed的冪次，放大不同字符間的hash值。 * 新增hash table用來查詢 ``` #define MAX_HASH_TABLE_SIZE (1 << 10) entry *hashTable[MAX_HASH_TABLE_SIZE]; ``` * 在main.c中，初始化 ``` #ifdef OPT /*hashTable initial*/ for(i = 0;i < MAX_HASH_TABLE_SIZE;i++) hashTable[i] = NULL; i = 0; #endif ``` * 修改findName()、append()，並新增hashFunction()用來計算hash值 * hash值不能超過hash table的size。 * append傳入的entry *e是多餘的。 * append中，為了減少去尋找link list尾端的cost，將資料直接插入在hash table link到的前端，排序與原本的順序不同。若是測資"zyxel"可能為較好的情況，因此測資改為"aaah"。 ``` int hashFunction(char *str){//BKDR int seed = 31; int hash = 0; while(*str) hash = hash * seed + (*str++); return (hash & (MAX_HASH_TABLE_SIZE-1)); } entry *findName(char lastName[], entry *pHead) { int hash = hashFunction(lastName); pHead = hashTable[hash]; while(pHead != NULL) { if(strcasecmp(lastName, pHead->lastName) == 0) return pHead; pHead = pHead->pNext; } return NULL; } entry *append(char lastName[], entry *e) { int hash = hashFunction(lastName); entry *newEntry = (entry *)malloc(sizeof(entry)); strcpy(newEntry->lastName, lastName); if(hashTable[hash] != NULL) newEntry->pNext = hashTable[hash]; else newEntry->pNext = NULL; hashTable[hash] = newEntry; return e; } ``` * 結果 ``` size of entry : 32 bytes execution time of append() : 0.029924 sec execution time of findName() : 0.000002 sec Performance counter stats for './phonebook_hash1' (100 runs): 15,289 cache-misses:u # 23.985 % of all cache refs ( +- 1.35% ) 63,743 cache-references:u ( +- 4.46% ) 222,071,376 instructions:u # 2.13 insn per cycle ( +- 0.02% ) 104,279,619 cycles:u ( +- 0.41% ) 0.033203057 seconds time elapsed ( +- 0.61% ) ``` ![](https://i.imgur.com/b434L0x.png) * 觀察與分析 * 利用BKDR hash function，cache miss可以有效降低許多（61.211% -> 23.985%） * append()時間較直接作linl list長。 ### RS Hash Function 不斷改變seed，藉以打的更散。 * 修改hash function ``` int hashFunction(char *str) { /*RS*/ unsigned int b = 378551; unsigned int a = 63689; unsigned int hash = 0; while(*str){ hash = hash * a + (*str++); a *= b; } return (hash & (MAX_HASH_TABLE_SIZE-1)); } ``` * 結果 ``` size of entry : 32 bytes execution time of append() : 0.032518 sec execution time of findName() : 0.000002 sec Performance counter stats for './phonebook_hash1' (100 runs): 15,940 cache-misses:u # 24.485 % of all cache refs ( +- 0.94% ) 65,103 cache-references:u ( +- 2.63% ) 230,886,729 instructions:u # 2.12 insn per cycle ( +- 0.02% ) 108,876,394 cycles:u ( +- 0.21% ) 0.035154803 seconds time elapsed ( +- 0.44% ) ``` ![](https://i.imgur.com/4Qe2Pdj.png) * 觀察與分析 * 結果與BKDR hash差不多好。 * 在hash function中，使用的係數較大，可能會發生overflow，因此使用unsigned int。 ### DJB hash function 給hash初始值5381，seed = 33。 * 修改hash function ``` int hashFunction(char *str) { unsigned hash = 5381; while(*str) hash += (hash << 5) + (*str++); return (hash & (MAX_HASH_TABLE_SIZE-1)); } ``` * 結果 ``` size of entry : 32 bytes execution time of append() : 0.030914 sec execution time of findName() : 0.000002 sec Performance counter stats for './phonebook_hash1' (100 runs): 15,730 cache-misses:u # 24.761 % of all cache refs ( +- 1.00% ) 63,526 cache-references:u ( +- 3.22% ) 221,659,786 instructions:u # 2.13 insn per cycle ( +- 0.02% ) 103,942,023 cycles:u ( +- 0.28% ) 0.033741678 seconds time elapsed ( +- 0.48% ) ``` ![](https://i.imgur.com/nLVwIqX.png) ### SDBM hash function seed = 65599。 * 修改hash function ``` int hashFunction(char *str) { int hash = 0; while(*str) hash -= (hash << 6) + (hash << 16) + (*str++); return (hash & (MAX_HASH_TABLE_SIZE-1)); } ``` * 結果 ``` size of entry : 32 bytes execution time of append() : 0.034913 sec execution time of findName() : 0.000002 sec Performance counter stats for './phonebook_hash1' (100 runs): 15,790 cache-misses:u # 25.202 % of all cache refs ( +- 1.10% ) 62,656 cache-references:u ( +- 2.46% ) 230,260,615 instructions:u # 2.15 insn per cycle ( +- 0.02% ) 107,101,986 cycles:u ( +- 0.18% ) 0.034494732 seconds time elapsed ( +- 0.41% ) ``` ![](https://i.imgur.com/0Ydq90z.png) ### JS hash function * 修改hash function ``` int hashFunction(char *str) { unsigned int hash = 1315423911; while(*str) hash ^= ((hash << 5) + (hash >> 2) + (*str++); return (hash & (MAX_HASH_TABLE_SIZE-1)); } ``` * 結果 ``` size of entry : 32 bytes execution time of append() : 0.036478 sec execution time of findName() : 0.000002 sec Performance counter stats for './phonebook_hash1' (100 runs): 15,887 cache-misses:u # 25.624 % of all cache refs ( +- 1.15% ) 62,000 cache-references:u ( +- 3.19% ) 230,204,545 instructions:u # 2.15 insn per cycle ( +- 0.02% ) 107,252,037 cycles:u ( +- 0.21% ) 0.034041865 seconds time elapsed ( +- 0.47% ) ``` ![](https://i.imgur.com/doZsiKJ.png) ### hash function 測試小結 * plot ![](https://i.imgur.com/f7IxVbk.png) hash function|cache miss rate -------------|--------------- BKDR|23.985% RS|24.485% DJB|24.761% SDBM|25.202% JS|25.624% * 觀察與分析 * 這五個不同的hash function做出來的結果是差不多的。只要打的夠散，基本上結果不會差太多。 * 測資單一，可能會造成剛好這個結果好而已，無法確認最差情況。 ## 總結 * 從上面的實驗看下來，最好的結果： * entry size: 32byte * hash table size: 2^15^ * hash function: BKDR(實際情況是每個function差不多) * 結果 ``` size of entry : 32 bytes execution time of append() : 0.037358 sec execution time of findName() : 0.000000 sec Performance counter stats for './phonebook_hash1' (100 runs): 26,556 cache-misses:u # 3.372 % of all cache refs ( +- 2.11% ) 787,426 cache-references:u ( +- 0.81% ) 221,982,740 instructions:u # 2.07 insn per cycle ( +- 0.02% ) 107,257,013 cycles:u ( +- 0.16% ) 0.034824564 seconds time elapsed ( +- 0.42% ) ``` ![](https://i.imgur.com/pniiJXA.png) ## 問題回答 * 本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？ * 代表性不高。雖然真實姓名屬於有意義的單字，對於現有的字串壓縮來說是有差別的，而對於hash function來說，是沒有什麼差的。 * 資料越多在搜尋上的時間自然就比較多，而且所需的空間也越多，所以也不是說越多越好，要看有沒有用。 * 除了姓氏資料以外，也需要有名字，甚至其他更多的資料，而且姓氏必定會有重複，甚至名字也會，在搜尋的時候或許需要比對二到三欄才能確定是正確的人。

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.