Performance of Concurrency
用 concurrency 就是為了更快，為了比 sequential 程式快，不然搞得那麼複雜幹嘛呢。
如何評估 concurrent 程式的效能提升？
speedup = sequential 程式執行時間 / concurrent 程式執行時間
speedup 可能隨著使用的 core 數改變，標示程式在不同 core 數上的 speedup，可以由不同 core 數的 speedup 變化知道程式的 scalability。speedup 的提升隨著使用 core 數增加而增加甚至比例接近 core 增加的數量，表示有好的 scalability。理想狀況是 core 數加倍 speedup 也加倍。
有時會發生 speedup 的提升超過 core 的增加數量，稱為 superlinear speedup。這通常是有問題，要再確認 concurrent 程式執行結果是否正確、是否使用一般情境下的 dataset 而非只是測試資料。superlinear speedup 常見的原因是資料量太小，sequential 程式因為不斷需要新資料而被清掉的 cache 反而在 concurrent 程式中因為各 core 處理的資料量太小而 cache 住，自然 concurrent 程式在資料讀取上會比較快，造成效能變超好的錯覺。（假的！）
如果已有 sequential 程式、要決定是否 concurrent 化，能事先估算效能提升比較好，畢竟 concurrent 程式複雜也需要投入成本開發，如果效能提升不好就白費工夫了。
接下來兩個定理皆假設一個 core 上只執行一個 thread，如果一個 core 上執行多個 thread，就要把下面公式中的 core 數換成 thread 的數量。
Amdahl’s law
在 dataset 大小是固定的情況下（dataset 不會隨著可用 core 數變多而跟著變多），可以用 Amdahl’s law 估算 speedup 的理論值。
使用 Amdahl’s law 要知道程式的執行時間有多少比例能平行化、又有多少比例只能以 sequential 執行，用估算值即可，當然也可以用 profiler 看程式的實際執行時間。Amdahl’s law 的 speedup 如下：
speedup <= 1 / ((1 - p) + (p / c))
p是程式執行時間中可平行化的比例c是使用的 core 數
舉個例子，假設一個 sequential 程式執行需要 10 分鐘，其中 2 分鐘的工作無法平行化、8 分鐘的工作可以平行化，那麼在 4 core 的環境下 speedup 是：
speedup <= 1 / ((1 - 0.8) + (0.8 / 4)) = 2.5
假設有無限多 core 可以使用，speedup 會趨近於 1 / (1 - p)，也就是跟無法平行化的執行時間成反比。蠻符合直覺的，因為一個程式平行化到極限，它的執行時間就是不能平行化的部份的執行時間（像例子的 2 分鐘）。
Gustafson’s law
Amdahl’s law 有個問題在它的前提：dataset 大小固定。這表示無論程式可使用的 core 如何變多，給程式跑的 dataset 都不變。問題是實際上隨著機器能力的增強（core 數變多），要處理的資料量也會變多（看看十幾年前 1MB 就很大了，現在隨便都是 TB 在喊的），在 dataset 會隨著 core 數變多的情況下就不能用 Amdahl’s law 啦。
於是有了 Gustafson’s law，也稱為 scaled speedup，考慮 dataset 隨著 core 數變多而等比例增加的情況下計算 speedup 的理論上限：
scaled speedup <= c + (1 - c) * s
c是使用的 core 數s是在給定 dataset 以及使用 core 數的情況下，程式花多少時間在 sequential 執行上的比例
舉例，假設有個平行化程式在 32 core 上執行花了 1000 秒，其中 30 秒花在 sequential 執行上（在一個 core 上 sequential 執行），那麼這個程式比起相同 dataset 只用一個 thread 執行（dataset 大能不能 single thread 跑是另一回事）的 speedup 是：
scaled speedup <= 32 + (1 - 32) * (30/1000) = 31.07
注意這邊的 s 不能當作 Amdahl’s law 的 1 - p，因為這裡的 s 是在某特定 core 數下的執行時間比例，而非 sequential 程式中預估可平行化部份的執行時間。
Gustafson’s law 跟處理龐大資料有關。資料量變大不見得得 sequential 處理的資料就變多，如果是可平行處理的資料變多，那麼反而 sequential 執行所佔的整體比例會下降（Amdahl’s law 沒有這一點是因為 dataset 固定），於是在資料逐漸龐大的情況下，sequential 部份的影響可能減小。
Efficiency（效率）
跟 speedup 有關的是 efficiency，efficiency 反映的是系統運算資源的使用狀況，看看 concurrent 程式對系統資源的使用效率如何。
efficiency = 實際觀察到的 speedup / 使用的 core 數
efficiency 通常以百分比表示，愈高表示愈沒有資源是閒置的。