Tuples are contiguous in memory, while lists are not. This should mean that iteration over tuples can be faster than lists, however I am unable to actually achieve this. I’ve come up with the following Benchee to highlight:
Name ips average deviation median 99th %
tuple_comp 53.02 K 18.86 μs ±31.14% 17.62 μs 38.55 μs
list_iter_recursive 11.79 K 84.80 μs ±122.94% 76.53 μs 204.74 μs
list_comp 9.28 K 107.81 μs ±19.39% 102.72 μs 186.49 μs
tuple_iter_no_check 7.69 K 130.08 μs ±25.14% 121.61 μs 244.62 μs
tuple_iter 6.23 K 160.46 μs ±22.88% 147.60 μs 301.26 μs
list_iter 2.13 K 469.78 μs ±10.40% 447.09 μs 649.97 μs
Comparison:
tuple_comp 53.02 K
list_iter_recursive 11.79 K - 4.50x slower +65.94 μs
list_comp 9.28 K - 5.72x slower +88.95 μs
tuple_iter_no_check 7.69 K - 6.90x slower +111.22 μs
tuple_iter 6.23 K - 8.51x slower +141.60 μs
list_iter 2.13 K - 24.91x slower +450.92 μs
Memory usage statistics:
Name Memory usage
tuple_comp 0 B
list_iter_recursive 0 B - 1.00x memory usage +0 B
list_comp 0 B - 1.00x memory usage +0 B
tuple_iter_no_check 1816 B - ∞ x memory usage +1816 B
tuple_iter 0 B - 1.00x memory usage +0 B
list_iter 0 B - 1.00x memory usage +0 B
**All measurements for memory usage were the same**
What this measures is tuple comparison being the fastest, followed by recursive list iteration, then list comparison, followed by two forms of tuple iteration, and finally list iteration using an Elixir standard library function.
And the code for each of the test cases:
list = Enum.to_list(1..50_000)
list2 = Enum.to_list(1..50_000)
tuple = List.to_tuple(list)
tuple2 = List.to_tuple(list)
tuple_size = tuple_size(tuple)
iter = Enum.to_list(1..1000)
defmodule BenchMod do
# Function to iterate over a tuple with a bounds check.
def tuple_iter(_, tuple_size, tuple_size), do: :ok
def tuple_iter(tuple, tuple_size, idx) do
_ = elem(tuple, idx)
tuple_iter(tuple, tuple_size, idx + 1)
end
# Function to iterate over a tuple without a bounds check.
def tuple_iter_no_check(tuple, idx) do
_ = elem(tuple, idx)
tuple_iter_no_check(tuple, idx + 1)
end
# Function to iterate over a list.
def list_iter([]), do: :ok
def list_iter([_h|t]) do
list_iter(t)
end
end
list_iter = fn ->
Enum.each(list, fn _y -> :ok end)
end
list_iter_recursive = fn ->
BenchMod.list_iter(list)
end
tuple_iter = fn ->
BenchMod.tuple_iter(tuple, tuple_size, 0)
end
tuple_iter_no_check = fn ->
try do
BenchMod.tuple_iter_no_check(tuple, 0)
rescue
_e -> :ok
end
end
list_comp = fn ->
list == list2
end
tuple_comp = fn ->
tuple == tuple2
end
Benchee.run(
%{
"list_iter" => list_iter,
"list_iter_recursive" => list_iter_recursive,
"tuple_iter" => tuple_iter,
"tuple_iter_no_check" => tuple_iter_no_check,
"list_comp" => list_comp,
"tuple_comp" => tuple_comp
},
time: 20,
memory_time: 2
)
I think it makes sense that tuple iteration the way that I have implemented it is slower, the BenchMod.tuple_iter/3 function has a size check. BenchMod.tuple_iter_no_check removes that check and becomes much faster using a try/catch to terminate iteration as a quick cheat. The enum and list variants aren’t completely similar as the list iterations discards the head of the list while the enum forces an access using elem and I assume uses an extra reduction to do so.
Beyond these initial thoughts is there any way to make tuple iteration as fast or faster than lists?