2016q3 Homework1 (phonebook)

contributed by <RayPan>

Reviewed bt `finalallpass`

因為沒有使用細部資料，可以考慮重建structure時不需多用一個指標指回細部資料。可以再減少8bytes的entry size。
可能可以分析一下為何djb2和BKDR的cache-misses的差異從何而來。
修改structure的部分可以補上cache reference的結果

開發環境

第一次使用linux作業系統
花了不少時間研究指令

raypan@raypan-X550JD:~$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
Thread(s) per core:    2
Core(s) per socket:    2
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 60
Model name:            Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz
Stepping:              3
CPU MHz:               2782.281
CPU max MHz:           3400.0000
CPU min MHz:           800.0000
BogoMIPS:              5587.62
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              3072K
NUMA node0 CPU(s):     0-3

請考慮升級到 Ubuntu 16.04，不然某些軟體套件會太舊 jserv
升級16.04版
$ sudo apt-get update && sudo apt-get dist-upgrade
$ sudo reboot
$ sudo update-manager -d

GitHub

簡介
是一個基於網站基礎的託管服務 (hosting service)平台，它提供了以Git為唯一的版本控制系統。
常用指令
$ git init:要開始使用 Git 你必須先建立一個 Git 的 Repository。
$ git remote add origin git@github.com:your_account/your_repository.git:可以連結到遠端的repository。
$ git clone git@github.com:Username/repository.git:可將遠端的repository複製一份到本機，若遇防火牆阻隔問題，請改用HTTPS通訊協定:https://github.com/...
$ git remote -v:查看working directory所連結的遠端repository。
$ git status：查看目前working directory中所有檔案的情形。
$ git add：將未被git追蹤的檔案加入追蹤，可最後加上.追蹤全部檔案。
$ git commit:將檔案提交。
$ git push:上傳到遠端repository。
$ git pull:從遠端更新

效能分析工具-Perf

應用程式可以利用 PMU (Performance Monitoring Unit), tracepoint 和核心內部的特殊計數器 (counter) 來進行統計，另外還能同時分析運行中的核心程式碼

常用指令
perf list : 印出perf可以觸發哪些event
perf top : 找出拖慢系統的熱點
perf stat : 已經有個要優化的目標，對這個目標進行特定或一系列的event檢查，進而了解該程序的效能概況。
perf stat -r 10 cache-misses ./example表示對特定程式example執行10次perf其cache-misses
perf record ：針對函式級別進行 event 統計，方便我們對程序「熱點」作更精細的分析和優化。

參考資料：成大wiki-Linux效能分析工具：Perf

Makefile

規則
target: dependencies
<tab>command
- target: 所要建立的檔案。
- dependencies：相依項目，make會依據此決定是否要重新編譯targey。
- commands:建立targets的指令。

注意：make 在編譯時，若發現 target 比較新，也就是 dependencies 都比 target 舊，那麼將不會重新建立 target，如此可以避免不必要的編譯動作。

.PHONY: 指定後面的為fake項目，利用.PHONY: clean來指定clean為fake項目,被視為要建立clean這個檔案，但永不被執行。

變數宣告

MACRO = value ：可利用$(MACRO)或${MARCO}來存取已定義的變數。
：= ：變數的值決定於它在Makefile中的位置，而不是整個Makefile展開後最終的值。
?= : 若變數未定義，則替它指定新的值。否則採用原有的值。
內部變數

$? ：已被更新的dependencies的值，i.e.dependencies中，比targets還新的值。
$@ : targets的值。
$< : 第一個dependencies的值。
$* : targets所指定的檔案，但不包含副檔名。
特別字元

@ ：不要顯示執行的指令在螢幕上。
- : 即使該行指令出錯，也不會中斷執行。
-DMACRO: 指定一個MARCO的名字。
參考資料： Makefile 語法簡介、猴子都會寫的Makefile

張貼程式碼時，請注意縮排 (空白，而非 tab，與原本程式碼一致的風格) 並且避免單行後方非必要的空白 jserv

延伸閱讀: The Lost Art of C Structure Packing jserv

可能的效能改進方法

改寫struct __PHONE_BOOK_ENTRY
使用 Hash function 加速查詢
使用字串壓縮的演算法，降低資料表示的成本
使用 binary search tree 改寫演算法

改善過程

未修改之前

size of entry : 136 bytes
execution time of append() : 0.053688 sec
execution time of findName() : 0.004984 sec

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

         1,003,292      cache-misses              #   84.258 % of all cache refs      ( +-  0.32% )
         1,190,732      cache-references                                              ( +-  0.20% )
       260,911,327      instructions              #    1.39  insns per cycle          ( +-  0.02% )
       187,778,382      cycles                                                        ( +-  0.19% )

       0.057238264 seconds time elapsed                                          ( +-  0.60% )

1. 修改`struct __PHONE_BOOK_ENTRY`

由main.c可知






#ifndef OPT
    e = pHead;
    assert(findName(input, e) &&
           "Did you implement findName() in " IMPL "?");
    assert(0 == strcmp(findName(input, e)->lastName, "zyxel"));
#endif

程式僅透過lastname來查找
其他聯絡人資訊可以放入另一個結構中
如有需要
透過pDetail來索取額外聯絡人資訊
可以減少entry的大小達到優化

修改後程式碼如下

















