CODEWITHSUNDEEP
recursionelixir
user10073186
user10073186

Reputation:

elixir: why tail-recursive use more memory than a body-recursive function?

I'm reading Learn Functional Programming with Elixir now, on chapter 4 the author talks about Tail-Call Optimization that a tail-recursive function will use less memory than a body-recursive function. But when I tried the examples in the book, the result is opposite.

# tail-recursive
defmodule TRFactorial do
  def of(n), do: factorial_of(n, 1)
  defp factorial_of(0, acc), do: acc
  defp factorial_of(n, acc) when n > 0, do: factorial_of(n - 1, n * acc)
end

TRFactorial.of(200_000)


# body-recursive 
defmodule Factorial do
  def of(0), do: 1
  def of(n) when n > 0, do: n * of(n - 1)
end

Factorial.of(200_000)

In my computer, the beam.smp of tail-recursive version will use 2.5G ~ 3G memory while the body-recursive only use around 1G. Am I misunderstanding something?

Upvotes: 3

Views: 545

Answers (1)

Aleksei Matiushkin
Aleksei Matiushkin

Reputation: 121000

TL;DR: virtual machine seems to optimize both to be TCO.

Nowadays compilers and virtual machines are too smart to predict their behavior. The advantage of tail recursion is not less memory consumption, but:

This is to ensure that no system resources, for example, call stack, are consumed.

When the call is not tail-recursive, the stack must be preserved across calls. Consider the following example.

▶ defmodule NTC do
    def inf do
      inf()
      IO.puts(".")
      DateTime.utc_now()
    end
  end

Here we need to preserve stack to make it possible to continue execution of the caller when the recursion would return. It won’t because this recursion is infinite. The compiler is unable to optimize it and here is what we get:

▶ NTC.inf                                                                    
[1]    351729 killed     iex

Please note, that no output has happened, which means we were recursively calling itself until the stack blew up. With TCO, infinite recursion is possible (and it is used widely in message handling.)

Turning back to your example. As we saw, TCO was made in both cases (otherwise we’d end up with stack overflow,) and the former keeps an accumulator in the dedicated variable, while the latter uses the return value on stack only. This gain you see: is immutable and the variable content (which is huge for factorial of 200K) gets copied and kept in the memory for each call.

Sidenote:

You might disassembly both modules with :erts_debug.df(Factorial) (which would produce Elixir.Factorial.dis files in the same directory) and see that the calls were implicitly TCO’ed.

Upvotes: 4

Related Questions