Elixir Struct Access Efficiency

Question

I am implementing a sorting algorithm to sort a collection of structs. I need to sort the collection on the value of a particular key in each struct. I can hard code the key into the function, but I'd like to generalize it. As you can see below, the specialized implementation is 3x faster than the generalized.

Is there a more efficient way to get the value of a key in a struct than defp get_value(x, key), do: get_in(x, [Access.key(key)])? Which comes from the docs.

Specialized

defmodule QuickSort do
  def qsort([]) do
    []
  end
  def qsort([pivot | rest]) do
    {left, right} = Enum.partition(rest, fn(x) -> x.key < pivot.key end)
    qsort(left) ++ [pivot] ++ qsort(right)
  end
end




iex(74)> Benchwarmer.benchmark fn -> QuickSort.qsort(collection, :key) end                                            
*** #Function<20.52032458/0 in :erl_eval.expr/5> ***
2.5 sec      3 iterations   863742.34 μs/op

Generalized

defmodule QuickSort do
  def qsort(collection, key \\ nil)
  def qsort([], _) do
    []
  end
  def qsort([pivot | rest], key) do
    {left, right} = Enum.partition(rest, fn(x) -> get_value(x, key) < get_value(pivot, key) end)
    qsort(left, key) ++ [pivot] ++ qsort(right, key)
  end

  defp get_value(x, key), do: get_in(x, [Access.key(key)])
end




iex(79)> Benchwarmer.benchmark fn -> QuickSort.qsort(collection, :key) end
*** #Function<20.52032458/0 in :erl_eval.expr/5> ***
3.1 sec      1 iterations   3180784.0 μs/op

Answer 1

get_in(..., [Access.key(key)]) does a lot of things most of which you don't need in this simple example. It's used for accessing nested structures so it needs to iterate over an array of functions (not to mention that you need to create those functions with Access.key). Not surprisingly it's much slower.

Map.get is calling Map.fetch first, then checking if an element exists to substitute it with default if it's not. Again, some extra code.

In my observation the closest thing you can get to .key is Map.fetch. Or if you want to go low-level :maps.find(key, map) (not much advantage over Map.fetch though).

The reason why .key is so efficient is because it's compiled directly into BEAM bytecode without calling external functions.

Answer 2

Map.get will get you pretty close to hardcoded key, but it's not as fast as hardcoded key as Erlang most likely does some extra optimizations for those. Here's your two versions against Map.get:

defmodule Thing do
  defstruct [:key]
end

defmodule QuickSortDotKey do
  def qsort([]), do: []
  def qsort([pivot | rest]) do
    {left, right} = Enum.partition(rest, fn(x) -> x.key < pivot.key end)
    qsort(left) ++ [pivot] ++ qsort(right)
  end
end

defmodule QuickSortAccessKey do
  def qsort([], _), do: []
  def qsort([pivot | rest], key) do
    {left, right} = Enum.partition(rest, fn(x) -> get_value(x, key) < get_value(pivot, key) end)
    qsort(left, key) ++ [pivot] ++ qsort(right, key)
  end

  defp get_value(x, key), do: get_in(x, [Access.key(key)])
end

defmodule QuickSortMapGet do
  def qsort([], _), do: []
  def qsort([pivot | rest], key) do
    {left, right} = Enum.partition(rest, fn(x) -> Map.get(x, key) < Map.get(pivot, key) end)
    qsort(left, key) ++ [pivot] ++ qsort(right, key)
  end
end

defmodule Bench do
  use Benchfella

  bench ".key", [list: gen()] do
    QuickSortDotKey.qsort(list)
  end

  bench "Access.key", [list: gen()] do
    QuickSortAccessKey.qsort(list, :key)
  end

  bench "Map.get", [list: gen()] do
    QuickSortMapGet.qsort(list, :key)
  end

  defp gen, do: for _ <- 1..10000, do: %Thing{key: :rand.uniform}

  # Tests
  list = for _ <- 1..10000, do: %Thing{key: :rand.uniform}
  sorted = Enum.sort_by(list, &(&1.key))
  true = sorted == QuickSortDotKey.qsort(list)
  true = sorted == QuickSortAccessKey.qsort(list, :key)
  true = sorted == QuickSortMapGet.qsort(list, :key)
end

Output:

## Bench
benchmark n iterations   average time
.key               100   15572.13 µs/op
Map.get            100   23042.38 µs/op
Access.key          50   60898.12 µs/op