Try   HackMD

2017q1 Homework4 (phonebook-concurrent)

contributed by <csielee>

開發環境

OS: ubuntu 16.04 LTS
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
Model name: Intel® Core™ i5-5200U CPU @ 2.20GHz
CPU MHz： 2500.109
CPU max MHz: 2700.0000
CPU min MHz: 500.0000
L1d 快取： 32K, 8-way Set-associative
L1i 快取： 32K, 8-way Set-associative
L2 快取： 256K, 8-way Set-associative
L3 快取： 3072K, 12-way Set-associative
記憶體： 8G

concurrent 效能

fork 完後，直接 $ make plot

發現這效能真是太驚人了！

分析 concurrent 的實作

主要是在 append() 的時候將工作分給多個 thread 一起做
並使用下面的方法，讓多個 thread 可以順利 concurrent

對齊

先將要讀取的名字檔案 DICT_FILE 利用 text_align 對齊 MAX_LAST_NAME_SIZE 的長度，變成 ALIGN_FILE

    text_align(DICT_FILE, ALIGN_FILE, MAX_LAST_NAME_SIZE);
    int fd = open(ALIGN_FILE, O_RDONLY | O_NONBLOCK);
    off_t file_size = fsize(ALIGN_FILE);

對映

並把 ALIGN_FILE 的檔案內容利用 mmap() 記憶體對映到記憶體當中
同時利用對齊後的檔案大小去計算出需要幾個 entry，利用一次 malloc 把需要的記憶體空間一次分配好

    map = mmap(NULL, file_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
    assert(map && "mmap error");
    entry_pool = (entry *)malloc(sizeof(entry) *
                                 file_size / MAX_LAST_NAME_SIZE);
    assert(entry_pool && "entry_pool error");

分配給 thread

最後將這些東西分配進每個 thread，這樣互相執行起來
就可以解決同時讀取同一個檔案的檔案指標 critical 問題，跟頻繁的 malloc

for (int i = 0; i < THREAD_NUM; i++)
        // Created by malloc, remeber to free them.
        thread_args[i] = createThead_arg(map + MAX_LAST_NAME_SIZE * i, map + file_size, i,
                                         THREAD_NUM, entry_pool + i);

函數原型：

thread_arg *createThead_arg(char *data_begin, char *data_end,
                            int threadID, int numOfThread,
                            entry *entryPool);

最後 merge linked list

底下就是最後等每個 thread 執行完，就把每個 thread 各自產生的 linked list 合併起來

(有刪減 DEBUG 的 CODE)

for (int i = 0; i < THREAD_NUM; i++) {
    if (i == 0) {
        pHead = thread_args[i]->lEntry_head->pNext;
    } else {
        e->pNext = thread_args[i]->lEntry_head->pNext;
    }

    e = thread_args[i]->lEntry_tail;
}

將 if (i == 0) 搬到 for 迴圈之外，可以降低對效能的影響 –jserv

好的，我會重構這部份東霖

如此一來，就能讓多個 thread 有效率的合作又不會有錯誤

Pthread 的 setconcurrency()

在 github 中，老師問說這部份是有什麼意義
因此我去查詢了 manual 關於這個函數的訊息
節錄其中一段

​​​​Concurrency levels are meaningful only for M:N threading implementations

​​​​Both LinuxThreads and NPTL are 1:1 threading implementations, so setting the concurrency level has no meaning.

上面提到這個函數所設置的 Concurrency levels
是要對 M 條 user thread 分配 N 條 kernel thread 的執行緒模型才有意義

因為這樣的設置可以提示系統，要讓多少 kernel thread 去對映到 user thread，讓效能發揮到最好

但是如果是 LinuxThreads 或 NPTL(Native POSIX Threads Library for Linux) 的模型就沒有意義了

因為他本身就是 1：1 的模型，每個 user thread 都有 kernel thread

但是寫上這函數還是有幫助的，這可以保證我們再不同的平台
能夠保證一樣的執行狀況

這也是 POSIX(Portable Operating System Interface) 想做到的
一種可移植的介面

重構 phonebook

重新定義 append 跟 findName，並增加 init、free 函數 函式

function 當作 procedure 用的時候，像是這裡，台灣的翻譯慣例為「函式」，而非「函數」(對岸慣例) "jserv"

學到了一課，我一直用函數用的太習慣東霖

void phonebook_init(void *option);
entry *phonebook_append(char *s);
entry *phonebook_findName(char *s);
void phonebook_free();

學習 server-framework 的包裝方式: async.h 和 async.c，並提供不同的 provider implementation –jserv

好酷的技巧，我會加入這改進 東霖

簡化複雜的 main.c ，方便建立測試的 code
重寫 phonebook_orig 成功，但是在重寫 phonebook_opt 時
遇到執行上的問題，利用 GDB 去追問題

發現是缺少 strcmp-sse42.S 這個檔案導致 strncasecmp 無法執行

Thread 1 "phonebook_opt" received signal SIGSEGV, Segmentation fault.
__strncasecmp_l_avx () at ../sysdeps/x86_64/multiarch/strcmp-sse42.S:165
165     ../sysdeps/x86_64/multiarch/strcmp-sse42.S: 沒有此一檔案或目錄.

爬了一陣子文，還是找不到解決的方法
決定自己寫 strncasecmp 東霖

後來發現，我真的是笨的可以
下面已有解決辦法 東霖

strncasecmp

static inline int strncasecmp_a(const char *s1,const char *s2,size_t n) {
	int c=0;
	for (int i=0;i<n && c==0;i++) {
		c = tolower(*s1++) - tolower(*s2++);
	}
	return c;
}

結果跑出來還是有錯誤，再用 GDB 查一下

Thread 1 "phonebook_opt" received signal SIGSEGV, Segmentation fault.
0x000000000040119e in strncasecmp_a (s1=0x7fffffffd891 "yxel", 
    s2=0x7ffff729a041 <error: Cannot access memory at address 0x7ffff729a041>, 
    n=5) at phonebook_opt.c:29
warning: Source file is more recent than executable.
29                      c = tolower(*s1++) - tolower(*s2++);

什麼？ s2 那邊是不能讀取的空間
回去研究 entry 的 lastName 在 append 是怎麼產生的
居然是利用開啟檔案並對映出來的空間，我在 append 結束時把對映出來的空間 munmap() 掉了
難怪執行上會有問題

最後重構出來的效能圖

發現到 append() 上升非常多
因為我在 append() 把對齊檔案的時間算進去了

為了驗證我想法是對的，重新製圖

把 對齊檔案 text_align() 的部份移到 init()

由此可知，為了對齊檔案所需要的時間非常多

參考 server-framework 的包裝方式

看了 jserv 老師提供的 async.h 和 async.c

學習到了很酷的包裝方法，重新設計我的 phonebook API

extern struct __PHONEBOOK_API {
    void (*init)(void *option);
    entry *(*append)(char *s);
    entry *(*findName)(char *s);
    void (*free)();
} Phonebook;

先利用 extren 把宣告出來的 Phonebook 定義留給其他檔案
這地方是交給實作的 C 檔案

然後在實作的時候，定義 Phonebook 變數裡的函式指標要到哪裡

struct __PHONEBOOK_API Phonebook = {
    .init = phonebook_init,
    .append = phonebook_append,
    .findName = phonebook_findName,
    .free = phonebook_free,
};

像這樣的寫法是 C99 所擁有的結構初始化，能夠有效簡化初始化
經過這樣的寫法之後，只要在 main.c 用下列的方法就能使用

Phonebook.findName("test");

調整結構，改進效能

重構雖然都是將原有程式架構進行調整
但是好的程式結構也是能夠增進效能的

for (int i = 0; i < THREAD_NUM; i++) {
    if (i == 0) {
        entryHead = thread_args[i]->lEntry_head->pNext;
    } else {
        e->pNext = thread_args[i]->lEntry_head->pNext;
    }

    e = thread_args[i]->lEntry_tail;
}

entryHead = thread_args[0]->lEntry_head->pNext;
e = thread_args[0]->lEntry_tail;
for (int i = 1; i < THREAD_NUM; i++) {
    e->pNext = thread_args[i]->lEntry_head->pNext;

    e = thread_args[i]->lEntry_tail;
}

這樣能夠減少 branch predict 的影響
因為其實只有 i == 0 要當特例，但如果每次執行都要判斷特例
就會有效能上的損失

調整函式的設計

一開始在設計函式的時候，考慮不夠周詳
重新設計如下

Phonebook.create();
Phonebook.appendByFile(char *fileName);
Phonebook.removeByFile(char *fileName);
Phonebook.append(char *lastName);
Phonebook.remove(char *lastName);
Phonebook.findName(char *lastName);
Phonebook.free();

以下說明我的設計原因

Phonebook.create();

分配之後執行必要的空間或參數給變數，讓 phonebook 隨時能夠執行

Phonebook.appendByFile(char *fileName);
Phonebook.removeByFile(char *fileName);
Phonebook.append(char *lastName);
Phonebook.remove(char *lastName);

都是將資訊在 phonebook 中增加或刪除
但能夠選擇從檔案中得到資料，或是單獨一筆資料

Phonebook.findName(char *lastName);

就是去找到這個 lastName 的 entry
但比起原本的 findName ，不用傳 linked list 的 head 進去

Phonebook.free();

釋放前面所有執行的函式有可能配置到的記憶體
避免 memork leak 產生

改善對齊檔案的效能損失

首先，我將 text_align() 的部份放到 appendByFile()
並重新製圖，這次主要著重在 opt 版本的時間分佈

發現執行時間不是非常穩定，每個時間差距很大
我想是因為 text_align() 造成的

把 text_align() 移到 create() 證明前面想法

發現 create() 就如預期變得各時間差距很大

不使用 text_align()

將檔案內容 mapping 到記憶體
然後將檔案內容分成 THREAD—NUM 個區塊
如果剛好割在不是 '\n' 會往後找到有 '\n' 的後一個位置
而檔案的結尾就是檔案的大小

begin 陣列紀錄了每個區塊的開頭
而對第 n 個區塊而言，開頭是 begin[n] ，結尾是 begin[n+1]

/* divide text file */
int begin[THREAD_NUM+1];
begin[THREAD_NUM] = fd_st.st_size;
begin[0] = 0;
for (int i = 1; i < THREAD_NUM; i++) {
    begin[i] = (begin[THREAD_NUM]/THREAD_NUM)*i;
    while (*(map+begin[i])!='\n')
        begin[i]++;
        
    begin[i]++;
}

這樣就能減少對齊造成的效能損失

orig 跟 opt 比較

多次執行 opt 時間分佈

但是這個方法還有一個問題，就是拿掉 text-align() 後
無法得知資料個數，無法一次 malloc() 好所需要的記憶體
所以我決定引入之前有用的 memory pool，並在多執行緒執行時使用
因此需要一個 lockfree memory pool

使用 lockfree memory pool

天阿！實作不出來
底下是屍體，暫時放在 lockfree-memorypool branch東霖

因為要在多執行緒裡被呼叫，然後我又想練習看看 lockfree
所以就使用 原子操作 來實作

/* Atomic */
#define barrier()                 (__sync_synchronize())
#define AO_GET(ptr)               ({ __typeof__(*(ptr)) volatile *_val = (ptr); barrier(); (*_val); })
#define AO_SET(ptr, value)        ((void)__sync_lock_test_and_set((ptr), (value)))
#define AO_ADD_F(ptr, value)      ((__typeof__(*(ptr)))__sync_add_and_fetch((ptr), (value)))
#define AO_CAS(ptr, comp, value)  ((__typeof__(*(ptr)))__sync_val_compare_and_swap((ptr), (comp), (value)))

/* memory pool */
#define MPSIZE 1000
typedef struct {
    void *next;
    int index;
} mp_node_t;
typedef struct {
    mp_node_t *head,*curr;
    size_t mp_size;
} mp_list_t;

mp_list_t *mp_init(size_t s)
{
    mp_list_t *n = malloc(sizeof(mp_list_t));
    n->head = malloc(sizeof(mp_node_t)+s*MPSIZE);
    n->head->next = NULL;
    n->head->index = 0;
    n->curr = n->head;
    n->mp_size = s;
    return n;
}

void *mp_alloc(mp_list_t *mp)
{
    void *r;
    int tmp;
    while (1) {
        /* wait malloc */
        while (!(r = AO_GET(&mp->curr)));
        tmp = AO_GET(&((mp_node_t *)r)->index);
        if (tmp == MPSIZE) {
            if (AO_CAS(&mp->curr,r,NULL)) {
                //set
                mp_node_t *t = malloc(sizeof(mp_node_t)+mp->mp_size*MPSIZE);
                t->next = mp->head;
                t->index = 0;
                mp->head = t;
                while (AO_CAS(&mp->curr,NULL,t));
            } else {
                // no set
                while (!(r = AO_GET(&mp->curr)));
            }
        } else {
            if (AO_CAS(&((mp_node_t *)r)->index,tmp,tmp+1)!=tmp+1) {
                //get
                break;
            }
        }
    }
    // tmp , r;
    return (r+sizeof(mp_node_t)+(tmp*mp->mp_size));
}

void mp_free(mp_list_t *mp)
{
    mp_node_t *tmp = mp->head;
    while (mp->head->next) {
        mp->head = mp->head->next;
        free(tmp);
        tmp = mp->head;
    }
    free(mp->head);
    free(mp);
}

static mp_list_t *entry_mp;

結果成功編譯後執行 $./phonebook_opt
就會卡在 appendByFile()

用 gdb 檢查

size of entry : 24 bytes
execution time of phonebook.create() : 0.000003 sec
[New Thread 0x7ffff6cde700 (LWP 29516)]
[New Thread 0x7ffff64dd700 (LWP 29517)]
[New Thread 0x7ffff5cdc700 (LWP 29518)]
[New Thread 0x7ffff54db700 (LWP 29519)]
[Thread 0x7ffff6cde700 (LWP 29516) exited]
[Thread 0x7ffff54db700 (LWP 29519) exited]
[Thread 0x7ffff5cdc700 (LWP 29518) exited]

發現會卡在某一個 thread ，因此我推測是我的 mp_alloc() 出現問題導致卡住

但是另外發現一個神奇事情，用 $make DEBUG=1 重新編譯
之後執行，確能夠正常執行到結束

參考資料

曾柏翔hw2共筆
POSIX線程(pthread)入門文章分享
C语言的原子操作

Last changed by 
 
李東霖
0
629
Published on HackMD