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.

Return to the comp.compilers page.
Search the comp.compilers archives again.