# 2016q3 Homework 1 (phonebook)
contributed by <`TotallyWrong`>
###### tags: `TotallyWrong` `On going`
### Reviewed by `GreenYo0413`
- 用26個字母當陣列指標的頭是個不錯的想法，但是真實世界對於英文名字裡以每個字母當開頭的名字統計數量並不一樣。可以嘗試對資料作分析再來找出適合的架構或是適合的hash function。

## 開發作業環境
**CPU** : Intel Core i5-5200U
**Cache size**: L1 Cache 128KB, L2 Cache 512K, L3 Cache 3072KB
**Operating System** : Ubuntu 15.10 Wily Werewolf

---

## 使用 Ubuntu 15.10

### 安狀相關開發工具

$ sudo apt-get update
$ sudo apt-get install build-essential
$ sudo apt-get install linux-tools-common linux-tools-generic
$ sudo apt-get install astyle colordiff gnuplot 

----

[Homework 1.](https://http://wiki.csie.ncku.edu.tw/embedded/2016q1h1)
> 安裝順利沒有問題

---

### 安裝Git與設定Github

**安裝Git**

$ sudo apt-get install git-core

[Git.](http://wiki.csie.ncku.edu.tw/git)
> 記得安裝先Git再試著使用Github

**設定Github**

1. 設定Git帳號

>如何找到 SSH key setting 的畫面

2. 取得 SSH key

$ ssh-keygen -t rsa -C "[e-mail]"
$ ssh-add ~/.ssh/id_rsa

>如果設定Passphrase 嘗試連到Github 時會背要求輸入

3. 打開 id_rsa.pub

$ lowriter id_rsa

>如果Vim還不是那麼熟練可以用 LibreWriter 開來做Copy&Paste

4. 測試 Github聯結

$ ssh -T [e-mail]

>記得Passphrase

5. 把程式碼複製下來

$ git clone [e-mail]:Username/phonebook.git

>需要先去fork程式碼

6. 改好的程式碼上傳

$ git add . 
$ git commit -m "更改檔案的原因"
$ git push

>如果因為某個原因背要求一直要輸入Github帳號請去改 Config file

[資料來源](http://wiki.csie.ncku.edu.tw/github)
[Furthur Study](https://github.com/doggy8088/Learn-Git-in-30-days)

### 測試Astyle

給個亂七八糟的程式碼

---

輸入
確實有作用

---

### 了解既有程式碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>
#include IMPL
#define DICT_FILE "./dictionary/words.txt"

> 資料來源 words.txt
> IMPL 給 Makefile 去選擇

---

static double diff_in_second(struct timespec t1, struct timespec t2)
{
    struct timespec diff;
    if (t2.tv_nsec-t1.tv_nsec < 0) {
        diff.tv_sec  = t2.tv_sec - t1.tv_sec - 1;
        diff.tv_nsec = t2.tv_nsec - t1.tv_nsec + 1000000000;
    } else {
        diff.tv_sec  = t2.tv_sec - t1.tv_sec;
        diff.tv_nsec = t2.tv_nsec - t1.tv_nsec;
    }
    return (diff.tv_sec + diff.tv_nsec / 1000000000.0);
}

> 計算時間的funcation

int main(int argc, char *argv[])
{
    FILE *fp;
    int i = 0;
    char line[MAX_LAST_NAME_SIZE];
    struct timespec start, end;
    double cpu_time1, cpu_time2;

> Main 下的資料宣告
> 感謝同實驗室的同學讓我稍微了解Struct 的用法

    /* check file opening */
    fp = fopen(DICT_FILE, "r");
    if (fp == NULL) {
        printf("cannot open the file\n");
        return -1;
    }

>打開檔案並檢查是否打開成功

/* build the entry */
    entry *pHead, *e;
    pHead = (entry *) malloc(sizeof(entry));
    printf("size of entry : %lu bytes\n", sizeof(entry));
    e = pHead;
    e->pNext = NULL;

>建立Entry和指標

#if defined(__GNUC__)
    __builtin___clear_cache((char *) pHead, (char *) pHead + sizeof(entry));
#endif

>查詢StackOverflow 這似乎是GNU Compiler的Macro還未確認這個Macro的功能是什麼

clock_gettime(CLOCK_REALTIME, &start);
    while (fgets(line, sizeof(line), fp)) {
        while (line[i] != '\0')
            i++;
        line[i - 1] = '\0';
        i = 0;
        e = append(line, e);
    }

>開始計時並從檔案中取得Last name 並使用Append 建立資料練結

clock_gettime(CLOCK_REALTIME, &end);
    cpu_time1 = diff_in_second(start, end);

>確認完成建立練結時間

    /* close file as soon as possible */
    fclose(fp);

    e = pHead;

    /* the givn last name to find */
    char input[MAX_LAST_NAME_SIZE] = "zyxel";
    e = pHead;

    assert(findName(input, e) &&
           "Did you implement findName() in " IMPL "?");
    assert(0 == strcmp(findName(input, e)->lastName, "zyxel"));

>這是呼叫findname來尋找zyxel

#if defined(__GNUC__)
    __builtin___clear_cache((char *) pHead, (char *) pHead + sizeof(entry));
#endif

<s>清除cache>清除cache 中的記憶體</s>
清除釋放 Cache 記憶體

>> 請認真想「清除 cache 中的記憶體」這描述正確嗎？理工科系的學生用語應當精確！請回去研讀計算機結構的 cache 描述 [name=jserv]
>感謝老師提醒

    /* compute the execution time */
    clock_gettime(CLOCK_REALTIME, &start);
    findName(input, e);
    clock_gettime(CLOCK_REALTIME, &end);
    cpu_time2 = diff_in_second(start, end);

>時間計算

---

### 原始程式碼的執行結果


>Cash Miss 91.018%

---

### 嘗試改善Cache Miss 的狀況

**方法1 :**
在main.c file 中所搜尋的字元為 "zyxel" 從頭搜尋對Link list 很不利，嘗試在main中建立一個26字母各字元的第一個字位置的簡易Table， 利用ASCII 號碼做類似Hash Function.

----

>> 程式碼請用指定的縮排方式處理後，再重新貼上！ [name=jserv]
>謝謝老師指教，以完成縮排處理。

---

#if defined(OPT)
//int j;
    char fichl='b';
    entry *Alpha[26];
    Alpha[0]=pHead;
#endif
    /*-------------------------------------------------------*/

---

clock_gettime(CLOCK_REALTIME, &start);
    while (fgets(line, sizeof(line), fp)) {
        while (line[i] != '\0')
            i++;
        line[i - 1] = '\0';
        i = 0;
        e = append(line, e);

        /* Store The location of first word of each alphabet */

---

#if defined(OPT)
        if(fichl == line[0]) {
            //j= fichl-'a';
            Alpha[fichl-'a']= e;
            fichl++;
        }
#endif
        /*------------------------------------------------*/
    }
    clock_gettime(CLOCK_REALTIME, &end);
    cpu_time1 = diff_in_second(start, end);

    /* close file as soon as possible */
    fclose(fp);

    e = pHead;

    /* the givn last name to find */
    char input[MAX_LAST_NAME_SIZE] = "zyxel";

    /* Pick a better start point for e */
#if defined(OPT)
    //j= input[0]-'a';
    e=Alpha[input[0]-'a'];
//	printf("%d",j);
#else
    e = pHead;
#endif
    /*--------------------------------*/

---

**結果**


在不改變資料結構的狀況下 Cache-misses 的狀況只改善10%，整體執行時間有縮短cache-misses 雖然還是高，但 cache-reference 次數下降 還有 time elapse 是 0.055349418

---


findName() 的時間大幅縮小但apped()時間變長

---

**方法二：**
試著改善資料結構，老師上課時有題到之前有同學改善資料結構大幅減少cache-misses，再搜尋上一學期的筆記後發現是 [dada](https://embedded2016.hackpad.com/ep/pad/static/YkqjhwgnQcA)的作法。因為思考後發現如果沒有聯結到細節資料則LastName搜尋似乎意義不明，所以還是建立一個鏈結連到一個空的細節資料。

---

typedef struct __PHONE_BOOK_DAENTRY {
    char firstName[16];
    char email[16];
    char phone[10];
    char cell[10];
    char state[2];
    char addr1[16];
    char addr2[16];
    char city[16];
    char zip[5];
} daentry;

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

---

entry *append(char lastName[], entry *e)
{
    /* allocate memory for the new entry and put lastName */
    e->pNext = (entry *) malloc(sizeof(entry));
    e->pData = (daentry *) malloc(sizeof(entry));
    e = e->pNext;
    strcpy(e->lastName, lastName);
    e->pNext = NULL;

    return e;
}


只改善Data結構沒用第一個方法時，Cache-misses 減少到 71% 左右但Cache references的次數還是很高。而Append()的時間增加與上學期同學的結果有不同


---

**方法三**

將上述兩種方案合併

---


---


---

兩種方案結合對似乎沒有時間上的進步(跟方法一)，但是Cache reference 的次數有明顯減少，似乎原因在於FindName()的時間下降不足以抵消Apped()的時間提升。

利用 perf 找熱點

./phonebook_opt & sudo perf top -p $!

---


---

如果採用跟dada學長版本資料結構,光是資料結構的改善就可以達到 64% cache misses 0.0535的 Run Time。

---


---

結合方法一則在把執行時間縮短Cache reference 的次數減少，但 cache misses 的比例乎沒有減少。


---


---

為了解我的作法和學長的作法的差異，我用程式印出Data的大小，

* Entry: 原始大小
* Entry dada:Dada 的資料大小
* Entry my version:我的資料大小
* Daentry 我的細節資料大小

---

大小指差8個bytes位址不該有如此巨大的差距，再請程式應出資料位置後發現雖然我的資料雖然沒大多少但是位置相距叫遠似乎因此造成較多的不必要Cache-misses

我的資料位置

address of entry 0x1b0d4a0 
address of entry 0x1b0d500 
address of entry 0x1b0d560 
address of entry 0x1b0d5c0 

學長的資料位置

address of entry 0xede490 
address of entry 0xede4b0 
address of entry 0xede4d0 
address of entry 0xede4f0 

因此再做個實驗保留我的資料結構，但是不去製作空資料

---

我的資料位置改善

address of entry 0xb054a0 
address of entry 0xb054d0 
address of entry 0xb05500 
address of entry 0xb05530

而Cache-miss也明顯改善

---

## 心得

這份作業前才剛讀完一本C語言的書，而且聯Struct和Pointer怎麼用都不是很了解，而這份讓我練習作了許Coding的練習，感謝同實驗室的同學協助這次也學會了Link List 的實作 和 C語言 Struct 的用法。在有限的時間中還有一些值得做的Idea會再以後據序測試例如字串壓縮，我有看了smaz 的file(還未全數弄懂)發現內容似乎是對英文的常出現詞語做轉換，看了之後覺得很複雜。我們只要存字母我估算了一下10個byte應該就可以做到目前還在思考如何快速的用算術作轉換。[27(含空)的16次方是7.977E+22，而2的80次方是1.209E24]。另外目前也還在找尋對memory address 距離改善的方法，之前方法討論中發現我的資料雖小但因為建構時位置不好造成後續的搜尋造成不必要的Cache-miss，目前還未找到可以搬動位置的方法。

## Code

$ echo 1 | sudo tee /proc/sys/vm/drop_caches

清空Cache

$ ./phonebook_orig & sudo perf top -p $!

用perf 觀察Funcation和Kernel狀況

## 現況
1. **9/24** : Finish install OS,finsh watching HackMD video, Finish get a git account,Finish watching homework #1 video.
2. **9/25** : Finish install 相關開發工具, Finish Set up Github,Finsh TestAstyle, Try to understand original code.
3. **9/26** : Finish Understand original code function, Test out GNU plot, Code first opt version, Understand the use of link list.
4. **9/27** : Finish Test out address, Update developer log.

## 須完成事項
1. ~~Finish Setting Github.~~
2. ~~Get bluetooth keyboard problem fixed.~~
3. Read Makefile document.
4. Read Perf document.
5. ~~Try out the original phonebook.~~
6. Read GNUplot document.
7. Implement and compare word compression between smaz and convert word into ASCII number then convert to 27 base number.