Try   HackMD

2016q3 Homework2 (phonebook-concurrent)

contributed by <vic85821>

開發環境

  • Ubuntu 16.04.1 LTS
  • Linux version 4.4.0-38-generic
  • CPU : Intel® Core™ i5-3230M CPU @ 2.60GHz
  • Main memory : 8GB
  • L1d cache : 32K
  • L1i cache : 32K
  • L2 cache : 256K
  • L3 cache : 3072K

目標

  • 驗證結果
  • 實作hash table
  • 實作thread pool

Pthread

mmap

Linux提供了記憶體映射函數 mmap，它把文件內容映射到一段虛擬記憶體上,讓存取或是寫入檔案更快速直接,不用經過buffer

原本以為將align的長度減少(min = 13)可以降低cache-miss,但實驗結果顯示align長度=16時cache-miss最低

Hint: cache line size jserv

void *mmap(void *start,size_t length, int prot, int flags, int fd, off_t offsize);

參數說明:

  • start : 指定從虛擬記憶體的哪個位置開始存放,若傳入NULL則會隨機配置可用的記憶體位置
  • length : 要映射的記憶體大小
  • prot 映射區域的保護方式




PROT_EXEC 映射區域可被執行
PROT_READ 映射區域可被讀取
PROT_WRITE 映射區域可被寫入
PROT_NONE 映射區域不能存取
  • flags : 影響映射區域的各種特性,以下為常見的


MAP_SHARED  允許其他映射該文件的行程共享，對映射區域的寫入數據會複製回文件。
MAP_PRIVATE 不允許其他映射該文件的行程共享，對映射區域的寫入操作會產生一個映射的複製(copy-on-write)，對此區域所做的修改不會寫回原文件。
  • fd : 由open返回的文件描述符，代表要映射到核心中的文件

    這部份不太清楚參數代表的意義

  • off_size : 從文件映射開始處的偏移量，通常為0，代表從文件最前方開始映射。(需為page size的整數倍)

參考資料 : mmap

案例分析

測試正確性及效能

size of entry : 24 bytes
execution time of append() : 0.006272 sec
execution time of findName() : 0.005810 sec

正確性的部份參考tempoJiJi的共筆,將程式的輸出與原本的字典檔做比較




#ifdef OPT
    show_entry(e);
#endif

./phonebook.opt > test.txt
因為輸出的格式與字典檔內容有些不同,因此額外parse資料並sort
並利用diff words.txt test.txt檢測檔案差異

輸出只有349896筆,但word.txt有349900筆,少了幾筆資料
對程式碼做了修正

for (int i = 0; i < THREAD_NUM; i++) {
        if (i == 0) {
            pHead = app[i]->pHead;
            dprintf("Connect %d head string %s %p\n", i,
                    app[i]->pHead->pNext->lastName, app[i]->ptr);
        } else {
            etmp->pNext = app[i]->pHead;
            dprintf("Connect %d head string %s %p\n", i,
                    app[i]->pHead->pNext->lastName, app[i]->ptr);
        }

pHead = app[i]->pHead->pNext; 改成 pHead = app[i]->pHead
etmp->pNext = app[i]->pHead->pNext;改成etmp->pNext = app[i]->pHead;
原本的寫法,各個thread_ll head 單字都會消失,修正完之後,結果就是對的了

在作業1的phonebook,我是透過build binary search tree以提高findName()的速度,因此藉由檢查output檔的機會,這次便利用hash table來檢驗正確性
(原本想說利用array存取資料,再直接sort比較就好,但資料量太大了…)

  • check_right.c

























int hash_value(char* ptr)
{
    unsigned int value = 0;
    unsigned int seed = 31;
    int i = 0;
    while(i < strlen(ptr))
    {
        value = value * seed + *ptr;
        i++;
    }
    return value % TABLE_SIZE;
}

hTable *create()
{
    hTable *table;
    table = malloc(sizeof(hTable));
    table -> list = malloc(sizeof(entry_c*) * TABLE_SIZE);
    int i = 0;

    for(i = 0; i < TABLE_SIZE; ++i)
        table -> list[i] = NULL;

    return table;
}

寫完才得知,原來linux本身就有sort指令可以幫忙排序Orz!!
$ sort output.txt

原始版本的效能改善與問題

效能改善

  • thread pool
  • hash table

問題

  • Pthread 假設有某個thread的執行時間過長,會拉低整個程式的效能
    • 增加thread卻沒有增加效能的原因
    • 透過 thread pool 來進行改善
  • 程式是將整個words都串聯起來,因此findname()仍必須線性搜尋
    • 透過hash table來提高findname()
    • 但必定會犧牲append()的效能

優化1_Hash Table

使用hash table加快了findName()的速度,各個thread先分別建立hash table,最後再join

  • append(): 建表的時候需要較多的時間
  • findName(): 利用hash table降低了許多
Performance counter stats for './phonebook_opt' (100 runs):

           452,045      cache-misses              #   37.454 % of all cache refs      ( +-  1.26% )
         1,206,946      cache-references                                              ( +-  1.31% )
       323,977,868      instructions              #    1.16  insns per cycle          ( +-  0.06% )
       279,321,497      cycles                                                        ( +-  0.58% )

       0.080669329 seconds time elapsed                                          ( +- 11.95% )

優化2_Thread Pool

為了降低append()的時間,因此想實作看看thread pool (研究中…)

Refactoring

定義 : 在不改變軟體的外在行為之下，改善既有軟體的內部設計
目標 : 判斷軟體中所存在的壞味道（smell），然後套用重構來移除這些壞味道

簡而言之,現行程式碼可以將內容分為form和context,我們可以透過挑除form當中的壞味道,讓程式更有效率.更好被理解

程式的壞味道










typedef struct _append_a {
    char *ptr;
    char *eptr;
    int tid;
    int nthread;
    entry *entryStart;
    entry *pHead;
    entry *pLast;
} append_a;

從append(),new_append_a()中可以發現,沒有使用到tid這個變數,因此將tid移除,並針對append(),new_append_a(),main()中有assign tid的地方修改,整個程式仍然是正確的

良性的批評是一併提出改進方案，show me the code! jserv

參考資料:什麼是refactoring

tags: phonebook concurrent refactoring Pthread
Last changed by 
 
張友誠
0
363
Published on HackMD