2017 q3 Homework1 (作業區)

contributed by<williamchangTW>

tags: Class_Project, Jserv

Reviewed by zhanyangch

• 針對 orig 與 opt 的比較不應只有時間差異，應探討造成此差異的原因，利用 perf 等工具可以協助分析。
• 對 cache 的介紹可以不夠詳盡，可以參考老師提供的 Computer Architecture (NOTE) 的 memory 章節。

Reviewed by tina0405

• 縮減 structure 裡的大小後，也可以考慮在其他方面去優化，像資料結構或記憶體的分析方面
• 利用 perf 工具去分析現況 perf stat 輸出解讀

Phonebook

建置環境所遇到的問題

• 在這我在使用 perf top 的時候遇到一個問題，花了點時間解決，就是一開始想把權限全打開，預設值是 3 ，我預先執行一段 command line : gedit /proc/sys/kernel/perf_event_paranoid 打開後想直接更換為 -1 ，可是出現 you do not have the permissions necessary to save the file.Please... 這一段使我不能更改這個檔案，我試過 sudo su 及 vim 和 gksudo 等方法去試著更改其中的值，最後我使用 sudo sh -c 'echo -1 > /proc/sys/kernel/perf_event_paranoid' ，最後是因為覺得跟 kernel 檔案的關係比較大才找到解決辦法。
• 最後做 cat /proc/sys/kernel/perf_event_paranoid 的值確定為 -1 。

還沒有優化前資料

• 再來當我輸入 perf top 如下顯示：
  

• 再來是一開始的 make plot:(opt code copy from orig)
  

• main.c define：

#ifdef OPT
#define OUT_FILE "opt.txt"
#else
#define OUT_FILE "orig.txt"
#endif

• 這裡是一種類似於 if … else 判斷式的定義，依照 #ifdef(+條件定義) 及 ＃else(+條件定義) #endif結束判斷式。

  • 這裡可以看到當有 OPT 這個 headerfile 就定義 OUT_FILE 生成 "opt.txt" 反之生成 "orig.txt"。

• 再來看 phonebook_opt.c code，我想從 orig去改 code 所以複製了一份去試試， trace 完後發現一個地方會忘了把 malloc free 。

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

#include "phonebook_orig.h"

/* original version */
entry *findName(char lastName[], entry *pHead)
{
    while (pHead != NULL) {
        if (strcasecmp(lastName, pHead->lastName) == 0)
            return pHead;
        pHead = pHead->pNext;
    }
    return NULL;
}

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

    return e;
}

• 更改完後

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

• 再來我朝 findName go down 開始，一開始想說在 while loop 中每次都要做判斷式，想減少他的 branch times ，因為 branch 是影響效能比重最重的一個 stage，可是想不出怎麼提出到外面解決，後來想說減少單次判斷所需等待時間著手。

• 先看 OPT 這個 headerfile ，於是找出 phonebook_opt.h

#ifndef _PHONEBOOK_H
#define _PHONEBOOK_H

#define MAX_LAST_NAME_SIZE 16

/* TODO: After modifying the original version, uncomment the following
 * line to set OPT properly */
// #define OPT 1
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;

entry *findName(char lastName[], entry *pHead);
entry *append(char lastName[], entry *e);

#endif

• 上述這段冗長的資料要花一點時間去做，每一次都要花這麼多時間，我決定除了 lastName 留下外其他放到一個新的結構內做需要的時候在搜尋它。其餘不變。

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __PHONE_BOOK_DET *pDet;
    struct __PHONE_BOOK_ENTRY *pNext;
    }entry;
    
typedef struct __PHONE_BOOK_DET {
    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];
} det;

• 很明顯的 find() 時間變短了，而 append() 小幅下降。

• 把註解掉的 OPT 打開。

#define OPT 1

cache 詳閱

• 首先是為何要有 cache ，從下面這張圖可以明顯地知道，為了填補 cpu ~ main memory 之間的差異，進而需要階層式的 table 來填補速度上的差異和 reduce cpu idle time。
  
• cache 被設計成一個 hash table 內存數組 index address，簡單概述的說 fully associative 不可能實現，因為這樣需要大量的尋找就損失原本的意義。
• direced mapped 也不好用，前幾個區塊常被用到，後面幾個區塊幾乎不用，浪費空間，使用率可能會很差。
• N-way associative & (LRU or Random) implemented.
• 把最近常用到的資料放在越靠近 CPU 的 memory 作儲存，這樣在抓取資料時 responds time 較短較有效率。