ayvango ayvango - 2 months ago 23
Scala Question

Make method actually inline

I forge a simple example to check the @inline annotation behavior:

import scala.annotation.tailrec

object InlineTest extends App {
@inline
private def corec(x : Int) : Int = rec(x - 1)

@tailrec
private def rec(x : Int) : Int =
if (x < 3) x else {
if (x % 3 == 0)
corec(x-1)
else
rec(x-4)
}

@tailrec
private def rec1(x : Int) : Int =
if (x < 3) x else {
if (x % 3 == 0) {
val arg = x - 1
rec1(arg - 1)
} else
rec1(x-4)
}

Console.println( rec(args(0).toInt) )
}


This example compiled without warnings, both tailrec annotations were in effect as I thought. But when I actually execute the code, it gives me stackoverflow exception. This means that the tail recursion optimization failed due to inline method being not so inlined.

I have control function
rec1
that differs from the original only with "inline" transformation performed manually. And as this function works well as expected avoiding stackoverflow exception with tail recursion.

What prevents the annotated method from being inlined?

Answer

This won't work, indeed. The treatment of @inline is applied way later than the treatment of tail calls, preventing the optimization you're hoping for.

During the so-called "tailcalls" phase of the compiler, the compiler tries to transform methods so that tail-recursive calls are removed and replaced by loops. Note that only calls within the same function can be eliminated in this way. So, here, the compiler will be able to transform the function rec into something more or less equivalent to the following:

  @tailrec
  private def rec(x0: Int) : Int =
    var x: Int = x0
    while (true) {
      if (x < 3) x else {
        if (x % 3 == 0)
          return corec(x-1)
        else {
          x = x-4
          continue
        }
      }
    }

Note that the call to corec is not eliminated, because you're calling another method. At that time in the compiler, @inline annotations are not even looked at.

But why doesn't the compiler warn you that it cannot eliminate the call, since you've put @tailrec? Because it only checks that it is actually able to replace all calls to the current method. It doesn't care whether another method in the program calls rec (even if that method, in this case corec, is itself called by rec).

So you get no warning, but still the called to corec is not tail-call eliminated.

When you get to the treatment of @inline later in the compiler pipeline, and assuming it does choose to follow your advice to inline corec, it will modify again rec to inline the body of corec, which gives the following:

  @tailrec
  private def rec(x0: Int) : Int =
    var x: Int = x0
    while (true) {
      if (x < 3) x else {
        if (x % 3 == 0)
          return rec((x-1) - 1)
        else {
          x = x-4
          continue
        }
      }
    }

Never mind then that this creates a new tail-recursive call. It's too late. It won't be eliminated anymore. Hence, the stack overflow.

You can use the TailCalls object and its methods to turn mutually tail-recursive methods into loops. See details in the API.