2017q3 Homework1 (phonebook)

--- tags: 研究所 --- # 2017q3 Homework1 (phonebook) contributed by <twngbm> ## 系統環境 ``` Distributor ID: Ubuntu Description: Ubuntu 16.04.3 LTS Release: 16.04 Codename: xenial L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 8192K ``` ## 原始碼閱讀-opt.txt輸出問題 + 一開始用make plot的時候，畫出來的兩張圖長的一樣 + 資料夾裏面只產生一個orig.txt檔，預期中的opt.txt並沒有產生 + 進入main裏面看到 ```c=9 #ifdef OPT #define OUT_FILE "opt.txt" #else #define OUT_FILE "orig.txt" #endif ``` + 但是上面有沒有看到 OPT的define，而且phonebook.h也沒有被include進來 + 看到main 裏面的IMPL ```c=7 #include IMPL ``` + 再看到MakeFile ```c=24 phonebook_opt: $(SRCS_common) phonebook_opt.c phonebook_opt.h clean $(CC) $(CFLAGS_common) $(CFLAGS_opt) \ -DIMPL="\"$@.h\"" -o $@ \ $(SRCS_common) $@.c ``` + 根據網路上的資料，-DIMPL會把 main.c裏面的 IMPL替換成後面給定的值，因此上面的指令會變成 ``` cc -Wall -std=gnu99 -O0 \ -DIMPL="\"phonebook_opt.h\"" -o phonebook_opt \ main.c phonebook_opt.c ``` + 最後我們進入phonebook_opt.h裏面，我們可以發現 ```c=8 //#define OPT 1 ``` + 將其取消註解即可正常輸出opt.txt和正常plot ## Orig輸出 ``` size of entry : 136 bytes execution time of append() : 0.055486 sec execution time of findName() : 0.010031 sec ``` * 用gnuplot繪圖後(修改scripts/runtime.gp) ![](https://i.imgur.com/0r4f3Fc.png) * 接著用 ``` $ make cache-test Performance counter stats for './phonebook_orig' (100 runs): 464,1253 cache-misses # 93.015 % of all cache refs ( +- 0.14% ) 498,9790 cache-references ( +- 0.32% ) 2,6225,0077 instructions # 1.18 insn per cycle ( +- 0.02% ) 2,2253,6808 cycles ( +- 0.66% ) 0.076652806 seconds time elapsed ( +- 0.77% ) ``` 可以看到高達93.015%的cache misses ## 優化1-減少struct大小 + 看到phonebook_orig.h ```c= typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; 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]; struct __PHONE_BOOK_ENTRY *pNext; } entry; ``` :::info * 這裡定義了entry是一個linked list 的結構，每一個節點裡面都存有上面列出的所有資料(last name,first name,email...)。每一個節點的大小是136bytes。 * 我們一個list的結構大小是136bytes，我電腦的L1 cache 是32K，因此我頂多只能放32x1024/（136X8）=30.12，30個entry在cache裏面，但是我們的基數有35萬個，因此cache-miss一定會很常發生。（引用自[programming small](https://hackmd.io/s/SkfffA-jZ)） ::: * 嘗試將不需要處理的資訊移出原本的資料結構，並用一指標儲存 * 因為我們的搜尋是用lastname來去搜尋的，因此我把lastname獨立出來做一個結構，再用指標指向詳細資料的結構 ```c= typedef struct __PHONE_BOOK_DATA { 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]; } pDATA; typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; struct __PHONE_BOOK_DATA *pDATA; struct __PHONE_BOOK_ENTRY *pNext; } entry; ``` + 執行後我們發現entry的大小變成32bytes，因此可預期cache的內可存放的entry會變多。 ``` Performance counter stats for './phonebook_orig' (100 runs): 459,1314 cache-misses # 93.554 % of all cache refs ( +- 0.15% ) 490,7672 cache-references ( +- 0.17% ) 2,6084,8591 instructions # 1.26 insns per cycle ( +- 0.02% ) 2,0721,3607 cycles ( +- 0.39% ) 0.061480693 seconds time elapsed ( +- 0.82% ) Performance counter stats for './phonebook_opt' (100 runs): 151,5075 cache-misses # 67.984 % of all cache refs ( +- 0.40% ) 222,8564 cache-references ( +- 0.31% ) 2,4404,7516 instructions # 1.73 insns per cycle ( +- 0.02% ) 1,4083,7182 cycles ( +- 0.62% ) 0.039998826 seconds time elapsed ( +- 0.79% ) ``` 可以發現cashe-miss的情況減少了27% 從圖片中也可以發現append和find執行時間有所減少 ![](https://i.imgur.com/0Lhn0mn.png) ## 優化2-hash table * 希望能利用hash的方法來解決linked list的循序搜循的時間複雜度為O(n)的情況，利用hash表來解決這個問題 + 本例利用BKDR hash,seed 選131,bucket大小選擇是4093 1. 首先先引入hash function ```c=7 unsigned long hash(char *str) { unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0; while (*str) { hash = hash*seed + (*str++); } hash &= 0x7FFFFFFF; return (hash %= SIZE); } ``` :::info + 這邊我們定義SIZE的大小為4093，SIZE的意義為Hash table的大小，同時也是hash bucket的數量 ::: 2. 修改main.c ```c=52 entry *hash_table_index[SIZE]; for (i = 0; i < SIZE; i++) { hash_table_index[i] = ( entry *) malloc(sizeof(entry)); } ``` :::info + 在這邊我建構 an array of pointer to struct entry + entry是利用優化1中，減小的data struct 來實作 + 建構完array之後，我就可以利用hash functin return 回來的key值，直接存取在array中的記憶體位址中的變數 + 此處中array所存放的變數為pointer to struct entry，因此我只要利用 hash_table_index[key]->lastName即可取出lastName資料 ::: 3. 建構append()和findName() + append() ```c=29 void *append(char lastName[], entry *hash_table_index[]) { int key = hash(lastName); entry *temp = hash_table_index[key]; hash_table_index[key] = (entry *) malloc(sizeof(entry)); strcpy(hash_table_index[key]->lastName,lastName); hash_table_index[key]->pNext = (temp == NULL) ? NULL : temp; return NULL; } ``` :::info + 為了解決collision的情況，因此我使用linked list來儲存同一個key的所有資料 + struet entry 中保留 struct ____PHONE_BOOK_ENTRY *pNext__ ::: :::warning + 原來的作法是，進入linked list之後，一一比較每個*pNext的值直到list的末端（pNext==NULL） + 耗時過長因此更改作法 ::: :::info + 後來更改作法為，直接在linked list 的頭，插入新的資料節點 + 將hash_table_indes[key]的pointer指向新的節點，將新的節點的pNext指向後方原來存在的linked list + 35行判斷此新增的資料結構是否為新的節點或是在bucket中已有其他資料結構，來判斷是否指向NULL或是原有的linked list ::: + findName() ```c=17 int findName(char lastName[], entry *hash_table_index[]) { unsigned long key = hash(lastName); entry *now = hash_table_index[key]; while (now->pNext != NULL) { if (strcasecmp(lastName, now->lastName) == 0) return 1; now = now->pNext; } return 0; } ``` :::info + 透過hash function算出key值後，透過array的存取來進入linked list中的第一個節點，並判斷字串是否相同，不相同則進入第二個節點 + 如果有找到則回傳1 ::: 5. 結果 + 首先先比較執行時間（原版,結構優化,Hash） ![](https://i.imgur.com/OMp7aBm.png) :::info 關於append time 1. 優化後的資料結構，在進行append的時候，因為資料結構較小，因此fetch進cache時，可以減少cache miss的機會，因此執行時間較快 2. hash雖然是使用優化後的資料結構，但是因為必須進行hash運算，所以整體的append時間約莫跟原版的一樣，但是還是比原版略快一點（某些情況下可以差到5%左右的時間）關於findName time 1. 優化後的資料結構，因為size較小，所以cache miss較少，固執行速度比原版快 2. 經過hash之後，search 的average time變成Θ(1)，雖然有linked list的Θ(n)存在，但是整體的搜尋時間已經變成線性的了，根據實測，每個bucket中的數量大概在80~100之間 3. 建構hash_table的缺點是，需要額外得記憶體空間來儲存hash table，本例使用hash table 內的儲存內容為pointer 因此額外的記憶體空間為8*SIZE bytes。 ::: + 再來比較cache miss ``` Performance counter stats for './phonebook_orig' (100 runs): 234,1706 cache-misses # 90.686 % of all cache refs ( +- 0.15% ) 258,2200 cache-references ( +- 0.21% ) 2,2097,8273 instructions # 1.26 insns per cycle ( +- 0.02% ) 1,7572,3132 cycles ( +- 0.55% ) 0.049907710 seconds time elapsed ( +- 1.03% ) Performance counter stats for './phonebook_opt_small_structure' (100 runs): 85,3654 cache-misses # 72.777 % of all cache refs ( +- 0.38% ) 117,2979 cache-references ( +- 0.37% ) 2,0419,5625 instructions # 1.64 insns per cycle ( +- 0.02% ) 1,2425,1403 cycles ( +- 0.44% ) 0.034413972 seconds time elapsed ( +- 0.56% ) Performance counter stats for './phonebook_opt_hash' (100 runs): 54,8297 cache-misses # 68.200 % of all cache refs ( +- 0.37% ) 80,3950 cache-references ( +- 1.07% ) 2,4281,2531 instructions # 1.66 insns per cycle ( +- 0.02% ) 1,4605,8299 cycles ( +- 0.41% ) 0.040509766 seconds time elapsed ( +- 0.50% ) ``` :::info hash中整體的cache miss影響在於bucket 數量的影響，實測過當bucket=32時，cache misses rate比bucket=4096時高了5%左右 ::: ## QA :::warning 本例選用的 dataset (也就是輸入電話簿的姓名)有代表性嗎？跟真實英文姓氏差異大嗎？ ::: :::info 本例子選用的資料，與真實英文姓名相差頗大。但是作為phonebook的dataset，必須考慮有人可能在新增資料時，就不注重名字的正確性，有些人可能只是想要儲存一個自己能夠看懂的資料進去。 ::: :::warning 資料難道「數大就是美」嗎？ ::: :::info 如果資料庫的大小越大，那麼我們就需要更符合資料庫結構的演算法來幫助我們儲存資料，甚至必須考慮，針對不同的search key去建立不同的資料結構，來符合快速的搜尋目的。 ::: :::warning 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？ ::: :::info 1. 如果是像本案例，由一排序過的檔案進行輸入，則可以使用hash來進行append 2. 如果是隨機輸入，則可以使用TST來進行append，並利用system idle time來進行balance。 ::: ### Reference + https://hackpad.com/ep/pad/static/xWkbsmaWVEn + https://hackmd.io/s/rJCs_ZVa#優化版本2-–-hash-function + http://blog.techbridge.cc/2017/01/21/simple-hash-table-intro/ + https://www.byvoid.com/zht/blog/string-hash-compare