11

I'm was messing around with tail-recursive functions in C++, and I've run into a bit of a snag with the g++ compiler.

The following code results in a stack overflow when numbers[] is over a couple hundred integers in size. Examining the assembly code generated by g++ for the following reveals that twoSum_Helper is executing a recursive call instruction to itself.

The question is which of the following is causing this?

  • A mistake in the following that I am overlooking which prevents tail-recursion.
  • A mistake with my usage of g++.
  • A flaw in the detection of tail-recursive functions within the g++ compiler.

I am compiling with g++ -O3 -Wall -fno-stack-protector test.c on Windows Vista x64 via MinGW with g++ 4.5.0. 

struct result
{
    int i;
    int j;
    bool found;
};

struct result gen_Result(int i, int j, bool found)
{
    struct result r;
    r.i = i;
    r.j = j;
    r.found = found;
    return r;
}

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i, int j)
{
    if (numbers[i] + numbers[j] == target)
        return gen_Result(i, j, true);
    if (i >= (size - 1))
        return gen_Result(i, j, false);
    if (j >= size)
        return twoSum_Helper(numbers, size, target, i + 1, i + 2);
    else
        return twoSum_Helper(numbers, size, target, i, j + 1);
}
Swiss
  • 5,556
  • 1
  • 28
  • 42
  • 1
    Did you already try to do the conditional increments separately and do the recursive call only once with the incremented parameters? It is less nice than your example, but it might shed some light on your problem. – stefaanv Dec 21 '10 at 08:37
  • @stefaanv Yes, to no avail. It appears that the call is occuring on the else statement, but no amount of tweaking will cause it to use a jmp instead of a call. – Swiss Dec 21 '10 at 09:31
  • 1
    Does it work if you use a single statement ala `return twoSum_Helper(numbers, size, target, i + j_ge_size, j_ge_size ? i + 2 : j + 1)` where `j_ge_size` is `bool j >= size`? (suit yourself re implicit conversion from bool). – Tony Delroy Dec 21 '10 at 09:43
  • @Tony Assembly still has a call to itself for what equates to the else clause above. – Swiss Dec 21 '10 at 09:52
  • 1
    Tom makes an interesting observation in http://stackoverflow.com/questions/34125 - his tail recursion needed the function to be static...? – Tony Delroy Dec 21 '10 at 10:09
  • @Tony: Tom doesn’t say this, and it’s wrong. Tom said that if you change the function linkage to `extern` TCO will no longer apply – which is completely different. Extern linkage will effectively defer the call resolution to link time and since GCC by default performs only very limited link-time optimization TCO no longer applies. But a function doesn’t need to be `static` for this to apply. – Konrad Rudolph Jan 25 '11 at 20:51

8 Answers8

4

Tail call optimization in C or C++ is extremely limited, and pretty much a lost cause. The reason is that there generally is no safe way to tail-call from a function that passes a pointer or reference to any local variable (as an argument to the call in question, or in fact any other call in the same function) -- which of course is happening all over the place in C/C++ land, and is almost impossible to live without.

The problem you are seeing is probably related: GCC likely compiles returning a struct by actually passing the address of a hidden variable allocated on the caller's stack into which the callee copies it -- which makes it fall into the above scenario.

Andreas Rossberg
  • 34,518
  • 3
  • 61
  • 72
2

Try compilling with -O2 instead of -O3.

How do I check if gcc is performing tail-recursion optimization?

well, it doesn't work with O2 anyway. The only thing that seems to work is returning the result object into a reference that is given as a parameter.

but really, it's much easier to just remove the Tail call and use a loop instead. TCO is here to optimize tail call that are found when inlining or when performing agressive unrolling, but you shouldn't attempt to use recursion when handling large values anyway.

Community
  • 1
  • 1
BatchyX
  • 4,986
  • 2
  • 18
  • 17
  • If you're curious, the flag for optimizing tail recursion is -foptimize-sibling-calls, and is included in -O2, -O3, and -Os. – Swiss Dec 21 '10 at 09:05
  • Well, the answer i'm linking to presents a case where O2 works, but not O3. – BatchyX Dec 21 '10 at 10:22
