從 C++11 規格和 Template Meta-Programming 的角度欣賞 Boost 對 atomic 和 memory order 的支援
為什麼要看 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 ,是一種比較有效率的學習路線。
先澄清一件事,
不是直接用 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 不會讓執行時間縮短,而是因為剛剛的測試範例只是直接把 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;
}
這段看起來,我們可能會這麼覺得:
剛剛我們示範了一個讓人用 覺得 來判斷的 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 的計算方式一樣
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 作一些控制。
我們從 instruction pipelining 來理解 out-of-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。
但如果是 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 是不是也有可能不一樣?
實際執行順序是允許和 sequenced-before 不一樣,但 C++11 支援不同的 memory order,可以控制實際執行順序
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 這種關係
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
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.
while (!head_.compare_exchange_weak(stale_head, n, boost::memory_order_release));
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)
producer–consumer problem 基本上分這幾種
由於 producer–consumer problem 不是這裡的重點,
所以只會講到所以只會講到 multi-producer and single consumer
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 跟猜測了?
END
COSCUP 2019
C++11
memory order
TMP
Template Meta-Programming
Boost
atomic
Boost.Atomic
1.66