2016q3 Homework1 (phonebook)

contributed by <aweimeow>

tags: `sysprog21` `aweimeow`

Reviewed by `HuangWenChen`

這裡只有使用一個 hash function 作效能分析，可以嘗試使用不同 hash function 去做各個 hash function 效能比較
可以利用字串壓縮法將名子長度縮小
github 尚未更新

作業環境

OS: Ubuntu 14.04.4 LTS
CPU: Intel® Core™ i5-4210M CPU @ 2.60GHz
Memory: 8G
Cache:
- L1d cache: 32KB
- L1i cache: 32KB
- L2 cache: 256KB
- L3 cache: 3072KB

安裝前置作業

這邊看到 @louielu 用了 lstopo 這個工具覺得很酷所以也想安裝一下，這邊紀錄一下安裝的流程:

Install lstopo

wget https://www.open-mpi.org/software/hwloc/v1.11/downloads/hwloc-1.11.4.tar.gz
tar zxvf hwloc-1.11.4.tar.gz
cd hwloc-1.11.4
cat README # 不過他的 README 沒有說明要怎麼安裝 Orz

./configure
make
sudo make install

BUT … !

libhwloc.so.5: cannot open shared object file: No such file or directory

後來找了一下發現 libhwloc.so.5 在 /usr/local/lib 裡面，所以我手動修改了 /usr/local/lib，再執行 ldconfig

輸出：

Machine (7879MB)
  Package L#0 + L3 L#0 (3072KB)
    L2 L#0 (256KB) + L1d L#0 (32KB) + L1i L#0 (32KB) + Core L#0
      PU L#0 (P#0)
      PU L#1 (P#1)
    L2 L#1 (256KB) + L1d L#1 (32KB) + L1i L#1 (32KB) + Core L#1
      PU L#2 (P#2)
      PU L#3 (P#3)
  HostBridge L#0
    PCIBridge
      PCI 10de:1341
    PCI 8086:0416
      GPU L#0 "card0"
      GPU L#1 "renderD128"
      GPU L#2 "controlD64"
    PCIBridge
      PCI 10ec:8168
        Net L#3 "eth0"
    PCIBridge
      PCI 168c:0036
        Net L#4 "wlan0"
    PCI 8086:8c03
      Block(Removable Media Device) L#5 "sr0"
      Block(Disk) L#6 "sda"

Install perf

根據 wiki 上面的說明，我的操作如下，過程沒有碰到任何問題：

$ sudo apt-get install linux-tools-common
$ sudo apt-get install linux-tools-4.2.0-27-generic linux-cloud-tools-4.2.0-27-generic

perf stat 存取局域性結果差異：

$ perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./test

 Performance counter stats for './test' (5 runs):

         2,614,830      cache-misses              #    2.525 % of all cache refs    
       100,415,393      cache-references                                            
     2,006,482,671      instructions              #    0.81  insns per cycle        
     2,409,393,663      cycles                                                      

       0.803709786 seconds time elapsed                                          ( +- 14.38% )

$ perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./test

 Performance counter stats for './test' (5 runs):

           217,059      cache-misses              #   63.407 % of all cache refs    
           347,854      cache-references                                            
     2,005,971,913      instructions              #    1.93  insns per cycle        
     1,032,907,799      cycles                                                      

       0.334975609 seconds time elapsed                                          ( +-  0.97% )

Install gnu plot

$ apt-get install gnuplot

Install astyle

$ apt-get install astyle

進入主題: phonebook

在我的電腦上，未修改的程式碼的 cache-miss 為 81.418%

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

         1,154,821      cache-misses              #   81.418 % of all cache refs    
         1,389,198      cache-references                                            
       263,656,721      instructions              #    1.06  insns per cycle        
       240,380,961      cycles                                                      

       0.081547701 seconds time elapsed                                          ( +-  0.82% )

以下先試試使用改變資料結構來改善效能

改變資料結構です

我們先從 phonebook_opt.h 來開始下手，讓我們先思考一個問題：在要查找電話簿時， key 應該是什麼？想當然是名字，在翻找電話簿時，找到名字後，跟隨在其後的地址、信箱、電話號碼 … 才會需要被看到。

因此，來修改一下程式碼，將 firstName, email, phone, … 這些資料先藏起來放到另一個資料結構中，我把它取名為 detail，搜尋到時可以存取這一筆 entry 裡面的細節（信箱、電話、…）

typedef struct __PHONE_BOOK_ENTRY_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];
    struct detail *detail;
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

這樣子改善之後，我們的 cache-miss 會下降多少呢？

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

           158,618      cache-misses              #   38.030 % of all cache refs    
           437,759      cache-references                                            
       245,272,988      instructions              #    1.52  insns per cycle        
       163,283,836      cycles                                                      

       0.053033708 seconds time elapsed                                          ( +-  1.06% )

從輸出當中我們可以觀察到 cache-miss 從 81.418% 下降到 38.030%

下圖是這個階段執行完的 function 時間比較：
compare for modify data structure

可以從圖中發現，時間也有明顯的下降。

使用 Hash Function

Hash Function 選用 djb2

不過真的很久沒有碰過 C 語言了，改改 header file 還可以，要重拾三年前的 C 語言讓我碰到滿滿的挫折（或者說以前根本沒好好學 C）

撰寫時碰到的問題們（以下會以我的理解盡力解釋問題，如果有誤請務必指正我感謝 QQ）：

Pointer 的觀念 ~~略懂略懂~~ 完全不懂 QQ

無法用 C 語言開發出 C compiler & UNIX 等級的軟體，就是不懂 C 語言，沒有「略懂」這回事。 jserv

entry *people;
strcpy(people->lastName, lastName);

然後就 Segment Fault 了，後來查到問題才發現原來我這樣子作是不對的。

在這邊都是指標，指標儲存的是一個記憶體位址，所以我直接把 lastName copy 到 people->lastName 就相當於：以 lastName 為 'AAAA' 來說，就是把 0x41414141 寫到 people->lastName，所以這個 pointer 就會指到這個奇怪的地址去，所以就錯了。