K.Sasada's Home Page

こめんとのついか

こめんとこめんと!

message

please add long comment :).

_6(Tue)

下記は、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 になったので、どこ削ろう...。

_ma2ge(Wed Sep 07 18:48:19 +0900 2016)

 g_pipe3 を生成する Guild.new へ渡す argv の中身が result_channel になってますが、result_ch が正しそうです。細かい点ですみません、発表楽しみにしております。


好きなだけ長いコメントをどうぞ。

お名前


back

tton 記述が使えます。YukiWikiな記述してりゃ問題ありません。

「行頭に#code」 と、「行頭に#end」 で挟むと、その間の行は pre で囲まれます。プログラムのソースを書くときに使ってください。

例:

#code

(なんかプログラム書く)

#end

リンクは

[[なまえ|http://www.example.org]]

とか

[[http://www.example.org]]

で貼れます。

$Date: 2003/04/28 10:27:51 $