2017q3 Homework1 (phonebook)

contributed by < vasv75182366 >

開發環境

​​​​$uname -a
​​​​Linux uscca22-Aspire-M5810 4.4.0-96-generic #119-Ubuntu SMP Tue Sep 12 14:59:54 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux

​​​​$lsb_release -a
​​​​No LSB modules are available.
​​​​Distributor ID:	Ubuntu
​​​​Description:	Ubuntu 16.04.3 LTS
​​​​Release:	16.04
​​​​Codename:	xenial
​​​​
​​​​$lscpu
​​​​Architecture:          x86_64
​​​​CPU 作業模式：    32-bit, 64-bit
​​​​Byte Order:            Little Endian
​​​​CPU(s):                8
​​​​On-line CPU(s) list:   0-7
​​​​每核心執行緒數：2
​​​​每通訊端核心數：4
​​​​Socket(s):             1
​​​​NUMA 節點：         1
​​​​供應商識別號：  GenuineIntel
​​​​CPU 家族：          6
​​​​型號：              30
​​​​Model name:            Intel(R) Core(TM) i7 CPU         860  @ 2.80GHz
​​​​製程：              5
​​​​CPU MHz：             1200.000
​​​​CPU max MHz:           2801.0000
​​​​CPU min MHz:           1200.0000
​​​​BogoMIPS:              5586.03
​​​​虛擬：              VT-x
​​​​L1d 快取：          32K
​​​​L1i 快取：          32K
​​​​L2 快取：           256K
​​​​L3 快取：           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 rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf pni dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm sse4_1 sse4_2 popcnt lahf_lm tpr_shadow vnmi flexpriority ept vpid dtherm ida
​​​​
​​​​$free
​​​​              total        used        free      shared  buff/cache   available
​​​​Mem:       16423308     2705868    13140196      102348      577244    13297076
​​​​置換：      999420           0      999420

Linux 效能分析工具: Perf

照著perf 原理和實務的步驟練習指令

• 偵測這個 process 每個指令所耗費的 CPU cycle，可按下 a 進一部做分析。
  $ perf top -p $pid
• 列出可偵測的event。
  $ perf list
• 針對 binary檔重複執行 n 次，偵測指定的event，在這個作業中主要需要顯示cache-misses、cache-references、instructions、cycles這四個 event。
  $ perf stat --repeat <num> -e <event> <bin>

案例探討：電話簿搜尋

按照步驟先 clone 專案再執行 make 編譯

執行make run後的輸出：

​​​​size of entry : 136 bytes
​​​​execution time of append() : 0.068812 sec
​​​​execution time of findName() : 0.005673 sec
​​​​3

閱讀程式碼

觀察主程式流程：
紀錄 append 起始時間→讀取資料並 append 建 Singly Linked List→紀錄 append 結束時間→紀錄 findName 起始時間→紀錄 findName 結束時間→釋放記憶體

在 append 以及 findName 是要進行優化的地方，注意到在程式最後沒有妥善釋放記憶體：

    if (pHead->pNext) free(pHead->pNext);
    free(pHead);

先對 main.c 根據 phonebook_orig.h 的資料結構做修改：

    entry *tmp;
    while (pHead->pNext) {
        tmp = pHead->pNext;
        free(pHead);
        pHead = tmp;
    }
    free(pHead);

執行

​​​​$ make cache-test

查看未優化過的 cache-misses：

​​​​ Performance counter stats for './phonebook_orig' (100 runs):

​​​​     1,349,155      cache-misses              #   93.717 % of all cache refs      ( +-  0.10% )
​​​​     1,439,606      cache-references                                              ( +-  0.14% )
​​​​   326,375,105      instructions              #    1.18  insns per cycle          ( +-  0.01% )
​​​​   277,271,600      cycles                                                        ( +-  0.11% )

​​​​   0.090609402 seconds time elapsed                                          ( +-  0.33% )

優化

修改 Makefile

參考 HMKR 的共筆修改 Makefile 內的 cache-test 讓資料更新

修改資料結構 ( Data Structure )

• 減少 entry 大小
  由於僅須查找 lastName，所以只保留 lastName 以及 pNext 在 entry 內，並且另外建立一個資料結構紀錄其他資訊，使 entry size 從 136 bytes 變成 32 bytes

    typedef struct __PHONE_BOOK_DETAIL {
        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];

    } detail;
    typedef struct __PHONE_BOOK_ENTRY {
        char lastName[MAX_LAST_NAME_SIZE];
        detail *pDetail;
        struct __PHONE_BOOK_ENTRY *pNext;
    } entry;

​​​​ Performance counter stats for './phonebook_opt' (100 runs):

​​​​       334,623      cache-misses              #   79.267 % of all cache refs      ( +-  0.41% )
​​​​       422,146      cache-references                                              ( +-  1.21% )
​​​​   287,704,114      instructions              #    1.45  insns per cycle          ( +-  0.01% )
​​​​   197,902,294      cycles                                                        ( +-  0.50% )

​​​​   0.067796114 seconds time elapsed                                          ( +-  0.72% )

降低 entry 的大小可以使 cache 內存放更多筆 entry 降低 cache-misses

利用雜湊表加速搜尋 ( Hash Table )

根據前面已修改過的資料結構增加 Hash Table 的查詢功能，另外新增了兩個檔案 phonebook_hash.c 、 phonebook_hash.h ， findName 以及 append 兩個函式都沒有做變動，僅增加運算雜湊值的函式：

BKRD Hash

unsigned int BKDRHash(char *str)
{

    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
    while (*str) {
        hash = hash * seed + (*str++);
    }
    return (hash & 0x7FFFFFFF) % HASH_TABLE_SIZE;
}

以及

#define HASH 1

用來在 main.c 內根據 #ifdef HASH 來做差別運算
修改 Makefile 、 calculate.c 、 runtime.png 以新增 hash 過後的數據進行比較

以下是使用 hash table size 為 1024 的 BKDRHash 結果

​​​​Performance counter stats for './phonebook_hash' (100 runs):

​​​​       899,631      cache-misses              #   60.016 % of all cache refs      ( +-  0.31% )
​​​​     1,498,980      cache-references                                              ( +-  0.30% )
​​​​   319,910,641      instructions              #    1.05  insns per cycle          ( +-  0.01% )
​​​​   306,092,376      cycles                                                        ( +-  0.16% )

​​​​   0.102225082 seconds time elapsed                                          ( +-  0.46% )

Cache miss 明顯從 80% 下降至 60%

在 append 所需的時間由於要進行 hash 明顯上升，但是在 findName 的時間明顯可以透過查表大幅下降

回答問題

• 有代表性嗎？跟真實英文姓氏差異大嗎？
  • 根據 dictionary/words.txt 內的資料來看，看起來並不太具有代表性，因為其中包含了如 zzzzzz、zzz之類的非英文姓氏的單字，並且在真實生活中名字會因各種情況而有其他差異，例如：部份名字較為熱門常見、根據地區或可能有所不同。
• 資料難道「數大就是美」嗎？
  • 資料如果沒有辦法被分析成有用的資訊，甚至化為知識、成就智慧，對大部分的人而言就只是霸佔儲存空間，或許對於樂於挑戰將之化為有用的資訊的人才是美吧。
• 如果我們要建立符合真實電話簿情境的輸入，該怎麼作？
  • 需有新增、查詢、修改、刪除功能
  • 每一筆資料的完整度並不一定，資料結構上需要再做修改
  • 實際電話簿是一筆龐大資料，虛有足夠儲存空間並配合如 hadoop 之類的分散式運算。