2016q3 Homework01 (phonebook)

contributed by <hugikun999>
Reviewed by <heathcliffYang>

Reviewed by heathcliffYang

在拿到一份程式碼之後，可以先嘗試把所有的程式碼理解、仔細看Makefile裡到底有那些指令，就可以大略知道這份程式碼的目的，也才不會走很多冤枉路(也是我的切身之痛QQQQQ)
如果時間足夠的話，應該可以再花更多力氣嘗試不同的優化方法，或者嘗試不同的data set

開發環境

• OS： Ubuntu16.04 LTS
• CPU: i7-4712MQ
• RAM: 8G
• Disk: 200G
  

安裝完成進入系統後發現File和Trash無法打開，重新開機後這個問題就消失了。另外我安裝的是英文版本，所以參考了網路上的作法安裝了ibus的拼音輸入。

如何在 Ubuntu 16.04 上使用預設的 ibus 中文輸入法 （及如何使用倉頡萬用字元）

Github

我以前曾經使用過github上面的source code,但是沒有自己的github帳戶,算是第一次使用。花了一些時間在github的ssh上面，主要是參考官方網站的教學的教學，比較不一樣的是我沒有用到xclip。

• 複製ssh key

$ cd .ssh 
$ vim id_rsm.pub

Perf

$ perf list				//perf可以觸發的event
$ perf stat				//顯示出統計結果
$ perf stat -e cache-misses		//記錄cache $misses的情況
$ perf stat --repeat			//重覆執行
$ perf top				//即時監測正在運行的工作
$ perf record				//統計函式級別的運作
$ perf record -g				//更詳細記錄每個函式
$ perf record -F				//增加取樣頻率
$ perf report				//觀看perf record的結果

Phonebook

遇到的問題

• make plot出來的圖表不會更新（已解決）－>記得要刪除orig.txt和opt.txt才會產生正確的圖表

我只有在下載phonebook後的第一次make plot才會有正確圖表產生，之後做的修改可以成功執行並cache-misses有正確的改變，但是圖表仍會出現第一次的結果。

優化方法

記錄一些平常可能會用到的優化想法和這次的目標

• 數據的分離或合併－如果有些數據是經常一起使用，可以將這些數據定意為一個結構體，減少之間的距離。如果一個結構體內有些資料較常用到就可以另建一個結構體給它們。

• 在陣列中，同一行的資料是相臨的，同一列卻不是。

• 減少cache misses

• 減少instruction

• binary search tree

function

strcasecmp(const char* s1,const char* s2)

說明：比較s1和s2字串的長度,會忽略大小寫。

回傳值： 0 字串相符； >0 s1長度大於s2； <0 s1 長度小於s2

malloc(size_t size)

說明：配置一個size大小的空間並回傳地址，此函式所配置的記憶體在程式結束前不會歸還，必須使用free()才能將記憶體歸還。

回傳值：動態計憶體的位置。

fgets(char* str, int n, FILE* stream)

說明：將streamn所指向的文件複製到str字串中，n指的是最大被讀取的字符數。

回傳值： successful 回傳str； 若為文件的最後回傳null pointer； error 回傳null pointer

未優化

底下是尚未優化執行100次的結果，可以發現cache-misses高達84.843％，instruction也多達2意6千萬次，由此可知從減少cache misses是一個明顯的目標。

優化後

1.重新寫一個結構體：原本的entry中存有許多的資料，真正用到的卻只有lastname和pNext，所以我寫了一個other去放其它的資料，可以看到cache misses已經降低了許多，instruction卻沒有明顯的減少。另外由於other沒有malloc()給它,所以append()的時間沒有增加。

typedef struct __PHONE_BOOK_OTHER {
    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];
} other;

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

如果在append()中將other配置記憶體會造成幾乎所有數據都變更差。

entry *append(char lastName[], entry *e)
{
    e->other = (other *) malloc(sizeof(other));
    e->pNext = (entry *) malloc(sizeof(entry));
    e = e->pNext;
    strcpy(e->lastName, lastName);
    e->pNext = NULL;

    return e;
}

2.Hash function:原本的搜尋方法必須從頭到尾每一筆資料都比對，透過hash function先將資料依照開頭字母做分類，我在entry中多加了一個pOther，在append()時先比對第一個字母如果不同則將指標指向pOther，如此一來便可大幅減少花在findname()的時間。但是會造成在append()的時間小幅上升，另外分類的寫法必須建立在database已經按字母排序的前題下。

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    other *other;
    struct __PHONE_BOOK_ENTRY *pNext;
    struct __PHONE_BOOK_ENTRY *pOther;
} entry;

static entry *record;
static int i=0;
/* FILL YOUR OWN IMPLEMENTATION HERE! */
entry *findName(char lastname[], entry *pHead)
{
    /* TODO: implement */
    pHead = pHead ->pNext;
    
    while (pHead != NULL) 
    {
        if(lastname[0] == pHead->lastName[0])
        {
            if (strcasecmp(lastname, pHead->lastName) == 0)
                return pHead;
            pHead = pHead->pNext;
        }
        else
            pHead = pHead->pOther;
            
    }
    return NULL;
}

entry *append(char lastName[], entry *e)
{
   // e->other = (other *) malloc(sizeof(other));
    if( i == 0 )
    {
        e->pNext = (entry *) malloc(sizeof(entry));
        e = e->pNext;
        strcpy(e->lastName, lastName);
        e->pNext = NULL;
        i++;
        record = e;
        return e;
    }
    else if(e->lastName[0] == lastName[0])
    {
        e->pNext = (entry *) malloc(sizeof(entry));
        e = e->pNext;
        strcpy(e->lastName, lastName);
        e->pNext = NULL;
        return e;
    }
    else 
    {
        e = record;
        e->pOther = (entry *) malloc(sizeof(entry));
        e = e->pOther;
        strcpy(e->lastName, lastName);
        e->pNext = NULL;
        record = e;
        return e;
    }
}