こんにちは、エンジニアの渡部です
最近、Elixirの本(プログラミングElixir)の日本語訳が出版されましたね。
その中でフィボナッチ数を分散処理で解決するコードが書かれていたのが面白そうだったため試してみました。
フィボナッチ数計算コード
コードは全部で3つのモジュールで構成されています。
- メインモジュール・・・プロセス数1から10までで同じ問題を解き、各々どれくらい時間がかかるかを表示する
- スケジューラ・・・手が空いたフィボナッチサーバプロセスに計算させるマン
- フィボナッチサーバ・・・ひたすらフィボナッチ数を計算をするナイスガイ。計算が終わったらすぐにスケジューラに次の仕事を要求する仕事中毒者
メインモジュール
defmodule Fibonacci do def main do to_process = [37, 37, 37, 37, 37, 37] # 1から10のプロセス数で実験する Enum.each 1..10, fn num_processes -> {time, result} = :timer.tc( Scheduler, :run, [num_processes, FibSolver, :fib, to_process] ) if num_processes == 1 do IO.puts inspect result # 計算結果を表示する IO.puts "\n # time (s)" end :io.format "~2B ~.2f~n", [num_processes, time / 1000000.0] end end end
スケジューラ
defmodule Scheduler do # num_processes数のプロセスを生成し、to_calculateリスト内のフィボナッチ数を全て計算していく def run(num_processes, module, func, to_calculate) do (1..num_processes) |> Enum.map(fn(_) -> spawn(module, func, [self]) end) |> schedule_processes(to_calculate, []) end defp schedule_processes(processes, queue, results) do receive do # まだ計算するフィボナッチ数が残っている場合は、サーバプロセスに計算を要求する {:ready, pid} when length(queue) > 0 -> [next | tail] = queue send pid, {:fib, next, self} schedule_processes(processes, tail, results) # 全てのフィボナッチ数を計算し終わった場合は、サーバプロセスをシャットダウンする {:ready, pid} -> send pid, [:shutdown] if length(processes) > 1 do schedule_processes(List.delete(processes, pid), queue, results) else # 全てのプロセスを終了したら、結果リストを並び替えたリストを生成し返す Enum.sort(results, fn {n1, _}, {n2, _} -> n1 <= n2 end) end # サーバプロセスが計算し終わった値を結果リストに格納する {:answer, number, result, _pid} -> schedule_processes(processes, queue, [{number, result} | results]) end end end
フィボナッチサーバ
defmodule FibSolver do # フィボナッチ数を計算して生成元に送る関数 def fib(scheduler) do send scheduler, {:ready, self} receive do {:fib, n, client} -> send client, {:answer, n, fib_calc(n), self} fib(scheduler) {:shutdown} -> exit(:normal) end end # わざと非効率的にする defp fib_calc(0), do: 0 defp fib_calc(1), do: 1 defp fib_calc(n), do: fib_calc(n - 1) + fib_calc(n - 2) end
実行結果
実行環境
- OS: Ubuntu 16.04.1 LTS (64bit)
- CPU: Intel(R) Xeon(R) CPU E5-2650 v2 @ 2.60GHz
- CPU数: 2 (コア数は各1個)
- メモリ: 1GB
結果
実行結果は下の画像のようになりました。
#の列が使用したプロセス数、timeは計算にかかったリアルタイム(現実時間)です。
このときのtopコマンドの出力ですが、きちんと分散処理がなされていて画像のようにCPU使用率200%となりました!
日常的に使っていてCPU使用率200%という数値を見たことがなかったので、少し感動しました。
せっかくなのでRubyと比較
業務でRubyのThreadを使いたいと思っているので、RubyのThreadはどんな結果になるか興味があります。
というのも、RubyのThreadはネイティブスレッドですが、Giant VM Lock(GVL)というVMでネイティブスレッドの数を一つに制限する機構があると見聞きしたためです。これがどのようにパフォーマンスに影響するのか実験してみます。
#!/usr/bin/env ruby # -*- coding: utf-8 -*- require 'benchmark' def fib(n) if n == 0 0 elsif n == 1 1 else fib(n - 1) + fib(n - 2) end end def main() to_calculate = [37, 37, 37, 37, 37, 37] thread_list = to_calculate.map do |n| Thread.new { fib(n) } end result = Benchmark.realtime { thread_list.each(&:join) } puts ' # time (s)' puts "%02d %.2f" % [thread_list.length, result] thread_list.each(&:join) end main if $0 == __FILE__
計算すべきフィボナッチ数は6個(to_calculateの要素数)あるので6スレッド生成して、実験してみました。
結果は、6スレッドで28.83秒(リアルタイム)となりました。
topコマンドの出力を見てみると、CPU使用率が100%以上あがりません。
やはり、GVLの効果でネイティブスレッド数が限定されて、コア数分の分散処理になっていないようです。
GVLがあるのは、Ruby自体がスレッドセーフでなく、他サードパーティーモジュールなどもスレッドセーフではないからというのが理由として挙げられているようです。
しかし、IO処理などはGVLの制限がはずれるらしく、実際に以下のコードを試すとCPU使用率128%となりました。
#!/usr/bin/env ruby # -*- coding: utf-8 -*- def f() 1_000_000_000.times { STDERR.puts "Hello" } end def main() thread_list = 6.times.map do |i| Thread.new { f } end thread_list.each(&:join) end main if $0 == __FILE__
まとめ
Elixirの分散処理はとてもすごいですね。コード自体に慣れることができればとても素早い処理をすることができそうです。
でも普段使いならRubyのほうが私の脳に優しいかなと思いました(^^;)
Elixirの日常使いを増やして色々と作っていきたいです。 (RubyはRubyistでPythonはPythonista、Elixirを使う人はなんていうんだろう?)