# 2017q1 Homework4 (phonebook-concurrent)
contributed by <`baimao8437`>
## 認識 Concurrent (並行)
- 工作可拆分成「獨立執行」的部份(decomposition), 這樣「可以」讓很多事情一起做, 但是「不一定」要真的同時做。
- Concurrency 可能會用到 parallelism，但不一定要用 parallelism 才能實現 concurrency。
這兩句話很簡單的可以理解並行與平行的差別
### 背景知識[^first]
1. Evaluation
- value computations:對一串運算式計算的結果
- side effect:也就是對物件狀態的修改
2. Sequenced-Before
對同一個thread下，求值順序關係的描述
3. Happens-Before
程式碼「效果」的呈現順序 舉例：
````
A = B + 1; // (1)
B = 1; // (2)
```
Compiler 最佳化編譯後組語為:
```
movl B(%rip), %eax
movl $1, B(%rip) //(2) finish
addl $1, %eax
movl %eax, A(%rip) //(1) finish
```
雖然後者先結束 但看起來效果像先 1 再 2 即符合 Happens-Before
4. Synchronized-with
就是跨 thread 版本的happens-before
*ps.Sequenced-before 其實就是同一個 thread 內的 happens-before*
5. Sequential Consistency
- 對於每個獨立的處理單元，執行時都維持程式的順序(Program Order)
- 整個程式以某種順序在所有處理器上執行
6. Lock-Free
還是有lock 但不會影響到其他執行續的運行(non-blocking)，不一定比非lock-free快
7. Coroutines
讓原本循序執行的陳述指令，得以做出交錯執行的結果，由 programmer 控制
[^first]: [Concurrency 系列文章](http://opass.logdown.com/posts/797957-concurrency-series-4-be-with-the-synchronizes-with-relation)
## Code Refactoring
「在不改變軟體的外在行為之下，改善既有軟體的內部設計」
重構的主要目的就是為了提升可讀性，以及為了日後有了需求的變化時，可以更容易因應修改或是擴充。
一些常見的 「Bad smell」[^second]
- Duplicated Code
在作業中，常因為要測試很多種方法，而使某些程式碼不斷的重複，可使用:
- Extract method
- Form Template Method
- Long Method
Programming people have realized that the longer a procedure is, the more difficult it is to understand.
- 有可另外提出的程式碼: Extract method
- 太多的 temporary variables: Replace Temp with Query
- Comments
需要comment表示這段程式碼充滿妨礙閱讀的 bad smell，先 refactoring 後，往往就不需要 comment 了
- 需要註解一段程式碼: Extract Method
- 需要註解的程式碼已是 method: Rename Method
- 需要註解執行程式的必要條件: Introduce assertion(老師常用！)
[^second]: [Refactoring](https://www.csie.ntu.edu.tw/~r95004/Refactoring_improving_the_design_of_existing_code.pdf)
## 實驗實作
### 開發環境
```
baimao@baimao-Aspire-V5-573G:~$ 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
型號： 69
Model name: Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
製程： 1
CPU MHz： 1711.242
CPU max MHz: 2600.0000
CPU min MHz: 800.0000
BogoMIPS: 4589.38
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
```
### 原始效能分析
記得 `echo 3 | sudo tee /proc/sys/vm/drop_caches` 清空 cache
- `$ ./phonebook_orig `
```
size of entry : 136 bytes
execution time of append() : 0.111719 sec
execution time of findName() : 0.005537 sec
```
- perf orig
```
Performance counter stats for './phonebook_orig' (100 runs):
1,202,610 cache-misses # 78.679 % of all cache refs ( +- 0.49% )
1,528,504 cache-references ( +- 0.19% )
320,439,956 instructions # 1.48 insn per cycle ( +- 0.02% )
216,931,003 cycles ( +- 0.15% )
0.087285532 seconds time elapsed ( +- 0.27% )
```
- `./phonebook_opt ` 這裡預設的 thread_num = 4
```
orginal file size = 3206080
size of entry : 24 bytes
execution time of append() : 0.012572 sec
execution time of findName() : 0.003665 sec
```
- perf opt THREAD=4
```
Performance counter stats for './phonebook_opt' (100 runs):
387,281 cache-misses # 23.459 % of all cache refs ( +- 0.47% )
1,650,873 cache-references ( +- 0.71% )
247,715,431 instructions # 1.43 insn per cycle ( +- 0.09% )
173,636,294 cycles ( +- 0.64% )
0.091929529 seconds time elapsed ( +- 1.40% )
```
- gnuplot
#### **分析**
opt 版本主要實作了以下去優化 append 效能:
- text align
- 將所有資料的長度對齊 輸出至 align.txt
- 不夠長補'\0' 太長截斷
- fsize 會回傳整的檔案的大小(bytes)
- entry_pool
- 依據 text align 的 fsize 去一次 malloc 全部 entry
- [mmap](http://welkinchen.pixnet.net/blog/post/41312211-%E8%A8%98%E6%86%B6%E9%AB%94%E6%98%A0%E5%B0%84%E5%87%BD%E6%95%B8-mmap-%E7%9A%84%E4%BD%BF%E7%94%A8%E6%96%B9%E6%B3%95)
- 將 align.txt 映射至虛擬記憶體 VMA（Virtual Memory Area）
- 好處:高速檔案存取、執行緒共享記憶體
- pthread
- 預設 thread num = 4
- 每個 thread 工作量一樣 (append data = 87475)
至於 findName() 時間也變快的原因 下面 show_entry 後就可以看出來
針對特定測資就會出現一些誤差 預設搜尋的`zyxel`
在 orig 版本 所在位置在 349891 行
而用 opt 版本 由於順序是會被打亂的 此次出現在 262423 行 所以搜尋的時間花費較少 但速度其實是一樣的
#### **正確性**
*append:*
利用 `phonebook_opt.c`定義的`show_entry`來檢視用 pthread 建立的 linked list 是否與來源(words.txt)一致
可以發現
- 順序是被打亂的
- words.txt 有 349900行 show_entry只有349896行 少四行
發現原本程式中有點小錯誤 再串接各 thread 建立的 list 時
```
pHead = thread_args[0]->lEntry_head->pNext;
...
for (int i = 1; i < THREAD_NUM; i++) {
e->pNext = thread_args[i]->lEntry_head->pNext;
...
```
應改為
```
pHead = thread_args[0]->lEntry_head;
...
for (int i = 1; i < THREAD_NUM; i++) {
e->pNext = thread_args[i]->lEntry_head;
...
```
行數就正確了
*findName:*
opt 版的 findName 有點小疑惑 建好 list 後 show_entry 為 349900 行沒錯
但不知道為何 findName 完後再執行 show_entry 就變成 349899 少了一行
回頭看完[學長影片](https://www.youtube.com/watch?v=sWtWslsr4Ac)才知道這是故意設計成這樣的
但我下面要實作 delete 所以設計回 findName 完後可以 show_entry 出完整 list 的版本
```c
while (pHead) {
if (strncasecmp(lastname, pHead->lastName, len) == 0
&& (pHead->lastName[len] == '\n' ||
pHead->lastName[len] == '\0')) {
// pHead->lastName[len] = '\0';
```
#### **再優化**
- **merge linked list improve[^third]**
- **use macro at thread set**
```c
for (int i = 0; i < THREAD_NUM; i++)
thread_args[i] = createThread_arg(map + MAX_LAST_NAME_SIZE * i, map + file_size, i,THREAD_NUM, entry_pool + i);
for (int i = 0; i < THREAD_NUM; i++)
pthread_create(&threads[i], NULL, (void *)&append, (void *)thread_args[i]);
```
改寫成
```
for (int i = 0; i < THREAD_NUM; i++)
THREAD_SET(i);
```
time(100 run):`append()0.004217 findName() 0.005007`
append 時間減少 一個設定好就先跑的概念
[^third]: [老師給東霖的意見](https://hackmd.io/s/ByiOeFYie#最後-merge-linked-list)
### 實作 Delete Name
- orig 時間:
```
execution time of append() : 0.052377 sec
execution time of delete() : 0.005598 sec
execution time of findName() : 0.005562 sec
```
- opt 時間:
```
execution time of append() : 0.004075 sec
execution time of delete() : 0.003510 sec
execution time of findName() : 0.003502 sec
```
在建完 list 後 可以透過指令`DELETE(name)`來刪除特定的資料
delete 的速度應該跟 findName 是差不多的
### Refactoring
- 改用之前修改的時間工具 Stopwatch 測量時間
- 參考[老師的API包裝法](https://github.com/sysprog21/matrix_oo/blob/master/stopwatch.c) 包裝了原本的 Stopwatch
- 將 orig & opt 版本包裝成 API ， `phonebook_orig.h` & `phonebook_opt.h` 合併成 `phonebook.h` 實現多型(polymorphism)
重構之後 程式碼好閱讀多了 依照階段來完成任務 並會自動對應到不同版本的實作 成就感UPUP~
~~然後剩不到一天 還剩兩個作業...~~
Sign in with Wallet
Connect another wallet