2016q3 Homework2 (phonebook-concurrent)

contributed by <Shaoyu-Chen>

Interface

為了讓程式有更好的可讀性，避免放置一堆 #define，目前實做介面如下：

void *init();
void *readFile(void *);
void *append(char [], void *);
void *findName(char [], void *);
void memory_free(void *);

• init: 初始化 phonebook 必要結構
• readFile: 讀入檔案，並使用 append 新增資料項到 phonebook
• append: 建立必要結構將資料加入 phonebook
• findName: 從 phonebook 找出指定資料項
• memory_free: 釋放動態配置結構的記憶體

mmap

• Great for multiple processes accessing the same file in read-only fasion
• Single vs. multiple system call
• No need to copy the data to the buffer C runtime maintain

Original Version

size of entry : 136 bytes
execution time of append() : 0.077778 +- 0.000892 sec
execution time of findName() : 0.004927 +- 0.000030 sec
(95% 信賴區間)

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

     2,010,723	cache-misses		#87.332% of all cache refs	( +-  0.13% )
     2,302,381	cache-references                             		( +-  0.07% )
   387,959,515	instructions    	#1.51  insns per cycle		( +-  0.01% )
   256,717,122	cycles							( +-  0.13% )

0.070331387 seconds time elapsed ( +-  1.31% )

Optimization

mmap 讀檔

1. • 假設： 若將所有 lastName 放置於一連續記憶體會提昇整體效能。

   • 實做：

     • entry struct
     ​​typedef struct __PHONE_BOOK_ENTRY {
     ​​    char *lastName;
     ​​    struct __PHONE_BOOK_DETAIL *pDetail;
     ​​    struct __PHONE_BOOK_ENTRY *pNext;
     ​​} entry;
     

     • 使用 mmap 讀入所有 lastName，並以 '\0' 取代所有 '\n'，將每個 lastName 視為獨立字串
     • append 時，不使用 strcpy，而是將 entry->lastName 指向對應位置

   • 結果： 相對原版 append 時間減少了 0.03 秒，但相對重要的 findName 時間卻增加了 0.001 秒

   ​size of entry : 24 bytes
   ​execution time of append() : 0.043081 +- 0.000606 sec
   ​execution time of findName() : 0.006310 +- 0.000031 sec
   ​(95% 信賴區間)
   

2. • 假設： 將各 entry 其 lastName 放置連續空間能夠提昇搜尋效能

   • 實做：

     • entry struct
     ​​typedef struct __PHONE_BOOK_ENTRY {
     ​​    char lastName[MAX_LAST_NAME_SIZE];
     ​​    struct __PHONE_BOOK_DETAIL *pDetail;
     ​​    struct __PHONE_BOOK_ENTRY *pNext;
     ​​} entry;
     

     • 使用 mmap 讀入所有 lastName，並以 '\0' 取代所有 '\n'，將每個 lastName 視為獨立字串
     • append 時，使用 strcpy 將 lastName 複製到 entry
     • 釋放 mmap 所配置空間

   • 結果： 相對原版 append 時間減少 0.02 秒，且 findName 時間減少 0.0015 秒

   ​size of entry : 32 bytes
   ​execution time of append() : 0.057684 +- 0.000508 sec
   ​execution time of findName() : 0.003563 +- 0.000017 sec
   ​(95% 信賴區間)
   

需要用統計方法，取出 95% 信賴區間，最好還能用 perf 分析效能 hotspot jserv
收到！Shaoyu-Chen

3. 討論
   • 前者 lastName 並不伴隨 entry，兩者在相對較遠的位置，較少機率會在同一快取線上
   • 計算 append 時間時，需使用 echo 3 > /proc/sys/vm/drop_caches (to free pagecache, dentries and *inodes)，否則因為 page cache 的原因，append 時間會因為不須真正做 I/O 而加速很多

Entry Slab

• 假設： 預先建立 entry pool，配置時直接於 pool 內取出，預期會比 malloc 數次花上較少時間（接續 mmap 讀檔第二項方法）
• 實做：
  • entry pool container： 紀錄 entry pool 串列
  ​static struct Pool_Cont
  ​{
  ​	struct Entry_Pool *pHead;
  ​	struct Entry_Pool *pCurrent;
  ​	struct Entry_Pool *pTail;
  ​} ppool_cont;
  

  • entry pool： 共有 64 entry 可供配置，並以 bitmap 紀錄各 entry 的配置情形
  ​static struct Entry_Pool
  ​{
  ​	uint64_t bitmap;
  ​	entry *pPool;
  ​	struct Entry_Pool *pNext;
  ​};
  

• 結果： append 時間多了 0.015 秒，findName 時間多 0.00025 秒，兩者皆無進步。若考慮到釋放 entry 與再次配置所需的額外檢測，則 append 時間則會大幅增加至 1 秒左右。

size of entry : 32 bytes
execution time of append() : 0.072752 +- 0.000958 sec
execution time of findName() : 0.003801 +- 0.000018 sec
(95% 信賴區間)

• 討論：
  推估原因為 runtime library 並不真的向作業系統 malloc 使用者指定大小空間，而是一次 malloc 更大的空間並進行管理，從結果來看我的作法顯得並不恰當。

Source of this article: https://hackmd.io/s/BJlPwHmA