CharlesO
Does placing the most likely-matched function heads first offer any benefit?
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
Trending in Questions
Other Trending Topics
Latest on Elixir Forum
Sponsor Spotlight
Phoenix, LiveView, multimedia pipelines, distributed systems. 400 engineers, Elixir since 2017. Available for hire.
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #channels
- #elixirconf
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #phoenix_html
- #iex
- #blog-post
- #graphql
- #genstage
- #ai
- #elixirconf-us
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #api
- #forms
- #metaprogramming
- #performance
- #security
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Error tracking, logs, uptime, and Just Enough APM. Built for developers.
Practical resources that improve the lives of professional developers.
Develop your skills with books, videos, and courses.
The deployment platform built for Elixir: PaaS ease, VPS control.
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"
First 10 of 10 Posts
tty
In Erlang
function headsandcaseare 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.Qqwy
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.
CharlesO
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
rvirding
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.
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.
CharlesO
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.
NobbZ
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.
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:
That article gave much better explanations than I could, and also the examples where better, it was erlang syntax though…
OvermindDL1
They also don’t do the same thing, the last
[:a, :c, :b] ->match will be optimized out because the prior case matches it.NobbZ
Yeah, my mistake… As I said, the article I read had much better examples… Examples that are actually equivalent
venkatd
Any chance you’d be able to hunt down this article? I’d love to read it
peerreynders
There is the Erlang Efficiency Guide: