Does placing the most likely-matched function heads first offer any benefit?

Questions / Help
1

Say we have several function heads or case do patterns to match on.

Will placing “common case” or “most likely” headers first offer any benefits?

I’m seeing timing improvements when I re-order case do match patterns in ELIXIR, putting the most common pattern first.

I had expected the VM to optimize this away, and the order shouldn’t matter.

Example:

  for {s, i} <- li do
    case :binary.split(s, spliter, [:global]) do
      [_, tag, val, _, _] -> 
        # this pattern occurs over 9/10 times.
        # in files with over 100000 rows matching this pattern
        # reduced processing time
        {:tv, i, tag, val}

      [_, "data", _] ->
        Process.put(:data_tag, true)
        {:tb, i, "data"}

      [_, "/data", _] ->
        Process.put(:data_tag, false)
        {:te, i, "data"}

      [_, "/" <> tag, _] ->
        if Process.get(:data_tag) do
          {nil, i}
        else
          {:te, i, tag}
        end

      [_, "?xml" <> _, _] ->
        {nil, i}

      [_, "!--" <> _, _] ->
        {nil, i}

      [_, "return" <> _, _] ->
        {nil, i}

      [_, tag, _] ->
        if Process.get(:data_tag) do
          {:tv, i, tag, ""}
        else
          {:tb, i, tag}
        end

      _ ->
        {nil, i}
    end
  end
1 Like
2

In Erlang function heads and case are pattern match from top down. I expect Elixir would be similar. In general I prefer ordering in the most readable manner, especially for the poor sod (usually me) who has to support the code.

5 Likes
3

Thinking too much about this is very likely a case of premature optimization: Only if you have an actual implementation that is too slow in a certain regard, and you have benchmarks that measure this, does it make sense to optimize in such a way.

Until you ever reach such a situation, readability is more important than hypothetical speed.

That said, I’m fairly certain (based on earlier papers on the implementations of pattern-matching I read) that Erlang is able to do at least a binary-search if the patterns are restrictive enough. (And patterns/guards that occur in multiple patterns are also probably only executed once). In some limited cases it might even be possible to perform an immediate jump to the correct implementation (such as when all patterns are different consecutive integer values).

In other cases, indeed, the first pattern is matched first, and then we continue on to the next.

2 Likes
4

Actually I have checked and I can tell you first hand, yes, I see some gain when I make this optimization, especially when it’s in a tight loop like have, and there’s substantially more hits of a certain pattern than others.

Moving the more frequently hit pattern to the top does indeed speed things along

2 Likes
5

The Erlang compiler is quite smart when compiling patterns but there are some things which are extremely difficult to optimise. So it can be really smart with atoms, integers, tuples and lists. However strings, and binaries which is how they are implemented, are much more difficult; in many cases it can’t do better then testing them sequentially which is why you can get some improvement by reordering them. This is a case where lists strings can be more efficient. :grinning:

So in your example it can group all the clauses and only do the list checking and extracting only once it still needs to test the strings sequentially.

Note that while the pattern matching compiler may choose to reorder clauses and checking it will semantically always behave as if it is done sequentially.

9 Likes
6

Thanks for the explanation.

This confirms if we know a particular string pattern will be the most frequent, it makes sense to place it first in a sequence of string patterns being matched.

7

I think the most benefit you’ll get by providing the erlang compiler as much room as possible to optimise and reorder the patterns.

I’ve once read a nice article about that topic, but I can not find it right now.

As far as I remember, it suggested to not use “broad” matches inbetween if possible.

[:a, :b, :c] -> ...
[a | _] -> ...
[:a, :c, :b] -> ...

Those 3 matches can’t be rewritten by the compiler into a more effective match, while the following version can be more efficiently transformed into tree-like matching:

[:a, :b, :c] -> ...
[:a, :c, :b] -> ...
[a | _] -> ...

That article gave much better explanations than I could, and also the examples where better, it was erlang syntax though…

8

They also don’t do the same thing, the last [:a, :c, :b] -> match will be optimized out because the prior case matches it.

9

Yeah, my mistake… As I said, the article I read had much better examples… Examples that are actually equivalent :wink:

1 Like
10

Any chance you’d be able to hunt down this article? I’d love to read it :slight_smile:

11

There is the Erlang Efficiency Guide:

1 Like