Elixirでフィボナッチ数

こんにちは、エンジニアの渡部です

最近、Elixirの本(プログラミングElixir)の日本語訳が出版されましたね。

その中でフィボナッチ数を分散処理で解決するコードが書かれていたのが面白そうだったため試してみました。

フィボナッチ数計算コード

コードは全部で3つのモジュールで構成されています。

  1. メインモジュール・・・プロセス数1から10までで同じ問題を解き、各々どれくらい時間がかかるかを表示する
  2. スケジューラ・・・手が空いたフィボナッチサーバプロセスに計算させるマン
  3. フィボナッチサーバ・・・ひたすらフィボナッチ数を計算をするナイスガイ。計算が終わったらすぐにスケジューラに次の仕事を要求する仕事中毒者

メインモジュール

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は計算にかかったリアルタイム(現実時間)です。

f:id:AdwaysEngineerBlog:20160923171231p:plain

このときのtopコマンドの出力ですが、きちんと分散処理がなされていて画像のようにCPU使用率200%となりました!

日常的に使っていてCPU使用率200%という数値を見たことがなかったので、少し感動しました。

f:id:AdwaysEngineerBlog:20160923171224p:plain

せっかくなので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%以上あがりません。

f:id:AdwaysEngineerBlog:20160923175206p:plain

やはり、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を使う人はなんていうんだろう?)