# 2017q1 Homework4 (phonebook-concurrent)
contributed by <`tina0405`>

## 開發環境
~~~
tina@tina-X550VB:~$ lscpu
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 58
Model name: Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
製程： 9
CPU MHz： 1270.750
CPU max MHz: 3200.0000
CPU min MHz: 1200.0000
BogoMIPS: 5188.47
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3

~~~

## 作業要求1

* #### 在 GitHub 上 fork [phonebook-concurrent](https://github.com/sysprog21/phonebook-concurrent)，然後適度修改 `phonebook_opt.c` 和相關的檔案

* 先跑跑看原先的程式碼
~~~ clike=
//origin
tina@tina-X550VB:~/phonebook-concurrent$ ./phonebook_orig
size of entry : 136 bytes
execution time of append() : 0.120663 sec
execution time of findName() : 0.006128 sec

//optimal
tina@tina-X550VB:~/phonebook-concurrent$ ./phonebook_opt
orginal file size = 3206080
size of entry : 24 bytes
execution time of append() : 0.008897 sec
execution time of findName() : 0.006555 sec
~~~

* 圖表

### 我的想法
我目前想做的是，上禮拜來不及做完的 memory pool ，因為這部份都是再課本上看過，但卻沒有實作的經驗:

首先參考 [memory pool](https://en.wikipedia.org/wiki/Memory_pool)
~~~
文中提及：
A more efficient solution is preallocating a number of memory
blocks with the same size called the memory pool.
The application can allocate, access, and free blocks
~~~
* 建立大小相同的 block
想到的是二維矩陣，想要建立起一大個區塊，每個人一個格
其他的資料放進第2層。
~~~
Example:
a[0][0]放David
a[0][1]放email
a[0][2]放phone
......
~~~

* 首先 allocate:
我想創建一個函式 malloc 我的二維矩陣。
~~~ clike=
//phonebook_opt.c
void create(int m,int n)
{
Array =(char **)malloc(m*sizeof(char *)+m*n*sizeof(char));
}

//main.c
create(10,50);
~~~

* access 和 free
因為我樓上的矩陣是建立 10*50 ，所以我想在裝超過10筆資料前，先 free 一次我的矩陣。
~~~ clike=
//phonebook_opt.c
void realease()
{
free(Array);
}
if (!pHead->dtl)
{
Array[i++]=pHead->dtl;
if(i%8==0)
{
free(Array);
}
}

//main.c
/* Free the allocated detail entry */
realease();
free(entry_pool);
~~~

* ### 結果
~~~

phonebook_orig:
size of entry : 136 bytes
execution time of append() : 0.081860 sec
execution time of findName() : 0.006235 sec

phonebook_opt:
size of entry : 24 bytes
execution time of append() : 0.008897 sec
execution time of findName() : 0.006555 sec

phonebook_opt:（接續原版的optimal改的）
size of entry : 24 bytes
execution time of append() : 0.007163 sec
execution time of findName() : 0.004693 sec

~~~
* 圖示

>> 發現結果比 origin 好很多，但因為是建立在optimal版本 上，只有再好一點點，如果跟原本的optimal比不顯著，想再嘗試以下方法。

## 作業要求2
* #### 至少涵蓋研讀 [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) 的基礎下進行

* ### 試看看 thread 的數量影響
參考了作業附上的[實驗](https://hackmd.io/s/BkN1JNQp#)連結，也想自己來改改看THREAD數量。

~~~ clike=
tina@tina-X550VB:~/phonebook-concurrent$ ./phonebook_opt
orginal file size = 3206080
size of entry : 24 bytes
thread number :1
execution time of append() : 0.008482 sec
execution time of findName() : 0.004718 sec

orginal file size = 3206080
size of entry : 24 bytes
thread number :2
execution time of append() : 0.004895 sec
execution time of findName() : 0.001542 sec

orginal file size = 3206080
size of entry : 24 bytes
thread number :3
execution time of append() : 0.008158 sec
execution time of findName() : 0.001325 sec

orginal file size = 3206080
size of entry : 24 bytes
thread number :4
execution time of append() : 0.008314 sec
execution time of findName() : 0.005944 sec

orginal file size = 3206080
size of entry : 24 bytes
thread number :5
execution time of append() : 0.008138 sec
execution time of findName() : 0.002413 sec

orginal file size = 3206080
size of entry : 24 bytes
thread number :6
execution time of append() : 0.010388 sec
execution time of findName() : 0.001620 sec

orginal file size = 3206080
size of entry : 24 bytes
thread number :7
execution time of append() : 0.010348 sec
execution time of findName() : 0.005564 sec

orginal file size = 3206080
size of entry : 24 bytes
thread number :8
execution time of append() : 0.011719 sec
execution time of findName() : 0.005054 sec
~~~
* 在這裡我只更改 THREAD 數量，發現兩條執行緒是最好的狀態，再上去則是愈多愈糟糕。

* 圖示是 2 條執行緒的情況，是全部裡面最好的，也比我原本 run 的 4 條執行緒快一點。


* 參考老師給的[Measuring Lock Contention](http://0pointer.de/blog/projects/mutrace.html)

>>的確之前一直覺得，沒有程式記憶體區段錯誤，就是好了，但卻忽略了 lock 的問題資源只要一直沒有被釋放，就可能造成很多的時間消耗。

## 作業要求3
* #### 學習 [concurrent-ll](https://github.com/jserv/concurrent-ll) (concurrent linked-list 實作) 的 scalability 分析方式，透過 gnuplot 製圖比較 list 操作的效能

* #### 一併嘗試重構 (refactor) 給定的程式碼，使得程式更容易閱讀和維護。延續 [B05: introspect](https://hackmd.io/s/SyFpOZQqx)，不只是在共筆上用文字提出良性詳盡的批評，也該反映在程式碼的變革