# 2017q1 Homework4 (phonebook-concurrent)
contributed by < ` changyuanhua ` >
## Toward Concurrency 閱讀
* 觀看教學影片 [Concurrency](https://www.youtube.com/watch?v=3mkug2ygdIs)
> 每次有些觀念總是聽聽過幾分鐘後就沒印象了，所以就把覺得不熟悉，會忘記的教學影片內容(老師說的話)，打出來
### 軟體開發現況
* 以前 CPU 增進效能的手段
* Cache：盡量減少存取 Main memory 的機會，避免快的處理器等慢的 memory
* 主記憶體發展比 CPU 慢
* 現在 CPU 增進效能的手段 (現在單一核心效能很難再提升，改以用多個處理器的核心，提升效能)
* Hyperthreading: 在 single CPU 上同時執行多個 thread，但是共用 ALU、FPU
* I/O device 的技術一直在進步( I/O bound 可能發生的幾率越來越小),所以 CPU bound 的技術也越加重要
### Functional Programming
* 多核，遞迴跟它不是直接相關，但設計概念卻跟它有很大的關聯，它可以減少區域變數或全域變數的使用，跟多核實作有很大關聯
* functional language 在多核執行緒情況下，有很大影響 ?
* functional language 沒有 shared state
* 使函式，可以大規模並行化
* 使不能同時從多個執行緒存存取相同資源來，讓多執行緒更加安全
* pure functions : 它不會修改程序中的任何其他狀態。這定義為 threadsafe (線程安全)
> 還是不太懂~

> 看 [functional programming](https://www.slideshare.net/ihower/fp-osdc2012v2) 後，正在理解中
* thread-safe
1. 每個存取到的共享變數，都要 synchronize
2. 操作要注意 atomic
3. 要可以避免 deadlock
* 問題: 當 synchronize 太多，都是 blocking threads ，那程式在同一時間就只會在一個 thread 跑
* 結果: mutable shared state ，以致於 multi-threading program 困難
* 解決想法: 如果沒有 mutable 變數，就不用擔心 synchronize 問題，也就不用擔心 multi-threading program 困難
* functional programming (提供開發 concurrency program 良好的基礎)
* 避免(降低?) state 和 mutable data
> 當 x = 1234; x = 3456; 如果 x 指派後是3456，那就是 mutable ，如果不行的話，就是 immtable
### 不是探討 Synchronization 而已
* mutex: 誰持有資源，誰去解，只在意通過數量(像鐵路平交道)，有 owner 概念，導致 priolity invention
* Priority inversion defined
* 如果低優先權持有一個 lock 的過程中，出現中度優先權，被中度搶占的話，會增加 lock 持有的時間
* 如果中度執行非常長，或是沒有結束的1天，會導致原本在等待低優先權的 lock 的高優先權，永遠沒有執行的1天
### Concurrency (並行) vs. Parallelism (平行)
* concurrency :解構
* 會使用的原因
* 分離可獨立運作的工作
* 為了效能，像是使用多核新的 CPU
* 如果程式的相依性太高或是太常取用共同資源則會拖慢 Concurrency 的效率
* parallelism :同時
* atomic operation
* 因為 concurrency 牽涉相當廣，從最基本的 lock, mutex, semaphore 等同步用的工具外，如果繼續往下鑽，就會遇到atomic operation，要透過不可分割的原子操作來實現這些工具
* 同步方式：如果用軟體實做，是一個大量的運算，會比硬體操作慢了一千倍，執行成本太高，像是 dekker 演算法
* 所以通常搭配由 cpu 提供的 atomic instruction
* instruction scheduling （由 compiler 實做）
* 因為每道指令花的時間不同，要避免 pipeline stall ，以及語意上是模糊的行為（不需要對一個無號數做大於零的判斷）
* happens-before
* 當行為 A happens-before B 時，代表 A 的效果可見，而且發生於 B 之前
* sequenced-Before
* 當 A Sequenced-Before B 時，表示在同一個 thread 下，A 比 B 先求值
* synchronized-with
* 當 A synchronized-with B 時，表示 A 在這一個 thread 對記憶體的操作，在另一個 thread 的 B 必須可見。
* Sequential consistency：無論處理器實際怎麼執行，確保結果跟照程式順序執行一樣
* Read before Write：在新值寫入前讀取到舊值
* Write after Write：在正確值寫入後被舊值複寫 (有先後)

### concurrency
* lock-free : 假設有4個執行緒，4個執行緒中間一定要有lock ，才能確保資料的一致性，所以 lock-free 不是說完全不用 mutex lock ，而是指「執行緒的執行不會被其他 lock 鎖住」
* lock-free 避免 spinlock
* spinlock :其他核做跟改變值無關的事
* GC
* 又為 lazy evaluation
* Acquire and Release Semantics
* Acquire semantics :只能被視爲對共享內存的讀取(read-acquire),且禁止 read-acquire 之後的所有操作被提前到它之前執行
* Release semantics :只能被視爲對共享內存的寫入(write-release),且禁止 write-release 之前的所有操作被延遲到它之後執行
## refactoring
* 觀看 [李昆憶學長的筆記](https://hackmd.io/s/HJFhaiAp)
* 定義 ：在不改變軟體的外在行為之下，改善既有軟體的內部設計
* 改善 ：先判斷軟體中所存在的壞味道（smell），然後套用重構來移除這些壞味道。每一條軟體重構就是一些告訴開發人員要如何移除各種壞味道的小步驟。
* 目的:
* 使程式更容易被理解和修改,但是相對的效能會有所降低(在重構不應該考慮效能問題,效能改進問題應該與重構分開進行,因爲重構在提高可讀性的同時也會提高優化的易難度)
## 開發環境
* 輸入指令 ` lscpu `

Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：1
每通訊端核心數：4
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              94
Model name:            Intel(R) Core(TM) i5-6300HQ CPU @ 2.30GHz
製程：              3
CPU MHz：             799.890
CPU max MHz:           3200.0000
CPU min MHz:           800.0000
BogoMIPS:              4608.00
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           6144K
NUMA node0 CPU(s):     0-3

## 原始程式
原始效能分析
* ` make plot ` 後得圖
* opt 版本：
* text-align