2017q1 Homework1(phonebook)

contributed by<yanang>

tags:yananag

Reviewed by csielee

• 最後 append() 時間上沒有下降，可以考慮實作 memory pool ，讓 malloc 呼叫次數減少，讓 append() 時間下降

開發環境

• OS: Ubuntu 16.04 LTS
• L1d cache: 32K
• L1i cache: 32K
• L2 cache: 256K
• L3 cache: 3072K
• Architecture: x86_64
• CPU 作業系統: 32-bit, 64-bit
• Byte Order: Little Endian
• CPU(s): 4
• Model name: Intel® Core™ i5-7200U CPU @ 2.50GHz
• Linux yanang 4.8.0-36-generic
  #36~16.04.1-Ubuntu SMP

未優化版本

• 執行: $ ./phonebook_orig

size of entry : 136 bytes
execution time of append() : 0.105205 sec
execution time of findName() : 0.004954 sec

• cache test $sudo make cache-test

         4,868,866      cache-misses              #   93.482 % of all cache refs      ( +-  0.20% )
         5,208,353      cache-references                                              ( +-  0.38% )
       262,398,775      instructions              #    1.35  insn per cycle           ( +-  0.02% )
       194,347,267      cycles                                                        ( +-  0.77% )

       0.064319469 seconds time elapsed  

version 1 - 減少資料結構

• 在 main.c append() findName() 當中可以發現目前只使用了 lastName 這項數據，也就是說其他項數據都是可以忽略的，但是考慮到不能喪失原本 phonebook 的功能，所以我們將其餘的數據到另一個 struct 。

typedef struct __PHONE_BOOK_ENTRY_REMAIN {
    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_remain;

typedef struct __PHONE_BOOK_ENTRY {
	char lastName[MAX_LAST_NAME_SIZE];
	struct __PHONE_BOOK_ENTRY_REMAIN *remain;
	struct __PHONE_BOOK_ENTRY *pNext;
} entry;

• 資料將以 linklist 方式

• 執行時間：

size of entry : 32 bytes
execution time of append() : 0.137438 sec
execution time of findName() : 0.002579 sec

• cache test
  • cache miss 明顯降低

         1,679,608      cache-misses              #   68.692 % of all cache refs      ( +-  0.48% )
         2,445,143      cache-references                                              ( +-  0.81% )
       244,480,047      instructions              #    1.84  insn per cycle           ( +-  0.02% )
       132,706,657      cycles                                                        ( +-  1.11% )

       0.044007362 seconds time elapsed 

• 圖表分析：
  
  雖然由此來看 append() 的時間是減少的，但是如果要使用到其餘的資料，則 append() 的時間應該會略高於原本的時間。

version 2 - hash function

• 在閱讀許多資料後，我將 hash table 建於 main.c ，並利用 #ifdef OPT_HASH 達到目的。
• 因為在 各種字符串Hash函数比較 當中 BKDRHash 函數的綜合評分最高，所以就選用此種方式。

可以參考閱讀 BKDR hash 詳盡解說 並嘗試引入其他 hash function 實驗比較課程助教

unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131;
    unsigned int hash = 0;

    while (*str)
    {
        hash = hash * seed + (*str++);
    }

    return (hash & 0x7FFFFFFF) % SIZE_OF_TABLE;
}

• 原先想以後置的方式將資料 link 起來，但是若要找到 list 的尾端將需要多 loop ，為了增進效能就放棄改為前置。

entry *pHead = (entry *) malloc (sizeof(entry));
pHead->pNext = e[hash];
e[hash] = pHead;
strcpy(pHead->lastName,lastName);
/*      entry *pLast = (entry *) malloc (sizeof(entry));
        pLast -> pNext = NULL ;
        strcpy(pLast->lastName,lastName);
        e[hash] -> pNext = pLast;
        * not finished
        * should add loop to find the last data
*/

• 執行時間：

size of entry : 24 bytes
execution time of append() : 0.039091 sec
execution time of findName() : 0.000009 sec

• cache test：

           437,137      cache-misses              #   58.419 % of all cache refs      ( +-  1.13% )
           748,282      cache-references                                              ( +-  2.45% )
       232,794,043      instructions              #    1.82  insn per cycle           ( +-  0.02% )
       127,598,545      cycles                                                        ( +-  0.89% )

       0.042041802 seconds time elapsed 

• 圖表分析：
  • hash 主要是將 findname() 的時間大幅減少。
    

修改錯誤訊息

• git push 之後突然發現 git commit 的 message 打錯字了，參閱 XYZ的筆記本

$ git commit --amend
$ git push --force-with-lease origin master