1

I can't get g++ 4.4.0 (under mingw) to perform tail recursion, even on this simple function:

static void f (int x)
  {
  if (x == 0) return ;
  printf ("%p\n", &x) ; // or cout in C++, if you prefer
  f (x - 1) ;
  }

I've tried -O3, -O2, -fno-stack-protector, C and C++ variants. No tail recursion.

TonyK
  • 16,761
  • 4
  • 37
  • 72
0

Try changing your code to:

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i, int j)
{
    if (numbers[i] + numbers[j] == target)
        return gen_Result(i, j, true);
    if (i >= (size - 1))
        return gen_Result(i, j, false);

    if(j >= size)
        i++; //call by value, changing i here does not matter
    return twoSum_Helper(numbers, size, target, i, i + 1);
}

edit: removed unnecessary parameter as per comment from asker

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i)
{
    if (numbers[i] + numbers[i+1] == target || i >= (size - 1))
        return gen_Result(i, i+1, true);

    if(i+1 >= size)
        i++; //call by value, changing i here does not matter
    return twoSum_Helper(numbers, size, target, i);
}
ted
  • 4,791
  • 5
  • 38
  • 84
  • This will probably work, but unfortunately it defeats the general idea of what I was testing. – Swiss Mar 12 '13 at 01:06
  • Also, j is not necessarily always going to be i+1 on every recursive call. – Swiss Mar 12 '13 at 01:06
  • @Swiss I just rewrote the bottom lines of zour code and kept the function signature, but since zou asked for it I changed the singature and shortened it a bit. – ted Mar 12 '13 at 07:53
  • @Swiss Also what would be the problem if this would work, this would mean that the problem is likely that you have two points from which you recurse. As the example shows this can easily be rewritten (like recursion could also be removed by using loops, I think there is a theorem for that, since I could not google it quick enough there is a [section in wikipedia](http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Expressive_power) wich hints to this) – ted Mar 12 '13 at 08:03
0

Support of Tail Call Optimization (TCO) is limited in C/C++.

So, if the code relies on TCO to avoid stack overflow it may be better to rewrite it with a loop. Otherwise some auto test is needed to be sure that the code is optimized.

Typically TCO may be suppressed by:

  • passing pointers to objects on stack of recursive function to external functions (in case of C++ also passing such object by reference);
  • local object with non-trivial destructor even if the tail recursion is valid (the destructor is called before the tail return statement), for example Why isn't g++ tail call optimizing while gcc is?

