2017q3 Homework1 (phonebook)

contributed by <twngbm>

系統環境

Distributor ID:	Ubuntu
Description:	Ubuntu 16.04.3 LTS
Release:	16.04
Codename:	xenial
    
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              8192K

原始碼閱讀-opt.txt輸出問題

• 一開始用make plot的時候，畫出來的兩張圖長的一樣

• 資料夾裏面只產生一個orig.txt檔，預期中的opt.txt並沒有產生

• 進入main裏面看到

  ​​​​#ifdef OPT
  ​​​​#define OUT_FILE "opt.txt"
  ​​​​#else
  ​​​​#define OUT_FILE "orig.txt"
  ​​​​#endif
  

• 但是上面有沒有看到 OPT的define，而且phonebook.h也沒有被include進來

• 看到main 裏面的IMPL

#include IMPL

• 再看到MakeFile

phonebook_opt: $(SRCS_common) phonebook_opt.c phonebook_opt.h clean
	$(CC) $(CFLAGS_common) $(CFLAGS_opt) \
		-DIMPL="\"$@.h\"" -o $@ \
		$(SRCS_common) $@.c

• 根據網路上的資料，-DIMPL會把 main.c裏面的 IMPL替換成後面給定的值，因此上面的指令會變成

cc -Wall -std=gnu99 -O0 \
	-DIMPL="\"phonebook_opt.h\"" -o phonebook_opt \
	main.c phonebook_opt.c

• 最後我們進入phonebook_opt.h裏面，我們可以發現

//#define OPT 1

• 將其取消註解即可正常輸出opt.txt和正常plot

Orig輸出

size of entry : 136 bytes
execution time of append() : 0.055486 sec
execution time of findName() : 0.010031 sec

• 用gnuplot繪圖後(修改scripts/runtime.gp)
  

• 接著用

$ make cache-test
Performance counter stats for './phonebook_orig' (100 runs):

          464,1253      cache-misses              #   93.015 % of all cache refs      ( +-  0.14% )
          498,9790      cache-references                                              ( +-  0.32% )
       2,6225,0077      instructions              #    1.18  insn per cycle           ( +-  0.02% )
       2,2253,6808      cycles                                                        ( +-  0.66% )

       0.076652806 seconds time elapsed                                          ( +-  0.77% )

可以看到高達93.015%的cache misses

優化1-減少struct大小

• 看到phonebook_orig.h

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    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];
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

• 這裡定義了entry是一個linked list 的結構，每一個節點裡面都存有上面列出的所有資料(last name,first name,email…)。每一個節點的大小是136bytes。

• 我們一個list的結構大小是136bytes，我電腦的L1 cache 是32K，因此我頂多只能放32x1024/（136X8）=30.12，30個entry在cache裏面，但是我們的基數有35萬個，因此cache-miss一定會很常發生。（引用自programming small）

• 嘗試將不需要處理的資訊移出原本的資料結構，並用一指標儲存
• 因為我們的搜尋是用lastname來去搜尋的，因此我把lastname獨立出來做一個結構，再用指標指向詳細資料的結構

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];
} pDATA;
typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __PHONE_BOOK_DATA *pDATA;
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

• 執行後我們發現entry的大小變成32bytes，因此可預期cache的內可存放的entry會變多。

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

          459,1314      cache-misses              #   93.554 % of all cache refs      ( +-  0.15% )
          490,7672      cache-references                                              ( +-  0.17% )
       2,6084,8591      instructions              #    1.26  insns per cycle          ( +-  0.02% )
       2,0721,3607      cycles                                                        ( +-  0.39% )

       0.061480693 seconds time elapsed                                          ( +-  0.82% )


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

          151,5075      cache-misses              #   67.984 % of all cache refs      ( +-  0.40% )
          222,8564      cache-references                                              ( +-  0.31% )
       2,4404,7516      instructions              #    1.73  insns per cycle          ( +-  0.02% )
       1,4083,7182      cycles                                                        ( +-  0.62% )

       0.039998826 seconds time elapsed                                          ( +-  0.79% )

可以發現cashe-miss的情況減少了27%
從圖片中也可以發現append和find執行時間有所減少

優化2-hash table

• 希望能利用hash的方法來解決linked list的循序搜循的時間複雜度為O(n)的情況，利用hash表來解決這個問題

• 本例利用BKDR hash,seed 選131,bucket大小選擇是4093

1. 首先先引入hash function

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

• 這邊我們定義SIZE的大小為4093，SIZE的意義為Hash table的大小，同時也是hash bucket的數量

2. 修改main.c

entry *hash_table_index[SIZE];
    for (i = 0; i < SIZE; i++) {
        hash_table_index[i] = ( entry *) malloc(sizeof(entry));
    }

• 在這邊我建構 an array of pointer to struct entry
• entry是利用優化1中，減小的data struct 來實作
• 建構完array之後，我就可以利用hash functin return 回來的key值，直接存取在array中的記憶體位址中的變數
• 此處中array所存放的變數為pointer to struct entry，因此我只要利用 hash_table_index[key]->lastName即可取出lastName資料

