Hi, I’m new here. I’m finally trying out Elixir after hearing and reading about it for quite some time.
I’m implementing simple algorithms first, and already at factorial I found something perplexing. I’ve implemented it in several versions, one of them being tail recursive. I expected that one to be the fastest, but to my surprise it wasn’t - body recursion was.
I’ve read Erlang's Tail Recursion is Not a Silver Bullet and http://erlang.org/doc/efficiency_guide/myths.html#myth--tail-recursive-functions-are-much-faster-----than-recursive-functions but these only talk about lists; when calculating simple value, like factorial does, tail recursion should be faster, as far as I understand.
I’m doing the benchmark using Benchee, in a script run with mix run benchmark.exs. Project is clean project created using mix new. Below is the code for the benchmark and the functions themselves.
Am I missing something? Are my implementations wrong? Is the benchmark wrong? Am I running it wrong? Is this “idiomatic code being optimized”?
# benchmark.exs
n = 10000
Benchee.run(%{
"body" => fn -> Factorial.body(n) end,
"tail" => fn -> Factorial.tail(n) end
})
# factorial.ex
defmodule Factorial do
def body(n) do
case n do
0 -> 1
1 -> 1
n -> n * body(n - 1)
end
end
def tail(n) do
tail_internal(1, n)
end
defp tail_internal(acc, 0), do: acc
defp tail_internal(acc, n) do
tail_internal(acc * n, n - 1)
end
end
One output is below, but the situation with tail recursion being 5 - 15% slower repeats consistently and goes down as the input goes up, presumably because there is less and less calls to the function (only 1 when n is 1 000 000).
Operating System: Linux
CPU Information: AMD Ryzen 5 3600 6-Core Processor
Number of Available Cores: 12
Available memory: 12.44 GB
Elixir 1.12.2
Erlang 24.0.5
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 14 s
Benchmarking body...
Benchmarking tail...
Name ips average deviation median 99th %
body 3.20 K 312.96 μs ±7.01% 309.20 μs 383.20 μs
tail 2.79 K 359.05 μs ±6.48% 355 μs 441.43 μs
Comparison:
body 3.20 K
tail 2.79 K - 1.15x slower +46.09 μs
