2017q3 Homework1 (phonebook)

# 2017q3 Homework1 (phonebook) ###### tags: `sysprog2017` `dev_record` contributed by <`HTYISABUG`> >**TODO**: 列出 malloc 後得到的位置[color=red] ## 系統環境 ```shell $ uname -a Linux overworld 4.10.0-35-generic #39-Ubuntu SMP Wed Sep 13 09:02:42 UTC 2017 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): 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: 94 Model name: Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz Stepping: 3 CPU MHz: 1137.817 CPU max MHz: 3500.0000 CPU min MHz: 800.0000 BogoMIPS: 5184.00 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 6144K NUMA node0 CPU(s): 0-7 $ free total used free shared buff/cache available Mem: 16326616 2833948 10524780 82344 2967888 13008632 Swap: 2097148 0 2097148 ``` ## 查閱資料這份作業的目標是降低執行時的 cache miss 與時間先上網查詢降低 cache miss 的方法查閱幾篇在 stackoverflow 與 wikipedia 的文章後 >> 為何先不看經典著作呢？你需要完整的背景知識 >> [name="jserv"][color=red] 統整出降低 cache miss 的方法大概有 1. 使用較小的資料結構 * 讓 cache 一次能存多點資料 2. 儘量讓資料連續 * 因為 cache 會猜下一筆資料你也要用 * **spatial locality** 3. 少用動態記憶體配置 * 理由跟第2項一樣，動態配置會讓資料離散 4. 確保會在迴圈中用到的資料是會頻繁呼叫的 * 直接避開 cache miss * **temporal locality** 5. 避免讓條件式判斷頻繁變動 * 這跟 cache 比較沒關係，是 branch prediction 的問題 * 能增進效能就姑且先記下 6. 還有其他再補上條列下來幾乎都是要求資料連續但現在不知道電話簿內會有幾份資料因此採用陣列讓資料連續不可行 ## 檢查程式碼先檢查 phonebook_orig.c 可以從 append 觀察到原版採用的資料結構是 linked list linked list 只能一條線查到底，中途有很多不必要的資料也被查到將資料依規則建表方式重新儲存應該能減少查詢時間因此決定採用建立 hash table 的方法 > 是 [linked list](https://en.wikipedia.org/wiki/Linked_list)，有 "-ed" > [name="jserv"][color=red] ## 嘗試建表以不同的 **hash function** 及 **hash table 長度**當作變數進行實驗 Hash function 用單純取 mod 及 BKDR 兩種, hash table 長度 `2017` 實驗結果如下 ![](https://i.imgur.com/VFnDd7U.png) |hash function|cache-misses|time(sec) | |-------------|------------|-----------| |original |90.158% |0.055980279| |mod |69.753% |0.102894758| |bkdr |68.086% |0.109897377| Hash table 長度 `2017`, `4013`, `8191`, hash function 用 bkdr 實驗結果如下 ![](https://i.imgur.com/jwqWEmK.png) |hash function|cache-misses|time(sec) | |-------------|------------|-----------| |original |90.158% |0.055980279| |bkdr 2k |68.086% |0.109897377| |bkdr 4k |69.324% |0.111428125| |bkdr 8k |69.412% |0.111067196| 從以上結果看, 建立 hash table 可以有效降低 findName 的執行時間 cache-miss 也略降低至原本的 **0.75~0.77** 倍 append 時間提升至 **1.22-1.25** 倍總時間升至原本的 **2** 倍從實驗結果看來 hash table 能再縮短搜索時間起到極佳的作用且能略為減少 cache-miss > 使用精確的話語來描述，像是 hash function 的選擇和資料表示的策略 > [name="jserv"][color=red] ## 縮小資料結構要減少 cache miss 的話還能讓 cahce 塞下儘可能多筆資料 ```c #define MAX_LAST_NAME_SIZE 16 typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; // 16B char firstName[16]; // 16B char email[16]; // 16B char phone[10]; // 10B char cell[10]; // 10B char addr1[16]; // 16B char addr2[16]; // 16B char city[16]; // 16B char state[2]; // 2 B char zip[5]; // 5 B struct __PHONE_BOOK_ENTRY *pNext; // 8 B } entry; // 131B ``` 這是電腦的 cache 資訊 ```shell L1d cache: 32K L2 cache: 256K L3 cache: 6144K ``` 現在大約有 350k 筆資料，總合約 46mB 就算三層 cache 合計也不過能存 50k 左右筆資料當然 cache-miss 在 findName 時會噴的很嚴重當前 append 跟 findName 在使用時都只用到 lastName 跟 pNext 所以其他的資料欄位其實可以到需要用時再分配空間光是這樣就預計每筆資料能省下 99B , 總計 35mB 的空間資料結構更改如下 ```c typedef struct { 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]; } Data; typedef struct __PHONE_BOOK_ENTRY { char lastName[MAX_LAST_NAME_SIZE]; // 16B Data *data; // 8 B struct __PHONE_BOOK_ENTRY *pNext; // 8 B } entry; // 32B ``` Hash function 選用 bkdr , table size `2017` 實驗結果如下 ![](https://i.imgur.com/VSyTlx3.png) |hash function|cache-misses|time(sec) | |-------------|------------|-----------| |original |90.248% |0.056481064| |bkdr 2k |68.086% |0.109897377| |optimized |64.235% |0.067265891| 縮小資料讓 append 比沒縮小的情況快了一些同時也降低了 cache miss 實驗中出了個小問題，讀取到的資料大小跟預期的不符 |資料大小 |預計 |實際| |---------|----|----| |original |131B|136B| 經同學提醒才想起還有 data structure alignment 這回事系統架構為 64bits , 所以一次應該會捉 8B 不過這不影響實驗結果，只是個插曲 ## 修改 Makefile 看了 [HMKRL](https://hackmd.io/s/HyyHC6moW) 的共筆才發現之前在做 hash table 測試的時候資料都沒更新修改 cache-test 讓資料能更新上方結果圖已更新 ## 將 malloc 改成取自 memory pool 在作業公佈欄底下有看到 memory pool 在 [wikipedia](https://en.wikipedia.org/wiki/Memory_pool) 查了一下就做了個簡單的版本試試效果 ```c= typedef struct { void *ptr; size_t size; size_t cnt; } MemPool; void *poolloc(size_t size, MemPool *pool) { if (pool->cnt + size <= pool->size) { void *p = pool->ptr + pool->cnt; pool->cnt += size; return p; } return NULL; } ``` Memory pool 先給了 400k 筆資料的空間實驗結果如下 ![](https://i.imgur.com/qF5PGSZ.png) |hash function |cache-misses|time(sec) | |--------------------|------------|-----------| |original |90.248% |0.056481064| |bkdr 2k |68.086% |0.109897377| |bkdr + reduce |64.235% |0.067265891| |bkdr + reduce + pool|40.694% |0.028073860| 實驗結果顯示 memory pool 大幅減少 append 的時間應該是因為 malloc 所耗去的時間藉由預先分配一大段記憶體 (memory pool)來省掉了同時因為 pool 是一整段<span style='color: red;'>**連續**</span>記憶體所以讀取時 cache miss 也比前一版本更進一步降低 ## 問題 :::danger 本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？ ::: :::success 是，大部份甚至都不是名字 ::: :::danger 有代表性嗎？跟真實英文姓氏差異大嗎？ ::: :::success 無代表性雖然有意義的單字也不少但連`zzzzzzz`這種毫無意義的東西都混進來了現實根本沒人用這種姓氏 ::: :::danger 資料難道「數大就是美」嗎？ ::: :::success 要視情況例如在人工智慧、資料分析領域大量的資料就像寶藏但其他領域大量的資料可能讀取困難導致拖垮效能 ::: :::danger 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？ ::: :::success 1. 填入名字 (新增資料) 2. 填入其他資訊 (擴增資料) 3. 存檔關閉 4. 視情況對同一人進行編輯 (編輯資料) * 總之應對各種情況的選項是不可或缺的 * 同時搜索要夠快, 不然資料一多起來再度編輯會找很慢 ::: ## 參考資料 [How does one write code that best utilizes the CPU cache to improve performance? (stackoverflow)](https://stackoverflow.com/questions/763262/how-does-one-write-code-that-best-utilizes-the-cpu-cache-to-improve-performance)  [Cache prefetching (wikipedia)](https://en.wikipedia.org/wiki/Cache_prefetching) [What is “cache-friendly” code? (stackoverflow)](https://stackoverflow.com/questions/16699247/what-is-cache-friendly-code)  [Data structure alignment (wikipedia)](https://en.wikipedia.org/wiki/Data_structure_alignment)