为什么模式匹配性能不如灵丹妙药中的ifelse/cond好多少？

Question

我被告知erlang beam通过模式匹配调整了很多,因此性能比条件表达式要好得多.我在elixir中进行了测试,并使用benchfella进行基准测试.但是,我发现与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

下面是核心代码,它基本上将数据格式化为不同情况下的字符串.整个项目可以通过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

我错过了什么吗？或者我是否需要更复杂的测试来找出erlang VM的模式匹配的强度？

Answer 1

两点:

1. 为了让你看到任何好处,你需要大量的测试,因为在一天结束时它可以归结为条件检查是线性(O(N)),而模式可以优化为二叉树搜索(O(log2N))

2. 尽管如此,并非所有模式都可以同等优化.如果我没记错的话,保护条款仍然是线性匹配的

模式优化肯定会引发的更直接的例子是Elixir用于Unicode操作的模式:

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

在这种情况下,VM能够构建树,而不是线性测试每个模式,直到找到匹配的模式,二叉树将执行更快的查找.

Erlang VM可能也能够优化列表和元组中的模式.鉴于模式匹配通常更具表现力,事实上它在平均速度上更快,而在最坏的情况下只是线性的,这是一个非常好的加分.