typedef struct __PHONE_BOOK_DETAILS{
    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];
}details;

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __PHONE_BOOK_DETAILS *pDetails;
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

執行看看

在執行程式之前先清空cache:
$ echo 1 | sudo tee /proc/sys/vm/drop_caches

size of entry : 32 bytes
execution time of append() : 0.037598 sec
execution time of findName() : 0.004964 sec

如此entry的大小變可縮小至32bytes

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

           135,386      cache-misses              #   44.511 % of all cache refs      ( +-  0.63% )
           304,164      cache-references                                              ( +-  0.45% )
       244,033,296      instructions              #    1.94  insns per cycle          ( +-  0.02% )
       125,671,746      cycles                                                        ( +-  0.20% )

       0.038329599 seconds time elapsed                                          ( +-  0.50% )

可以發現cache-misses由原本的84.258%下降至44.511%

接著使用makeplot繪製效能比較圖
由於main.c中83行，OPT存在才能輸出opt.txt，所以在phonebook.h中必須#define OPT 1


#if defined(OPT)
    output = fopen("opt.txt", "a");

繪圖如下

避免用圖片來表達文字輸出 jserv
不要只做執行時間的比較，要對照看 cache reference 的差異，拿出你的專業來 jserv

2.使用Hash function 加速查詢

（1）使用djb2 hash函式

參考共筆：rni c

捨棄原本的sequential search
首先利用hashInitial（）建立hash table
hash table size訂為65537（質數）
結構hashTable內包含tableSize及list









hashTable *hashInitial(){
    hashTable *ht = NULL;
    ht = (hashTable *)malloc(sizeof(hashTable));
    ht->list = (entry **)malloc(sizeof(entry *)*HASHTABLE_SIZE);
    for (int i = 0; i < HASHTABLE_SIZE; i++)
        ht->list[i] = NULL;
    
    return ht;
}

注意：選擇hashTable大小為質數的原因為
避免hash collison（輸入字串不同，雜湊值相同）

hashFunction使用Dan Bernstein提出的djb2hash函式






unsigned int hashFunction(char *lastName){
    unsigned int hashVal = 0;
    while (*lastName != '\0')
        hashVal = (hashVal << 5) + *lastName++;
    return hashVal % HASHTABLE_SIZE;
}

改寫append函式
可以注意到由於findname長度已定義在MAX_LAST_NAME_SIZE
所以將原本strcpy改為strncpy
可省去比對其他無效字元。








int hashAppend(char *lastName, hashTable *ht){
    entry *newEntry;
    newEntry = (entry *)malloc(sizeof(entry));
    strncpy(newEntry->lastName, lastName, MAX_LAST_NAME_SIZE);
    newEntry->pNext = ht->list[hashFunction(lastName)];
    ht->list[hashFunction(lastName)] = newEntry;
    return 0;
}

size of entry : 32 bytes
execution time of append() : 0.054746 sec
execution time of findName() : 0.000008 sec

可以發現到
由於須另外建構一個hashtable
append的執行時間會略為上升
但查找時間會大幅下降

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

           151,896      cache-misses              #   38.517 % of all cache refs      ( +-  2.53% )
           394,365      cache-references                                              ( +-  0.76% )
       298,128,462      instructions              #    1.70  insns per cycle          ( +-  0.03% )
       175,143,354      cycles                                                        ( +-  0.53% )

       0.053467373 seconds time elapsed                                          ( +-  0.82% )

cache misses也下降到了38.517%

（2）使用BKDR hash函式

參考老師提供的Programming Small









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 % HASHTABLE_SIZE;
}

size of entry : 32 bytes
execution time of append() : 0.052487 sec
execution time of findName() : 0.000008 sec

執行時間大略相同

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

           106,166      cache-misses              #   26.940 % of all cache refs      ( +-  1.09% )
           394,080      cache-references                                              ( +-  0.26% )
       298,896,581      instructions              #    1.71  insns per cycle          ( +-  0.03% )
       174,642,726      cycles                                                        ( +-  0.57% )

       0.052549821 seconds time elapsed                                          ( +-  0.57% )

但會發現cache-misses可以再下降到26.397%

其他筆記

關於前置處理器#if defined

若有兩個c檔案同時include同一個標頭檔，但要同時編譯成一個檔案，會造成衝突。

#if defined（ABC） or #ifdef(ABC)  //若ABC有定義過（i.e. #define） 
   程式1   則編譯程式1（非執行）
#else 
   程式2   否則編譯程式2
#endif

參考資料： #ifndef#define#endif的用法(整理) 原作者：icwk

關於gcc參數

-c : 只做編譯並生成目標文件。
-g : 編入除錯資訊（使用gdb時必要）。
-O0 : 不進行優化（注意：是英文字母大歐+零）。
-Wall ：顯示所有警告訊息。

關於指標大小

32bits的電腦,指標大小為4bytes
64bits的電腦,指標大小為8bytes

作業詳細資訊：A01: phonebook

2016q3 Homework1 (phonebook)

Reviewed bt finalallpass

開發環境

GitHub

效能分析工具-Perf

Makefile

規則

變數宣告

內部變數

特別字元

可能的效能改進方法

改善過程

未修改之前

1. 修改struct __PHONE_BOOK_ENTRY

2.使用Hash function 加速查詢

（1）使用djb2 hash函式

（2）使用BKDR hash函式