【Enun.sum vs Enum.reduce】Elixirでの実行速度の測定と色々と実験してみた

測定に至る背景

再来週に開催する清流elixirの勉強会でifとパターンマッチでそれだけ実行速度に差が出るのかを測定しようと企画している
そのために自身の予習を兼ねて、Elixirでの実行速度の測定方法について調査し、簡単な実験を行なってみた
以前から気になっていた

  • Enum.sum()
  • Enun.reduce()

上記2つはどちらが速いのか(sumはreduceで記述可能なため) 再帰関数とEnun.map()はどっちが速いのかなど...

色々と速度比較してみたのでまとめていく

Elixirでの実行速度の測定方法

Elixirには実行速度を測定するような関数は用意されていない
そのためErlangの:timer.tcという関数をcallする :timer.tcには以下のように

  • :timer.tc(function)
  • :timer.tc(function, [arguments])
  • :timer.tc(module, function, [arguments])

引数違いで3種類用意されている
戻り値はそれぞれ

{micro second, result}

のタプル形式になっている

マイクロ秒(マイクロびょう、microsecond、記号: µs)は、100万分の1秒(10−6 s, 1/1,000,000s
https://ja.wikipedia.org/wiki/%E3%83%9E%E3%82%A4%E3%82%AF%E3%83%AD%E7%A7%92

順に適当なサンプルを使って実行速度を測定してみる
今回は1..100のレンジの各要素を2倍にしてリストで返してみる

引数が1つの:timer.tc(function)

無名関数を作成して渡してやれば良い
無名関数の引数はなしにしてあげれば問題なくパスできる

:timer.tc(fn -> Enum.map(1..100, &(&1 * 2)) end)
{175,
 [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40,
  42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78,
  80, 82, 84, 86, 88, 90, 92, 94, 96, ...]}

最初、無名関数に「 _ 」の引数を用意してしまっていた割とハマった
引数なしでも実行できるの知らなかったので勉強になった

fn -> IO.puts("こんな書き方あったんかい!") end

以下の書き方ではerrorになる
「 _ 」でも引数として認識されている模様

:timer.tc(fn _ -> Enum.map(1..100, &(&1 * 2)) end)

** (BadArityError) #Function<6.128620087/1 in :erl_eval.expr/5> with arity 1 called with no arguments
    (stdlib) timer.erl:166: :timer.tc/1

無名関数に引数を与えてはいけないんだね

引数が2つの:timer.tc(function, [arguments])

先ほどとは異なり、無名関数に引数を用意して:timer.tcの第2引数から渡してもらえるようにする

:timer.tc(fn lst -> Enum.map(lst, &(&1 * 2)) end, [1..100])
{229,
 [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40,
  42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78,
  80, 82, 84, 86, 88, 90, 92, 94, 96, ...]}

引数が3つの:timer.tc(module, function, [arguments])

まずはモジュールと関数を適当に用意する

defmodule Sample do
  def calc(enum_) do
    enum_ |> Enum.map(&(&1 * 2))
  end
end

第2引数の渡し方に注意。Erlangドキュメントに記載があるように関数はアトム型として待ち構えている
そのため「:関数名」という形式で記述をする必要がある。ここで割とハマった

Erlang Reference Manual Version 3.9より Types
Module = module()
Function = atom()
Arguments = [term()]
Time = integer()
In microseconds
Value = term()

:timer.tc(Sample, :calc, [1..100])
{26,
 [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40,
  42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78,
  80, 82, 84, 86, 88, 90, 92, 94, 96, ...]}

第2引数がアトム型だと気づかずerrorを出しまくったパターン達

:timer.tc(Sample, by, [[1,2,3,4,5], []])
:timer.tc(Sample, by(), [[1,2,3,4,5], []])
:timer.tc(Sample, by/2, [[1,2,3,4,5], []])
:timer.tc(Sample, Sample.by/2, [[1,2,3,4,5], []])

色々、試したけど全部ダメ。やはり公式ドキュメント最強

色々と実験

実行速度の測定方法も何となく分かったところで早速、実験をやってみようと思う
今回試してみるのは以下

  • Enum.reduce()の引数2つと引数3つはどっちが速いのか
  • Enum.max()とEnum.reduce()はどっちが速いのか
  • 再帰関数とEnum.map()はどっちが速いのか

を100回の実行での平均値をとってそれぞれ比較してみる
グラフの描画にはpythonのmatplotlibを使用した
適当な関数を作ったので一応、貼っておく

def plot_result(result_ary, try_num, title, x_label, y_label, is_gird=True, is_average_show=True):
    """
        draw result graph from result array and total try
        >>> result_ary = [12, 43, 23, 34, 54] # free size
        >>> try_num = 5 # must: result_ary size == try_num
        >>> title = "Result time"
        >>> x_label = "try"
        >>> y_label = "time(micro second)
        >>> is_grid = True # default: True, show grid in graph?
        >>> is_average_show = True #default: True, show average line in graph?
        >>> plot_result(result_ary, try_num, title, x_label, y_label)
        create graph, use matplotlib
    """
    if len(result_ary) != try_num:
        raise ValueError(f"not match {len(result_ary)} size != {try_num}")
    
    try_num_lst = [num for num in range(try_num)]    
    plt.plot(try_num_lst, result, lw=3, label="result")
    
    if is_average_show:
        average = sum(result) / len(result)
        average_lst = [average for _ in range(try_num)]
        plt.plot(try_num_lst, average_lst, 'g--', color="r", lw=2, label='average')
        max_val = max(result_ary)
        plt.text(5, max_val - max_val * 0.1, f"average: {average}", size = 15, color = "green")

    plt.title(title)
    plt.xlabel(x_label)
    plt.ylabel(y_label)

    plt.legend()
    plt.grid(is_gird)
    plt.savefig(f'{title}.png')
    plt.show()

筆者のPCスペック

  • MacBook Pro (13-inch, 2016, Two Thunderbolt 3 ports)
  • プロセッサ: 2GHz Intel Core i5
  • メモリ: 8GB 1867 MHz LPDDR3
  • グラフィックス: Intel Iris Graphics 540 1536 MB

1.Enum.reduce()の引数2つと引数3つ対決

1から100までの数値を合計する処理で2つを比較してみる

# 引数が2つ
Enum.reduce(1..100, fn x, acc -> x + acc end)

# 引数が3つ
Enum.reduce(1..100, 0, fn x, acc -> x + acc end)

100回の実行はEnun.mapを使って実行している。そして結果を描画する
引数が2つの場合

res = Enum.map(1..100, fn _ -> 
  :timer.tc(fn -> Enum.reduce(1..100, fn x, acc -> x + acc end) end)
end)
|> Enum.map(fn {s, _} -> s end)

f:id:takamizawa46:20190728120636p:plain

引数が3つの場合

res = Enum.map(1..100, fn _ -> 
  :timer.tc(fn -> Enum.reduce(1..100, 0, fn x, acc -> x + acc end) end)
end)
|> Enum.map(fn {s, _} -> s end)

f:id:takamizawa46:20190728121134p:plain

accumlatorの初期値を渡さない引数2つのパターンの方が速い
たまに発生する急激な処理速度の低下は何なんだろう。音楽流しながら測定してるのが関係あるか?

2.Enum.max()とEnum.reduce()の合計対決

Enum.max()

res = Enum.map(1..100, fn _ -> 
  :timer.tc(fn -> Enum.max(1..100) end)
end)
|> Enum.map(fn {s, _} -> s end)

f:id:takamizawa46:20190728121551p:plain

Enum.reduce()でmaxを算出

# Enum.reduce() 先ほどの検証で分かった高速な引数3のreduce()を使用
res = Enum.map(1..100, fn _ -> 
  :timer.tc(fn -> Enum.reduce(1..100, 0, fn x, acc ->
     if x > acc do
       x
     else
       acc
     end
  end) end)
end)
|> Enum.map(fn {s, _} -> s end)

f:id:takamizawa46:20190728121925p:plain

なんとEnum.max()よりもEnum.reduce()の方が速いではないか
速度の最大値(μs)と最小値(μs)でこれだけ差が開くのはなんでなんだろうか
しかし、今のmax値の探索は100が当然ながら答えなので最大長(O(n))の結果となっているため
自身で用意したランダムなリストでどのような結果になるのかを確かめてる

指定範囲内で指定回数分のランダム数値を持つリストを作成する無名関数を用意した

random_creater = fn total_elem, max -> Enum.map(total_elem, fn _ -> :random.uniform(max) end) end
random_creater.(1..100, 100) 
iex(116)> random_creater.(1..100, 100)
[18, 95, 80, 85, 95, 5, 41, 29, 78, 89, 7, 88, 22, 85, 14, 50, 29,
 42, 29, 98, 7, 27, 48, 18, 62, 74, 76, 89, 85, 71, 82, 27, 21, 29,
 32, 3, 22, 65, 1, 36, 6, 59, 61, 12, 49, 97, 5, 19, 71, 52, ...]

同様にそれぞれ結果を見てみる
f:id:takamizawa46:20190728213615p:plain
f:id:takamizawa46:20190728214248p:plain

なんじゃこりゃ。ランダムな要素で作成したリストで同じ処理をしたら
先ほどと結果が逆転して、かなりの差がついた
もしかしてレンジを使っていたのが良くなかったのかもしれない(Enum.reduce()の方がレンジの処理性能が良い?)

3.再帰関数とEnum.map()はどっちが速いのか

先ほどの結果も踏まえて、ランダな要素を持つ配列を使用する
全ての要素を2倍にする実行速度を比較してみる

再帰関数

defmodule Sample do
  def by([], accum), do: accum
  def by([head | tail], accum) do
    by(tail, accum ++ [head * 2])
  end
end

res = Enum.map(1..100, fn _ -> 
  :timer.tc(Sample, :by, [lst, []])
end) |> Enum.map(fn {s, _} -> s end)

f:id:takamizawa46:20190728215325p:plain

Enum.map()

res = Enum.map(1..100, fn _ ->
  :timer.tc(fn -> Enum.map(lst, &(&1 * 2)) end)
end) |> Enum.map(fn {s, _} -> s end)

f:id:takamizawa46:20190728215353p:plain

圧倒的に再帰関数の方が早かった
Elixir&ErlangFestでzackyさんからLTのあった通りの結果になった
とは言いつつも、Enum.map()の方が記述もしやすく手軽なのは紛れもない事実だ

普段、何気なく書いている処理の性能を比較してみると面白い
今回選定したテーマは割と強引に持ってきた感があるが、普段記述に迷うような処理があれば
Elixirであれば:timer.tc()を使って手軽に試せるので、実測してみるのも良い

参考文献

Erlang Reference Manual Version 3.9
Simplicity
Elixirで関数の実行速度を測定する
Elixirでパフォーマンス測定
Elixir Zen スタイルプログラミング講座