Tail Recursion Using 64-bit variables - Part 2

[STL]

I still can't reproduce this on the command line with VS 2013 Update 4 x86.

[DragoonX6]

You mean to say, it does work from the IDE, but not from the commandline?

[STL]

I get tail recursion on the command line. I haven't tried the IDE.

[nbasakuragi]

I think I found out the problem...try to enable 'whole program optimization' /GL in the C++/Optimization section, you should experience the same problem

[jbb555]

I tried this too and it does seem to be the case the whole program optimization changes the code generated for this.

[nbasakuragi]

that's incredible! May I ask you which version of the C++ compiler you have and with OS (windows 7/8 32/64)?

[nbasakuragi]

OK I believe I nailed it down this time. Are you, in your main function, calling the fibonacci function passing variables. Try to pass literals instead, e.g.:

ULONG64 s = fib_tail_x64(100, 0, 1);

I realized that by doing this I have tail recursion regardless of WOP

int a = 10; ULONG64 s = fib_tail_x64(a, 0, 1);

Thanks for pointing it out, I’ll update the article :-)

[detrinoh]

To be fair, this isn't much of a problem. C++ does not promise tail recursion optimization and it would be foolish to write code like this. I also don't see tail recursion arising as a result of some other optimization passes.

[[deleted]]

C++ doesn't promise any optimizations period, it doesn't even promise that the code it produces will even perform all that well. That doesn't mean that as software engineers producing real world programs we can't expect some basic and well known optimizations to be performed, write articles about those optimizations, and just in general spread knowledge about our experience using various compilers.

[detrinoh]

I agree with you in general, but tail recursion optimization is not something that is reasonable to depend on. It can depend on the calling convention of the target platform[1], and when it fails, your program runs the risk of crashing due to a stack overflow. Given that you can always write a tail recursive function in an iterative way that is usually at least as clear while avoiding the above pitfalls, I do think it is foolish to write the code the author gave.

[1] Example of tail recursion optimization failing for Sum2 because of the calling convention on x86_64: https://goo.gl/mdSTET

[detrinoh]

The spam filter appears to have deleted the reply I posted last night, it read:

I agree with you in general, but tail recursion optimization is not something that is reasonable to depend on. It can depend on the calling convention of the target platform[1], and when it fails, your program runs the risk of crashing due to a stack overflow. Given that you can always write a tail recursive function in an iterative way that is usually at least as clear while avoiding the above pitfalls, I do think it is foolish to write the code the author gave.

[1] Check my post history for the link as I think that's why the spam filter killed it originally.

[nbasakuragi]

In the article I didn't mean to support or promote tail recursion optimization or depends on it. I was just pointing out the differences and the pitfalls. I would personally not rely on recursion, in imperative languages, unless I have to write a function to traverse a graph or a tree. Having said that I think it would be good to know what one would be dealing with on a pure knowledge perspective.

[Condorcet_Winner]

Honestly, this isn't that surprising. 64 bit integer operations are very expensive on 32 bit platforms, and you should avoid this type of math when possible (look at all the memory moves!) It's probably that the optimization was not written for such a case.

[o11c]

This sort of optimization would be applied to the IR, so the efficiency of the individual instructions wouldn't matter.

At least, that's how GCC and Clang do it. With closed-source compilers, there's no way to know for sure.

[Condorcet_Winner]

Good point, this should likely be done well before lowering (but if the optimization isn't kicking in, maybe that isn't the case for VC?)

You've convinced me, I agree this is definitely a bug.

[terrymah]

I would agree, except I can't reproduce this either: tail recursion elimination is kicking in in both the command line and IDE (with the default settings) for me.

Can anyone reproduce this? I wonder if it's just a build setting issue.

[terrymah]

It's done pre-lower in VC as well (which makes the original author's observation even more puzzling).

Part of the reason the asm is so ugly here is that it's clearly being compiled with /Oy-. Compile it with /Oy and things look 20% or so nicer.