2012年9月19日 星期三

Software Transactional Memory

Software Transactional Memory

正在 survey STM,看了一下各語言的支援情形:
  • C#
  • 透過外掛修飾 class,讓這個 class 所有的 data member 都是 private,所有的 setter/getter 都是 virtual,看起來是要讓某個 class template 來 mock 那個 class,但是 setter/getter 是 atomic 的。可以作到 C++ 的 一樣的事情,但是沒有 transactional block 的能力。
    stackoverflow 上面有一篇討論,C# 沒有語言層面的支援,可以透過 library 來完成。
  • Java
  • 也是一樣,透過 library 完成。
  • Golang
  • 應該是沒打算提供 transactional memory,根據這篇討論,go 提供 message passing 作為取代。
  • C++
  • 有兩個 compiler 提供了 atomic block 的實作,一個是 Intel C++ compiler(真是太強了),另外一個是 g++(嘖嘖),大概最後還是選擇以類似 C++ 的形式為目標。

找到 gcc 的 transactional memory 的 spec,正在讀,作一點筆記。

__transaction_relaxed and __transaction_atomic

有兩個關鍵字:
  1. __transaction_relaxed
  2. 用來表示........ 其實我沒看懂。好,看到後面,懂了。這種 transaction 比較 weak,他只保證 transaction 「看起來」沒有跟別的 transaction 有交錯執行,但是,他還是可能跟別 thread 有交錯。舉例來說的話:
    Thread AThread B
    __transaction_relaxed {
        a = 1;
        b = a;
    }
    
    a = 3;
    
    這樣 Thread A 的 b 有可能會是 4。因為被另外一個 Thread B 的 a = 3; 亂入了。但是呢,如果寫:
    Thread AThread B
    __transaction_relaxed {
        a = 1;
        b = a;
    }
    
    __transaction_relaxed {
        a = 3;
    }
    
    那 b 就保證會是 1 了。因為 relaxed transaction 有保證這個 transaction 看起來不會跟別的 transaction 交錯執行。
    這邊一直強調「看起來」是很重要的,因為實際上,根據實作的細節(且為了效率的考量),執行的過程本身可能還是交錯並行的,只是透演算法的控制,讓執行的結果跟沒有交錯一樣,所以程式設計師就可以很直覺的認定這段程式碼的形為就如同一般 single thread 一樣。
    特性:
    • 其他的 transaction 無法觀察到 __transaction_relaxed 的 partial result
    • 其他的 thread 有可能觀察到 __transaction_relaxed 的 partial result
    • __transaction_relaxed 有可能觀察到其他 thread 的 partial result,有的時候你會想要等待某一個 std::atomic 變數變化來作事情,所以 relaxed transaction 有其必要性
    • 沒有限制 operation 的種類,什麼都可以放進去(如果我沒誤解的話,第 8 頁 45 行)
    • 無法 cancel,因為(見規格書第 9 頁第 16 行)容許有 side effect 的動作(比方說IO)而這些動作無法撤銷
    • Relaxed transaction 可以 nested 含有 relaxed transaction

  3. __transaction_atomic
  4. 用來表示(跟 __transaction_relaxed 比起來)更嚴格的的 transaction。這大概是我們要做的,但不確定前一種要不要作 :P
    這邊現在我也看懂了,也就是說,在 atomic transaction 之下,即使只寫
    Thread AThread B
    __transaction_relaxed {
        a = 1;
        b = a;
    }
    
    a = 3;
    
    我們也可以保證 b 百分之一是對的,會是 1。哇勒~!這種東西要怎麼作阿!!!
    特性:
    • 只有 "safe" code 可以放在裡面(等一下在 4.2 節說明)
    • 可以被 cancel
    • 不能有 side effect(比方說 IO)

transaction_safe

為了確保 transaction 是「可能」的,atomic block 裡面能寫的程式碼必須要加上一些限制,也就是 atomic block 裡面只能有 "safe" statements 。safe satements 所呼叫的 function 裡面,也只能含有 safe statements(這感覺很像 pure function ,一個 pure function 裡面只能呼叫 pure function)。
為了表明一個 function 是 safe function,需要在函數前面加上 attribute transaction_safe 修飾這個 function(safe 屬性在某些狀況下也有由 compiler 推導出來,見後續)。 transaction_unsafe 用來表明一個 function 不 safe,compiler 就可以阻止他被呼叫(比方說雖然現在這個 function safe,但是未來改版以後可能不 safe,我們知道他未來有不 safe 的可能性,所以我們希望現在就禁止他被使用)。
也可以直接修飾 class,這樣這個 class 所有的 member function 都會被修飾,然後每一個函數也可以各自修飾來 override safety。

__transaction_cancel

可以用 __transaction_cancel 放棄一個 transaction。__transaction_cancel 也可以跟 throw 一起使用,發出一個 cancel-and-throw,也會放棄 transaction。

outer

transaction 可以 nested,也可以用 outer 修飾來阻止被 nested-inside。另外 outer 也可以用來修飾 throw,讓最外圍的 transaction 被 cancle。只有被 outer 修飾的 transaction 可以被這樣 cancel(目前還沒看到為什麼這麼限制的原因,但應該有原因,後面可能會講到),且 function 也需要標上 transaction_may_cancel_outer 來修飾,不然不能發出 outer throw。
exception 被丟出 transaction,且不是使用 cancel-and-cancel 的話,transaction 有效!(這點跟 wiki 上面提到的不一樣,看樣子這個設計不是普世價值)

Safe and Unsafe

單位是 statement。safe statement 或是 unsafe statement。
只有 safe 的 function 可以被呼叫,這些 function 叫做 transaction-safe function,另外一類叫做 transaction-unsafe function。一個 function safe 不 safe 是型別的一部分,所有寫到這個函數的地方都必須一致,不能有的地方 safe 有的地方不 safe。
你可以用一個 unsafe 的 function pointer 指到一個 safe 的 function。但是不能用一個 safe 的 function pointer 指到一個 unsafe 的 function(有點類似 const 的觀念)。

Lambda 也有 safe/unsafe。

如果一個 statement 有以下任何一個特性,那他就是 unsafe:
  • 他是一個 relaxed transaction
  • 他是一個 outer atomic transaction
  • 初始化一個 volatile 或 assign to 一個 volatile 或 read from 一個 volatile 變數
  • 他是一個 unsafe asm,但是什麼 asm 是 unsafe 則是看 implementation dep
  • 呼叫一個函數,但是這個函數不是 transaction-safe 或是 may-cancel-outer(It contains a function call to a function not known to have a transaction-safe or may-cancel-outer function type)到底在講什麼...

一般的 function 宣告,如果你沒有特別指定,他 implicit 根據裡面有沒有含有 unsafe 的 statement 來決定自己 implicit 宣告成 safe 還是 unsafe。但是「直接呼叫自己」的 recursive 函數是 unsafe(應該是說 compiler 會偵測 directly recursive call,但是 indirectly call 就不管),但是你也可以 explicitly 指定 recursive funciton 是 safe。

template function 一樣也會自動推導則,但是,是具現化以後才推導,會看內含 statement safe 不 safe,如果有 unsafe 的 statement,那就 implicit unsafe,如果全部的 statement 都是 safe,那就 implicit safe。

Ctro 跟 Dtor,user defined 的當然就是作一般 (template) function,compiler generated 的,就看 base class 跟 non-static data member 的 Ctor/Dtor 是不是 safe。

Transaction Expression

SomeType myObj = __transaction_atomic ( expr );
SomeType myObj = __transaction_relaxed ( expr );

作用於 expression 求值的過程。也就這個求值的過程,會是 trasactional 的。

transaction expression 不能 nested。也不允許用 outer 修飾,也不能含有 transaction statement,也不能含有 cancel,也不能含有 cancel-and-throw,因為 C++ 不允許 expression 含有 statement。接下來還有一堆超饒舌的,先跳過,看了實在好想吐 orz 18 頁第 1 行。

Function Transaction Blocks

void f() __transaction_relaxed {
}
void f() __transaction_atomic {
}

意思就是這個 function body 內部的執行,會是 transactional。

如果這個 function 剛好是 Ctor/Dtor 的話,那個 base class 跟 member class 的初始化也都是 transactional 的。下面一個例子,比方說這個 class 的每個物件都有一個流水號,根據一個 global variable 來的。

class Foo {
    static size_t _count = 0;
    size_t _id;
    Foo() __transaction_atomic {
        _id = _count++;
    }
}

function transaction block 也可以跟 try block 混在一起。

try __transaction_atomic : Foo() {
}
catch (...) {} // catch 不是 transaction 的一部分
__transaction_atomic try : Foo() {
}
catch (...) {} // catch 是 transaction 的一部分

__transaction_cancel

可以用來放棄一個 transaction,只能寫在 atomic transaction 裡面。transactional expression 不能 cancel,function transactional block 也不能 cancel。

__transaction_cancel [[outer]];

outer cancel statement 只能寫在被標明為 transaction_may_cancel_outer 的 atomic transaction 或是 function block transaction 裡面。

幹……怎麼會這麼多……後面還有……好想哭……