Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why would code actively try to prevent tail-call optimization?

The title of the question might be a bit strange, but the thing is that, as far as I know, there is nothing that speaks against tail call optimization at all. However, while browsing open source projects, I already came across a few functions that actively try to stop the compiler from doing a tail call optimization, for example the implementation of CFRunLoopRef which is full of such hacks. For example:

static void __CFRUNLOOP_IS_CALLING_OUT_TO_AN_OBSERVER_CALLBACK_FUNCTION__() __attribute__((noinline)); static void __CFRUNLOOP_IS_CALLING_OUT_TO_AN_OBSERVER_CALLBACK_FUNCTION__(CFRunLoopObserverCallBack func, CFRunLoopObserverRef observer, CFRunLoopActivity activity, void *info) {     if (func) {         func(observer, activity, info);     }     getpid(); // thwart tail-call optimization } 

I would love to know why this is seemingly so important, and are there any cases were I as a normal developer should keep this is mind too? Eg. are there common pitfalls with tail call optimization?

like image 563
JustSid Avatar asked May 28 '12 21:05

JustSid


People also ask

What is tail-call optimization What is the benefit of using it?

Tail-call optimization is where you are able to avoid allocating a new stack frame for a function because the calling function will simply return the value that it gets from the called function.

Why should we try to eliminate tail recursion?

Tail call elimination reduces the space complexity of recursion from O(N) to O(1). As function call is eliminated, no new stack frames are created and the function is executed in constant memory space.

Should tail recursion be avoided?

No. Go for readability. Many computations are better expressed as recursive (tail or otherwise) functions. The only other reason to avoid them would be if your compiler does not do tail call optimizations and you expect you might blow the call stack.

What languages support tail-call optimization?

This kind of function call is called a tail call, and languages like Haskell, Scala, and Scheme can avoid keeping around unnecessary stack frames in such calls. This is called tail call optimization (TCO) or tail call elimitation.


2 Answers

My guess here is that it's to ensure that __CFRUNLOOP_IS_CALLING_OUT_TO_AN_OBSERVER_CALLBACK_FUNCTION__ is in the stack trace for debugging purposes. It has __attribute__((no inline)) which backs up this idea.

If you notice, that function just goes and bounces to another function anyway, so it's a form of trampoline which I can only think is there with such a verbose name to aid debugging. This would be especially helpful given that the function is calling a function pointer that has been registered from elsewhere and therefore that function may not have debugging symbols accessible.

Notice also the other similarly named functions which do similar things - it really looks like it's there to aid in seeing what has happened from a backtrace. Keep in mind that this is core Mac OS X code and will show up in crash reports and process sample reports too.

like image 97
mattjgalloway Avatar answered Oct 23 '22 09:10

mattjgalloway


This is only a guess, but maybe to avoid an infinite loop vs bombing out with a stack overflow error.

Since the method in question doesn't put anything on the stack it would seem possible for the tail-call recursion optimization to produce code that would enter an infinite loop as opposed to the non-optimized code which would put the return address on the stack which would eventually overflow in the event of misuse.

The only other thought I have is related to preserving the calls on the stack for debugging and stacktrace printing.

like image 21
Andrew White Avatar answered Oct 23 '22 08:10

Andrew White