2017q1 Homework4 (phonebook-concurrent)

contributed by <PeterTing>

tags: `phonebook-concurrent` `PeterTing`

作業要求

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

初步測試

 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(…)
不懂 (…) 的意思
丁榮主

請找 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所提到的 thread_pool 來進行改善
方法選擇參考 threadpool-mbrossard
如何使用參考petermouse的共筆

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 想請教各位大大可能的原因

請愛用 GDB，然後你要更詳細分析 –jserv