ワールドエンドエコノミカ一巻読了。中盤までつらすぎた。なんというか、読みづらいというか、それ要らないよね、的な表現が多かった気が。ノベルゲー原作だからか。狼は気にならなかった気がするけど、昔々の記憶だからなあ。最後は、盛り上がったけど、そこそこ予想通り。ただ、終わり方が予想外だった（落ちをつけるかと思ったのに）。
IIJ mio の音声 SIM が届いたので、iPhone SE のセットアップ。
13時ごろ、MNP の手続きを追えたんだけど、22時現在、まだ手続きが終了していないっぽい...。
と思って softbank 携帯で電話したら、つながらなかった（圏外になった）ので、おわったっぽいが、なぜ IIJ mio のほうは圏外のままなのか。
IIJ mio のサイトからプロファイルをダウンロードして、無署名の警告をものともせずにインストールし、再起動したら docomo 回線を拾ってくれた。
Pony で Actor の GC がどうのってのがあって、ぴんとこなかったんだけど、やっとわかった。
Elixir（多分 Erlang も）の場合、こんな感じで、誰からも参照されない Process を沢山作って、永遠に待つような例が書ける。誰も参照していないので、その Process にメッセージが届くことはない。
defmodule Test do
def waiter n do
IO.puts(n)
receive do
# infinite loop
end
end
def make 0 do
end
def make n do
spawn(Test, :waiter, [n])
make(n-1)
end
end
Test.make(100_000)
receive do
# wait ...
end
この場合、何が起こるかと言うと、生成した実行中のプロセスが永遠に待つことになる。なるほどなぁ。
Pony の場合、receive 相当が言語組込みなので、この問題は起きず、誰も参照していない、待ちの Actor はガシガシ消せる、ということなのか。
昔、八杉先生から become があるから Actor なんだよ、と教えて貰って、なんとなく想像していたことが、原論文を読むとさっくりわかって、やっぱりちゃんと読まないとなぁ、などと。
Erlang は、なぜああいう receive を陽に書くデザインにしたんだろうな。 というか、最近 Actor って言ってるやつって、みんな receive してない？
Akka の場合は、receive 関数を定義するから、それが become 相当ってことか。
sinatra の do_GET みたいなものかな。
Guild で Actor を標準で備えるぜー、と思ってたけど、どうやらそれじゃ駄目だな。
package main
import "fmt"
import "time"
func waiter(n int, ch chan int) {
// fmt.Println(n)
var i = <- ch // wait forever
fmt.Println(i) // unreachable
}
func invoker(max int) {
var i = 0
for ; i<max; i++ {
var ch = make(chan int)
go waiter(i, ch)
// forget ch, so that nobody can send message via this channel.
}
}
func main() {
invoker(100000)
time.Sleep(10 * time.Second)
}
golang を久々に書いた。何もわからないので、まずはインストールの方法をぐぐるところからだった...。
で、結論からいうと、多分やはり goroutine は残る。
最初、main goroutine を、<- ch で待とうとすると、すべての goroutine が待ちに入るからだと思うから、デッドロックだと検出されたので、お、やるな、と思ったんだけど、別に GC されるというわけでもないようだ。
って、待てよ、GC が起きていないだけ、という気もするな ... と思ったけど、100000 個作ったら、さすがに何個かは消えるよな。一応、ゴミを作って確かめよう。
package main
import "fmt"
import "time"
func waiter(n int, ch chan int) {
// fmt.Println(n)
var i = <- ch // wait forever
fmt.Println(i) // unreachable
}
func invoker(max int) {
var i = 0
for ; i<max; i++ {
var ch = make(chan int)
go waiter(i, ch)
// forget ch, so that nobody can send message via this channel.
}
}
func main() {
invoker(100000)
var i = 0
var s = "foo"
for ; i<28; i++ {
s = s + s // 2^28
}
time.Sleep(10 * time.Second)
}
メモリ消費量を見ると、消えてないっぽい。main が終わるとプロセスは終了する。
しかし、time.Sleep(3 * time.Second) って冗長だけどわかりやすいな。time.Sleep(3.second) って Ruby だと書かせたくなるのかな。Elixir だと、そこはマクロにするんだろうな。駄目だ、複雑だ。
さて、Guild はどうするべきか。つまり、状態は 4 つある。
今の Thread は、走っていれば GC されない（root になる）ので、(4) 以外は GC されない。
(2) は I/O 待ちか何か、やるべき仕事で停まっている。(3) はやるべき仕事を待っているが、誰もそこに仕事を投げないので GC されうる。
(3) で停まっているとき、つまり channel 待ちの時、その channel への参照が GC されたら（つまり、自 Guild 以外、その channel を持たないのであれば）、その channel で待つと例外、とすればいいのかな。
自 Guild で channel 経由した通信はできなくなるけど（ch <- 1; var v = <- ch みたいな）、まぁ、そこは無理してサポートしなくても良いよね。Thread 使うなら、Queue を使ってくれ。
しかし、dynamic reconfiguration のための become ってのが、イマイチピンと来ない。ネットワークレイアウトが決まっているから、ということだが、物理的なそこと、どうつながるのか。
Erlang は Actor model を指向したものではなく、少なくとも開発時には知らなかった、ということを教えてもらった
actor model の要件がイマイチわからないし、理論的には同一のものだよね、と言えるのかもしれない。が、イマイチ自信がない。無限に待つような receive を書くことが出来るが（そして、それで無限に待てるけど）、それは actor model では許容されてるんだろうか。デッドロックだよなぁ。
上記で考えたとおり、回避することは出来るので、単に実装の問題、と言えるような気もするけれど。
もう全然駄目だ。ご迷惑をおかけして本当に済みません。
ちょっと本当に久々に文献を調べてたんだけど、ちゃんと actor model とは何かを調べたくて Concurrent programming using actors を読んでたんだけど、色々新しい発見というか receive って無いんだね、知らなかった。
で、2.2 Basci Constructs に
The mail system system buffers the communication until it can be delivered to the target. The buffering of communication until it can be delivered to the target. However, the order in which the communications are delivered is non deterministic. The buffering of communications has the consequence that actor languages support recursion. In languages relying on synchronous communication, any recursive procedure immediately leads to deadlock [Hewitt, et al 1984] [Agha 1985].
この意味がわからない...。何で consequence なの？ mail system によって、async になったから、recursive 許すぜ、ってことかな？ しかし、なんで sync + recursive でデッドロックするんだろ。Actor が無限ループすると（受け取らないと）、送り側が詰まるからデッドロックするぜ、ってことか。
become するまで次のメッセージを受け取らない => synchronous だと become 前の自分にメッセージが届いたとき受け取れないから死ぬ？
(文脈を知らずに推測で書きますが)1アクターは1スレッド、同期メッセージ送信は返事が来るまでブロックする、ブロック中のアクターはメッセージの受信もできない、従って自分自身へのメッセージ送信はデッドロックする、ということだと思います。
recursive procedure というのが、自分自身へのメッセージの送信という意味でしたか（単に関数の recursive call だと思っていた）。
IDCF クラウドを vagrant から使おうとしたら、はまった話。
ふつーに VM 作ったら ssh で入れるのに、vagrant-cloudstack 経由で作ると ssh が通らない。なぜか。
結論からいうと、デフォルトで設定される host 名が長すぎるので、dpkg-reconfigure openssh-server で起動される ssh-keygen -A で、"gethostname: file name too long" というエラーが出て、sshd の設定がうまいこと出来ていなかった。
解決策としては、cloudstack.name という設定を、てきとうに短い名前で加えてやれば OK。
なお、Vagrantでクラウド上にDocker環境を作る（IDCFクラウドの場合） を参考に、Docker じゃなくて、普通の VM を作る場合。
とにかく console で見てみないとわからないのだが、多分 VNC を html で無理矢理表示しているからか、遅いし、すぐに無反応になるし、でつらかった。
しかし、vagrant up すると、rsync しようとするのはどこで切れるのかな。要らないんだけど。
あと、これ coreos で動くのかな...。
cloudstack.template_name = "CoreOS (stable) 494.4.0 64-bit"
これで動いた。
override.ssh.username = "core"
これが root のままで、通らなくて悩んだ。こういう、なんというかつらい知識はなんというんだろうな。バッドノウハウじゃないしな。
作ろうとしているのものは、簡単にすればいいや、と思って YAML::Store でいいかと思ってたんだけど（性能要らないし）、なんというか、やっぱり RDB 使った方がいいかな、という気分になってきており、そうすると、やはり Heroku が楽でいいよな、ってことになってしまう。
一度使った cloudstack.name を使おうとすると、
The vm with hostName ... already exists in the network domain: ...
てな感じで怒られてしまう。が、ある程度時間をおくと、大丈夫みたいなんだけど、どの程度の時間でいいんかなあ。
しかし、毎度のことだけど、windows でやってると、cygwin の ssh と putty とで色々混ざってやりづらい。このパス名は、cygwin と Windows の、どっちだっけ、とか。
ReCore 、いつのまにか終盤なんだけど、急に難易度あがってない？ 瞬殺されてばかり。死んだ後の復帰に時間がかかるのもストレス。まぁ、しょうがないんだろうなぁ、というのもわかる。
あと、各地のダンジョン、あれ時間内にクリアするの無理だろ。
結婚記念日だったので、近所のイタリアンのお店。大変美味しかった。
しかし、この辺イタリアン多すぎ。
recore、初見殺しが多すぎ。でも楽しい。明らかなバグがいくつか確認できたんだが、update はあるんだろうか。報告した方がいいのかな。
ReCore をするためには、Windows 10 Anniversary version というものにアップグレードしないといけないと出るので、しょうがないからアップグレード。が、何度やっても（何時間かけて、ダウンロードして、アップグレードして）、途中で止る。3回くらい繰り返して、つらくなってドライバ沢山削除したりとかしたが、直らない。
で、色々探してたら http://ch.nicovideo.jp/lunaorbit/blomaga/ar1086073 にある Logicool の Unfy レシーバというものが問題だったらしい。諸々消したり、外したりして、無事アップグレード完了。
さすがにわからなかった...。この記事を書いて下さった方、ありがとうございます。
近所に宮川さんがいらっしゃったらしく、夕飯をちょっとご一緒させて頂いた。
Rebuild: 158: Kill All The Threads (ko1, Matz)
怖いタイトルですが、収録頂いたものを公開して頂きました。
色々言い足りなかったなぁ、と思うことが多いので、どっかで喋りたい。なんか良い機会はないですかね。
Rob pike の話は、昔読んだ気がしたんだけどなぁ。
なお、収録中で使った言葉は、多分「Thread が居るぞ、殺せ！」です。
色々と教えて頂く。 ありがたいことです。
PS3 のゲームアーカイブ（でいいのかな）でクロノクロスがあるそうなので、プレイしてみる。解像度が凄い。昔はこれで良かったんだな。4K ディスプレイ（43インチ）だと、つらすぎる。
ReCore という Windows 10 でプレイできるゲームをやろうとしたら、OS をUpgrade しないといけないってことらしいんだけど、それに10時間くらいかかる（まだやってる）。
そういえば、Guild の前の、ownership のアイデアが駄目だったって理由をちゃんと言っていなかった気がするんですが、結構めんどくさい例で駄目だったので、説明が難しい。
Balmuda の扇風機、首がゴロっともげてしまったので修理に出す。つらい。ちょうど、保証期間が切れる頃だったみたい。でも、そもそもレシート見つからなかった。
今日も朝から。
podcast 2 本。rebuild 特別編と、Heroku のを収録して頂いた。どちらも、添え物的な感じで。
打ち上げも参加したけど、なんというか煙草がつらかった。
もうちょっと、のんびり飲みに行ければ良かったんだけど。
今日も朝から、スタッフの奥さんを送迎（着いてっただけ）。
keynote よくわからなかったなぁ（聞いてなかったとも）。
つらかった。
持っていった Elixir 本、全部売れて良かった。
今日の発表 A proposal of new concurrency model for Ruby 3 の資料です。
そこそこ反響があって良かった。あと、マーケの威力も。
並行Ruby会議が別室であって、色々議論していた。
懇親会後、奥さんとご飯を別途食べに。
そういえば、Guild という名前ですが、次のような理由から決めました。
まつもとさんから Verse（multi-verse としたかったらしい）を提案されたが、verse gem というのがあり、断念。
鳥井さんから、糸の集合として Tassel という名前を提案されて、途中までそれで考えてたんだけど、T が被るから断念。
実は、Guild の前に、Government というのを考えていたんだけど（これも、gem で被ってなかった！）、さすがにあんまりかなぁ、と思って、Guild になった。
個人的には、Guild は短いし、オブジェクトを何かに所属させたかったし、G1、G2 って書けるし良いなぁ、と思い始めています。
当初、ownership と言ってたんだけど、Guild なので membership という言葉に変えました。
Racket に Place って機能があって、だいぶこれに近いんですが、でも、どちらかというと MVM そのまんまで。もっとアグレッシブに共有するやつが欲しくて、Guild にしました。
共有の具合でいうと、疎な順に、
という感じ。
Ruby開発者会議。map_v が無くなって良かった。
美味しい夕飯だった。明日発表なので、美味しいお酒飲み放題だったのに、あまり飲めなくて残念であった。
下記は、RubyKaigi 2016 で発表する予定の「A proposal of new concurrency model for Ruby 3」の内容です。書き殴りなので、誤字脱字などはご容赦下さい。
私の発表の、予習用の予稿とでも捉えて頂ければ。
これ絶対 40 min で間に合わないので、大鉈を振るわないといけないですね...。どこかで長時間で発表できるといいんだけど。
本稿では、Ruby 3 で採用されたらいいな、という並行・並列処理機構である Guild という、新しいモデルについて提案します。
プログラミング言語は進化してきました。 とくに Ruby は、「プログラムを簡単にする」という方向に進化しています。
たとえ話を2つします。私が C 言語をよく使っているので、C 言語でのプログラミングの話をします。
C 言語でプログラムを書いていた頃、文字列はポインタを使って操作するものでした。 ポインタを使えば、基本的になんでも出来るし、高速なコードを書くことができます。 しかし、ポインタを使う操作は扱いが難しく、少し間違えると、変な結果になってしまったり、 プログラムが異常終了してしまうこともあります。
Rubyでは、文字列を文字列オブジェクトのメソッドを用いて処理を行ないます。 ポインタを用いないでも、文字列操作を行なうプログラムを比較的簡単に作ることができます。 少なくとも、ミスによって、プログラムが異常終了することはありません。 ただし、ポインタを直接使えば、高速なプログラムが書けるような場合でも、ポインタを扱うことができません。 つまり、少しの性能低下と、簡単で安全なプログラミングのトレードオフがあり、Ruby は後者を選んでいるのです。
C 言語では、GC がないので、メモリの解放を自分で適切に行なわなければなりません。 解放してはならないオブジェクトを解放してしまったり、解放しなければならないオブジェクトを解放せずにリークをさせてしまったり、といった具合です。
Ruby には GC があるので、オブジェクトの解放について悩む必要はほとんどありません。 GC が、不要になったタイミングで、オブジェクトを解放してくれるからです。 少なくとも、解放してはいけないタイミングでオブジェクトを解放してしまうことはありません （もしあれば、それは処理系のバグなので、報告して下さい）。 ただし、GC による自動的なメモリ管理は、タイミングを細かく制御することはできず、 またいくらかのオーバーヘッドを生じることになります （世代別 GC によって、それはだいぶ小さくなったと思います）。 つまり、少しの融通のきかなさ、性能低下と、簡単で安全なプログラミングのトレードオフがあり、 そしてこれについても、 Ruby は後者を選んでいます。
最近登場してきているプログラミング言語の多くは、 文字列操作のためにポインタを直接操作できないようにしているし、GC を最初から搭載しています。 つまり、多少の効率よりも、簡単で安全なプログラミングを重視している、と言えると思います。 理由は、すでに多くの場所で語られているように、 コンピューターの計算能力が十分に高くなったこと、 効率が本当に必要になるようなケースは十分に少ないこと、 それから、そのような非効率性を言語処理系の実装技術によって抑える技術が発達してきたこと、 などがあげられます。 要するに、難しいことはコンピューターに任せて、プログラマは楽をする、というのが最近のトレンドになっていると思います。 私も同意しますし、Ruby はまさに、そういう目的のために作られたプログラミング言語です。
さて、話を並行、並列プログラミングに戻します。
並行、並列プログラミングは根本的に難しいです。 正しく設計するためには色々なことを知っておかなければなりません。 よく知られている、並行プログラミングに起因する問題には、次のようなものがあります。
さらに、正しく動作するプログラムを作っても、並列実行における性能チューニングが難しい、と言った問題もありますが、まずはバグのないプログラムを作る、という観点から話を進めていこうと思います。
一度に多くのことを議論するのは大変なので、この発表では並行プログラミングにおける競合状態の回避について議論していきたいと思います。
Race Condition vs. Data Race http://blog.regehr.org/archives/490 というブログ記事から例を引用します。 （例は Ruby に書き直しています）
def transfer1 (amount, account_from, account_to) if (account_from.balance < amount) return NOPE account_to.balance += amount account_from.balance -= amount return YEP end
このプログラムは、ある銀行口座の
このプログラムはレースコンディションがあるため、複数のスレッドで実行すると、おかしなことになります。 どうおかしいかを少し説明します。
まずは、この足し算の部分です。
account_to.balance += amount
この行は、二つの操作にわけられます。
t = account_to.balance account_to.balance = t + amount
このプログラムが、2つのスレッド T1、T2 で実行されるとどうなるでしょうか。 amount が T1 は 100、T2 は 200 で実行していたとします。 例えば、このような実行になる場合があります。
T1: t1 = account_to.balance # t1 = 10 T2: t2 = account_to.balance # t2 = 10 T1: account_to.balance = t1 + amount # t1 + 100 #=> 110 T2: account_to.balance = t2 + amount # t2 + 200 #=> 210
account_to.balance の値は、この結果、210 になりました。 おそらく、最終的には 310 になって欲しかったんじゃないかと思います。 この問題を、data race 言います。 正しい結果にするためには、ここで適切な同期をしなければなりません。
また、 += の操作がアトミックであったとします。 わかりやすくするために、Thread.exclusive を使って、このブロックは、ただ一つのスレッドしか動作しないようにしておきます。
def transfer2 (amount, account_from, account_to)
if (account_from.balance < amount) return NOPE
Thread.exclusive{ account_to.balance += amount }
Thread.exclusive{ account_from.balance -= amount }
return YEP
end
こうすれば問題は解決するでしょうか。しません。同じように、T1 が amount = 100、T2 が amount = 200 で動作するとき、どうなるか考えてみます。
def transfer2 (amount, account_from, account_to) if (account_from.balance < amount) return NOPE Thread.exclusive{ account_to.balance += amount } Thread.exclusive{ account_from.balance -= amount } return YEP end
T1: if (account_from.balance (== 250) < 100) return NOPE # OK, go thorough
T2: if (account_from.balance (== 250) < 200) return NOPE
T2: Thread.exclusive{ account_to.balance += 200 }
T2: Thread.exclusive{ account_from.balance -= 200 } #=> 250-200 => 50
T1: Thread.exclusive{ account_to.balance += 100 }
T1: Thread.exclusive{ account_from.balance -= 100 } #=> 50 - 100 => negative number!!
この例では account_from.balance が amount よりも大きい、という invariant （不変条件）を壊しています。 これが、race condition になります。
最終的には、このプログラムは、メソッド全体を同期することで解決することができます。
def transfer3 (amount, account_from, account_to)
Thread.exclusive{
if (account_from.balance < amount) return NOPE
account_to.balance += amount
account_from.balance -= amount
return YEP
}
end
古典的な銀行口座の例でしたが、いくつかの問題があることがわかりました。
もう一つの例を紹介します。
ary = [1, 2, 3]
t1 = Thread.new{
ary.concat [4, 5, 6]
}
t2 = Thread.new{
p ary
}.join
ある配列に、別のスレッドが concat した結果を、別のスレッドが見たらどうなるか、という問題です。 このプログラムは、どのような結果を生じるでしょうか。
答えは、(4) 処理系依存、です。
MRI の場合は、(3) の [1, 2, 3] か [1, 2, 3, 4, 5, 6] のどちらか、になります。 どちらのスレッドが先に走ったか、で結果が変わるというものです。
次に、JRuby の場合を考えてみます。 先ほどのプログラムでは、あまり問題が顕在化しづらいのですが、 沢山のスレッドが、多くの操作を行なうように、次のように書き換えてみます。
h = Hash.new(0)
NA = 1_000
10_000.times{
ary = []
(1..10).each{
Thread.new{
NA.times{|i|
ary.concat [i]
}
}
}
obj = nil
s = 0
t2 = Thread.new{
s = ary.dup
}.join
h[s.inspect] += 1
}
pp h
8 hardware thread のマシンで動かすと、次のような例外が出ました（jruby 9.1.2.0 (2.3.0) 2016-05-26 7357c8f OpenJDK 64-Bit Server VM 24.95-b01 on 1.7.0_101-b00 +jit [linux-x86_64]）。
Unhandled Java exception: java.lang.NullPointerException
java.lang.NullPointerException: null
rbInspect at org/jruby/RubyBasicObject.java:1105
inspect at org/jruby/RubyObject.java:516
inspectAry at org/jruby/RubyArray.java:1469
inspect at org/jruby/RubyArray.java:1497
cacheAndCall at org/jruby/runtime/callsite/CachingCallSite.java:293
call at org/jruby/runtime/callsite/CachingCallSite.java:131
block in t.rb at t.rb:17
yieldDirect at org/jruby/runtime/CompiledIRBlockBody.java:156
yieldSpecific at org/jruby/runtime/IRBlockBody.java:73
yieldSpecific at org/jruby/runtime/Block.java:136
times at org/jruby/RubyFixnum.java:291
cacheAndCall at org/jruby/runtime/callsite/CachingCallSite.java:303
callBlock at org/jruby/runtime/callsite/CachingCallSite.java:141
call at org/jruby/runtime/callsite/CachingCallSite.java:145
<top> at t.rb:3
invokeWithArguments at java/lang/invoke/MethodHandle.java:599
load at org/jruby/ir/Compiler.java:111
runScript at org/jruby/Ruby.java:833
runScript at org/jruby/Ruby.java:825
runNormally at org/jruby/Ruby.java:760
runFromMain at org/jruby/Ruby.java:579
doRunFromMain at org/jruby/Main.java:425
internalRun at org/jruby/Main.java:313
run at org/jruby/Main.java:242
main at org/jruby/Main.java:204
この例外は、Java の例外で、つまり JRuby の下側で発生している問題です。 なぜこのようなことが起こるかと言うと、Array#concat および Array#dup がスレッドセーフではないからです。 スレッドセーフではない操作をスレッド間で同時に行なうと、すでに見たとおり、data race や race condtion がおき、このような問題が起こります。
これを防ぐためには、共有している Array オブジェクトに Mutex などを利用して同期する必要があります。
NA = 1_000
m = Mutex.new
10_000.times{
ary = []
(1..10).each{
Thread.new{
NA.times{|i|
m.synchronize{
ary.concat [i]
}
}
}
}
obj = nil
s = 0
t2 = Thread.new{
s = m.synchronize{ ary.dup }
}.join
}
このようにすると、ちゃんと動きます。 つまり、マルチスレッドプログラミングは、どのデータがスレッド間で共有されているか、そして、どのタイミングで排他制御などの同期を行なえばよいか、適切に判断する必要があります。 今回の例は、短いプログラムでしたので、どこで同期をすれば良いかは比較的自明ですが、大きなプログラム、フレームワークを使ったプログラム、 gem ライブラリを使ったプログラムでは、どこでどのような操作を行なうのか、完全に把握するのは困難です。 とくに、他人の作ったプログラムをマルチスレッドで利用する場合、そのプログラムでどのような操作を行なうか、すべてチェックしないといけないということになります。 これは、現実的には不可能なので、ドキュメントなどで、「このメソッドは thread-safe である」といった記述をすべてしていく必要があるでしょう。 そのためには、ドキュメントを適切にメンテナンスする必要があります。つまり、バージョンアップなどで thread-safe ではなくなったのに、thread-safe と書いてあったらまずいわけです。
もし、同期を忘れてしまったら、先ほど JRuby の例で出したとおり、意図しない（おそらく、先ほどの結果は意図したものではないでしょう）ことが起こります。もちろん、それはバグです。 さらに悪いことに、このようなバグはテスト中に見つけることができるとは限りません。小さなデータセットを対象にしていると出てこないので、気づかずに本番運用時に時々出現する、といった具合です。 そしてさらにさらに悪いことに、この種のバグは再現が大変難しく、デバッグは困難です。
なお、先ほど紹介したとおり、MRI では Array#concat などは thread-safe になっています。 それは、GVL（Giant/Global VM Lock）によって、Array#concat などを実行中はスレッドを切り替えないようにしているためです。 なので、そこそこ MRI ではスレッドによる並行プログラミングは楽になっているはずです。 その代わりに、各スレッドは同時に実行しない、つまり並列に実行はしません。
同期を使うと、他にも問題があります。性能の問題です。
並列実行により、スレッドが同時に走る JRuby で少し試してみます。
t1 = Thread.new{
NA.times{|i|
a1 << i
}
}.join
t2 = Thread.new{
NA.times{|i|
a2 << i
}
}.join
real 0m8.568s
user 0m37.816s
sys 0m5.530s
このプログラムは、2つの独立した配列を、それぞれ別のスレッドで操作しています。 ただし、各スレッドは join しているので、逐次実行と同じです。約 8 秒かかっていますね。
a1 = []
a2 = []
NA = 10_000_000
t1 = Thread.new{
NA.times{|i|
a1 << i
}
}#.join
t2 = Thread.new{
NA.times{|i|
a2 << i
}
}#.join
t1.join; t2.join
real 0m6.411s
user 0m20.527s
sys 0m7.798s
では、join を後ろに回して、各スレッドを並列に実行してみると、約6秒になりました。ちゃんと並列実行によって速くなっていますね。
次に、本当は不要ですが、Mutex を利用して同期するプログラムを実行してみます。
a1 = []
a2 = []
NA = 10_000_000
m = Mutex.new
t1 = Thread.new{
NA.times{|i|
m.synchronize{ a1 << i }
}
}
t2 = Thread.new{
NA.times{|i|
m.synchronize{ a2 << i }
}
}
t1.join; t2.join
real 0m15.163s
user 0m45.317s
sys 0m9.658s
約15秒と、逐次実行を行なうよりも遅くなってしまいました。 つまり、同期を行なうにはオーバヘッドがかかるという意味です。 この例では、本当は不要なロックですが、例えばライブラリを書いていれば、保守的にロックをしたい、という話は考えられるでしょう。 つまり、同期が必要な数より少なければバグになり、多すぎれば性能低下の原因になります。 「適切に」同期するのが難しい、という理由がわかって頂けたと思います。
なお、同期する方法にも色々研究が進んでいます。
しかし、それぞれ適切な使い方をしなければバグになる、といったことは同じです。とくに、アトミック命令を用いた方法は、利用が難しいと思います。
同期を用いたスレッドプログラミングは難しい、という話をしました。これに対して、別の解決策をとるプログラミング言語がいくつかあります。 その方法を一言でいうと、変更を行なうデータを共有しない、というものです。 （なお、これ以外にも型による解決というのもありますが、Ruby には型がないので除外します）
シェルスクリプトというか、Unix のコマンドをパイプでつなげれば、並列、並行に各コマンドを実行することができます。 例えば、grep ... | wc とすれば、grep と wc コマンドは並列、並行に実行します。 このとき、データを渡す時は、コピーが渡されます。つまり、同時にあるデータに書き込んだりすることはない、ということです。 データの共有は、基本的にはコピーなので、時間がかかるというデメリットがあります。
Erlang/Elixir は同時に書き込みを行なわない、ということを徹底するために、すべてのデータは読み込み専用で、書き込むことができないようになっています。 （あ、Elixir についてご存じなければ、いい本がありますよ https://www.amazon.co.jp/gp/product/4274219151 ） この読み込み専用のデータを不変データ（immutable data）と言います。 すべてのデータが書き込み禁止であれば、データを各スレッド（Erlang/Elixir ではプロセスと言います）間で共有することは、何も問題ありませんし、 一貫性を保証するための排他制御も必要ありません。
Scala はよく知らないので言いませんが、Clojure は、基本的にはデータを読み込み専用にします。 各スレッドが同時に読み書きするデータについては、特別な方法を用意しており、その方法を用いなければアクセスできないようになっています。 そして、その方法を用いれば、問題無く読み書きできるように設計されています（厳密には、race condition の問題は残りますので、やはり難しいのですが）。 ただし、Scala と Clojure は Java VM の上で動作しており、Java のプログラムに簡単にアクセスできます。 Java のプログラムは、スレッドセーフでなくてはならず、この点にはこれまで通りの注意が必要になります。
まとめると、排他制御などの同期を不要にする並列・並行プログラミングでは、次のような方法が考えられ、それぞれにメリットデメリットがあります。
さて、ここまでが前提です。お疲れ様でした。
Ruby 3 の並行・並列処理機構は、どのようなものを検討すると良いでしょうか。 これまでの検討の結果、いいとこ取りをして、私は、次のような目標をたてました。
この目標を達成するために、"Guild" というインターフェースを考えました。 Thread の代わりに Guild を使う、というイメージです。
まず、基本的なイメージです。 Ruby インタプリタを開始すると、自動的に Guild を生成し、その中でメインスレッドが実行されます（厳密には、さらにメインの Fiber が生成され、それが実行されます）。 既存のプログラムは、いっさい Guild を気にしないで、同じように利用することができます。 Guild は複数のスレッドをもつことができます。図にするとこんな感じです。
（図略）
Guild 中のスレッドは、これまで通り同時に実行しますが、Guild が持つロックによって、並列に実行はしません（GVL の代わりに GGL みたいな名前にしなければならないかもしれません）。 これも、これまで通りの挙動です。つまり、例えば Array#concat などは、thread-safe のままです。
Guild は複数生成することができます。 Guild を生成すると、インタプリタ開始時と同じように、その Guild に属するスレッドが生成されます。 各 Guild のスレッドは、それぞれ同時に実行します。
そして、ここからが大事なところですが、読み書きを行なう可変オブジェクトは特定の Guild に属します。 複数の Guild が、同時にあるオブジェクトを読み書きすることは出来ません。
可変オブジェクトを別の Guild に渡す必要があることもあるでしょう。 その場合は、チャンネル（Guild::Channel）を使って可変オブジェクトを渡すことができます。 チャンネルを使って、2通りの方法で可変オブジェクトを渡すことができます。 一つはコピー、一つは移動です。 コピーはそのまんまですよね。簡単です。 オブジェクトを deep copy して送ります。普通の dup じゃないことに注意が必要です。 dRuby などを使うと、たいていこのような挙動になります。 ロックなどを用いなくてもよくて簡単ですが、コピーには時間がかかることが多いです（Copy on Write のような仕組みを入れれば、そこそこマシになりますが）。
二つ目の移動は、新しい概念です。 全部コピーするのは難しいので、参照を送りたいですが、ただ参照を送るだけでは、 可変オブジェクトを同時に複数の Guild が共有してしまうことになり、ロックなどについて考えなければならなくなります。 そもそも、可変オブジェクトが特定の Guild に属する、という前提が崩れてしまいます。
そこで、「移籍（transfer membership）」という新しい操作を導入します。 情報、この場合はオブジェクトへの参照ですが、これをある場所からある場所に移動しても、元の場所には残ってしまします。 可変オブジェクトへの参照が、送り元の Guild から、そのまま見えてしまうのがまずいのです。 そこで、ある可変オブジェクトを移籍するとき、その可変オブジェクトを脱退（leave）させます。 そして、移動先の Guild へ参加（join）します。 脱退した可変オブジェクトへの参照を用いても、移動元の Guild からはアクセスできないようにします。 このようにすることで、可変オブジェクトが特定の Guild にのみ属する、という状況を維持するようにします。 送った後は、使わない、ということは、そこそこありえるシチュエーションだと思います。この機能は、そのようなシチュエーションに適しています。
なお、不変オブジェクトは、チャンネルを用いて参照を自由にやりとりすることができます。 なので、複数の Guild を用いて並行・並列プログラミングをするときは、やりとりする場合は不変オブジェクトを用いるとよいかもしれませんね。
ただ、不変オブジェクトは、単に freeze されたオブジェクトというわけにはいきません。 例えば、[Object.new].freeze という配列は、freeze されていますが要素は可変オブジェクトです。 そのため、不変オブジェクトであるためには、参照可能なオブジェクトがすべて不変オブジェクトである必要があります。 これを、deeply frozen と呼ぶことにします（が、もっと良い名前があれば、教えて下さい）。
さて、紹介をしたので、具体的にどのようにプログラムを行なうか見ていきます。
まずは、do-all 型の、ある処理を別の Guild でやってもらう並行・並列プログラミングの例について見ていきます。
def fib(n) ... end
g_fib = Guild.new(script: %q{
ch = Guild.deafult_channel
while n, return_ch = ch.receive
return_ch.transfer fib(n)
end
})
ch = Guild::Channel.new
g_fib.transfer([3, ch])
p ch.receive
このプログラムは、フィボナッチ数を計算する Guild g_fib を生成します。Guild にはデフォルトチャンネルが用意されており、 Guild オブジェクトに対して transfer を行なうと、その Guild のデフォルトチャンネルにデータを送ります。
Guild::Channel.new により、チャンネルを生成することができます。 このプログラムでは、メイン Guild から、g_fib へ計算して欲しい数値と、結果を送り返して欲しいチャンネルを渡しています。 g_fib では、数値とチャンネルを Guild::Channnel#receive メソッドで受け取り、フィボナッチ数を計算して結果を返します。 数値などは不変オブジェクトなので、コスト無しで転送することが可能です（配列はコピーしていますね）。 （これを実現するために、Ruby 2.0 から 2.2 で、Fixnum や Symbol などを freeze するようにしていました）
今回は、フィボナッチ Guild を一つしか作らないため、並列に計算することはしませんが、 フィボナッチ Guild を複数作成すれば、並列に動作させることが可能です。
次に、並行、並列に行なうパイプライン処理について紹介します。
result_ch = Guild::Channel.new
g_pipe3 = Guild.new(script: %q{
while obj = Guild.default_channel.receive
obj = modify_obj3(obj)
Guild.argv[0].transfer_membership(obj)
end
}, argv: [result_channel])
g_pipe3 = Guild.new(script: %q{
while obj = Guild.default_channel.receive
obj = modify_obj2(obj)
Guild.argv[0].transfer_membership(obj)
end
}, argv: [g_pipe3])
g_pipe1 = Guild.new(script: %q{
while obj = Guild.default_channel.receive
obj = modify_obj1(obj)
Guild.argv[0].transfer_membership(obj)
end
}, argv: [g_pipe2])
obj = SomeClass.new
g_pipe1.transfer_membership(obj)
obj = result_ch.receive
この例では、3つの仕事（modify_obj1, 2, 3）を並行、並列に行なうパイプライン処理を表わしています。 最初に渡す SomeClass のオブジェクトは、可変オブジェクトであると考えて下さい。 Guild::Channel#transfer_membership(obj) を使うことで、コピーではなく移籍を行なうため、高速に転送することが可能です。
最後に、先ほど紹介した銀行口座管理のプログラムを紹介します。これについては、2つの方法を紹介します。
銀行口座の管理は、並行、並列に実行するなら同期が必要になりますが、どうせなら一つの Guild に任せてしまうのはどうでしょうか。
g_bank = Guild.new(script: %q{
while account_from, account_to, amount, ch = Guild.default_cahnnel.receive
if (Bank[account_from].balance < amount)
ch.transfer :NOPE
else
Bank[account_to].balance += amount
Bank[account_from].balance -= amount
ch.transfer :YEP
end
end
})
このように、一つの Guild が処理を行なうようにすれば、同期は一切不要になります。 もちろん、並列度は出せませんが、そもそも全体にロックをかけなければならない、という話でしたので、この例だけなら問題ない、ということができます。
もう一つの方法は、変更可能なオブジェクトを共有し、特別な方法でアクセスする、というものです。 一番簡単な方法は、RDB へデータを保存する、という方法です。SQL によって、適切に可変データをやりとりすることが可能です。 これは、冗談ではなくて、例えば RDB や key/value store のようなデータ構造を、Guild の共有 storage として新たに提供することは可能ですので、 そのようなものを実装してやればよいことになります。Clojure が提供しているデータ構造などが参考になると思います。
典型的な使い方をまとめます。
オブジェクトの受け渡しについては、下記の順番で検討していくと良いと思います。
上にいくほど気楽であり、一番下が複雑です。
Guild とオブジェクトのメンバーシップという考え方を用いることで、スレッドと何が異なるでしょうか。 それは、可変オブジェクトの共有を制限している、ということです。 スレッドは、容易に可変オブジェクトを共有することができるため、 ロックをうっかり忘れてしまったりして、データレースやレースコンディションが容易に発生させてしまいます。 また、どこで間違いがあったか、それを見つけるのは困難です。
しかし、Guild のモデルでは、そもそもそのようなことが起こらないため、並行プログラミングが容易になります。 また、特殊な方法を用いる場合、何か間違いがあれば、それを利用しているところのみをチェックすればよく、問題の切り分けが容易になります。 その代わり、スレッド間のデータ共有に比べて、多少のオーバヘッドがかかります。 これは、最初に紹介した、性能と安全性、使いやすさのトレードオフと同じであり、Ruby は後者を選択するべきだと考えます。
では、実装について、ポイントだけ紹介します。
Guild を実現するためには、2つの key point が必要になります。
それぞれ見ていきます。
移籍が今回の発表で一番新規性のあるアイデアになります。 移籍元の Guild から、参照させないようにするには、どうすれば良いでしょうか。
今回は、移籍するとき、新しいオブジェクトを作り、それを移籍先の Guild へ送ることにしました。 そして、移籍元のオブジェクトを、参照したら（例えばメソッドを呼んだりしたら）、例外が出るように変更することにしました。 オブジェクトを新しく作るなら、それはコピーと同じではないか、と思われるかもしれませんが、例えば配列の場合、配列の実体を別に持っています。 その実体を、元のオブジェクトからは参照しないようにし、新しいオブジェクトのみが参照することにします。 これにより、コピーよりは速い、Guild 間のオブジェクトの転送が実現出来ました。 転送元では、そのデータは参照しないだろう、という前提の高速化と言うこともできます。
次に、インタプリタ上の共有データをどのようにあつかうか、という問題です。
まず、言語機能的に共有しそうなものをあげ、その対処を考えます。 それぞれ選択した理由がありますが、時間がないので細かい説明は省略します。
次に、インタプリタプロセスが共有するものを考えます。
さて、性能評価を行ないます。
まだ、複数 Guild で Ruby プログラムを実行するところまで、出来ていないので、 Ruby プログラムを実行するメイン Guild と、C 言語で実装したワーカー Guild で評価します。
2 core の VM 上で動作するので、最大で2並列になります。
まず、4 つの fib guild（フィボナッチ数を計算して、返す Guild）を生成し、メイン Guild がそれらに計算を依頼する、というものです。 fib(40) を 50 回計算させてみました。
user system total real
single-guild 19.460000 0.000000 19.460000 ( 19.454509)
multi-guild 20.680000 0.020000 20.700000 ( 10.450687)
ちゃんと、並列処理ができています。
次に、数値の入った10万要素の配列（(1..10_000_000).to_a）を渡し、合計を計算する sum Guild を 4 つ生成し、 同じくメイン Guild から、それら Guild に配列を渡し、その計算を 100 回行なって貰います。
user system total real
serial 1.000000 0.000000 1.000000 ( 1.000823)
ref 1.240000 0.030000 1.270000 ( 0.648116)
move 5.400000 0.060000 5.460000 ( 4.293291)
copy 4.130000 1.050000 5.180000 ( 5.162813)
逐次実行（つまり、複数 Guild を使わない）では、1秒だったものが、 複数 Guild を利用すると、参照渡し（つまり、行ないたくないもの）は 0.6 秒と速くなっていますが、 move つまり移籍を行なう場合は 4 秒、copy では 5 秒と、とても遅くなってしまいました。 これは、移籍やコピー時に、配列の要素をチェックし、可変オブジェクトを参照していないか、ということを、すべての要素でチェックしているためです。
オブジェクトを deeply frozen であるとして計算すると、下記のように、参照を渡すのと、ほぼ同じ程度の性能が出ています。
user system total real
serial 1.020000 0.000000 1.020000 ( 1.017517)
ref 1.210000 0.040000 1.250000 ( 0.626588)
move 1.250000 0.030000 1.280000 ( 0.647243)
copy 1.270000 0.030000 1.300000 ( 0.654752)
例えば、配列の要素に、数値しか入っていない、という情報があれば（つまり、要素はすべて deeply frozen）、 要素のチェックは不要になるため、移籍のコストは deeply frozen の場合と、ほぼ同様になることが期待できます。 これは、要素が deeply frozen のものしか認めない、特殊な配列を用意するといったことで実現可能です（NArray 対応とか）。
そのほかの性能については、以前行なった 並列スレッドの研究、MVM （multiple-VM）の研究の成果が、ほぼそのまま利用可能になるかと思います。 気になった人は調べてみて下さい。
まとめます。
本稿では、Ruby 3 の並行モデルとして、Guild と、オブジェクトのメンバーシップという考え方を提案しました。すべての可変オブジェクトは特定の Guild に属する、という制約を加えることで、ロックなどをあまり気にせずに並行・並列プログラムを行なう仕組みになっています。また、実装方法についての指針を示しました。
まだ、完全に実装できていないため、ぜひ試して下さい、とは言えませんが、 新しい並行・並列モデルの提案として、少し考えてみるのはどうでしょうか。
細かいので省略、というところのほうが、本当は凄い悩んだ結果なんだけど、そういうのを説明するのは難しいねぇ。
Guild 間で可変状態のまま持ち運べる「特殊なオブジェクト」、Ruby で定義できるようにするか悩んでるんですよね。Object#marshal_dump みたいなのを定義して、どう移籍するか定義できるようにしてもいいんだけど、そこでミスると可変オブジェクトが渡っちゃうんですよね。いくつか選択肢があって、
といった方法が考えられます。
事情により、京都に先乗り。
80 page になったので、どこ削ろう...。
g_pipe3 を生成する Guild.new へ渡す argv の中身が result_channel になってますが、result_ch が正しそうです。細かい点ですみません、発表楽しみにしております。
今日中に終わらせよう、と思っていたことが終わらなかった。 明日までには...。
race condition と data race の違いの話。よく、違いがわかってなかったんだけど、http://blog.regehr.org/archives/490 などを見て、理解。
一貫性の欠如、という一言でまとめられそうに思うんだけど、そうでもないのかな。 どちらもトランザクションで解決、トランザクションは一貫性を保つための仕組み、的な。
なんというか、ちゃんと用語の定義を抑えられてないんだよな。何を参照すればいいんだろうか。wikipedia も微妙な感じだったしな。
ホテルが札幌駅から離れていたんだけど、運良く最寄り駅へ歩いている途中で札幌駅行きのバスがきたので、それに乗ることができた。
雪印パーラーでパフェ食べて、千歳空港で昼食食べて、お腹いっぱい。
GSoC の「Certificate of Appreciation」というものを貰ったが、これは何に役立てればいいんだろうか。
札幌で Elixir 本の話をさせて頂きました。機会を頂けて本当にありがとうございました。
Elixir において、同じ変数に再束縛できることについて、うまく説明できなかったんだけど、単に新しい let なんだよ、と言うだけで良かった。F# も、という話があったけれど、そうなのかな。
Golangのそれはgoroutine-leakと呼ばれていて、回避するたのめtipsは若干あるものの「そういうもの」と考えられています。