2016q3 Homework1 (phonebook)

contributed by <atlantis0914>

未優化版本

• Entry

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;

​使用perf量測cache miss

         1,354,901      cache-misses #   68.477 % of all cache refs (73.93%)
         1,770,259      cache-references (75.52%)
       305,758,311      instructions #    1.21  insns per cycle (76.75%)
       258,470,718      cycles (75.60%)

       0.091748655 seconds time elapsed ( +-  0.74% )

使用B-Tree實做

• 介紹

  • B-Tree(Bayer-McCreight, 1972):
    參數為degree，或稱branching factor，表示一個node包含的children數量，B-Tree儲存的資料為key-value的組合，標準的B-Tree結構為（以degree ＝M為例）：

    • Leaf: 
      為key-value pair儲存的地方，可以儲存L個key-value pair，每個leaf的高度相同。

    • Internal node:
      為key儲存的地方，每個node最多可以儲存M-1個key，以及M/2至M個children。

    • Root:
      可以儲存2至M個children。

  • 一個標準的B-Tree如下圖:

• 這次實作的B-Tree是針對phonebook做的修改，如下:

  • 1. Root、Internal node與Leaf均為同一種data type。
  • 2. 儲存的data以value取代標準的key-value pair。
  • 3. 實做部份參考了：
    http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/BTree.java.html
    只是將Java用C語言改寫

• 以圖示來表達資料結構:

  • Entry:
  ​typedef struct __BTREE_ENTRY {
  ​	char lastName[MAX_LAST_NAME_NUM];
  ​	struct __BTREE_NODE *pNext;
  ​} bTreeEntry;
  

  

  • Node:
  ​typedef struct __BTREE_NODE {
  ​int degree;
  ​struct __BTREE_ENTRY children[DEGREE];
  ​} bTreeNode;
  

  ​​  其中DEGREE為一個Node可以儲存的entry個數，相當於branching factor。
  

  

• 以下是B-Tree如何進行append(以DEGREE = 4為例):

  

  此時root的degree已經等於DEGREE的值(DEGREE = 4)，root會分裂並且新增root如下:

  

  繼續append…

  

  

  此時左下角的Node已經滿了，必須分裂

  

  繼續append

  

  

  右下角的Node滿了，必須分裂

  

  這時候Root滿了，同樣要再分裂

  

  從圖中描述可以得知，B-Tree在append的過程是不斷的往上長。

DEGREE = 64

           721,939      cache-misses              #   76.656 % of all cache refs      (74.79%)
           922,121      cache-references                                              (75.07%)
     3,193,521,105      instructions              #    2.12  insns per cycle          (75.39%)
     1,503,996,958      cycles                                                        (75.03%)

       0.514395667 seconds time elapsed                                          ( +-  0.26% )

DEGREE = 128

           625,691      cache-misses              #   66.105 % of all cache refs      (74.92%)
           915,545      cache-references                                              (75.03%)
     4,722,925,716      instructions              #    2.21  insns per cycle          (75.16%)
     2,096,578,194      cycles                                                        (75.04%)

       0.747960187 seconds time elapsed                                          ( +-  0.65% )

• findName()的時間比之前的Unrolled linked list低了許多，但是append()的執行時間卻暴增許多，增加DEGREE的值又再增加append()的執行時間，推測原因為append()內使用了許多for loop所導致。

改進方向:

• 減少append()所需的時間。
• 實作delete()。