# Experiments on Concurrency - Happens-before contributed by < [`jeffrey.w`](https://github.com/jeffrey-minwei/experiments-on-concurrency/tree/master/c11-standard) > ## Introduction C 語言在 C99 的時候還沒有將並行 (`concurrency`) 納入到語言的標準，但到了[`C11 standard`](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf) 就開始將並行、`memory order` 相關的機制加入到規格裡，本文將透過學習 [`C11 standard`](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf) 和 [`C++11 standard`](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3376.pdf) 來理解並行在語言層面的機制，然後使用 `C11` 來實驗並行。 ## Modification order §5.1.2.4/7 定義了 `modification order` > All modifications to a particular atomic object M occur in some particular total order, called the modification order of M. If A and B are modifications of an atomic object M, and A happens before B, then A shall precede B in the modification order of M... §5.1.2.4/7 提到兩件事： 1. particular total order 2. 假設 A 和 B 代表對 atomic object M 的 modification ，然後 A happens before B ${\Rightarrow}$ 對於 M 的 modification order，**A 會先於 B** ### Total order §5.1.2.4/7 所說的 `particular total order` 是指什麼？ > All modifications to a particular atomic object M occur in some **particular total order** 數學上的 `total order` 是指一個集合裡的 `binary relation` [[`1`](https://en.wikipedia.org/wiki/Total_order)]，這個二元關係具有三個特性：反對稱、遞移和 `Connexity`： - 反對稱 ([antisymmetric](https://en.wikipedia.org/wiki/Antisymmetric_relation)) - ${\displaystyle \forall a, b\in X, \ aRb \ and \ bRa\;\Rightarrow \;a=b}$ - 遞移 ([transitive](https://en.wikipedia.org/wiki/Transitive_relation)) - ${\displaystyle \forall a,b,c\in X,\ aRb\ and \ bRc\;\Rightarrow aRc}$ - [Connexity](https://en.wikipedia.org/wiki/Connex_relation) - ${\displaystyle \forall a, b\in X, \ \displaystyle aRb}$ or ${\displaystyle bRa}$ 這三個特性如果從 modification order 的角度來看會是怎樣？ 假設 A, B, C 各自代表**一個 atomic object 的 modification**，底下就可以用 `binary relation` ${R}$ 來表示 **happens-before relation** - ${\displaystyle \forall A, B, C\in X}$ - ${\ R(A, B)}$ and${\ R(B, A)}$ ${\Rightarrow \;A=B}$. - ${\ R(A, B)}$ and${\ R(B, C)}$ ${\Rightarrow \ R(A, C)}$ - ${\ R(A, B)}$ or${\ R(B, A)}$ 回到 §5.1.2.4/7 所說的 `particular total order`，假設其中一種 `total order` 如下圖所示： ```graphviz digraph G{ A -> B -> C; } ``` :::warning 上圖只是 `total order`，還沒有提到 `modification order` ::: 初始條件: - `binary relation` ${R}$ 表示 **happens-before relation** - ${\displaystyle A, B, C\in X}$ - ${\displaystyle (A, B), (B, C), (A, C)\in R}$ 我們一條一條來檢視一下這幾個 `modification` 的順序符不符合 `total order` 的定義 - ${(A, B)}$, ${(B, A) \in R}$ ${\Rightarrow \ A=B}$ - ${(B, A) \notin R}$, ${(C, B) \notin R}$, ${(C, A) \notin R}$ - ${(A, B)}$, ${(B, C) \in R}$ ${\Rightarrow \ (A, C) \in R}$ - trivial - ${(A, B) \in R}$ or ${(B, A) \in R}$ - ${(A, B) \in R \Rightarrow (A, B) \notin R}$ - ${(B, C) \in R \Rightarrow (C, B) \notin R}$ - ${(A, C) \in R \Rightarrow (C, A) \notin R}$ 至此，我們知道了 ${A, B, C}$ 這三個 `modification` 的 `happens-before relation` 符合 `total order` 的定義。 所以 ${A, B, C}$ 的 `modification order` 符合規格書的順序就會是 ${A \rightarrow B \rightarrow C}$。 ### Example 寫一段 code 來實驗 `modification order`，底下的範例改寫自 [`Preshing on Programming, Memory Ordering at Compile Time`](https://preshing.com/20120625/memory-ordering-at-compile-time/) ```clike #include <stdatomic.h> atomic_int a = ATOMIC_VAR_INIT(0); atomic_int b = ATOMIC_VAR_INIT(0); int c, d; void test_atomic() { atomic_fetch_add(&b, 5); atomic_store(&a, b); b = ATOMIC_VAR_INIT(42); } void test(){ c = d + 5; d = 42; } int main(int argc, char **argv) { test(); test_atomic(); return 0; } ``` 先看 `test` 的組合語言在 `gcc -O2 -S -masm=intel` 和 `gcc -S -masm=intel` 的差別 **gcc -O2 -S -masm=intel** ``` test: ... mov eax, DWORD PTR d[rip] mov DWORD PTR d[rip], 42 add eax, 5 ... ``` **沒有最佳化** `gcc -S -masm=intel` ``` test: ... add eax, 5 mov DWORD PTR c[rip], eax mov DWORD PTR d[rip], 42 ... ``` 再使用 `gcc -O2 -S -masm=intel`，從組合語言來比較 `test` 和 `test_atomic` ``` test_atomic: ... lock add DWORD PTR b[rip], 5 mov eax, DWORD PTR b[rip] mov DWORD PTR a[rip], eax mfence mov DWORD PTR b[rip], 42 ... ``` ``` test: ... mov eax, DWORD PTR d[rip] mov DWORD PTR d[rip], 42 add eax, 5 ... ``` 我們從幾個角度來看上述幾種結果在 [`C11 規格`](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf) 的意義： - test 在 -O2 的 assembly 有沒有違反 `happens-before`？ - test_atomic 在 -O2 的 assembly 有沒有符合 `modification order`？ - [`C11 規格`](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf)<sub>(§5.1.2.4/7)</sub> 對 `modification order` 的定義 > If A and B are modifications of an atomic object M, and A happens before B, then A shall precede B in the modification order of M... - 假設 $A$ 和 $B$ 是對 `atomic object` 的 `modification` - $A$ `happens before` $B$ ${\Rightarrow}$ $A$ 的 `modification order` 在 $B$ 的前面 - 所以，加了 `-O2` 仍然符合 `modification order` 參考維基百科對 [全序關係](https://zh.wikipedia.org/wiki/%E5%85%A8%E5%BA%8F%E5%85%B3%E7%B3%BB) 的說明，我們知道全序關係是一個二元關係，全序集是指一個**滿足全序關係的集合**，在全序集裡，元素任意一對都是可以比較的。 至此，重新再看一次 [`C11 規格, §5.1.2.4/7`](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf) 所定義的 `modification order` > All modifications to a particular atomic object M occur in some particular total order, called the modification order of M. If A and B are modifications of an atomic object M, and A happens before B, then A shall precede B in the modification order of M... - 有一個全序集，裡面的元素都是**對 atomic object 的 modification**，這個全序集上的二元關係就是 `happens before`。 - 因為**任意一對**元素都是可以比較的，所以，任意兩個 `modification` $A$, $B$，比較的結果可以是 $A$ `happens before` $B$ 也可以是 $B$ `happens before` $A$。 - 如果 $A$ `happens before` $B$ 而且 $B$ `happens before` $A$ $\Rightarrow$ $A$ = $B$ - 如果 $A$ `happens before` $B$ $\Rightarrow$ $A$ 的 `modification order` 會在 $B$ 之前。 ## Happens before ## References - [ ] [並行程式設計](https://hackmd.io/@sysprog/concurrency) - [ ] [Preshing on Programming, Memory Ordering at Compile Time, JUN 25, 2012](https://preshing.com/20120625/memory-ordering-at-compile-time/) - [ ] [Concurrency系列(二): 從Sequenced-Before開始說起](http://opass.logdown.com/posts/788206-concurrency-series-2-starting-from-sequenced-before) ###### tags: `concurrency` `c11` `c++11` `happens-before`
Last changed by  
 
