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.
I'd use Benchee for this @atomkirk: