Posted at

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

Elixir 1.5(結構前ですね)から Enum.filter_map/3 がdeprecatedになりました。

フォーラムでもなんでなのか、というスレッドがありました(Why Enum.filter_map is deprecated? | Elixir Forum

filter_mapfilter |> 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になるわな、という感じでした