Structs: pattern matching on nil values

Ahh, I think I was thinking about lists (as lists are the default ‘string’ type in erlang):

##### With input binary #####
Name                ips        average  deviation         median         99th %
guard_top       34.09 K       29.34 μs    ±74.54%          28 μs          45 μs
guard_bot       30.61 K       32.67 μs    ±74.42%          31 μs          48 μs
match_bot       22.81 K       43.85 μs    ±35.95%          41 μs          78 μs
match_top       22.38 K       44.69 μs    ±38.02%          43 μs          67 μs

Comparison: 
guard_top       34.09 K
guard_bot       30.61 K - 1.11x slower
match_bot       22.81 K - 1.49x slower
match_top       22.38 K - 1.52x slower

##### With input list #####
Name                ips        average  deviation         median         99th %
match_bot       34.39 K       29.08 μs    ±65.78%          28 μs          41 μs
guard_top       34.24 K       29.21 μs    ±54.19%          28 μs          45 μs
match_top       31.49 K       31.75 μs    ±61.61%          31 μs          46 μs
guard_bot       31.25 K       32.00 μs    ±57.29%          31 μs          49 μs

Comparison: 
match_bot       34.39 K
guard_top       34.24 K - 1.00x slower
match_top       31.49 K - 1.09x slower
guard_bot       31.25 K - 1.10x slower

##### With input not binary #####
Name                ips        average  deviation         median         99th %
guard_bot       31.18 K       32.07 μs    ±63.11%          31 μs          44 μs
guard_top       31.15 K       32.10 μs    ±58.90%          30 μs          50 μs
match_bot       29.16 K       34.30 μs    ±38.15%          33 μs          49 μs
match_top       27.41 K       36.48 μs    ±36.63%          35 μs          52 μs

Comparison: 
guard_bot       31.18 K
guard_top       31.15 K - 1.00x slower
match_bot       29.16 K - 1.07x slower
match_top       27.41 K - 1.14x slower

Substantial performance difference on binaries though (a good 50% slower for match contexts)! And of course the list test is faster than the binary test regardless of how it is done (the BEAM is built for lists instead of binaries when processing them out). ^.^

EDIT: The code is about the same is @michalmuskala’s except the count is increased to 1000 to prevent fast function warnings and I added some tuple cases to each set (unmatched in all cases) with the string/list test being at the top or bottom of the tuple matchers as per the test name.

Ooo really? Interesting… Back in the day just by swapping from guards to match’s of precisely that style on erlang more than doubled the speed of things I made that were head-heavy. At least back then I remember Guards being run ‘after’ the match tree had been run, so if you had any kind of sizeable head-count for functions/cases then lifting more into the match context would be quite valuable. Fascinating though, thanks for the benchmark, though I wonder if that holds true with large head counts still?

This is not true. At least not on today’s BEAM. Matching on <<_:binary>> is going to be faster, if you’re doing a binary pattern match already, to keep the “single match context” optimization. But if you’re only checking if something is a binary, it’s going to be slower. This is primarily because it needs to allocate the match context (which creates garbage on the heap that will lead to sooner garbage collection), while checking is_binary does not involve any memory movements. This memory access (and GC jitter) can be seen in the increased deviation of the benchmark.

Operating System: macOS
CPU Information: Intel(R) Core(TM) i7-4770HQ CPU @ 2.20GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.6.0-dev
Erlang 20.1
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
parallel: 1
inputs: binary, not binary
Estimated total run time: 28 s

##### With input binary #####
Name            ips        average  deviation         median         99th %
guard      436.27 K        2.29 μs    ±34.28%        2.10 μs        4.20 μs
match      236.41 K        4.23 μs  ±1391.73%           4 μs          11 μs

Comparison:
guard      436.27 K
match      236.41 K - 1.85x slower

##### With input not binary #####
Name            ips        average  deviation         median         99th %
guard      448.69 K        2.23 μs    ±35.38%           2 μs        4.40 μs
match      431.08 K        2.32 μs    ±43.81%        2.20 μs        4.60 μs

Comparison:
guard      448.69 K
match      431.08 K - 1.04x slower

The benchmark code:

defmodule Bench do
  def match(<<_::binary>>), do: :binary
  def match(_), do: :not_binary

  def guard(binary) when is_binary(binary), do: :binary
  def guard(_), do: :not_binary

  def loop(0, _fun) do
    :ok
  end
  def loop(n, fun) do
    fun.()
    loop(n - 1, fun)
  end
end

jobs = %{
  "match" => fn input -> Bench.loop(100, fn -> Bench.match(input) end) end,
  "guard" => fn input -> Bench.loop(100, fn -> Bench.guard(input) end) end
}

inputs = %{
  "binary" => "foo",
  "not binary" => 123
}

Benchee.run(jobs, inputs: inputs)

How would you do that?

A struct is just a map, so worst-case someone could just Map.put(someStruct, :theKey, nil)…

I came from the erlang world with a lot of network parsing, I’ve been working with the BEAM off and on for ~15 years I think now (early 2000’s). ^.^

Not necessarily. One could forbid keeping nil values in structs but keep the set of possible keys somewhere else (which, in turn, might be useful for defining the order of keys for instance).

Interesting, I would not have guessed. Did you learn it by trying to optimize some code or by learning BEAM internals?

That is entirely dictated by the BEAM VM itself.

As for structs, they act very much like ‘records’ from Erlang.

And to do something like having match?(%A{a: a}, %A{}) return false then it would have to have a guard, and guards introduce a non-trivial hit in processing time (doing <<_:binary>> is faster than doing s when is_binary(s) for one example), which is dreadfully important at times.

Ben, thanks a lot for your detailed answer. I was probably not clear enough about it, but I am not interested in match? per se but rather in the design decision behind pattern matching implementation for structs. Given that I understand how structs are implemented I see that pattern matching works in a most straightforward way.

It provides tons of value if you include a pattern on those members, or if you include those members in a guard.

Let’s filter all As that are empty

as |> Enum.filter(&match?(%A{a: []}, &1))

Ultimately the whole point of match? is that it works exactly like:

case value do
  %A{a: a} -> true
  _ -> false
end

If you want some other characteristic then you want some other function.

We are more than happy to try to help provide the most idiomatic way to achieve whatever your goal is in this situation. Just understand that suggestions that involve breaking changes to core functions are unlikely to gain a lot of traction.

Thanks for the suggestions. Indeed, !! won’t work within a function signature unfortunately.

Oh, I thought the goal was to get a false.