Stratus3D

Software Engineering, Web Development and 3D Design

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.

Fibonacci Algorithms in Elixir - Part 2

Another look at algorithm time complexity

In my last post I wrote about various Fibonacci implementations in Elixir. I timed each implementation generating a list of the first N Fibonacci numbers, and compared the performance characteristics of each implementation. Based on what unwind said on Lobsters in response I decided to revisit Fibonacci implementations in Elixir. I’m going to update the implementatios I used in my last blog post so they use Erlang processes to store previously computed Fibonacci numbers. I’ll then benchmark each implementation against the Fibonacci implementation to see how much processes sped things up.

Rewriting the Algorithms

I needed to have a process for each algorithm to store the computed Fibonacci numbers. I chose to create a single generic GenServer that I could spawn for each algorithm I was testing. Below is the implementation I settled on. It’s fairly straightforward. The only thing special about this GenServer code is that it allows the caller to specify the server they want to use. This is necessary because I will have multiple processes running different instances of this GenServer. One for each implementation I am testing. I need to have a different FibStore server because each algorithm is different so I need to make sure I store and fetch Fibonacci numbers from the correct server.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
defmodule FibStore do
  use GenServer

  def do_fib(name, number, fib_fun) do
    case get(name, number) do
      nil ->
        result = fib_fun.(number)
        put(name, number, result)
        result
      result ->
        result
    end
  end

  defp get(name, number) do
    GenServer.call(name, {:get, number})
  end

  defp put(name, number, value) do
    GenServer.call(name, {:put, number, value})
  end

  def maybe_start(name) do
    case GenServer.start_link(__MODULE__, [], [name: name]) do
      {:ok, _pid} ->
        :ok
      {:error, {:already_started, _pid}} ->
        :ok
    end
  end

  # GenServer callbacks
  def init(_) do
    {:ok, %{}}
  end

  def handle_call({:get, number}, _from, state) do
    {:reply, Map.get(state, number), state}
  end

  def handle_call({:put, number, value}, _from, state) do
    {:reply, :ok, Map.put(state, number, value)}
  end
end

Next I needed to update the existing functions to use this new GenServer for fetching and storing values. The previous implementations had a fib function that performed the actual computation. To avoid modifying a lot of code I added a new function named do_fib that only calls the existing fib function to do the computation if the Fibonacci number has not already been computed and stored in the GenServer instance. Below are the three new implementations:

My Implementation

In my updated implementation so that the fib clause for generating any number after the first two in the Fibonacci sequence invokes FibStore.do_fib/3. This ensures it will reuse already an computed number if there is one. Otherwise FibStore.do_fib/3 will invoke fib/1 to compute and store the number.

1
2
3
4
5
6
7
8
9
10
11
12
13
defmodule MyFib do
  def fibonacci(number) do
    FibStore.maybe_start(__MODULE__)
    Enum.reverse(FibStore.do_fib(__MODULE__, number, &fib/1))
  end

  def fib(0), do: [0]
  def fib(1), do: [1|fib(0)]
  def fib(number) when number > 1 do
    [x, y|_] = all = FibStore.do_fib(__MODULE__, number-1, &fib/1)
    [x + y|all]
  end
end

Rosetta Code

In much the same way I changed the Rosetta Code algorithm. It invokes FibStore.do_fib/3 when computing Fibonacci numbers so it uses pre-computed numbers if exist in the FibStore process. Otherwise it invokes fib/1 to compute the Fibonacci number. Note that unlike my implementation this one must recompute everything when generating a new number in the sequence. For example, when generating the fifth number it would not be able to reuse the 2 and the 3 cached in the FibStore process. I could not make it reuse pre-computed numbers without changing the way the fib/3 function works.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
defmodule RosettaCodeFib do
  def fibonacci(number) do
    FibStore.maybe_start(__MODULE__)
    Enum.map(0..number, fn(n) -> FibStore.do_fib(__MODULE__, n, &fib/1) end)
  end

  def fib(0), do: 0
  def fib(1), do: 1
  def fib(n), do: fib(0, 1, n-2)

  def fib(_, prv, -1), do: prv
  def fib(prvprv, prv, n) do
    next = prv + prvprv
    fib(prv, next, n-1)
  end
