# 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(R) Core(TM) 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`
```clike
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 把需要的記憶體空間一次分配好
```clike
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
```clike
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);
```
函數原型：
```clike
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)
```clike
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;
}
```
:::danger
將 `if (i == 0)` 搬到 for 迴圈之外，可以降低對效能的影響 --jserv
:::
> 好的，我會重構這部份[name=東霖]
如此一來，就能讓多個 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 <s>函數</s> 函式
>> function 當作 procedure 用的時候，像是這裡，台灣的翻譯慣例為「函式」，而非「函數」(對岸慣例) [name="jserv"]
>> > 學到了一課，我一直用函數用的太習慣[name=東霖]
```clike
void phonebook_init(void *option);
entry *phonebook_append(char *s);
entry *phonebook_findName(char *s);
void phonebook_free();
```
:::danger
學習 server-framework 的包裝方式: [async.h](https://github.com/embedded2016/server-framework/blob/master/async.h) 和 [async.c](https://github.com/embedded2016/server-framework/blob/master/async.c)，並提供不同的 provider implementation --jserv
:::
> 好酷的技巧，我會加入這改進 [name=東霖]
簡化複雜的 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 [name=東霖]
>> 後來發現，我真的是笨的可以
>> 下面已有解決辦法 [name=東霖]
### strncasecmp
```clike
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](https://github.com/embedded2016/server-framework/blob/master/async.h) 和 [async.c](https://github.com/embedded2016/server-framework/blob/master/async.c)
學習到了很酷的包裝方法，重新設計我的 phonebook API
```clike
extern struct __PHONEBOOK_API {
void (*init)(void *option);
entry *(*append)(char *s);
entry *(*findName)(char *s);
void (*free)();
} Phonebook;
```
先利用 extren 把宣告出來的 Phonebook 定義留給其他檔案
這地方是交給實作的 C 檔案
然後在實作的時候，定義 Phonebook 變數裡的函式指標要到哪裡
```clike
struct __PHONEBOOK_API Phonebook = {
.init = phonebook_init,
.append = phonebook_append,
.findName = phonebook_findName,
.free = phonebook_free,
};
```
像這樣的寫法是 C99 所擁有的結構初始化，能夠有效簡化初始化
經過這樣的寫法之後，只要在 main.c 用下列的方法就能使用
```clike
Phonebook.findName("test");
```
### 調整結構，改進效能
重構雖然都是將原有程式架構進行調整
但是好的程式結構也是能夠增進效能的
```clike
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;
}
```
```clike
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 要當特例，但如果每次執行都要判斷特例
就會有效能上的損失
### 調整函式的設計
一開始在設計函式的時候，考慮不夠周詳
重新設計如下
```clike
Phonebook.create();
Phonebook.appendByFile(char *fileName);
Phonebook.removeByFile(char *fileName);
Phonebook.append(char *lastName);
Phonebook.remove(char *lastName);
Phonebook.findName(char *lastName);
Phonebook.free();
```
以下說明我的設計原因
```clike
Phonebook.create();
```
分配之後執行必要的空間或參數給變數，讓 phonebook 隨時能夠執行
```clike
Phonebook.appendByFile(char *fileName);
Phonebook.removeByFile(char *fileName);
Phonebook.append(char *lastName);
Phonebook.remove(char *lastName);
```
都是將資訊在 phonebook 中增加或刪除
但能夠選擇從檔案中得到資料，或是單獨一筆資料
```clike
Phonebook.findName(char *lastName);
```
就是去找到這個 lastName 的 entry
但比起原本的 findName ，不用傳 linked list 的 head 進去
```clike
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]
```clike
/* 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[name=東霖]
因為要在多執行緒裡被呼叫，然後我又想練習看看 lockfree
所以就使用 原子操作 來實作
```clike
/* 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共筆](https://embedded2015.hackpad.com/HW2-s2RxRpAfedD)
[POSIX線程(pthread)入門文章分享](http://dragonspring.pixnet.net/blog/post/32963482-posix%E7%B7%9A%E7%A8%8B(pthread)%E5%85%A5%E9%96%80%E6%96%87%E7%AB%A0%E5%88%86%E4%BA%AB)
[C语言的原子操作](http://www.jianshu.com/p/cb7b726e943c)
Sign in with Wallet
Connect another wallet