[LLVMdev] Does LLVM optimize recursive call?

[Matthieu Moy]

Preston Briggs <preston.briggs at gmail.com> writes:

> On Wed, Oct 3, 2012 at 10:15 AM, Matthieu Moy
> <Matthieu.Moy at grenoble-inp.fr> wrote:
>> Preston Briggs <preston.briggs at gmail.com> writes:
>>> Think about costs asymptotically; that's what matters. Calls and
>>> returns require constant time, just like addition and multiplication.
>>
>> Constant time, but not necessarily constant memory.
>>
>> Deep recursion will blow up your stack (AKA "segmentation fault" :-( )
>> if the compiler could not optimize it (tail recursion optimization).
>
> Only if the recursion is very deep.

Not so much. Stack size is usually a few megabytes, much smaller than
the heap size.

> In practice, a recursive descent parser isn't going to run out of
> stack space, nor will a quicksort or binary-tree walker,

Yes, because you're taking examples where the recursion depth is log(n)
or close to it. "there are cases where recursion is OK" is true, but it
doesn't imply "you shouldn't worry about your stack size".

> Yes, it's a mistake to have a set of mutually recursive routines that
> chew up all your stack space; but it's a mistake to reply on a
> compiler optimization to avoid such problems.

I agree with this, but this is not what the message I replied to said.
Comparing calls and returns to addition and multiplication in terms of
performance is still wrong.

(BTW, it actually depends if the language enforces this optimization.
IIRC, C doesn't so you can't rely on it, but Caml does, so
tail-recursion is OK even for large datasets in Caml)

-- 
Matthieu Moy
http://www-verimag.imag.fr/~moy/