Togetter/min.tを安心してお使い頂くためのガイドラインを公開しました。
2011年3月25日

真夜中のSTMトーク

某ピーFIさんの白熱したお話が聞けました。
25
kumagi @kumagi_bot

原始的なSTMのおはなし。STMは複数の箇所の書き換えをatomicに行えるが一体どうやってるのか、今の段階でうろ覚えしながら書きます。

2011-03-25 01:11:36
kumagi @kumagi_bot

CASは1wordしか書き換えれないのになんでアトミックに複数箇所を書き換えれるのか、平たく言うとそれはオブジェクトそのものをCASで書き換えるのではなく、各スレッドの状態をCASで書き換えるから。

2011-03-25 01:13:33
kumagi @kumagi_bot

どのようにしてそのような面妖な仕組みを生み出したかというとこれまたコンピュータ界の格言である「間接参照はすべての問題を解決するそのものであり、STMにはその間接参照という魔法が2つもかけられている。

2011-03-25 01:14:41
kumagi @kumagi_bot

一つのオブジェクトに対して「古いオブジェクト」「新しいオブジェクト」「持ち主が誰なのか」を保存しており、少なく見積もっても2倍のメモリを消費する。

2011-03-25 01:17:29
kumagi @kumagi_bot

持ち主の状態は3通りあり「放置(commit)」「作業中だから触れるな(run?)」「不貞寝(abort)」のどれかの状態である。値を読み出すときは、commitなら「新しい値」run,abortなら「古い値」を対外的には読み出させる。

2011-03-25 01:20:32
kumagi @kumagi_bot

commitする前には「書き換えたい全部のデータの所有者が自分」になっており、全部のデータは「新しいほうが自分の書き換えたいデータ、古いほうがもとのデータ」になっており、その状態から自スレッドの状態を run → commitにcasすることで複数箇所の見かけの情報が一息で変化。

2011-03-25 01:24:05
kumagi @kumagi_bot

ここまでの説明で、腕っ節のある人なら実装はできるだろうけれど、このSTMがなんで原始的かというと、2回の間接参照というコストがあまりにも高いから。最近のSTMはロックベースであることは有名だけど、問題の本質はロックベースになった事ではなくて、間接参照を減らした事が一番の変化。

2011-03-25 01:29:34
kumagi @kumagi_bot

STMの進化は僕の視点だと「間接参照という万能の錬金術をいかに薄めて目的を達成するか」に心血を注ぐ物であるので、間接参照の塊のような言語は簡潔に書けることを認めながらも、今ひとつ好きになれない。

2011-03-25 01:30:45
kumagi @kumagi_bot

自分が特定のデータを書き換えようと思った際にそのデータを他のスレッドがrunのまま保持していた場合、トランザクションマネージャという神に信託を委ねる。トランザクションマネージャの実装は思想や研究に応じて様々なものが考えられるが、極端な話だと乱数でもトランザクションの性質は満たす。

2011-03-25 01:33:09
kumagi @kumagi_bot

あ、read→readとwrite→readとでトランザクション中のデータの扱いは変わるんだった。今までの話は正確じゃないかも。基本的な考えはともかくとして。

2011-03-25 01:34:27
kumagi @kumagi_bot

STMのおはなしおしまい。反響があったら次はもうちょっとだけ近代的な物について調べてみようかと思います。

2011-03-25 01:37:32
SKS/ファントムの申し子 @repeatedly

STMはとりあえず分かりやすい実装をですね(ry

2011-03-25 01:39:24
kumagi @kumagi_bot

STMの分かりやすい実装なぞ存在しない(キリッ

2011-03-25 01:40:33
kumagi @kumagi_bot

あ、トランザクションマネージャが走るとどちらかのスレッドの状態がabortedになるので、該当スレッドがrun→commitのCASを発行した時に失敗を検知して初めからやり直すことになる。各スレッドの状態変数はスレッド自身とトランザクションマネージャの2つが触りにくるのでCAS。

2011-03-25 01:40:07
kumagi @kumagi_bot

STMはもう新手のデータ構造だと思ったほうがいい。しかも世代が変わるごとにbinary treeとhash mapぐらい実装の方針が大きく変わる。間接参照を削ろうとしてるんだから当たり前ではある。

2011-03-25 01:42:01
SKS/ファントムの申し子 @repeatedly

これがよく分からない.古いオブジェクトと新しいオブジェクトはどこに保存していて,フィールドとかはどうなってるのん? > 一つのオブジェクトに対して「古いオブジェクト」「新しいオブジェクト」「持ち主が誰なのか」を保存しており

2011-03-25 01:44:42
kumagi @kumagi_bot

@repeatedly それぞれのオブジェクトはヒープの中に保存されてます。あるトランザクションが、他のスレッドによりcommitされた情報にアクセスする際には、「新しいオブジェクト」の所の物を「古いオブジェクト」の方から指すよう継ぎ換えた上で「新しいオブジェクト」の上で作業。

2011-03-25 01:50:06
SKS/ファントムの申し子 @repeatedly

STMって何行くらいで書けるか.1万はいらんよなぁ.トランザクションマネージャとトランザクションコンテキストがメインか…

2011-03-25 01:48:21
kumagi @kumagi_bot

でもピーFIの人ならSTMの実装とか常識過ぎるとか言い出しそうな気配がある。

2011-03-25 01:45:42
Nobuyuki Kubota @nobu_k

@kumagi_bot そんなわけあるかあああああああああああ

2011-03-25 01:48:36
Hideyuki Tanaka @tanakh

Haskellを用いてD言語を実装すればSTM簡単に実装できるんではないか?

2011-03-25 01:51:35
Nobuyuki Kubota @nobu_k

Transactional Information Systemsェ・・・。頑張って読みたい!

2011-03-25 01:54:28
残りを読む(68)

コメント

Kenji Yoshida @xuwei_k 2011年3月27日
#scala のSTMの話がでてこない(・_・`)Haskellとかclojureとはどう違うんだろ・・・
0