Stratus3D

Software Engineering, Web Development and 3D Design

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.

Performance of Elixir's Access Behavior

In Erlang we have two ways of getting a value from a map. We can use map:get/2 or we can pattern match the value out of the list using the #{ key := Value } = Map syntax. In Elixir we have another option Access. With Access we can get values out of a map or a keyword/property list using a square bracket syntax:

map[:key]

What is interesting is that Access was originally implemented as a protocol and was converted to a behavior. Protocols are a way to facilitate polymorphism in Elixir and define a single interface for different data types. You can define a protocol and than implement it for all the built in data types and any custom data types you create. It’s specifically for data types. The protocol was replaced by a behavior because the protocol was too slow. Access is now implemented as a behavior and is much faster.

This got me thinking about the implementation. Is the Access behavior in Elixir just as fast as the map:get/2 function?

Benchmarking the Different Methods

The two implementations I am benchmarking look like this:

defmodule ElixirAccess do
  def get(map, key) do
    map[key]
  end
end

defmodule ElixirMapGet do
  def get(map, key) do
    Map.get(map, key)
  end
end

Building the Benchmark

I decided to benchmark each method by generating lists of a dozen random keys and then building a map containing 75% of those keys. Then I look up each of the generated keys in the map. I repeat the process 50000 times per method and take an average of the execution times. The benchmarking code is shown below:

defmodule ElixirAccessBenchmark do
  @impls [ElixirAccess, ElixirMapGet]
  @times 50000
  @num_keys 12
  # 75% of keys will be in the maps
  @num_keys_to_include 9

  def measure(module, map, keys) do
    {time, :ok} = :timer.tc(__MODULE__, :measure_impl, [module, map, keys])
    time
  end

  def run do
    Enum.each(@impls, fn(module) ->
      IO.puts("Benchmarking #{module}")
      times = run_impl(module)
      len = length(times)
      total = List.foldl(times, 0, fn(time, sum) ->
        time + sum
      end)
      average = total / len
      IO.puts("Average time for looking up all keys was #{inspect(average)} microseconds")
    end)
  end

  def run_impl(module) do
    Enum.map(1..@times, fn(_) ->
      list_of_keys = generate_keys()
      map = generate_map_with_some_keys(list_of_keys)
      measure(module, map, list_of_keys)
    end)
  end

  def measure_impl(module, map, keys) do
    Enum.each(keys, fn(key) ->
      _ = apply(module, :get, [map, key])
    end)
  end

  defp generate_keys do
    1..@num_keys
    |> Enum.to_list()
    |> Enum.map(fn(key) ->
      Integer.to_string(key)
    end)
  end

  defp generate_map_with_some_keys(keys) do
    keys
    |> Enum.take_random(@num_keys_to_include)
    |> Map.new(fn(key) ->
      {key, true}
    end)
  end
end

ElixirAccessBenchmark.run()

Results

Running the exs file containing this code produced the following output:

Benchmarking Elixir.ElixirAccess
Average time for looking up all keys was 1.0482 microseconds
Benchmarking Elixir.ElixirMapGet
Average time for looking up all keys was 1.0430 microseconds

I ran the script several times and consistently got similar numbers.

  • Access: 1.0482 microseconds average

  • Map.get/2: 1.0430 microseconds average

Conclusion

The Access behavior does have to do type checking at some point during execution to determine whether or not it’s dealing with a map or keyword list. That type checking isn’t free but it only makes the square bracket syntax 0.5% slower than Map.get/2. With such a minor small difference in execution time the square bracket syntax should not have a noticeable affect on performance when running real Elixir applications. Obviously the less type checking you can do the faster your app will be, but in cases like this it’s not something that will ever become a bottleneck, even when your app is pushed to the limits.

If you don’t care about performance you can safely use either of these methods to lookup values in a map. The Access behavior is only 0.5% slower, so even if you are concerned about performance there are probably other things in your codebase that are having a greater impact on the performance than the square bracket syntax.

OTP Cheatsheet

OTP cheatsheet webpage screenshot

A last year I created an Erlang cheatsheet. I goal was to keep it fairly simple and only include the things that I often forgot. I decided to limit it to a single page so I could print it out and pin it on the wall for reference. I’ve been doing a lot of Elixir recently, but the cheatsheet has still be useful to me and my coworkers. There are a lot of things I often have to lookup with working with supervisors and other OTP behaviors so this month I decided it would be nice to have a seperate cheatsheet for OTP. This new cheatsheet follows in the same vein as my Erlang cheatsheet. It is intended for those experienced with OTP and not beginners.

The cheatsheet is available for you to freely print or download at https://stratus3d.com/otp-cheatsheet/. The source code has been released under the MIT license and is available in the same repository as the Erlang cheatsheet on GitHub at Stratus3D/erlang-cheatsheet.

I’d really like to hear your thoughts on this new OTP cheatsheet. Is there something it is missing? Is there something that can be simplified or removed?

Let me know via email or twitter. If you want to contribute directly feel free to create an issue or pull request on the GitHub repository.