ElixirのEnum.filter_map/3、実は速くなかった説 #Elixir

Elixir 1.5(結構前ですね)から Enum.filter_map/3 がdeprecatedになりました。
フォーラムでもなんでなのか、というスレッドがありました（Why Enum.filter_map is deprecated? | Elixir Forum）

filter_map と filter |> map だとリストをなめる回数が倍になるから遅くなるのでは？と思ったのですが、測定しているのを見かけなかったので軽く測定しました

測定

コード

defmodule Targets do
  import Integer

  def list, do: Enum.to_list(1..10_000)
  def map_fun, do: fn i -> [i, i * i] end

  def filter_map do
    list |> Enum.filter_map(&is_even/1, map_fun)
  end

  def filter_then_map do
    list |> Enum.filter(&is_even/1) |> Enum.map(map_fun)
  end

  def flat_map do
    list
    |> Enum.flat_map(fn
      x when x |> is_even() -> [x |> map_fun.()]
      _ -> []
    end)
  end

  def comprehensions do
    for n <- list, is_even(n), do: map_fun.(n)
  end
end

Benchee.run(%{
  "filter_map" => &Targets.filter_map/0,
  "filter |> map" => &Targets.filter_then_map/0,
  "flat_map" => &Targets.flat_map/0,
  "comprehensions" => &Targets.comprehensions/0
})

結果

Operating System: macOS
CPU Information: Intel(R) Core(TM) i7-6567U CPU @ 3.30GHz
Number of Available Cores: 4
Available memory: 16 GB
Elixir 1.9.0
Erlang 22.0

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 28 s

Benchmarking comprehensions...
Benchmarking filter |> map...
Benchmarking filter_map...
Benchmarking flat_map...

Name                     ips        average  deviation         median         99th %
comprehensions        1.77 K      564.92 μs    ±16.07%         537 μs      939.67 μs
filter |> map         1.43 K      698.73 μs    ±16.88%         646 μs     1172.80 μs
filter_map            1.35 K      742.58 μs    ±16.73%         717 μs     1273.34 μs
flat_map              1.33 K      752.49 μs    ±19.94%         682 μs     1258.67 μs

Comparison: 
comprehensions        1.77 K
filter |> map         1.43 K - 1.24x slower +133.81 μs
filter_map            1.35 K - 1.31x slower +177.66 μs
flat_map              1.33 K - 1.33x slower +187.57 μs

いや filter |> map 速いじゃん…
今回はfilter部分で要素が半分になるのですが、要素数が減ったのが原因なのかと思ってフィルターをAll Trueにしたバージョンもやってみましたが、

Name                     ips        average  deviation         median         99th %
comprehensions        1.06 K      944.05 μs    ±24.59%      911.00 μs     1533.15 μs
filter |> map         1.03 K      969.13 μs    ±21.81%      862.00 μs     1482.06 μs
filter_map            1.01 K      990.51 μs    ±23.25%      953.00 μs     1581.86 μs

Comparison: 
comprehensions        1.06 K
filter |> map         1.03 K - 1.03x slower +25.09 μs
filter_map            1.01 K - 1.05x slower +46.47 μs

やはり順位は変わらず。

考察

Enum.filter_map/3 の定義は以下のようになっています (Elixir 1.9.0)

enum.ex

@doc false
@deprecated "Use Enum.filter/2 + Enum.map/2 or for comprehensions instead"
def filter_map(enumerable, filter, mapper) when is_list(enumerable) do
  for element <- enumerable, filter.(element), do: mapper.(element)
end

def filter_map(enumerable, filter, mapper) do
  enumerable
  |> reduce([], R.filter_map(filter, mapper))
  |> :lists.reverse()
end

…これまんま Targets.comprehensions じゃんなんで遅いんだ…

対して Enum.filter の実装はListの再帰呼び出しでした

enum.ex

@spec filter(t, (element -> as_boolean(term))) :: list
def filter(enumerable, fun) when is_list(enumerable) do
  filter_list(enumerable, fun)
end

def filter(enumerable, fun) do
  reduce(enumerable, [], R.filter(fun)) |> :lists.reverse()
end

defp filter_list([head | tail], fun) do
  if fun.(head) do
    [head | filter_list(tail, fun)]
  else
    filter_list(tail, fun)
  end
end

defp filter_list([], _fun) do
  []
end

for文より速い…のか…？
Enum.map はErlangの :lists.map に移譲してありました。

for文が効率悪いならなんでcomprehensionが一番早かったのか説明ができないし実に謎ですが、とりあえず今回の例だと filter_map/3 速くなかったしdeprecatedになるわな、という感じでした