Jeffrey.W
473

Read more

I/O ordering 學習紀錄

contributed by < jserv, jeffrey.w > Arm 工程師 Will Deacon 在 Edinburgh 的演講 Uh-oh; it's I/O ordering 中提到一個範例： 初始條件：*x, *y 在記憶體裡，初始值為 0，foo, bar 是 local variable digraph g { rankdir = "RL"; "cpu0" [label= "CPU0 | a: WRITE_ONCE(*x, 1); | b: foo = READ_ONCE(*y);", shape="record"];

8/16/2023
Design patterns 筆記 - Strategy pattern on C++

contributed by < jeffrey.w > 這篇筆記回顧我 2001 年剛學 design patterns 的時候對 strategy pattern 的誤解，透過重新審視 2001 那年的誤解，重新學習 strategy pattern。 Strategy pattern 很容易跟 template method pattern 混淆，2001 年我剛學這兩種 pattern 的時候，甚至直接誤以為「把實作碼寫在 base class 讓 derived class 繼承就是 design pattern」，當年我真是完全誤解了 strategy pattern 和 template method pattern 在設計上的初衷。 先舉一個跟 design pattern 完全沒有關係 的例子，但我在 2001 年卻曾經把這個例子誤會成 design pattern。 以下這個例子和 design pattern 沒有任何關係

8/2/2021
Notes on Java8 Stream and Lambda expression

contributed by < jeffrey.w > Introduction Java 1.8 新增了幾個 feature，其中一些對於提升程式可讀性很有幫助，例如 stream, lambda expression, method references 和 functional interface。 stream operations 會組成一個 stream pipeline，stream pipeline 包含了一個 source、零個或一個以上的 intermediate operations (例如 filter)，還有一個 terminal operation (例如 forEach) [1]。 Intermediate operations intermediate operations 是指像 filter、map、distinct 之類的 method，這些 method 會將一個 stream 轉換成另一個 stream [1]。

7/1/2021
從 [C++11 規格](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3376.pdf#chapter.14) 學習 C++ Templates — 第一篇

contributed by < jeffrey.w > Template metaprogramming (TMP) 是一種從 template 的角度開發的 paradigm，也就是說他不是著眼在 int 或是 float 這種特定的 type，而是著眼在形而上的 type。原本我想用 concept 或是 generic 來說明，但由於 concept 和 generic 在 C++ 另有其他的解釋，為避免混淆，所以這裡不會提到 concept 和 generic。 C++11 從規格定義了 template，是學習 template 相當有用的第一手資料。本文是透過規格書學習 templates 的筆記，範圍包含 constexpr、type traits、partial specializations和template constructor，並且對於 compiler 在編譯時產生的 error 給出規格書上的解釋。 :::info 透過這份文件 N3377=12-0067，可以知道 N3376 是最接近 C++11 規格的草案，所以這份筆記主要是以 N3376 為主。 :::

4/15/2021
Read more from Jeffrey.W
Published on HackMD