從 C++11 規格和 Template Meta-Programming 的角度欣賞 Boost 對 atomic 和 memory order 的支援 - 翁敏維

由於場地問題，第二天我們移動到另一棟大樓啦！議程教室變動請見網站上的議程表。

歡迎來到 https://hackmd.io/@coscup/2019 共筆

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

點擊本頁上方的開始用 Markdown 一起寫筆記！
手機版請點選上方按鈕展開議程列表。

簡報模式

Agenda

Introduction
Why needs Template metaprogramming?
What is memory order?
How C++11 supports memory order？
Boost.Atomic

Introduction

為什麼要看 C++11 規格？
















  void push(const T &data)
  {
    node * n = new node;
    n->data = data;
    node * stale_head = head_.load(boost::memory_order_relaxed);
    do {
      n->next = stale_head;
    } while (!head_.compare_exchange_weak(stale_head, n, boost::memory_order_release));
  }
  ...
  node * pop_all_reverse(void)
  {
    return head_.exchange(0, boost::memory_order_consume);
  }
  private:
  boost::atomic<node *> head_;

Reference
Boost.Atomic, Usage example

上面這段節錄自 Boost.Atomic, Usage example，由於直接看 code 並不是有效率的學習方式，甚至可能得到錯誤的認知，所以從理解 C++11 規格開始。
透過理解 C++11 規格，看到上面這段 code 就不必用猜的，也不必用 try and error ，是一種比較有效率的學習路線。

Why needs Template metaprogramming?

先澄清一件事，

不是直接用 templates 程式就會變快。

雖然 template 會在 compile-time 作展開和運算，但如果僅僅只是直接把 function 改成 template，就如同直接換成 inline 或 macro一樣，執行的時間是沒有差別的

作一個實驗來說明這個概念

// templates.cpp
template <class T> T add(T a, T b){
        return a + b;
}

int main(){
        int ans = 0;
        int a = 1, b = 2;
        for(int i = 0; i < 1000000; ++i){
                ans += add(a, b);
        }
}

// no-templates.cpp
int add(int a, int b){
        return a + b;
}

int main(){
        int ans = 0;
        int a = 1, b = 2;
        for(int i = 0; i < 1000000; ++i){
                ans += add(a, b);
        }
}

 Performance counter stats for './templates' (10000 runs):

         8,911,140      cycles                                                        ( +-  0.09% )

       0.003526686 seconds time elapsed                                          ( +-  0.11% )


 Performance counter stats for './no-templates' (10000 runs):

         9,010,668      cycles                                                        ( +-  0.11% )

       0.003570547 seconds time elapsed                                          ( +-  0.13% )

是不是 templates 的差異只有 0.05 ms
0.05 ms 是執行 1 萬次的平均時間
並不是直接換成 template 就會變快

並不是 templates 不會讓執行時間縮短，而是因為剛剛的測試範例只是直接把 function 換成 templates

用 templates 實作出在 compile-time 運算來縮短執行時間，同時具有 inline 和 macro 所不具有的優點，並不是這一次 talk 的主題

那 template metaprogramming 要探討什麼？

有。
write generic code

用對照組，體會一下是不是 generic code 的差異

unsigned int calc(unsigned int a, unsigned int b, unsigned int c){
	return a ^ 2 + b * 3 + c * 2;
}
int calc(int a, int b, int c){
	return a * 2 + b * 2 + c ^ 2;
}
long calc(long a, long b, long c){
	return a * 3 + b ^ 2 + c ^ 3;
}

這段看起來，我們可能會這麼覺得：

這是 overloading，只是其中幾個寫錯
- 那麼哪一個寫錯？
- 還是有兩個寫錯？
  - 哪麼是哪兩個寫錯？
不同的 types 的計算方式本來就不一樣

剛剛我們示範了一個讓人用覺得來判斷的 code，這在可讀性上來說，實在不妥

或許可以用加註解來解決可讀性，
不過上面這個例子有更好的解法

更好的解決方法是 write generic code，所以我們用 templates metaprogramming，修改後是這樣子

template<class T> T calc(T a, T b, T c){
	return a ^2 + b^2 + c^2;
}

當然，我們假設上面的例子，每一個 calc 的計算方式一樣

What is memory order?

reorder
out-of-order

reorder

shared memory: x = 0; y = 0

P0             | P1             ;
a: MOV [x],$1  | c: MOV [y],$1  ;
b: MOV EAX,[y] | d: MOV EAX,[x] ;

a, b, c, d 的執行順序有沒有可能是 b, d, c, a
由於 CPU 會進行 reorder，所以未必會照著順序執行，因此在這個範例中，processor 0 的 EAX 和 processor 1 的 EAX 有可能都是 0 (只是經過測試，100 萬次裡出現的次數是個位數)

reorder 在不同的 CPU 會有不一樣的行為

reorder 之後 有可能 是照著這個順序執行

shared memory: x = 0; y = 0