Here TCO is confused by returning structure by value. It can be fixed if the result of all recursive calls will be written to the same memory address allocated in other function twoSum (similarly to the answer https://stackoverflow.com/a/30090390/4023446 to Tail-recursion not happening)

struct result
{
    int i;
    int j;
    bool found;
};

struct result gen_Result(int i, int j, bool found)
{
    struct result r;
    r.i = i;
    r.j = j;
    r.found = found;
    return r;
}

struct result* twoSum_Helper(int numbers[], int size, int target,
    int i, int j, struct result* res_)
{
    if (i >= (size - 1)) {
        *res_ = gen_Result(i, j, false);
        return res_;
    }
    if (numbers[i] + numbers[j] == target) {
        *res_ = gen_Result(i, j, true);
        return res_;
    }
    if (j >= size)
        return twoSum_Helper(numbers, size, target, i + 1, i + 2, res_);
    else
        return twoSum_Helper(numbers, size, target, i, j + 1, res_);
}

// Return 2 indexes from numbers that sum up to target.
struct result twoSum(int numbers[], int size, int target)
{
    struct result r;
    return *twoSum_Helper(numbers, size, target, 0, 1, &r);
}

The value of res_ pointer is constant for all recursive calls of twoSum_Helper. It can be seen in the assembly output (the -S flag) that the twoSum_Helper tail recursion is optimized as a loop even with two recursive exit points.

Compile options: g++ -O2 -S (g++ version 4.7.2).

Community
  • 1
  • 1
Orest Hera
  • 6,706
  • 2
  • 21
  • 35
0

I would look at 2 things.

  1. The return call in the if statement is going to have a branch target for the else in the stack frame for the current run of the function that needs to be resolved post call (which would mean any TCO attempt would not be able overwrite the executing stack frame thus negating the TCO)

  2. The numbers[] array argument is a variable length data structure which could also prevent TCO because in TCO the same stack frame is used in one way or another. If the call is self referencing (like yours) then it will overwrite the stack defined variables (or locally defined) with the values/references of the new call. If the tail call is to another function then it will overwrite the entire stack frame with the new function (in a case where TCO can be done in A => B => C, TCO could make this look like A => C in memory during execution). I would try a pointer.

It has been a couple months since I have built anything in C++ so I didn't run any tests, but I think one/both of those are preventing the optimization.

Brandon
  • 2,574
  • 19
  • 17
  • 1
    There is no “numbers[] array argument”, that’s misleading (and it certainly isn’t of variable length). There is only a *pointer* argument, the stack frame is always used identically, and that’s almost certainly not the cause here. And if-else isn’t the cause either. **Every** recursion needs a base case, and hence a conditional statement. – Konrad Rudolph Jan 25 '11 at 20:44
  • Has been a while since C++, I get that it is a pointer, thnx. I do think the conditional is the source though, recursion does need a base case, but Tail Call optimization means that there is no instruction left on the stack except return after the recursive call has been made, in order for the compiler to optimize, the recursive call needs to be the last statement in the frame, the 2nd IF still has a branch target for the ELSE after it in the execution stack. It is the logical last statement but not the physical (when the assembly is in memory). – Brandon Jan 25 '11 at 20:58
  • And I did mean the 3rd IF (the one that decides the next self referencing recursive call) – Brandon Jan 25 '11 at 21:28
-2

I have heard others complain, that tail recursion is only optimized with gcc and not g++. Could you try using gcc.

Lasse Nielsen
  • 1
-3

Since the code of twoSum_Helper is calling itself it shouldn't come as a surprise that the assembly shows exactly that happening. That's the whole point of a recursion :-) So this hasn't got anything to do with g++.

Every recursion creates a new stack frame, and stack space is limited by default. You can increase the stack size (don't know how to do that on Windows, on UNIX the ulimit command is used), but that only defers the crash.

The real solution is to get rid of the recursion. See for example this question and this question.

Community
  • 1
  • 1
DarkDust
  • 90,870
  • 19
  • 190
  • 224
  • 2
    Tail recursive functions are unique because it is theoretically possible to optimize their recursion from a call instruction to a jmp instruction. This changes the stack requirement of the function from O(n) to O(1). In practice it's not so simple, because it relies on the compiler to make the distinction and utilize the optimization. – Swiss Dec 21 '10 at 08:58
  • This doesn't answer the question: tail recursion should elide the call and prevent the stack from overflowing, but the optimisation is not being applied, and the OP wants to know why. – Jon Purdy Dec 21 '10 at 08:58
  • 2
    Sorry, I've missed that there's an optimization which is not applied since this wasn't mentioned in the question. Still, it's a bit dangerous to rely on a specific compiler optimization, no ? – DarkDust Dec 21 '10 at 09:05
  • @DarkDust I'm starting to feel that way about tail-recursion. It's nice in theory, but can go terribly wrong with no real warnings. – Swiss Dec 21 '10 at 09:42
  • 2
    @Swiss: that's a C++ problem (or in general a language-specific problem). There are languages which guarantee that tail recursion is done. For people experimenting with their own compilers, the easiest way to start is by adding an explicit `tailcall %1` instruction. – MSalters Dec 21 '10 at 13:00
  • @Dark: that depends. In principle, tail recursion is very well known, a relatively common case and it’s well established that all modern compilers *do* support it. So many people argue (and I include myself here) that you *should* be able to rely on this optimization. It’s indeed baffling that g++ doesn’t do this here, and arguably an optimization *bug*. – Konrad Rudolph Jan 25 '11 at 20:43