# 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(R) Core(TM) i5-4210M CPU @ 2.60GHz
* Memory: 8G
* Cache:
* L1d cache: 32KB
* L1i cache: 32KB
* L2 cache: 256KB
* L3 cache: 3072KB

### 安裝前置作業

這邊看到 [@louielu](https://hackmd.io/CYJgZgHA7AnADAFgLQGMCmaCGSEGYCsyMARjPkgIwhS4gT4VwogJA===#) 用了 `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 ... !
:::danger
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](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 上面的說明，我的操作如下，過程沒有碰到任何問題：

$ 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 時間比較：

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

#### 使用 Hash Function

Hash Function 選用 [djb2](http://stackoverflow.com/questions/7666509/hash-function-for-string)

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

##### 撰寫時碰到的問題們（以下會以我的理解盡力解釋問題，如果有誤請務必指正我感謝 QQ）：
* Pointer 的觀念 ~~略懂略懂~~ 完全不懂 QQ
>> 無法用 C 語言開發出 C compiler & UNIX 等級的軟體，就是不懂 C 語言，沒有「略懂」這回事。 [name=jserv]

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

然後就 `Segment Fault` 了，後來查到[問題](http://stackoverflow.com/questions/6447744/segmentation-fault-around-strcpy)才發現原來我這樣子作是不對的。

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

*