2017q1 Homework4 (phonebook-concurrent)
===
contributed by <`PeterTing`>
###### tags: `phonebook-concurrent` `PeterTing`

## 作業要求

* 在 GitHub 上 fork [phonebook-concurrent](https://github.com/sysprog21/phonebook-concurrent)，然後適度修改 `phonebook_opt.c` 和相關的檔案
* 除了修改程式，也要編輯「[作業區](https://hackmd.io/s/r1lxtzpOig)」，增添開發紀錄和 GitHub 連結
* 至少涵蓋研讀 [concurrency](https://hackmd.io/s/Skh_AaVix) 教材的認知、程式正確性驗證、效能分析實驗 (必須要有圖表)，以及充份說明你如何改善效能
* 延續 [B01: phonebook](https://hackmd.io/s/rJYD4UPKe) 的開發方向，本作業著重於透過 POSIX Thread 來縮減 `alloc()` 的時間成本
* 詳細閱讀吳彥寬的[實驗](/s/BkN1JNQp)，指出他的實做缺失，並提出改進縮減 append() 時間的可行提案，接著開發程式來驗證
* 提示：可透過建立 thread pool 來管理 worker thread
* ==需要一併實作出刪除 (remove) 特定資料的功能==，並且分析對效能的影響。要留意 race condition 和正確性議題。
* 第一週 phonebook 未完成和待改進項目也一併在 [phonebook-concurrent](https://github.com/sysprog21/phonebook-concurrent) 的基礎下進行
* 學習 [concurrent-ll](https://github.com/jserv/concurrent-ll) (concurrent linked-list 實作) 的 scalability 分析方式，透過 gnuplot 製圖比較 list 操作的效能
* 一併嘗試重構 (refactor) 給定的程式碼，使得程式更容易閱讀和維護。延續 [B05: introspect](https://hackmd.io/s/SyFpOZQqx)，不只是在共筆上用文字提出良性詳盡的批評，也該反映在程式碼的變革

## 初步測試

 Performance counter stats for './phonebook_opt' (100 runs):

         3,321,487      cache-misses              #   64.381 % of all cache refs      ( +-  0.13% )
         5,159,115      cache-references                                              ( +-  0.13% )
       247,682,208      instructions              #    1.08  insn per cycle           ( +-  0.06% )
       228,536,997      cycles                                                        ( +-  0.75% )

       0.079388178 seconds time elapsed                                          ( +-  0.77% )

./calculate
gnuplot scripts/runtime.gp


append() 比 findName() 還快！

## 開發紀錄

### 理解程式

把程式碼打開之後發現，GG 完全沒頭緒，因此先來理解一下

先來看看 orig 和 opt 的差別

* 從 main.c 中可以看到 opt 加上了
* test_align.h
* 若字串長度大於給定值，警告使用者，但還是會將此字串寫入檔案內
* debug.h
* 可以顯示出 log 訊息幫助 debug
* <fcntl.h>
* 針對文件描述符提供控制
> #define DEBUG_LOG(...)
> 不懂 (...) 的意思
[name=丁榮主]
:::danger
請找 `stdarg.h`，不定個數參數的處理 --jserv
:::

在 opt 內可以看到

 33 typedef struct _thread_argument {
 34     char *data_begin;
 35     char *data_end;
 36     int threadID;
 37     int numOfThread;
 38     entry *lEntryPool_begin;    /* The local entry pool */
 39     entry *lEntry_head; /* local entry linked list */
 40     entry *lEntry_tail; /* local entry linked list */
 41 } thread_arg;

裏面包含了 thread 所要的參數，再來就式要研究一下這個是要怎麼使用了

open() 和 fopen() 的差別
* fopen() : 有緩存區，會先將緩存區塞滿後再取出來，緩存區愈大，
速度愈快，具移植性，會在background 呼叫 open()
* open() : 無緩存區，不具移植性，是低階的 os call，只能讀二進制文件

不過若要使用 mmap 映射記憶體位置，就要使用 open

## 程式改進

使用 [Toward Concurrency](https://hackmd.io/s/Skh_AaVix#)所提到的 thread_pool 來進行改善
方法選擇參考 [threadpool-mbrossard](https://github.com/mbrossard/threadpool/blob/master/src/threadpool.c)
如何使用參考[petermouse的共筆](https://hackmd.io/s/S1nwG80og#)

thread pool 的結構如下：

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;
};


可以發現 threadpool append() 的時間跟 opt 的差不多，不過稍嫌慢了一點，並且有時候跑一跑會 segmentation fault，不過只有一部份

> 有試著去找原因，不過找不出來QQ 想請教各位大大可能的原因
:::danger
請愛用 GDB，然後你要更詳細分析 --jserv
:::