Can't recursive functions be inlined? [duplicate]

This question already has answers here: Closed 12 years ago.

Possible Duplicate:

Can a recursive function be inline?

What are the trade offs of making recursiv开发者_开发知识库e functions inline.

---

Recursive functions that can be optimised by tail-end recursion can certainly be inlined. If the last thing a function does is call itself, then it can be converted into a plain loop.

---

Arbitrary recursive functions can't be inlined for the same reason a snake can't swallow its own tail.

---

[Edit: just noticed that although your title says "be inlined", your actual question says "making functions inline". The two effectively have nothing to do with one another, they just have confusingly similar names. In modern compilers, the primary effect of inline is the thing that originally in C99 was (I think) just a necessary detail to make inline work at all: to permit multiple definitions of a symbol with external linkage. That's because modern compilers don't pay a whole lot of attention to the programmer's opinion of whether a function should be inlined. They do pay some, though, so the confusion of concepts persists. I've answered the question in the title, which is the decision the compiler makes, not the question in the body, which is the decision the programmer makes.]

Inlining is not necessarily an all-or-nothing deal. One strategy which compilers use to decide whether to inline, is to keep inlining function calls until the resulting code is "too big". "Big" is defined by some hopefully sensible heuristic.

So consider the following recursive function (which deliberately is not simply tail-recursive):

int triangle(int n) {
    if (n == 1) return 1;
    return n + triangle(n-1);
}

If it's called like this:

int t100() {
    return triangle(100);
}

Then there's no particular reason in principle that the usual rules that the compiler uses for inlining shouldn't result in this:

int t100() {
    // inline call to triangle(100)
    int result;
    if (100 == 1) { result = 1; } else {
        // inline call to triangle(99)
        int t99;
        if (100 - 1 == 1) { t99 = 1; } else {
            // inline call to triangle(98)
            int t98;
            if (100 - 1 - 1 == 1) { t98 = 1; } else {
                // oops, "too big", no more inlining
                t98 = triangle(100 - 1 - 1 - 1) + 98;
            }
            t99 = t98 + 99;
        }
        result = t99 + 100;
    }
    return result;
}

Obviously the optimiser will have a field day with that, so it's much "smaller" than it looks:

int t100() {
    return triangle(97) + 297;
}

The code in triangle itself could be "unrolled" a few steps by a few levels of inlining, in exactly the same way, except that it doesn't have the benefits of constants:

int triangle(int n) {
    if (n == 1) return 1;
    if (n == 2) return 3;
    if (n == 3) return 6;
    return triangle(n-3) + 3*n - 3;
}

I doubt whether compilers actually do this, though, I don't think I've ever noticed it [Edit: MSVC does if you tell it to, thanks peterchen].

There's an obvious potential benefit in saving call overhead, but as against that people don't really expect recursive functions to get inlined, and there's no particular guarantee that the usual inlining heuristics will perform well with recursive functions (where there are two different places, the call site and the recursive call, that might be inlined, with different benefits in each case). Furthermore, it's difficult at compile time to estimate how deep the recursion will go, and the inline heuristics might like to take account of the call depth to make decisions. So it may be that the compiler just doesn't bother.

Functional language compilers are typically a lot more aggressive dealing with recursion than C or C++ compilers. The relevant trade-off there is that so many functions written in functional languages are recursive, that performance might be hopeless if the compiler couldn't optimise tail-recursion. So Lisp programmers typically rely on good optimisation of recursive functions, whereas C and C++ programmers typically don't.

---

If your compiler does not support it, you can try manually inlining instead...

int factorial(int n) {
    int result = 1;
    if (n-- == 0) {
        return result;
    } else {
        result *= 1;
        if (n-- == 0) {
            return result;
        } else {
            result *= 2;
            if (n-- == 0) {
                return result;
            } else {
                result *= 3;
                if (n-- == 0) {
                    return result;
                } else {
                    result *= 4;
                    if (n-- == 0) {
                        return result;
                    } else {
                        // ...
                    }
                }
            }
        }
    }
}

See the problem yet?

---

Tail recursion (a special case of recursion) it's possible to be inlined by smart compilers.

---

Now, hold on. A tail-recursive function could be unrolled and inlined pretty easily. Apparently there are compilers that do this, but I am not aware of specifics.

---

Of course. Any function can be inlined if it makes sense to do it:

int f(int i)
{
    if (i <= 0) return 1;
    else return i * f(i - 1);
}
int main()
{
    return f(10);
}

pseudo assembly (f is inlined in main):

main:
    mov r0, #10   ; Pass 10 to f
f:
    cmp r0, #0    ; arg <= 0? ...
    bge 1l
    mov r0, #1    ; ... is so, return 1
    ret

 1:
    mov r0, -(sp) ; if not, save arg.
    dec r0        ; pass arg - 1 to f
    call f        ; just because it's inlined doesn't mean I can't call it.
    mul r0, (sp)+ ; compute the result
    ret           ; done.

;-)

---

When you call an ordinary function when you change command sequential execution order and jump(call or jmp) into some address where the function resides. Inlining mean that you place in all occurences of this function the commands of this function, so you don't have a one place where you could jump, also other types of optimisations can be used, like elemination of pushing/popping function parameters.

---

When you know, that the recursive chain will in normal cases be not so long, you could do inlining upto a predefined level (I don't know, if any existing compiler is intelligent enough for this today).

Inlining a recursive function is much like unrolling a loop. You will end up with much duplicate code -- but in some cases it could be worthwhile:

• The number of recursive calls (the length of the chain) is normally short (in cases it gets longer than predefined, just do normal recursion)
• The overhead for the functions calls is relatively big compared to the logic -- so do some "unrolling" for example five instances and end up doing a recursive call again -- this would lead to saving 80% of the call overhead.
• Off course the tail-recursive special-case -- but this was mentioned by others.

---

Of course can be declared inline. The inline keyword is just a hint to the compiler. In many case the compiler just ignore it and depending on the compiler this could be one of this situatios.

---

Some compilers cna turn tail recursion into plain loops, and thus inline them normally.

Non-tail recursion could be inlined up to a given depth, usually decided by the compiler.

I've never encountered a practical application for that, as the cost of call isn't high enough anymore to offset the increase in code size.

[edit] (to clarify that: even though I like to toy with these things, and often check what code my compiler generates for "funny stuff" just out of curiosity, I haven't encountered a use case where any such unrolling helped significantly. This doesn't mean they don't exist or couldn't be constructed.

The only place where it would help is precalculating low iterations during compile time. However, in my experience this immensely increases compile times for often negligible runtime performance benefits.

Note that Visual Studio 2008 (and earlier) gives you quite some control over this:

#pragma inline_recursion(on)
#pragma inline_depth(N)
__forceinline

Be careful with the latter, it can easily overload the compiler :)

---

Inline means that on each place a call to a function marked as inline gets done, the compiler places a copy of the said function code there. This avoids function calling mechanisms, and it's usual argument stack pushing-poping, saving time in gazillion-calls-per-second situations. You see the consequences to static variables and stuff like that? all gone...

So, if you had an inlined recursive call, either your compiler is super smart and figures whether the number of copies is deterministic, of it will say "Cannot make it inline", because it wouldn't know when to stop.