2016q1 Homework1 (phonebook)

contributed by <kylingithub>

Reviewed by <`snoopy831002`>

建議可以每個版本git commit一次
建議可以補上使用perf找熱點，因為如果hash function沒有經過特殊處理 append()應該會比opt版本還要慢，因為要進行hash(可以使用perf看出來)

環境設置

使用光碟安裝lubuntu16.04 於筆電，與win10共存
- UEFI開機
  第一次安裝時，出現無法安裝的情況，推測是win10預設為UEFI開機模式。因此進入BIOS關閉UEFI–>Disable，但這樣一來win10就無法正常使用。
  參考[]
  重新安裝一次即可成功。
- 輸入法
  系統預設的語言包是簡單的注音，就算安裝新酷音選字的選單也會顯示黑屏，無法正常使用。
  因此參考[]將系統的顯示語言改成ibus後，安裝新酷音即可正常使用。
- 音效卡
  想要一邊看教學影片一邊實做練習時，發現影片竟然沒有聲音！
  推測是驅動程式的問題，參考[]，進入alsa
  但仍無法正常使用，因此去尋找其他的Driver
  參考音效程式安裝，將系統內建的ALSA解除安裝，並裝上pavucontrol，即可聽到聲音，即可順利進行。

C語言的複習

觀看你所不知道的C語言：指標篇
陣列

陣列的參數傳遞：C語言只能傳遞指標,無法傳遞陣列的內容。
Pointer 觀念整理

Pointer 實驗
- 以下為測試程式碼




























#include <stdlib.h>
#include <stdio.h>

int b =2048;
void testfunc(int** ptrptr){
    printf("In function Before : ptrptr = %d , *ptrptr = %d , **ptrptr = %d \n\n",ptrptr,*ptrptr,**ptrptr);
    *ptrptr= &b;
    printf("Do : *ptrptr= &b;\n");
    
}

int main(){
    int a =5270;
    int* ptrA = &a;
    int* ptrptrA = &ptrA;
    printf("Before\n");  
    printf("a = %d, &a = %d, ptrA=%d, &ptrA = %d,*ptrA = %d \n",a,&a,ptrA,&ptrA,*ptrA);
    printf("&*ptrA = %d, *&ptrA = %d, ptrptrA = %d \n",&*ptrA,*&ptrA,ptrptrA);
    printf("b = %d, &b = %d \n\n",b,&b);

    testfunc(ptrptrA);
    printf("After\n");
    printf("a = %d, &a = %d, ptrA=%d, &ptrA = %d,*ptrA = %d \n",a,&a,ptrA,&ptrA,*ptrA);
    printf("&*ptrA = %d, *&ptrA = %d, ptrptrA = %d \n",&*ptrA,*&ptrA,ptrptrA);
    printf("ptrptrA = %d \n",ptrptrA);
    printf("b = %d, &b = %d \n",b,&b);
    return 0;
}

結果顯示
概念探討
- pointer of A 就是紀錄 A的記憶體位置(或者說 A的門牌號碼)的純量。
- *ptrA 的 * 表示一個運算符號，意義為ptrA指向的值。
- 根據上述的實驗與概念，將其繪製成圖表顯示，總算對指標有點感覺，在使用指標的指標也有多了一些些的理解。

工具學習

Phone Book

要增加效能，首先先參考programming small的方式，簡化了資料結構，以及使用Hash Function

作業目標
- 減少cache-miss。
- 加快程式運作速度。
原理分析
- 造成cache-miss最主要的原因是，cache中沒有程式所需要的資料，因此需要往下一層cache或memory查找資料。
- 增加cache中實用資料的比率，可降低cache-miss。
1. 簡化資料結構，去掉不必要的資訊，可以減少程式執行時對cache的負擔。
2. 使用Hash Table，可以加快程式查詢電話簿的時間，增加執行效率。
程式設計
- 新增另外一個main_opt.c，並更改Makefile。
- main_opt.c中會建立HashTable，並且在append()與findName()中，只需要輸入字串，就可以直接新增或是查找，不需要丟入entry*。
- append() 輸入名字字串，即直接丟進HashTable，若HashTable中有物件，也會將存在Table的物件向後移，並將新增的物件放在HashTable的第一個位置。
- findName() 回傳一個entry* 表示有找到，回傳NULL，表示並沒有找到。
- 程式碼

void append(char lastName[])
{
    /* allocate memory for the new entry and put lastName */
    int index = hash(lastName);
    entry* e = (entry *) malloc(sizeof(entry));
    strcpy(e->lastName, lastName);

    //insert to hash table
    e->pNext = hashtable[index];
    hashtable[index] = e;

}

entry *findName(char lastname[])
{
    int index = hash(lastname);
    entry* e = hashtable[index];
    while (e != NULL) {
        if (strcasecmp(lastname, e->lastName) == 0)
            return e;
        e= e->pNext;
    }
    return NULL;
}

效能分析
- 原生版本
- 優化版本
  
  cache-miss cache-reference 都減少許多。
- 執行時間的比較
  
  因為使用HashTable查找，查詢時間趨近於0，比起原本依序查找要快上許多。
  
  可以看到不僅是findName()，append()的時間也減少許多，推測是因為我減少了append輸入的參數量。
問題討論
1.為何輸出HashTable的size，會顯示8bytes?
- 可以理解HashTable這個pointer of pointer的大小為8bytes。
- 但我想知道HashTable的陣列大小，卻不知要如何顯示？

參考資料

音效程式安裝

2016q1 Homework1 (phonebook)

Reviewed by <snoopy831002>

環境設置

C語言的複習

工具學習

Phone Book

參考資料

Reviewed by <`snoopy831002`>