end

Popular Implementation/Dave Thomas

This implementation benefited the most from the FibStore caching of pre-computed numbers. It remains similar to the original implementation, but now it invokes FibStore.do_fib/3 when computing numbers. Due to the recursive nature of the fib/1 function, calls are made to FibStore.do_fib/3 for every number that must be computed. This implementation is able to use the pre-computed numbers as a starting point when computing new numbers. Unlike the Rosetta Code implementation which cannot.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
defmodule ThomasFib do
  def fibonacci(number) do
    FibStore.maybe_start(__MODULE__)
    Enum.map(0..number, fn(n) -> do_fib(n, &fib/1) end)
  end

  def fib(0), do: 0
  def fib(1), do: 1
  def fib(n), do: do_fib(n-1, &fib/1) + do_fib(n-2, &fib/1)

  defp do_fib(number, fun) do
    FibStore.do_fib(__MODULE__, number, fun)
  end
end

Which function generates a list of Fibonacci numbers the fastest?

My bet was that my implementation would still perform better than the others, but I wasn’t sure which of the others would be the fastest. The Rosetta Code algorithm wasn’t able to leverage the FibStore caching as much as others; but then again it was already a fairly fast algorithm.

Benchmarking

I reused my benchmarking code from the first blog post. See the source file for the benchmarking code.

Since the new algorithms now maintain state their performance on the first run will differ from their performance on all subsequent runs. I decided I would run the benchmarks once to capture the performance on initial runs. Then I would run the benchmarks four more times to measure the performance on subsequent runs just as I did in my first blog post.

Results

Initial Run

I ran the benchmark once to capture the performance when no state. Time is in microseconds.

Number Rosetta Code Dave Thomas’
Mine
3 36 83 30
5 22 56 16
10 76 69 31
20 87 111 48
30 144 133 56
45 143 205 87

Four Subsequent Runs

After the first run I ran the benchmark again against each algorithm four times. The average run times are shown in the table below in microseconds.

Number Rosetta Code Dave Thomas’
Mine
3 13 22 5
5 17 15 3
10 21 25 5
20 55 40 4
30 64
65 3
45 78 94 4

For comparison here are the average run times of the original algorithms:

List Size Rosetta Code Dave Thomas’ Mine
3 4 543 1
5 2 3 0
10 8 11 0
20 5 880 4
30 8 97500 1
45 17 131900822 2

Conclusion

Looking at the data in these tables it’s clear the Dave Thomas algorithm benefited the most from the new process caching of computed numbers. This isn’t surprising due to the increasing number of recursive calls the original algorithm used when computing large numbers. It’s clear from the run times that the time complexity of the original algorithm was exponential. With the process caching in place the time complexity is no longer exponential. I didn’t take the time to figure it out, but I would guess the new Dave Thomas’ algorithm with process caching has linear time complexity.

The Rosetta Code algorithm doesn’t really benefit from the new process caching. The performance characteristics remain the same, and it runs nearly 5 times slower. My algorithm did not benefit from the process caching either. It ran about 4 times slower than the original algorithm. Even though processes are cheap on the Erlang VM, and local messages are fast it’s clear the overhead of caching the data in a separate process is taking a toll on these algorithms. Sending a message is cheap, but eventually the time it takes for the process to be scheduled after receiving a message adds up. When no data is cached these algorithms must send and receive at least 2 messages for every recursion needed to compute the final number. Even when the number has already been computed two messages are needed to fetch the number. The two original algorithms performed well by keep pre-computed numbers in process memory and reusing them when necessary, so this caching only reduces the arithmetic operations needed on subsequent calls. And even on subsequent calls the overhead of sending and receiving two messages is greater than the cost of computing the list of Fibonacci numbers all over again; at least for the first 45 Fibonacci numbers in the sequence.

When it comes to generating a list of the first N Fibonacci numbers my original algorithm still seems to be the fastest out of all the algorithms I’ve tested. My algorithm was designed from the ground up for specifically for generating a list of the first N Fibonacci numbers in the sequence so I think the take away here is that code written for a specific task may outperform code that is more general purpose.

Resources