why pattern matching performance is not much better than ifelse/cond in elixir?

Question

I was told that erlang beam tuned a lot with pattern matching, thus the performance is much better than conditional expression. I did a test in elixir, and run the benchmark testing with benchfella. However, I found the pattern matching performance is almost the same level of performance compared with if/cond.

$ mix bench -d 10
Settings:
  duration:      10.0 s
  mem stats:     false
  sys mem stats: false

[12:30:08] 1/3: PatternMatchBench.if else performance
[12:30:28] 2/3: PatternMatchBench.cond performance
[12:30:47] 3/3: PatternMatchBench.pattern match performance
Finished in 57.5 seconds

PatternMatchBench.if else performance:            10000   1723.24 µs/op
PatternMatchBench.cond performance:               10000   1723.36 µs/op
PatternMatchBench.pattern match performance:      10000   1726.95 µs/op

Below is the core code, it basically format the data to string under different situation. The whole project could be obtained via https://github.com/tyrchen/pattern_match.

defmodule Ifelse do
  def process(data) do
    if is_list(data) do
      data
      |> Enum.map(fn(entry) ->
          if is_tuple(entry) do
            {k,v} = entry
            "#{k}: #{v}" |> transform
          else
            entry |> process
          end
      end)
      |> Enum.join("\n")
    else
      if is_map(data) do
        data
        |> Enum.map(fn({k, v}) -> transform("#{k}: #{v}") end)
        |> Enum.join("\n")
      else
        data |> transform
      end
    end
  end

  defp transform(str) do
    "    #{str}"
  end
end

defmodule Cond do
  def process(data) do
    cond do
      is_list(data) ->
        data
        |> Enum.map(fn(item) ->
          cond do
            is_tuple(item) ->
              {k, v} = item
              "#{k}: #{v}" |> transform
            true ->
              item |> process
          end
        end)
        |> Enum.join("\n")
      is_map(data) ->
        data
        |> Enum.map(fn({k, v}) -> "#{k}: #{v}" |> transform end)
        |> Enum.join("\n")
      true ->
        "    #{data}"
    end
  end

  defp transform(str) do
    "    #{str}"
  end

end

defmodule Pattern do
  def process(data) when is_tuple(data) do
    {k, v} = data
    "#{k}: #{v}" |> process
  end

  def process(data) when is_list(data) or is_map(data) do
    data
    |> Enum.map(fn(entry) -> process(entry) end)
    |> Enum.join("\n")
  end

  def process(data) do
    "    #{data}"
  end

end

Did I miss anything? Or do I need more complicated tests to find out the strength of the pattern matching of erlang VM?

Answer 1

Two points:

1. For you to see any benefits, you would need a good number of tests because at the end of the day it boils down to the fact conditional checking is linear (O(N)) while patterns may be optimized to a binary tree search (O(log2N))

2. Even though, not all patterns can be equally optimized. If I remember correctly, guard clauses are still matched linearly

A more straight-forward example where pattern optimization will certainly kick in are the patterns Elixir uses for Unicode operations:

case codepoint do
  ?á -> ?Á
  ?é -> ?É
  ?í -> ?Í
  ...
  ?ū -> ?Ū
end

The VM is able to build a tree in this case and, instead of linearly testing each pattern until you find a matching one, the binary tree will do a much faster lookup.

Erlang VM is likely able to optimize patterns insides lists and tuples too. Given pattern matching is often much more expressive, the fact it is faster on average and linear only in the worst-case scenario is a really nice plus.