「Elixirで速度を追い求めるときのプログラミングスタイル - Qiita」という記事にある、「Enum.mapと再帰スタイルは，ほとんど差がない」という検証結果が興味深かったので、自分でもやってみました。興味深かったポイントは、末尾再帰にしたらやっぱり速くなるのではないか？ということです。

この記事に記載している検証コードはkentaro/r_map_benchに置いてありますので、そちらもご参照ください（本文中からも適宜リンクしています）。

ベンチマーク対象のコード

`Enum.map`による実装

Enum.map(@list, & &1 * 2)

再帰による実装

lib/recursive.ex

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)

ここまでは元記事の通りです。

末尾再帰による実装

lib/tail_recursive.ex

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)

こちらが、あらたに追加した実装です。

テストによる実装の確認

そもそも実装がちゃんとできているのか、テストしてみます。

test/r_map_bench_test.exs

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を使ってベンチマークします。

bench/r_map_bench.ex

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も相対的に多く走ることになるため、パフォーマンスが安定しなくなる問題もあると記事ではいわれています。

また、可読性という意味でも末尾再帰のほうが相対的に読みにくくなるため、無理に書き換える必要があるかといえばそうでもないという場面もありそうです。

Enum.mapと再帰スタイルの比較、ふたたび（末尾再帰版）