2016q3 Homework1 (phonebook)

contributed by <petermouse>

Reviewed by <`jkrvivian`>

可以嘗試引入不同的hash function 進行效能比較
還有其他的方法可以實驗，如：字串壓縮法
還未引進符合現實狀況的 data set實驗
改良版本v2貼上的每段程式碼，加入說明會比較清楚
參考How to Write a Git Commit Message，Title以大寫開頭
8dc5a4f從標題看不出在哪裡做了甚麼修改

開發環境

OS:Lubuntu 16.04 LTS
Memory: 8 GB
CPU:
- Name:
  - Intel® Core™ i5-4200H CPU @ 2.80GHz
- Cache:
  - L1d Cache： 32K
  - L1i Cache： 32K
  - L2 Cache： 256K
  - L3 Cache： 3072K
- Frequency:
  - CPU max MHz: 3400
  - CPU min MHz: 800

測試時governor皆設定為performance

$ cpupower frequency-set -g performance (需root權限)

Frequency: > 2.8 GHz

Perf測試

根據Linux 效能分析工具: Perf perf_top_example.c做測試

Samples: 1K of event 'cycles:pp', Event count (approx.): 951215754      
Overhead  Shared O  Symbol                                              
  99.40%  test      [.] compute_pi_baseline
   0.41%  [kernel]  [k] _nv014159rm
   0.06%  [kernel]  [k] _nv014096rm
   0.06%  [kernel]  [k] pci_conf1_read
   0.06%  [kernel]  [k] __internal_add_timer
   0.01%  [kernel]  [k] entry_SYSCALL_64_fastpath
   0.00%  [kernel]  [k] native_write_msr_safe

「程式輸出的文字訊息」請勿使用圖片表示，請改由文字貼上課程助教
不好意思，已更正petermouse

大部分的執行時間都花在了compute_pi_baseline上

Makefile

ing…

Phone Book

原始版本

不修改code，執行make cache-test看cache miss rate

結果:

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

         1,024,374      cache-misses              #   85.793 % of all cache refs      ( +-  0.26% )
         1,194,011      cache-references                                              ( +-  0.30% )
       260,843,909      instructions              #    1.38  insns per cycle          ( +-  0.02% )
       188,829,353      cycles                                                        ( +-  0.51% )

       0.057309105 seconds time elapsed                                          ( +-  0.92% )

100次平均時間

append() 0.037041
findName() 0.005024

改良版本v1

在原始版本中，因為struct太大，導致cache中最多能夠存的資料量極少，cache miss機率高，影響到效能，因此最直接的作法是改良struct的大小。

將phonebook_opt.h資料結構改變。


















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];
}data;

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __PHONE_BOOK_DATA *pData; // a pointer to other data
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

而phonebook_opt.c與phonebook_orig.c大致相等。

結果

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

           139,238      cache-misses              #   46.657 % of all cache refs      ( +-  0.35% )
           298,427      cache-references                                              ( +-  0.45% )
       244,614,107      instructions              #    1.93  insns per cycle          ( +-  0.02% )
       126,809,543      cycles                                                        ( +-  0.40% )

       0.038456267 seconds time elapsed                                          ( +-  0.51% )

100次平均時間

append() 0.030186
findName() 0.001915

長條圖

Cache miss 大幅降低，但仍有45%
而append()與findName()時間都減少了
我並沒有分配空間給其他資料，所以還不能存取

改良版本v2

因為資料多達35萬筆，且採用linked list結構，萬一資料在linked list尾端，每次重頭搜尋會花太多時間。
解決辦法：引入hash(使用djb2)，pHead也改為陣列。
以下為幾個程式碼片段(main.c)


#define PRIME_NUM 42737










unsigned int Hash(char *str) //djb2
{
    unsigned long hash = 5381;
    int c;

    while ((c = *str++)) 
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash%PRIME_NUM;
}


    pHead = (entry *) malloc(sizeof(entry)*PRIME_NUM);


        e=pHead+Hash(line);
        e=append(line, e);

結果：

可以發現append會比較花時間，而findName幾乎瞬間完成，原因是append需要經過hash才能append，findName反而透過hash使得總體要找的linked list資料變少，幾乎瞬間完成。

因為測資只有一筆資料(zyxel)，如果有多筆資料的查詢，findName會節省更多時間，將會比前兩組有更好的效能

改良版本v3

待續

參考資料

課程video
Linux 效能分析工具: Perf
使用gnuplot科學作圖