Elixir/Erlang: Fast lookup with static table

Question

In my application I need to convert integer to some term; for example:

1 → :red
2 → :green
3 → :blue

The table is static, it is known during compilation time and its indices range from <1, n>. There is around 60 of them.

In which way should the table be represented, so the lookup is the fastest? Dict, HashDict, tuple (with kernel.elem()), ets, function with pattern matching...?

Answer 1

As Julius Beckmann suggested in this case functions with pattern matching should be sufficient as they are according to my measurements over 5 times faster than accessing a map.

Below you can find an implementation of what you are looking for (benchmark code included at the bottom):

defmodule TermLookUpByInteger do
  @term_by_integer %{
    1 => :aa, 11 => :ba, 21 => :ca, 31 => :da, 41 => :ea, 51 => :fa, 61 => :ga,
    2 => :ab, 12 => :bb, 22 => :cb, 32 => :db, 42 => :eb, 52 => :fb, 62 => :gb,
    3 => :ac, 13 => :bc, 23 => :cc, 33 => :dc, 43 => :ec, 53 => :fc, 63 => :gc,
    4 => :ad, 14 => :bd, 24 => :cd, 34 => :dd, 44 => :ed, 54 => :fd, 64 => :gd,
    5 => :ae, 15 => :be, 25 => :ce, 35 => :de, 45 => :ee, 55 => :fe, 65 => :ge,
    6 => :af, 16 => :bf, 26 => :cf, 36 => :df, 46 => :ef, 56 => :ff, 66 => :gf,
    7 => :ag, 17 => :bg, 27 => :cg, 37 => :dg, 47 => :eg, 57 => :fg, 67 => :gg,
    8 => :ah, 18 => :bh, 28 => :ch, 38 => :dh, 48 => :eh, 58 => :fh, 68 => :gh,
    9 => :ai, 19 => :bi, 29 => :ci, 39 => :di, 49 => :ei, 59 => :fi, 69 => :gi,
    0 => :aj, 10 => :bj, 20 => :cj, 30 => :dj, 40 => :ej, 50 => :fj, 60 => :gj,
  }

  @doc """
    iex> TermLookUpByInteger.lookup_pmf(2)
    :ab
  """
  def lookup_pmf(int), do: do_lookup(int)

  for {int, term} <- @term_by_integer do
    defp do_lookup(unquote(int)), do: unquote(term)
  end

  @doc """
    iex> TermLookUpByInteger.lookup_m(3)
    :ac
  """
  def lookup_m(int), do: @term_by_integer[int]
end

# Benchmark:

n = 1_000_000
range = 1..(n)
measure = fn fun -> :timer.tc(fn -> for _ <- range, do: fun.() end) end
{time_pmf, _result} = measure.(fn -> TermLookUpByInteger.lookup_pmf(:random.uniform(60)) end)
{time_m, _result}   = measure.(fn -> TermLookUpByInteger.lookup_m(:random.uniform(60)) end)

IO.puts "                      Sample size: #{n}"
IO.puts "Pattern matching functions lookup: #{time_pmf/1000} ms"
IO.puts "                       Map lookup: #{time_m/1000} ms"
IO.puts "              Absolute Difference: #{(time_pmf-time_m)/1000} ms"
IO.puts "              Relative Difference: #{round((time_pmf-time_m)/time_m*100)}%"
IO.puts "                           Faster: x #{Float.round(time_m/time_pmf, 2)} times"

Results:

                      Sample size: 1000000
Pattern matching functions lookup: 447.6 ms
                       Map lookup: 2423.517 ms
              Absolute Difference: -1975.917 ms
              Relative Difference: -82%
                           Faster: x 5.41 times

I hope that will be useful.