P0             | P1             ;
b: MOV EAX,[y] | d: MOV EAX,[x] ;
               | c: MOV [y],$1  ;
a: MOV [x],$1  |                ;

compiler 會對 program order 作 reorder，而 CPU 也會對 instruction 執行的順序作 reorder。
阻止全部的 reorder 雖然也是一種方法，但這樣會產生效率低落的結果。所以需要研究 memory order，讓工程師能對 reorder 作一些控制。

out-of-order

我們從 instruction pipelining 來理解 out-of-order

in-order

                 1      2         3         4       5        6         7         8
fetch      |  fetch1                              fetch2 
decode     |          decode1                               decode2
execute    |                    execute1                             execute2
write-back |                               write1                                write1

如果是照著以上的順序來執行 2 個 instruction，會用掉 8 個 cycle 來執行 2 個 instruction。

out-of-order

但如果是 OoOE，可能會是以下的順序，這樣就可以只用 5 個 cycle 執行 2 個 instruction

                 1      2         3         4        5
fetch      |  fetch1  fetch2 
decode     |          decode1  decode2
execute    |                   execute1  execute2
write-back |                              write1    write1

但是 out-of-order 會有一個延伸的問題，execute2 如果會從 register 讀取一個值，而這個值要 write1 執行後才會更新…
那 execute2 的結果？

現在我們知道 program order 是我們從 source code 看到的順序，但是實際執行的順序，未必和 program order 一樣。

CPU 會對 instruction 作 reordering，所以我們看到的 assembly 的 program order 未必是執行順序

如果我們寫的是 C++11 的 code，program order 是不是也有可能不一樣？

對，program order 是允許不一樣的，但 C++11 支援不同的 memory order，可以控制實際執行順序

How C++11 supports memory order？

data races
synchronization operations / atomic operations
memory_order_seq_cst
memory_order_relaxed
如何透過 memory model 建立 happens-before 的關係

從 C++11 規格來看 data races

C++11 1.10/21

The execution of a program contains a data race if it contains two conflicting actions in different threads, at least one of which is not atomic, and neither happens before the other.

Reference
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3376.pdf

其中一個 thread 的 operation 不是 atomic operation，而且也沒有 happens before 這種關係

synchronization operations
atomic operation
如何建立 happens before 這種關係？

A synchronization operation on one or more memory locations is either a consume operation, an acquire operation, a release operation, or both an acquire and release operation.

Reference
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3376.pdf#section.1.10

synchronization operation 是要在不同的執行緒之間同步，等一下我們會在範例中看到這是如何運作的
在 wait-free multi-producer queue 會用到 memory_order_relaxed、memory_order_release 和 memory_order_consume

wait-free multi-producer queue 就是一開始提到的 Boost 的範例

特別要留意的地方是：
relaxed operations 雖然是 atomic，但不是 synchronization operations

In addition, there are relaxed atomic operations, which are not synchronization operations, and atomic read modify-write operations

Reference
C++11 1.10 Multi-threaded executions and data races

C++11, page 1115 說明了 memory_order_seq_cst 是一種 single total order

consistent with the “happens before” order and modification orders for all affected locations

因為 memory_order_seq_cst 會維持所有執行緒的同步，考慮到效能，所以需要再理解其他的 memor order，例如接下來要探討的 memory_order_relaxed 、memory_order_release 和 memory_order_consume。

// Thread 1:
r1 = y.load(memory_order_relaxed);
x.store(r1, memory_order_relaxed);
// Thread 2:
r2 = x.load(memory_order_relaxed);
y.store(42, memory_order_relaxed);

Reference:
C++11 規格, page 1116

有沒有可能最後的結果是 r1 = r2 = 42？

因為 memory_order_relaxed 只是 atomic operaion 不是 synchronization operations

所以執行順序有可能是這樣

y.store(42, memory_order_relaxed);
r1 = y.load(memory_order_relaxed);
x.store(r1, memory_order_relaxed);
r2 = x.load(memory_order_relaxed);

Reference:
C++11 規格, page 1116

Boost.Atomic

Example about atomic
















  void push(const T &data)
  {
    node * n = new node;
    n->data = data;
    node * stale_head = head_.load(boost::memory_order_relaxed);
    do {
      n->next = stale_head;
    } while (!head_.compare_exchange_weak(stale_head, n, boost::memory_order_release));
  }
  ...
  node * pop_all_reverse(void)
  {
    return head_.exchange(0, boost::memory_order_consume);
  }
  private:
  boost::atomic<node *> head_;

第 5 、8 行的 load、compare_exchange_weak 就是 atomic operation，底下會再討論到這兩個 atomic operation，也會提到 3 個 memory order：memory_order_relaxed、memory_order_release 和 memory_order_consume。

Reference
Boost.Atomic, Usage examples

C++11, page 1124 對 compare_exchange_weak 是這麼說的
Implementations should ensure that weak compare-and-exchange operations do not consistently return false unless either the atomic object has value different from expected or there are concurrent modifications to the atomic object.

