Try   HackMD

2017q3 Homework1 (phonebook)

tags: sysprog2017 dev_record

contributed by <HTYISABUG>

TODO: 列出 malloc 後得到的位置

系統環境

$ 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 的文章後

為何先不看經典著作呢？你需要完整的背景知識
"jserv"

統整出降低 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，有 "-ed"
"jserv"

嘗試建表

以不同的 hash function 及 hash table 長度當作變數進行實驗

Hash function 用單純取 mod 及 BKDR 兩種, hash table 長度 2017
實驗結果如下

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
實驗結果如下

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 的選擇和資料表示的策略
"jserv"

縮小資料結構

要減少 cache miss 的話還能讓 cahce 塞下儘可能多筆資料

#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 資訊

L1d cache:             32K
L2 cache:              256K
L3 cache:              6144K

現在大約有 350k 筆資料，總合約 46mB
就算三層 cache 合計也不過能存 50k 左右筆資料
當然 cache-miss 在 findName 時會噴的很嚴重

當前 append 跟 findName 在使用時都只用到 lastName 跟 pNext
所以其他的資料欄位其實可以到需要用時再分配空間
光是這樣就預計每筆資料能省下 99B , 總計 35mB 的空間

資料結構更改如下

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
實驗結果如下

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 的共筆才發現之前在做 hash table 測試的時候資料都沒更新
修改 cache-test 讓資料能更新
上方結果圖已更新

將 malloc 改成取自 memory pool

在作業公佈欄底下有看到 memory pool
在 wikipedia 查了一下就做了個簡單的版本試試效果

















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 筆資料的空間
實驗結果如下

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 是一整段連續記憶體
所以讀取時 cache miss 也比前一版本更進一步降低

問題

本例選用的 dataset (也就是輸入電話簿的姓名) 是否存在問題？

是，大部份甚至都不是名字

有代表性嗎？跟真實英文姓氏差異大嗎？

無代表性
雖然有意義的單字也不少
但連zzzzzzz這種毫無意義的東西都混進來了
現實根本沒人用這種姓氏

資料難道「數大就是美」嗎？

要視情況
例如在人工智慧、資料分析領域大量的資料就像寶藏
但其他領域大量的資料可能讀取困難
導致拖垮效能

如果我們要建立符合真實電話簿情境的輸入，該怎麼作？

  1. 填入名字 (新增資料)
  2. 填入其他資訊 (擴增資料)
  3. 存檔關閉
  4. 視情況對同一人進行編輯 (編輯資料)
  • 總之應對各種情況的選項是不可或缺的
  • 同時搜索要夠快, 不然資料一多起來再度編輯會找很慢

參考資料

How does one write code that best utilizes the CPU cache to improve performance? (stackoverflow)

Cache prefetching (wikipedia)

What is “cache-friendly” code? (stackoverflow)

Data structure alignment (wikipedia)

Last changed by 
 
TSUNGYU HSIEH
0
679
Published on HackMD