Disassembling pattern matching
In my ElixirConf talk I said that pattern matching doesn't work in the magical way that many of us might think it does. As demonstrated in the talk, this is true enough when using guard clauses. But what if we're only matching on different arguments? Let's take a closer look.
We start with a simple multi-clause function. Given the atom :a it returns 1000, given :bit returns 2000, and given :c it returns 3000.
defmodule Pattern do
def matching(:a), do: 1000
def matching(:b), do: 2000
def matching(:c), do: 3000
end
We compile the module, enter iex, and disassemble the function using :erts_debug.df.
$ elixirc pattern.ex
$ iex
Erlang/OTP 18 [erts-7.1] [source] [64-bit] [smp:8:8]
[async-threads:10] [hipe] [kernel-poll:false] [dtrace]
Interactive Elixir (1.1.1) - press Ctrl+C to exit
(type h() ENTER for help)
iex(1)> :erts_debug.df Pattern, :matching
:ok
This gives us a .dis file that we can open to see the transformed and optimised instructions of the loaded module rather than that of the BEAM file.
0000000021A92EC0: i_func_info_IaaI 0 'Elixir.Pattern' matching 1
0000000021A92EE8: i_select_val_lins_rfI x(0) f(0000000021A92EC0) 4
c a b -1
f(0000000021A92F40) f(0000000021A92F60)
f(0000000021A92F50) f(0000000021A92EC0)
0000000021A92F40: move_return_cr 3000 x(0)
0000000021A92F50: move_return_cr 2000 x(0)
0000000021A92F60: move_return_cr 1000 x(0)
Notice the i_select_val_lins instruction. I couldn't find any documentation on it, but it seems to work somewhat similar to the i_select_val instruction (documented here). The operands list rfi indicates three operands; r for the x(0) register, f for the default jump address, and I for the number of alternatives. Following these operands are the alternatives. They are effectively a number of key-value pairs, except the pairs have been split into two sequences of keys and values (actually jump addresses).
Given a value in x(0), which will contain the argument of our matching function, go through the keys of the alternatives. If a match is found, continue execution at the corresponding jump address.
Yes, this does look like a switch statement condensed into a single instruction.
Notice how the second operand, the default jump address, is repeated as the key-pair -1 and f(0000000021A92EC0). Interestingly, this is the address of the disassembled function. Not quite sure how this results in a FunctionClauseError when invoking matching with e.g. the atom :d.
Duplicating the default jump address as part of the list of alternatives if we add a another function clause, catching all previously non-matching parameters passed to our function.
defmodule Pattern do
def matching(:a), do: 1000
def matching(:b), do: 2000
def matching(:c), do: 3000
def matching(_default), do: 1_000_000
end
Once again, notice how the default jump address corresponds to the final alternative.
000000001F28AB00: i_func_info_IaaI 0 'Elixir.Pattern' matching 1
000000001F28AB28: i_select_val_lins_rfI x(0) f(000000001F28ABB0) 4
c a b -1
f(000000001F28AB80) f(000000001F28ABA0)
f(000000001F28AB90) f(000000001F28ABB0)
000000001F28AB80: move_return_cr 3000 x(0)
000000001F28AB90: move_return_cr 2000 x(0)
000000001F28ABA0: move_return_cr 1000 x(0)
000000001F28ABB0: move_return_cr 1000000 x(0)
Okay, but what if we add additional function clauses, matching on numbers rather than atoms?
defmodule Pattern do
def matching(:a), do: 1000
def matching(:b), do: 2000
def matching(:c), do: 3000
def matching(123), do: :alpha
def matching(456), do: :beta
def matching(789), do: :gamma
def matching(_default), do: 1_000_000
end
Loading and disassembling this gives us this:
000000001F100E40: i_func_info_IaaI 0 'Elixir.Pattern' matching 1
000000001F100E68: is_atom_fr f(000000001F100F00) x(0)
000000001F100E78: i_select_val_lins_rfI x(0) f(000000001F100F88) 4
c a b -1
f(000000001F100ED0) f(000000001F100EF0)
f(000000001F100EE0) f(000000001F100F88)
000000001F100ED0: move_return_cr 3000 x(0)
000000001F100EE0: move_return_cr 2000 x(0)
000000001F100EF0: move_return_cr 1000 x(0)
000000001F100F00: i_select_val_lins_rfI x(0) f(000000001F100F88) 4
123 456 789 -1
f(000000001F100F78) f(000000001F100F68)
f(000000001F100F58) f(000000001F100F88)
000000001F100F58: move_return_cr gamma x(0)
000000001F100F68: move_return_cr beta x(0)
000000001F100F78: move_return_cr alpha x(0)
000000001F100F88: move_return_cr 1000000 x(0)
This gives us two i_select_val_lins instructions, one for handling the atoms and one for handling the integers. At the top of the function we have the is_atom instruction that decides which to use. Well, that still looks rather nice and tidy. But what happens if we reorder the function clauses, mixing and matching atoms and integers?
defmodule Pattern do
def matching(:a), do: 1000
def matching(123), do: :alpha
def matching(:b), do: 2000
def matching(456), do: :beta
def matching(:c), do: 3000
def matching(789), do: :gamma
def matching(_default), do: 1_000_000
end
It turns out the disassembled code looks the same as before.
000000001EF809C0: i_func_info_IaaI 0 'Elixir.Pattern' matching 1
000000001EF809E8: is_atom_fr f(000000001EF80A80) x(0)
000000001EF809F8: i_select_val_lins_rfI x(0) f(000000001EF80B08) 4
c a b -1
f(000000001EF80A50) f(000000001EF80A70)
f(000000001EF80A60) f(000000001EF80B08)
000000001EF80A50: move_return_cr 3000 x(0)
000000001EF80A60: move_return_cr 2000 x(0)
000000001EF80A70: move_return_cr 1000 x(0)
000000001EF80A80: i_select_val_lins_rfI x(0) f(000000001EF80B08) 4
123 456 789 -1
f(000000001EF80AF8) f(000000001EF80AE8)
f(000000001EF80AD8) f(000000001EF80B08)
000000001EF80AD8: move_return_cr gamma x(0)
000000001EF80AE8: move_return_cr beta x(0)
000000001EF80AF8: move_return_cr alpha x(0)
000000001EF80B08: move_return_cr 1000000 x(0)
Now, if we were to reduce the number of patterns matched on by removing an atom-handling function clause, say :c, we would get a very different disassembled code. The same holds true if we were to only handle two numbers or only match on sequential numbers, e.g. 1, 2, 3 instead of our 123, 456, 789.
How the disassembled code looks in those cases? For now, I leave that as an exercise to you, the reader.