Stratus3D

A blog on software engineering by Trevor Brown

Pattern Matching Versus Elixir's Access Behavior

In my last blog post I tried to compare the performance of Elixir’s Access behavior to the Map.get/2 function. While my benchmark did reveal that the Access behavior is a little slower strmpnk on Lobste.rs pointed out a few issues with my benchmarking code. I was generating a new map for every run of the benchmark which put a lot of data on the process heap. The Map.get/2 and the Access behavior both only took just over one microsecond to execute on average so the overhead from all the data in on the heap could easily skew the benchmarks.

New Benchmarks

With the new benchmarking code I only generate a map once and then lookup numerous all the generated keys in the map. Not all keys are present in the map so some lookups will fail. I wanted to test looking up keys that are not present in the map to make it more realistic. Often programs contain conditional logic based on the presence of a key, so I wanted to mirror that in my benchmarking code.

I also updated the code to generate larger maps and lookup more keys. The new code generates maps with 40 keys and tries to lookup 50 different keys. It uses Benchee for the benchmarks. The new benchmarking code looks like this (thanks to strmpnk for this code):

num_map_keys = 40
num_keys_total = 50

keys =
  1..num_keys_total
  |> Enum.map(fn key ->
    Integer.to_string(key)
  end)

map =
  keys
  |> Enum.take_random(num_map_keys)
  |> Map.new(&{&1, true})

num_times = 1..100_000

Benchee.run(%{
  # Compare an empty loop as a baseline
  "baseline" => fn ->
    for _key <- keys, _ <- num_times, do: :ok
    :ok
  end,
  "Map.get" => fn ->
    for key <- keys, _ <- num_times do
      Map.get(map, key)
    end

    :ok
  end,
  "Access" => fn ->
    for key <- keys, _ <- num_times do
      map[key]
    end

    :ok
  end
})

All these functions return :ok instead of the list generated by the for loop. This is to reduce the impact of the list generated by the for loop as it can be garbage collected as soon as the loop finishes. I also have a baseline function that contains the same for loop as the functions, but without the code to lookup values in the map. This allows me to measure the overhead of the for loop and other code in the benchmark functions here.

Pattern Matching

In my last blog post I didn’t consider another option for getting a value out of a map - pattern matching. It’s easy enough to pattern match a value out of a map when you know the key, and it’s the only way to bind a variable to a value in a function head. It’s also available in Erlang and Elixir, unlike the Access behavior and the Map.get/2 function. The only difference is that with pattern matching the map will not match if the key is not found, so we have to use the pattern as a clause in a case statement if we do not want to raise an exception:

  "Pattern Matching" => fn ->
    for key <- keys, _ <- num_times do
      case map do
        %{^key => value} ->
          value

        _ ->
          false
      end
    end

    :ok
  end

Results

Name                       ips        average  deviation         median         99th %
baseline                  8.54      117.08 ms     ±4.28%      115.46 ms      143.10 ms
Pattern Matching          7.72      129.50 ms     ±8.66%      125.02 ms      164.67 ms
Map.get                   2.32      431.59 ms     ±5.07%      424.35 ms      500.32 ms
Access                    1.32      757.32 ms    ±38.46%      565.16 ms     1266.41 ms

Comparison:
baseline                  8.54
Pattern Matching          7.72 - 1.11x slower +12.41 ms
Map.get                   2.32 - 3.69x slower +314.50 ms
Access                    1.32 - 6.47x slower +640.23 ms

Pattern matching was only slightly slower than the baseline benchmark. It was about 3 times faster than Map.get/2 and about 6 times faster than the Access behavior. I expected pattern matching to be faster than the Access behavior, but not expect it to be so much faster than the Map.get/2 function. It’s not immediately clear why it’s so much faster. After all, the Map.get/2 implementation is almost exactly the same as the code I wrote above for the benchmark:

# Map.get/2 implementation

@spec get(map, key, value) :: value
def get(map, key, default \\ nil) do
  case map do
    %{^key => value} ->
      value

    %{} ->
      default

    other ->
      :erlang.error({:badmap, other}, [map, key, default])
  end
end

My theory is the compiler is combining the case statement and the anonymous function in the benchmark code during an optimization pass to reduce the number of reductions needed to execute the code. It’s possible the compiler optimized out the pattern matching code completely, since the value it retrieves is never used. Perhaps I’ll investigate this in a later blog post.

Conclusion

If you are concerned about performance use pattern matching. Pattern matching is one of the core features of the Erlang VM and it’s used extensively in the standard library. In this case Map.get/2 and the Access behavior are using pattern matching under the hood so for whichever method you choose pattern matching will be used to retrieve the value you want to lookup. If pattern matching isn’t easy to do in the context in which you need the value, Map.get/2 performs better than square bracket Access syntax, but is still slower than doing pattern matching directly.

Whether the performance of code used to retrieve a key from a map matters at all in practice is another discussion. In most cases it’s not even something you should think about.

References