Performance test of Enumeration, Body-recursive, Tail-recursive in Elixir

recursion.md

inspired by https://blog.appsignal.com/2019/03/19/elixir-alchemy-recursion.html

defmodule Bench do
  import Benchee

  @moduledoc """
  Documentation for `Bench`.
  """

  @doc """
  Hello world.

  ## Examples

      iex> Bench.hello()
      :world

  """
  def sum_numbers1(list) do
    list
    |> Enum.filter(&is_number/1)
    |> Enum.reduce(0, fn n, sum -> n + sum end)
  end

  # 1
  def sum_numbers2([head | tail]) when is_number(head) do
    sum_numbers2(tail) + head
  end

  # 2
  def sum_numbers2([_head | tail]) do
    sum_numbers2(tail)
  end

  # 3
  def sum_numbers2([]) do
    0
  end

  # 1
  def sum_numbers3(list) do
    do_sum_numbers3(list, 0)
  end

  # 2
  defp do_sum_numbers3([head | tail], sum) when is_number(head) do
    do_sum_numbers3(tail, sum + head)
  end

  # 3
  defp do_sum_numbers3([_head | tail], sum) do
    do_sum_numbers3(tail, sum)
  end

  # 4
  defp do_sum_numbers3([], sum) do
    sum
  end

  def hello do
    letters = Enum.map(?a..?z, fn x -> <<x::utf8>> end)
    numbers = Enum.to_list(0..10_000)
    list = Enum.shuffle(letters ++ numbers)

    Benchee.run(
      %{
        "Enum.filter/2 and Enum.reduce/3" => fn -> Bench.sum_numbers1(list) end,
        "Body-recursive" => fn -> Bench.sum_numbers2(list) end,
        "Tail-recursive" => fn -> Bench.sum_numbers3(list) end
      },
      time: 10,
      memory_time: 2
    )
  end
end

Bench.hello()

result:

Operating System: macOS
CPU Information: Apple M2 Pro
Number of Available Cores: 10
Available memory: 16 GB
Elixir 1.16.2
Erlang 26.2.2
JIT enabled: true

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 10 s
memory time: 2 s
reduction time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 42 s

Benchmarking Body-recursive ...
Benchmarking Enum.filter/2 and Enum.reduce/3 ...
Benchmarking Tail-recursive ...
Calculating statistics...
Formatting results...

Name                                      ips        average  deviation         median         99th %
Tail-recursive                        56.11 K       17.82 μs    ±20.50%       18.08 μs       25.46 μs
Body-recursive                        14.52 K       68.86 μs    ±10.96%       68.92 μs       78.92 μs
Enum.filter/2 and Enum.reduce/3        7.09 K      141.06 μs     ±4.17%      139.17 μs      159.58 μs

Comparison:
Tail-recursive                        56.11 K
Body-recursive                        14.52 K - 3.86x slower +51.04 μs
Enum.filter/2 and Enum.reduce/3        7.09 K - 7.91x slower +123.24 μs

Memory usage statistics:

Name                               Memory usage
Tail-recursive                              0 B
Body-recursive                              0 B - 1.00x memory usage +0 B
Enum.filter/2 and Enum.reduce/3        160016 B - ∞ x memory usage +160016 B