# 2017q1 Homework4 (phonebook-concurrent)

contributed by <`petermouse`>

## 開發環境

* OS: Ubuntu 16.04 LTS
* Memory: 8 GB
* CPU:
* Name:
* Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz
* Cache:
* L1d Cache： 32K
* L1i Cache： 32K
* L2 Cache： 256K
* L3 Cache： 3072K

## 執行程式

先執行原本的程式看看，由於 opt 版本多使用了 gprof ，避免時間影響先移除 `-pg`


`append()` 加快好多，快要接近 `findName()` 的時間了

## 分析程式碼

opt 比起 orig 做了幾個改動:

### 1. text align

將所有字以 16 bytes 對齊，固定的偏移量可以直接計算存取下一筆字的位置

### 2. `mmap()`

[mmap(2)](http://man7.org/linux/man-pages/man2/mmap.2.html)


在 process 的 virtual address space 建立新的映射

[TLPI](http://man7.org/tlpi/) 一書提到 `mmap()` 可能帶來的優點

* 一般 `read()` 與 `write()` 要經過兩次的傳輸
file <--> kernel buffer cache <--> user space buffer [(參考圖片)](http://www.programering.com/a/MjN2EzNwATc.html)
不過使用 `mmap()` 省去 kernel buffer cache <--> user space buffer 的傳輸

* 等於 kernel 與 user 共享一個 buffer ，多個 process 也共用同個 buffer

### 3. Pthread

使用 Pthread 平行處理，預設為 4 個 thread
每個 thread 用 cyclic 的方式建立 local linked-list ，最後再串接起來

### 4. 其他

* 使用 Variadic Macros ([C](https://gcc.gnu.org/onlinedocs/gcc/Variadic-Macros.html) [C++](https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html)) 做出 debug 訊息

## 改進程式

### 建立 thread pool

#### 觀察 mbrossard 的 thread pool 程式碼

參考 [threadpool-mbrossard](https://github.com/mbrossard/threadpool) 的作法，先釐清一下內部的實作，不過覺得有點難懂

struct threadpool_t {
  pthread_mutex_t lock;
  pthread_cond_t notify;
  pthread_t *threads;
  threadpool_task_t *queue;
  int thread_count;
  int queue_size;
  int head;
  int tail;
  int count;
  int shutdown;
  int started;
};

這是 thread pool 的資料結構，裡面是用 queue 來存放 task，thread 再從 queue 拿取 task

threadpool_t *threadpool_create(int thread_count, int queue_size, int flags)

建立一個 thread pool ，並指定 thread 數量以及 queue 大小
thread 會在此時就建立

/* in threadpool_create() function */
for(i = 0; i < thread_count; i++) {
    if(pthread_create(&(pool->threads[i]), NULL,
                      threadpool_thread, (void*)pool) != 0){
        /* error handling*/                  
    }
}

不過每個 thread 執行的函式是 `threadpool_thread` ，參數是 `pool` ，也就是 `threadpool_thread` 是取得 task 的接口，並從參數 thread pool 中的 queue 接收 task

接下來的 thread 搶奪 lock 的過程原網頁都有提到了

int threadpool_destroy(threadpool_t *pool, int flags);

用來結束 thread pool ， 分為 graceful shutdown ( `flags` 不為 0) 代表正常結束，以及 immediate shutdown ( `flags` 為 0)，通知所有 thread 喚醒，並且離開 `threadpool_thread` 最後 join ，釋放空間

#### 在 phonebook-concurrent 內使用

在還沒使用 thread pool 之前，我預期結果會比原本還要慢，因為就只是把原本的 4 個 task (即 `thread_args[]` ) 先放入 queue 中， 4 個 thread 再去從 queue 拿取，比起直接 4 個 thread 分配各 1 個 task 多了初始化 thread pool 以及 強奪 lock 的成本

實際上是稍微久了一些，但不會差距太多

接著我試著把 task 切得更細，不過一直 core dumped，後來發現在給 thread 執行 `threadpool_thread` 內執行 task `append()` 時最後直接呼叫了 `pthread_exit(NULL)` ，竟然把 thread 直接結束了，剩餘的 task 並沒有執行到。

嘗試 `TASK=100` ，thread 維持在 4，結果奇怪的事情發生了


`append()` 的時間變得更多了，我覺得算是正常的
不過 `findName()` 時間突然暴漲了，怎麼會這樣RRR?

由於是 cyclic 建立 linked list，所以 `zyxel` 也會隨著 task 的數量不同而放到 linked list 的不同位置，所以有機會可以秒殺找到
但是原始版本中是按照字典序建立 linked list ，找尋 `zyxel` 已經是接近最糟的情況，結果相差快兩倍了!

我也試著用 `show_entry()` 驗證正確性，這部份是沒問題的

我推測是頻繁的 cache miss但導致的狀況, 但尚未建立實驗

#### findName() 也用 thread pool

我把 `findName()` 也試著用thread pool 處理
同樣是 task=100 thread=4


可以降低一些時間，但是會有幾個問題

* 原本的 `append()` 會 return 找到的 entry ，但現在 thread pool 的形式沒辦法有效取得 entry
* 解決辦法是在原本的 task 中紀錄結果，但最後還要從所有 task 找尋，很沒效率
* 一個 task 找到沒有辦法停止其他 thread 的找尋
* 我覺得有辦法再調整，還要在思考如何適當的停止 thread pool

#### mutrace 測試
參考 [B08: mergesort-conurrent](https://hackmd.io/s/B1xV_p_jl#)

使用 mutrace 測試 mutex 帶來的影響 (THREAD=4 TASK=100)

以下省略每個 mutex 的詳細資料

mutrace: 0.2 sucessfully initialized for process phonebook_tp (pid 2981).
orginal file size = 3206080
size of entry : 24 bytes
execution time of append() : 0.005685 sec
execution time of findName() : 0.007196 sec

mutrace: Showing statistics for process phonebook_tp (pid 2981).
mutrace: 3 mutexes used.

mutrace: Showing 3 most contended mutexes:

 Mutex #   Locked  Changed    Cont. tot.Time[ms] avg.Time[ms] max.Time[ms]  Flags
       1      206      106       36        0.029        0.000        0.000 Mx.--.
       2      209      110       30        0.040        0.000        0.005 Mx.--.
       0       40       24       10        0.005        0.000        0.001 M-.--.
                                                                           ||||||
                                                                           /|||||
          Object:                                     M = Mutex, W = RWLock /||||
           State:                                 x = dead, ! = inconsistent /|||
             Use:                                 R = used in realtime thread /||
      Mutex Type:                 r = RECURSIVE, e = ERRRORCHECK, a = ADAPTIVE /|
  Mutex Protocol:                                      i = INHERIT, p = PROTECT /
     RWLock Kind: r = PREFER_READER, w = PREFER_WRITER, W = PREFER_WRITER_NONREC 

mutrace: Note that the flags column R is only valid in --track-rt mode!

mutrace: Total runtime is 68.093 ms.

mutrace: Results for SMP with 4 processors.

`Locked`: mutex 鎖了幾次
`Changed`: thread 轉換的次數
`Cont.`: thread 嘗試要求已鎖住的 mutex 的次數
`tot.Time[ms]`: mutex 鎖住的總時間
`avg.Time[ms]`: 平均鎖住 mutex 的時間 (?)
`max.Time[ms]`: 持有 mutex 的最大時間

觀察 各個 mutex 的資訊

Mutex #1 (0x0x20da650) first referenced by:
	/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7f206ff724b2]
	./phonebook_tp(threadpool_create+0xf3) [0x4021ab]
	./phonebook_tp(main+0x2df) [0x4017ab]
	/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7f206f9a9830]

輸入 `$ addr2line -e phonebook_tp 0x4021ab` 就得到 mutex 的位置

/home/petermouse/workspace/sysprog/phonebook-concurrent/threadpool.c:122

### 實作 remove

## 參考資料
[threadpool-mbrossard](https://github.com/mbrossard/threadpool)
[mutrace](http://0pointer.de/blog/projects/mutrace.html)