3. 建構append()和findName()

• append()

void *append(char lastName[], entry *hash_table_index[])
{
    int key = hash(lastName);
    entry *temp = hash_table_index[key];
    hash_table_index[key] = (entry *) malloc(sizeof(entry));
    strcpy(hash_table_index[key]->lastName,lastName);
    hash_table_index[key]->pNext = (temp == NULL) ? NULL : temp;
    return NULL;
}

• 為了解決collision的情況，因此我使用linked list來儲存同一個key的所有資料
• struet entry 中保留 struct __PHONE_BOOK_ENTRY *pNext

• 原來的作法是，進入linked list之後，一一比較每個*pNext的值直到list的末端（pNext==NULL）
• 耗時過長因此更改作法

• 後來更改作法為，直接在linked list 的頭，插入新的資料節點
• 將hash_table_indes[key]的pointer指向新的節點，將新的節點的pNext指向後方原來存在的linked list
• 35行判斷此新增的資料結構是否為新的節點或是在bucket中已有其他資料結構，來判斷是否指向NULL或是原有的linked list

• findName()

int findName(char lastName[], entry *hash_table_index[])
{
    unsigned long key = hash(lastName);
    entry *now = hash_table_index[key];
    while (now->pNext != NULL) {
        if (strcasecmp(lastName, now->lastName) == 0)
            return 1;
        now = now->pNext;
    }
    return 0;
}

• 透過hash function算出key值後，透過array的存取來進入linked list中的第一個節點，並判斷字串是否相同，不相同則進入第二個節點
• 如果有找到則回傳1

5. 結果

• 首先先比較執行時間（原版,結構優化,Hash）
  
  

關於append time

1. 優化後的資料結構，在進行append的時候，因為資料結構較小，因此fetch進cache時，可以減少cache miss的機會，因此執行時間較快
2. hash雖然是使用優化後的資料結構，但是因為必須進行hash運算，所以整體的append時間約莫跟原版的一樣，但是還是比原版略快一點（某些情況下可以差到5%左右的時間）

關於findName time

1. 優化後的資料結構，因為size較小，所以cache miss較少，固執行速度比原版快
2. 經過hash之後，search 的average time變成Θ(1)，雖然有linked list的Θ(n)存在，但是整體的搜尋時間已經變成線性的了，根據實測，每個bucket中的數量大概在80~100之間
3. 建構hash_table的缺點是，需要額外得記憶體空間來儲存hash table，本例使用hash table 內的儲存內容為pointer 因此額外的記憶體空間為8*SIZE bytes。

• 再來比較cache miss

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

          234,1706      cache-misses              #   90.686 % of all cache refs      ( +-  0.15% )
          258,2200      cache-references                                              ( +-  0.21% )
       2,2097,8273      instructions              #    1.26  insns per cycle          ( +-  0.02% )
       1,7572,3132      cycles                                                        ( +-  0.55% )

       0.049907710 seconds time elapsed                                          ( +-  1.03% )

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

           85,3654      cache-misses              #   72.777 % of all cache refs      ( +-  0.38% )
          117,2979      cache-references                                              ( +-  0.37% )
       2,0419,5625      instructions              #    1.64  insns per cycle          ( +-  0.02% )
       1,2425,1403      cycles                                                        ( +-  0.44% )

       0.034413972 seconds time elapsed                                          ( +-  0.56% )

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

           54,8297      cache-misses              #   68.200 % of all cache refs      ( +-  0.37% )
           80,3950      cache-references                                              ( +-  1.07% )
       2,4281,2531      instructions              #    1.66  insns per cycle          ( +-  0.02% )
       1,4605,8299      cycles                                                        ( +-  0.41% )

       0.040509766 seconds time elapsed                                          ( +-  0.50% )

hash中整體的cache miss影響在於bucket 數量的影響，實測過當bucket=32時，cache misses rate比bucket=4096時高了5%左右

QA

本例選用的 dataset (也就是輸入電話簿的姓名)有代表性嗎？跟真實英文姓氏差異大嗎？

本例子選用的資料，與真實英文姓名相差頗大。
但是作為phonebook的dataset，必須考慮有人可能在新增資料時，就不注重名字的正確性，有些人可能只是想要儲存一個自己能夠看懂的資料進去。

資料難道「數大就是美」嗎？

如果資料庫的大小越大，那麼我們就需要更符合資料庫結構的演算法來幫助我們儲存資料，甚至必須考慮，針對不同的search key去建立不同的資料結構，來符合快速的搜尋目的。

如果我們要建立符合真實電話簿情境的輸入，該怎麼作？

1. 如果是像本案例，由一排序過的檔案進行輸入，則可以使用hash來進行append
2. 如果是隨機輸入，則可以使用TST來進行append，並利用system idle time來進行balance。

Reference

• https://hackpad.com/ep/pad/static/xWkbsmaWVEn
• https://hackmd.io/s/rJCs_ZVa#優化版本2-–-hash-function
• http://blog.techbridge.cc/2017/01/21/simple-hash-table-intro/
• https://www.byvoid.com/zht/blog/string-hash-compare