compare_exchange_weak 在 exchange 前會先作比較，比較結果不一樣才會 exchange，如果 exchange 就會 return true，否則 return false。
所以範例裡會有一個

while (!head_.compare_exchange_weak(stale_head, n, boost::memory_order_release));

在這個範例，我們用 memory_order_release 作為 atomic operation 的標記，底下將會探討 memory_order_release 還有與之成對的 memory_order_consume

memory_order_release v.s. memory_order_consume

Boost 是這麼說的

The use of memory_order_release after creating and initializing the object and memory_order_consume before dereferencing the object provides this guarantee.

再看看 C++11, page 1114 怎麼說

memory_order_release, memory_order_acq_rel, and memory_order_seq_cst:
a store operation performs a release operation on the affected memory location.
memory_order_consume:
a load operation performs a consume operation on the affected memorylocation

如果用 memory_order_acquire 來理解 memory_order_consume，會容易點，但是 memory_order_consume 不等於 memory_order_acquire

可以把 memory_order_consume 換成 memory_order_acquire，但不能把 memory_order_acquire 換成 memory_order_consume

透過 memory_order_release、memory_order_consume 建立了 happens-before 的關係

head_.compare_exchange_weak(stale_head, n, boost::memory_order_release));

head_.exchange(0, boost::memory_order_consume)

Boost.Atomic

Boost 實作了一個 Wait-free multi-producer queue
透過以上對 C++11、memory order 和 atomic operation 的了解，我們來欣賞一下 Boost 如何用 memory order 和 atomic operation 來實作出一個 Wait-free multi-producer queue。

producer–consumer problem
multi-producer and single consumer queue

multi-producer and single consumer queue

producer–consumer problem 基本上分這幾種

multi-producer and single consumer
single-producer and multi-consumer
multi-producer and multi-consumer
single producer and single consumer

由於 producer–consumer problem 不是這裡的重點，
所以只會講到所以只會講到 multi-producer and single consumer

multi-producer and single consumer queue

producer 會 push message 到 queue ，然後 consumer 會將 queue 裡的 message 取走

queue 是一個先進先出的 FIFO, First-In-First-Out 的資料結構，但是如果加了在多執行緒下有多個 producer 同時 push to queue，情況就有點複雜

digraph G{
rankdir = "LR";
   producer1 -> queue;
   producer2 -> queue;
   queue -> consumer
   queue[shape="quare"];
}

節錄自 Boost.Atomic, Usage example
















  void push(const T &data)
  {
    node * n = new node;
    n->data = data;
    node * stale_head = head_.load(boost::memory_order_relaxed);
    do {
      n->next = stale_head;
    } while (!head_.compare_exchange_weak(stale_head, n, boost::memory_order_release));
  }
  ...
  node * pop_all_reverse(void)
  {
    return head_.exchange(0, boost::memory_order_consume);
  }
  private:
  boost::atomic<node *> head_;

現在再看這個範例，是不是就可以不用靠 try and error 跟猜測了？

Reference
Boost.Atomic, Usage example, multi-producer queue

Reference

END

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

從 C++11 規格和 Template Meta-Programming 的角度欣賞 Boost 對 atomic 和 memory order 的支援 - 翁敏維

由於場地問題，第二天我們移動到另一棟大樓啦！議程教室變動請見網站上的議程表。

Agenda

Introduction

Why needs Template metaprogramming?

What is memory order?

reorder

out-of-order

in-order

out-of-order

How C++11 supports memory order？

從 C++11 規格來看 data races

Boost.Atomic

Example about atomic

Boost.Atomic

multi-producer and single consumer queue

multi-producer and single consumer queue

Reference

tags: `COSCUP2019` `帶您讀源碼` `IE2102`

tags: `C++11` `memory order` `TMP` `Template Meta-Programming` `Boost` `atomic` `Boost.Atomic` `1.66`

從 C++11 規格和 Template Meta-Programming 的角度欣賞 Boost 對 atomic 和 memory order 的支援 - 翁敏維

由於場地問題，第二天我們移動到另一棟大樓啦！議程教室變動請見網站上的議程表。

Agenda

Introduction

Why needs Template metaprogramming?

What is memory order?

reorder

out-of-order

in-order

out-of-order

How C++11 supports memory order？

從 C++11 規格來看 data races

Boost.Atomic

Example about atomic

Boost.Atomic

multi-producer and single consumer queue

multi-producer and single consumer queue

Reference

tags: COSCUP2019 帶您讀源碼 IE2102

tags: C++11 memory order TMP Template Meta-Programming Boost atomic Boost.Atomic 1.66

tags: `COSCUP2019` `帶您讀源碼` `IE2102`

tags: `C++11` `memory order` `TMP` `Template Meta-Programming` `Boost` `atomic` `Boost.Atomic` `1.66`