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?

Haven't really been able to take a close look, but from what I see above this isn't a particularly great test case for comparing performance characteristics of pattern matching vs. conditional lists. I don't know how much Elixir allows you to do in terms of expressing patterns, but a more robust use of pattern matching in Erlang would use a series function clauses binding specific parameters to, say, positions in tuple. What you have here looks like a recursive function that makes a very basic check in the guard portion of the function definition before calling itself again. — Soup d'Campbells
Because it's a recursive function, you're not giving the BEAM compiler much wiggle room to flex its pattern-matching muscles. When it comes to a simple check like is_list or is_tuple, there's not going to be a significant difference from pattern matching (especially w/guard statements) to conditional evaluation. Consider something like: foo({bar, A = 0, Z}) -> Z; foo({bar, A, Z = 0}) -> A; foo({bar, A, Z}) when A > Z -> A; foo({bar, A, Z}) -> Z; ..., as this kind of setup allows the BEAM compiler to build out decision trees for which clause of the function foo to invoke. — Soup d'Campbells
Thanks. I further tried to do pattern matching on http headers, as what you said, makes a difference (though still small due to the N is small). — Tyr

José Valim José Valim · Accepted Answer · 2015-03-04T09:29:02

Two points:

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))
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.

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

1 Answers