benchmark.exs

Mix.install([
  {:benchee, "~> 1.0"}
])

defmodule Benchmark do

  def reduce(items, y) do
    {items, _} = Enum.reduce(items, {[], y},
      fn %{height: h} = item, {converted_items, y} -> {converted_items ++ [%{item | y: y}], y + h} end)
    items
  end

  def reduce_with_reverse(items, y) do
    {items, _} = Enum.reduce(items, {[], y},
      fn %{height: h} = item, {converted_items, y} -> {[%{item | y: y} | converted_items], y + h} end)
    Enum.reverse(items)
  end

  def map_reduce(items, y) do
    {items, _} = Enum.map_reduce(items, y, fn item, acc -> {Map.put(item, :y, acc), acc + item.height} end)
    items
  end

  def recursion([], _), do: []
  def recursion([%{height: h} = item | t], y), do: [%{item | y: y} | recursion(t, h + y)]

  def tail_recursion(items, y, converted_items \\ [])
  def tail_recursion([], _y, converted_items), do: converted_items
  def tail_recursion([h | t], y, converted_items), do:
    tail_recursion(t, y + h.height, converted_items ++ [%{y: y, height: h.height}])

  def tail_recursion_with_reverse(items, y, converted_items \\ [])
  def tail_recursion_with_reverse([], _y, converted_items), do: Enum.reverse(converted_items)
  def tail_recursion_with_reverse([h | t], y, converted_items), do:
    tail_recursion_with_reverse(t, y + h.height, [%{y: y, height: h.height} | converted_items])

end

Benchee.run(
  %{
    "tail_recursion" =>              fn(items) -> Benchmark.tail_recursion(items, 1)              end,
    "tail_recursion_with_reverse" => fn(items) -> Benchmark.tail_recursion_with_reverse(items, 1) end,
    "recursion" =>                   fn(items) -> Benchmark.recursion(items, 1)                   end,
    "reduce" =>                      fn(items) -> Benchmark.reduce(items, 1)                      end,
    "reduce_with_reverse" =>         fn(items) -> Benchmark.reduce_with_reverse(items, 1)         end,
    "map_reduce" =>                  fn(items) -> Benchmark.map_reduce(items, 1)                  end
  },
  inputs: %{
    "'list with 10 items'" =>      0..10      |> Enum.map(fn _ -> %{height: 1, y: 0} end),
    "'list with 1_000 items" =>    0..1_000   |> Enum.map(fn _ -> %{height: 1, y: 0} end),
    "'list with 100_000 items'" => 0..100_000 |> Enum.map(fn _ -> %{height: 1, y: 0} end)
  }
)

result.txt

Operating System: Linux
CPU Information: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
Number of Available Cores: 8
Available memory: 3.53 GB
Elixir 1.13.2
Erlang 24.3.2

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
reduction time: 0 ns
parallel: 1
inputs: 'list with 10 items', 'list with 100_000 items', 'list with 1_000 items
Estimated total run time: 2.10 min

Benchmarking map_reduce with input 'list with 10 items' ...
Benchmarking map_reduce with input 'list with 100_000 items' ...
Benchmarking map_reduce with input 'list with 1_000 items ...
Benchmarking recursion with input 'list with 10 items' ...
Benchmarking recursion with input 'list with 100_000 items' ...
Benchmarking recursion with input 'list with 1_000 items ...
Benchmarking reduce with input 'list with 10 items' ...
Benchmarking reduce with input 'list with 100_000 items' ...
Benchmarking reduce with input 'list with 1_000 items ...
Benchmarking reduce_with_reverse with input 'list with 10 items' ...
Benchmarking reduce_with_reverse with input 'list with 100_000 items' ...
Benchmarking reduce_with_reverse with input 'list with 1_000 items ...
Benchmarking tail_recursion with input 'list with 10 items' ...
Benchmarking tail_recursion with input 'list with 100_000 items' ...
Benchmarking tail_recursion with input 'list with 1_000 items ...
Benchmarking tail_recursion_with_reverse with input 'list with 10 items' ...
Benchmarking tail_recursion_with_reverse with input 'list with 100_000 items' ...
Benchmarking tail_recursion_with_reverse with input 'list with 1_000 items ...

##### With input 'list with 10 items' #####
Name                                  ips        average  deviation         median         99th %
recursion                          2.75 M      363.22 ns  ±9777.46%         217 ns         557 ns
tail_recursion_with_reverse        2.37 M      422.81 ns  ±9363.73%         268 ns         671 ns
tail_recursion                     1.84 M      543.39 ns  ±5748.26%         416 ns        1048 ns
reduce_with_reverse                1.82 M      550.84 ns  ±7763.41%         323 ns        1006 ns
map_reduce                         1.39 M      720.62 ns  ±5381.42%         479 ns        1616 ns
reduce                             1.32 M      756.62 ns  ±4000.97%         482 ns        1263 ns

Comparison: 
recursion                          2.75 M
tail_recursion_with_reverse        2.37 M - 1.16x slower +59.60 ns
tail_recursion                     1.84 M - 1.50x slower +180.17 ns
reduce_with_reverse                1.82 M - 1.52x slower +187.63 ns
map_reduce                         1.39 M - 1.98x slower +357.41 ns
reduce                             1.32 M - 2.08x slower +393.40 ns

##### With input 'list with 100_000 items' #####
Name                                  ips        average  deviation         median         99th %
recursion                          265.44        3.77 ms    ±14.84%        3.68 ms        6.27 ms
tail_recursion_with_reverse        164.16        6.09 ms    ±32.13%        6.29 ms       10.61 ms
reduce_with_reverse                141.15        7.08 ms    ±34.84%        6.51 ms       16.24 ms
map_reduce                          83.93       11.92 ms    ±31.23%       11.57 ms       26.51 ms
reduce                             0.0386    25909.06 ms     ±0.00%    25909.06 ms    25909.06 ms
tail_recursion                     0.0380    26313.50 ms     ±0.00%    26313.50 ms    26313.50 ms

Comparison: 
recursion                          265.44
tail_recursion_with_reverse        164.16 - 1.62x slower +2.32 ms
reduce_with_reverse                141.15 - 1.88x slower +3.32 ms
map_reduce                          83.93 - 3.16x slower +8.15 ms
reduce                             0.0386 - 6877.38x slower +25905.30 ms
tail_recursion                     0.0380 - 6984.73x slower +26309.73 ms

##### With input 'list with 1_000 items #####
Name                                  ips        average  deviation         median         99th %
tail_recursion_with_reverse       56.63 K       17.66 μs    ±19.90%       16.64 μs       27.73 μs
recursion                         53.00 K       18.87 μs    ±19.75%       17.66 μs       32.72 μs
reduce_with_reverse               45.46 K       22.00 μs    ±17.62%       21.10 μs       37.79 μs
map_reduce                        31.67 K       31.57 μs    ±17.58%       29.60 μs       53.50 μs
tail_recursion                     0.76 K     1316.87 μs    ±17.70%     1272.94 μs     1798.91 μs
reduce                             0.73 K     1378.07 μs    ±23.06%     1318.21 μs     2851.13 μs

Comparison: 
tail_recursion_with_reverse       56.63 K
recursion                         53.00 K - 1.07x slower +1.21 μs
reduce_with_reverse               45.46 K - 1.25x slower +4.34 μs
map_reduce                        31.67 K - 1.79x slower +13.91 μs
tail_recursion                     0.76 K - 74.57x slower +1299.21 μs
reduce                             0.73 K - 78.04x slower +1360.42 μs