Re: inling/tail recursion, recursive decent parser


Lefteris Keftedopoulos wrote:
> 1)
> Would inlining / tail recursion have significant effect on the amount
> of call stack space used by a recursive decent parser?
>
> 2)
> would a generated parser (javaCC) compiled by javac, automatically
> be inlined / and tail recursionified by javac, and would it have any
> significant effect.
>

Javac does not perform inlining, even for private methods. Bytecode has
no way to express tail recursive calls, and Java's exception model
(i.e. the availability of a stack trace) makes it basically impossible
to do tail recursion elimination, either by Javac or by the VM. VM's
will do aggressive inlining of calls along hot paths using CHA or
guarded inling strategies; in fact, I think that worrying about what
calls are present in the bytecode of your application isn't much
warranted these days, as VMs are getting more and more aggressive
optimization strategies.

If you're worried about the call stack depth, I'd suggest that you
re-engineer your grammar to be more iterative and less recursive (i.e.
use lists of productions rather than tail-recursive productions). Also,
unless you are worried about running on an embedded device (in which
case, your performance problems are severe due to the slowness of
crappy VMs for phones and such), don't even bother worrying about call
stack depth.

And I would suggest that you get real familiar with the profiling
utilities in the standard VM (e.g. Hotspot) and profile your parser in
detail before you begin optimization. Unless you live and die by a
profiler, you're only kidding yourself that you care about performance.

.

Relevant Pages

  • Re: using MISC (post 1987 Forth hardware) opcodes
    ... bigger is bigger. ... call, return, jump, return ... Ah, tail recursion. ... stack space, and not be quite as clear as it was. ...
    (comp.lang.forth)
  • Re: tail recursion guidelines
    ... To keep from overflowing the stack, ... But don't expect every Common Lisp compiler to ... Tail recursion is not the same thing as tail recursion optimization. ...
    (comp.lang.lisp)
  • Re: Stack usage
    ... and barring library functions that is your stack usage. ... Except that 1) there still isn't any "stack" to be used in Standard ... and 2) there still isn't any way to "measure the deepest leaf" ... rewriting the tail recursion as branching. ...
    (comp.lang.c)
  • Re: How can I make this function simplier?
    ... > If I understand what you are saying, you are turning "on" tail recursion ... With the settings I ... stack overflow because the optimized calls will be turned into jumps. ... Tail recursion isn't a speed optimization, ...
    (comp.lang.lisp)
  • Re: OT: Performance of optimizing compilers.
    ... C code uses the C stack, ... better compiler. ... to implement multiple function tail recursion, ...
    (comp.lang.functional)