Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
elixir tuple constant time

Whats the fastest way to look up an index in Elixir?

Lets create a long list of a million items and look up the 500,000th item

iex(54)> range = 1..1_000_000
1..1000000

iex(55)> index = 500_000
500000

iex(57)> list = range |> Enum.map(& &1)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]

iex(58)> tuple = List.to_tuple(list)
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...}

iex(59)> map = list |> Enum.with_index() |> Map.new()
%{
  702155 => 702154,
  868847 => 868846,
  899014 => 899013,
  ...
}

Here we can see that looking up an index in a linked list is very slow compared to looking up an index in a map or tuple:

iex(61)> :timer.tc(fn -> Enum.each(1..1000, fn _ -> list |> Enum.at(index) end) end)
{2154386, :ok}
iex(62)> :timer.tc(fn -> Enum.each(1..1000, fn _ -> tuple |> elem(index) end) end)
{1357, :ok}
iex(63)> :timer.tc(fn -> Enum.each(1..1000, fn _ -> map[index] end) end)
{1065, :ok}

So, which is faster? A tuple or a map?

iex(65)> :timer.tc(fn -> Enum.each(1..1_000_000, fn _ -> tuple |> elem(index) end) end)
{1272816, :ok}
iex(66)> :timer.tc(fn -> Enum.each(1..1_000_000, fn _ -> map[index] end) end)
{1065876, :ok}

A map keyed by index is even faster than a tuple. My guess is that even though a tuple is laid out in memory sequentially, you can't just <memory_address_of_first_item> + index because items in the tuple don't have to be the same type/size.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment