「Elixirで速度を追い求めるときのプログラミングスタイル - Qiita」という記事にある、「Enum.mapと再帰スタイルは，ほとんど差がない」という検証結果が興味深かったので、自分でもやってみました。興味深かったポイントは、末尾再帰にしたらやっぱり速くなるのではないか？ということです。
この記事に記載している検証コードはkentaro/r_map_benchに置いてありますので、そちらもご参照ください（本文中からも適宜リンクしています）。
ベンチマーク対象のコード
Enum.mapによる実装
Enum.map(@list, & &1 * 2)
再帰による実装
defmodule Recursive do
def r_map([], _func), do: []
def r_map([head | tail], func) do
[func.(head) | r_map(tail, func)]
end
end
Recursive.r_map(@list, & &1 * 2)
ここまでは元記事の通りです。
末尾再帰による実装
defmodule TailRecursive do
def r_map(list, func) do
r_map_rec(list, func, [])
|> Enum.reverse()
end
defp r_map_rec([], _func, acc), do: acc
defp r_map_rec([head | tail], func, acc) do
r_map_rec(tail, func, [func.(head) | acc])
end
end
TailRecursive.r_map(@list, & &1 * 2)
こちらが、あらたに追加した実装です。
テストによる実装の確認
そもそも実装がちゃんとできているのか、テストしてみます。
defmodule RMapBenchTest do
use ExUnit.Case
setup_all do
%{list: Enum.to_list(1..100)}
end
test "all functions return same values", %{list: list} do
l1 = Enum.map(list, &(&1 * 2))
l2 = Recursive.r_map(list, &(&1 * 2))
l3 = TailRecursive.r_map(list, &(&1 * 2))
assert l1 == l2
assert l2 == l3
assert l1 == l3
end
end
以下の通り実行しました。
$ mix test
.
Finished in 0.04 seconds
1 test, 0 failures
Randomized with seed 985632
実装はOKなようですね。
ベンチマーク
元記事同様、benchfellaを使ってベンチマークします。
defmodule EnumBench do
use Benchfella
@list Enum.to_list(1..1_000_000)
bench "Enum.map" do
Enum.map(@list, & &1 * 2)
end
bench "recursive" do
Recursive.r_map(@list, & &1 * 2)
end
bench "tail recursive" do
TailRecursive.r_map(@list, & &1 * 2)
end
end
以下の通り、3回実行してみました（bench/snapshotsに結果が格納されています）。
1回目
$ mix bench
Settings:
duration: 1.0 s
## EnumBench
[19:21:17] 1/3: Enum.map
[19:21:21] 2/3: recursive
[19:21:24] 3/3: tail recursive
Finished in 10.31 seconds
## EnumBench
benchmark name iterations average time
tail recursive 50 48389.76 µs/op
recursive 50 56384.84 µs/op
Enum.map 50 58459.10 µs/op
2回目
$ mix bench
Settings:
duration: 1.0 s
## EnumBench
[19:21:51] 1/3: Enum.map
[19:21:55] 2/3: recursive
[19:21:58] 3/3: tail recursive
Finished in 10.32 seconds
## EnumBench
benchmark name iterations average time
tail recursive 50 47577.26 µs/op
recursive 50 57106.66 µs/op
Enum.map 50 57772.08 µs/op
3回目
$ mix bench
Settings:
duration: 1.0 s
## EnumBench
[19:22:26] 1/3: Enum.map
[19:22:30] 2/3: recursive
[19:22:33] 3/3: tail recursive
Finished in 10.35 seconds
## EnumBench
benchmark name iterations average time
tail recursive 50 58784.60 µs/op
Enum.map 50 70148.52 µs/op
recursive 20 71049.85 µs/op
結果の考察
元記事にある通り、Enum.mapと再帰とでは、あまり変わりがないように見えます。しかし、末尾再帰による実装では、やや目に見えて速くなっているようにも思われます。
そのため、以下の箇所については、
リストの走査には，
Enum.map/2を使うのが推奨。以前に比べてパフォーマンス面も改善したようなので，再帰スタイルをあえて使う理由がないです。
パフォーマンスを追求する際には、Enum.map/2ではなく末尾再帰となる再帰による実装が有効である場面も依然としてあるといえるようにも思われました。
なにか勘違いがありましたらご教示おねがいします＞＜
追記
@jj1bdxさんに、以下についてご教示いただきました。
https://twitter.com/jj1bdx/status/1347496601791594497
Erlangのドキュメントによると、末尾再帰の方がそうでない再帰より常に速いというのは「神話」であるといわれています。
Erlang -- The Seven Myths of Erlang Performance
その理由として、Erlang's Tail Recursion is Not a Silver Bulletという記事で解説がされています。速い場面がないわけではないのですが、
tail recursion should require a top memory consumption of 2 * size(MsgList) words more than body recursion. This will cause extra garbage collection. Also the lists:reverse/1 is extra work that the body recursive variant avoids. In this case I speculate body recursion wins.
という理由によってむしろ遅くなることもあるようです。さらには、GCも相対的に多く走ることになるため、パフォーマンスが安定しなくなる問題もあると記事ではいわれています。
また、可読性という意味でも末尾再帰のほうが相対的に読みにくくなるため、無理に書き換える必要があるかといえばそうでもないという場面もありそうです。