Skip to content

Instantly share code, notes, and snippets.

@atomkirk
Last active April 15, 2020 21:56
Show Gist options
  • Save atomkirk/6704b1d1b9c646df6f00914c398ce6bb to your computer and use it in GitHub Desktop.
Save atomkirk/6704b1d1b9c646df6f00914c398ce6bb to your computer and use it in GitHub Desktop.
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